ARTS是由左耳朵耗子陈皓在极客时间专栏《左耳听风》中发起的一个每周学习打卡计划。

  1. Algorithm：至少做一个 LeetCode 的算法题。主要为了编程训练和学习。
  3. Review：阅读并点评至少一篇英文技术文章。主要为了学习英文，如果你英文不行，很难成为技术高手。
  5. Tip：学习至少一个技术技巧。主要是为了总结和归纳你日常工作中所遇到的知识点。
  7. Share：分享一篇有观点和思考的技术文章。主要为了输出你的影响力，能够输出你的价值观。

1. Algorithm(算法)

[1,2,3,2,3]找出其中只出现一次的数（让用位操作去实现）
题目来源：字节跳动实习生Java一二面面经

1.1 LeetCode-137

https://leetcode-cn.com/problems/single-number-ii/comments/

方法三：位运算符：NOT，AND 和 XOR

思路

使用位运算符可以实现 O(1) 的空间复杂度。

ARTS-高行行（3-2~3-8） - 图1

XOR

该运算符用于检测出现奇数次的位：1、3、5 等。

0 与任何数 XOR 结果为该数。

  1. 0⊕x=x

两个相同的数 XOR 结果为 0。

  1. x⊕x=0

以此类推，只有某个位置的数字出现奇数次时，该位的掩码才不为 0。

ARTS-高行行（3-2~3-8） - 图2

因此，可以检测出出现一次的位和出现三次的位，但是要注意区分这两种情况。

AND 和 NOT

为了区分出现一次的数字和出现三次的数字，使用两个位掩码：seen_once 和 seen_twice。

思路是：

  • 仅当 seen_twice 未变时，改变 seen_once。
  • 仅当 seen_once 未变时，改变 seen_twice。

ARTS-高行行（3-2~3-8） - 图3

位掩码 seen_once 仅保留出现一次的数字，不保留出现三次的数字。

  1. class Solution {
  2.   public int singleNumber(int[] nums) {
  3.     int seenOnce = 0, seenTwice = 0;
  5.     for (int num : nums) {
  6.       // first appearence: 
  7.       // add num to seen_once 
  8.       // don't add to seen_twice because of presence in seen_once
  10.       // second appearance: 
  11.       // remove num from seen_once 
  12.       // add num to seen_twice
  14.       // third appearance: 
  15.       // don't add to seen_once because of presence in seen_twice
  16.       // remove num from seen_twice
  17.       seenOnce = ~seenTwice & (seenOnce ^ num);
  18.       seenTwice = ~seenOnce & (seenTwice ^ num);
  19.     }
  21.     return seenOnce;
  22.   }
  23. }

复杂度分析
  • 时间复杂度：O(N)，遍历输入数组。
  • 空间复杂度：O(1)，不使用额外空间。

2. Review(点评)

2.1 如何成功

作者：Sam Altman (YC总裁)

原文地址：https://threadreaderapp.com/thread/1214274038933020672.html


3. Tip(技巧)

3.1 使用 String.join() 连接字符串

有时候我们需要将数组或集合以某拼接符拼接到一起形成新的字符串，可以使用 Java8 的 String.join() 方法连接字符串。

  1. String[] strings = {"a", "b", "c", "d", "e"};
  3. // a,b,c,d,e
  4. String join = String.join(",", strings);

4. Share(分享)

写了篇文章，讲了下我为什么选择语雀

为什么我推荐你用语雀记笔记