双指针

344.反转字符串

  1. class Solution {
  2.     public void reverseString(char[] s) {
  3.         int start = 0, end = s.length - 1;
  4.         while(start < end) {
  5.             char temp = s[start];
  6.             s[start] = s[end];
  7.             s[end] = temp;
  8.             start++;
  9.             end--;
  10.         }
  11.     }
  12. }

面试题16.24.数对和（例题1）

  1. class Solution {
  2.     public List<List<Integer>> pairSums(int[] nums, int target) {
  3.         List<List<Integer>> result = new ArrayList<>();
  4.         Arrays.sort(nums);
  5.         int start = 0, end = nums.length - 1;
  6.         while(start < end) {
  7.             int sum = nums[start] + nums[end];
  8.             if(sum == target) {
  9.                 List<Integer> list = new ArrayList<>();
  10.                 list.add(nums[start]);
  11.                 list.add(nums[end]);
  12.                 result.add(list);
  13.                 start++;
  14.                 end--;
  15.             }else if(sum > target) {
  16.                 end--;
  17.             } else {
  18.                 start++;
  19.             }
  20.         }
  21.         return result;
  22.     }
  23. }

1.两数之和

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         int start = 0, end = nums.length - 1;
  4.         int[] temp = Arrays.copyOf(nums, nums.length);
  5.         Arrays.sort(temp);
  6.         int[] result = new int[] {-1, -1};
  7.         while(start < end) {
  8.             int sum = temp[start] + temp[end];
  9.             if(target == sum) {
  10.                 break;
  11.             } else if(target > sum) {
  12.                 start++;
  13.             } else {
  14.                 end--;
  15.             }
  16.         }
  17.         for(int i = 0; i < nums.length; i++) {
  18.             if(temp[start] == nums[i] && result[0] == -1) {
  19.                 result[0] = i;
  20.                 continue;
  21.             }
  22.             if(temp[end] == nums[i] && result[1] == -1) {
  23.                 result[1] = i;
  24.             }
  25.         }   
  26.         return result;
  27.     }
  28. }

15.三数之和

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         List<List<Integer>> reslut = new ArrayList<>();
  4.         int n = nums.length;
  5.         Arrays.sort(nums);
  6.         // 边界条件
  7.         if(n < 3 || nums[0] > 0 || nums[n - 1] < 0) {
  8.             return new ArrayList<>();
  9.         }
  10.         for(int i = 0; i < n; i++) {
  11.             // 过滤重复数据
  12.             if(i != 0 && nums[i] == nums[i - 1]) {
  13.                 continue;
  14.             }
  15.             int target = -nums[i];
  16.             int head = i + 1, tail = n - 1;
  17.             while(head < tail) {
  18.                 int sum = nums[head] + nums[tail];
  19.                 if(sum == target) {
  20.                     List<Integer> list = new ArrayList<>();
  21.                     list.add(nums[i]);
  22.                     list.add(nums[head]);
  23.                     list.add(nums[tail]);
  24.                     reslut.add(list);
  25.                     head++;
  26.                     tail--;
  27.                     // 过滤重复数据
  28.                     while(head < tail && nums[head] == nums[head - 1]) {
  29.                         head++;
  30.                     }
  31.                     // 过滤重复数据
  32.                     while(head < tail && nums[tail] == nums[tail + 1]) {
  33.                         tail--;
  34.                     }
  35.                 } else if (sum < target) {
  36.                     head++;
  37.                 } else {
  38.                     tail--;
  39.                 }
  40.             }
  41.         }
  42.         return reslut;
  43.     }
  44. }

剑指 Offer 21.调整数组顺序使奇数位于偶数前面

首尾指针

  1. class Solution {
  2.     public int[] exchange(int[] nums) {
  3.         // 首尾指针
  4.         int head = 0, tail = nums.length - 1;
  5.         while(head < tail) {
  6.             while(head < tail && (nums[head] & 1) == 1) {
  7.                 head++;
  8.             }
  10.             while(head < tail && (nums[tail] & 1) != 1) {
  11.                 tail--;
  12.             }
  14.             if(head < tail) {
  15.                 int temp = nums[head];
  16.                 nums[head] = nums[tail];
  17.                 nums[tail] = temp;
  18.             }
  19.         }
  20.         return nums;
  21.     }
  22. }

快慢指针

  1. class Solution {
  2.     public int[] exchange(int[] nums) {
  3.         int slow = 0, fast = 0;
  4.         while(fast < nums.length) {
  5.             if((nums[fast] & 1) == 1) {
  6.                 int temp = nums[slow];
  7.                 nums[slow] = nums[fast];
  8.                 nums[fast] = temp;
  9.                 slow++;
  10.             }
  11.             fast++;
  12.         }
  13.         return nums;
  14.     }
  15. }

75.颜色分类

单指针解法

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         // 单指针解法
  4.         int idx = 0;
  5.         // 先把0移至数组前面
  6.         for(int i = 0; i < nums.length; i++) {
  7.             if(nums[i] == 0) {
  8.                 swap(nums, idx, i);
  9.                 idx++;
  10.             }
  11.         }
  13.         // 然后把1移至最后一个0的后面
  14.         for(int i = idx; i < nums.length; i++) {
  15.             if(nums[i] == 1) {
  16.                 swap(nums, idx, i);
  17.                 idx++;
  18.             }
  19.         }
  20.     }
  22.     private void swap(int[] nums, int s, int t) {
  23.         int temp = nums[s];
  24.         nums[s] = nums[t];
  25.         nums[t] = temp;
  26.     }
  27. }

单数组上前后指针（首尾指针）-solution1

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int head = 0, tail = nums.length - 1;
  4.         // 先交换0
  5.         head = sort(nums, head, 0);
  6.         sort(nums, head, 1);
  7.     }
  9.     private int sort(int[] nums, int head, int color) {
  10.         int tail = nums.length - 1;
  11.         while(head <= tail) {
  12.             while(head <= tail && nums[head] == color) {
  13.                 head++;
  14.             }
  15.             while(head <= tail && nums[tail] != color) {
  16.                 tail--;
  17.             }
  18.             if(head < tail) {
  19.                 swap(nums, head, tail);
  20.                 head++;
  21.                 tail--;
  22.             }
  23.         }
  24.         return head;
  25.     }
  27.     private void swap(int[] nums, int s, int t) {
  28.         int temp = nums[s];
  29.         nums[s] = nums[t];
  30.         nums[t] = temp;
  31.     }
  32. }

单数组上前后指针（首尾指针）-solution2

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int head = 0, tail = nums.length - 1, size = nums.length;
  4.         // 双指针解法
  5.         for(int i = 0; i < size; i++) {
  6.             while(i < tail && nums[i] == 2) {
  7.                 swap(nums, i, tail);
  8.                 tail--;
  9.             }
  11.             if(nums[i] == 0) {
  12.                 swap(nums, i, head);
  13.                 head++;
  14.             }
  15.         }
  16.     }
  18.     private void swap(int[] nums, int s, int t) {
  19.         int temp = nums[s];
  20.         nums[s] = nums[t];
  21.         nums[t] = temp;
  22.     }
  23. }

283.移动零已排序未排序指针（例题2）

快慢指针

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         // 快慢指针
  4.         int fast = 0, slow = 0, size = nums.length;
  5.         while(fast < nums.length) {
  6.             while(slow < size && nums[slow] != 0) {
  7.                 slow++;
  8.             }
  9.             fast = slow + 1;
  10.             while(fast < size && nums[fast] == 0) {
  11.                 fast++;
  12.             }
  13.             if(fast < size) {
  14.                 swap(nums, slow, fast);
  15.                 slow++;
  16.                 fast++;
  17.             }
  18.         }
  19.     }
  21.     private void swap(int[] nums, int s, int t) {
  22.         int temp = nums[s];
  23.         nums[s] = nums[t];
  24.         nums[t] = temp;
  25.     }
  26. }

借鉴快排的分区思想-区间指针

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         int size = nums.length, sorted = 0;
  4.         for(int i = 0; i < size; i++) {
  5.             if(nums[i] != 0) {
  6.                 swap(nums, sorted, i);
  7.                 sorted++;
  8.             }
  9.         }
  10.     }
  12.     private void swap(int[] nums, int s, int t) {
  13.         int temp = nums[s];
  14.         nums[s] = nums[t];
  15.         nums[t] = temp;
  16.     }
  17. }

面试题 16.06.最小差 类似合并两个有序数组（例题3）

区间指针

  1. class Solution {
  2.     public int smallestDifference(int[] a, int[] b) {
  3.         // 排序
  4.         Arrays.sort(a);
  5.         Arrays.sort(b);
  6.         long min = Long.MAX_VALUE;
  7.         int s1 = 0, s2 = 0;
  8.         while(s1 < a.length && s2 < b.length) {
  9.             if(a[s1] < b[s2]) {
  10.                 min = Math.min(min, (long) b[s2] - a[s1]);
  11.                 s1++;
  12.             } else {
  13.                 min = Math.min(min, (long) a[s1] - b[s2]);
  14.                 s2++;
  15.             }
  16.         }
  17.         return (int) min;
  18.     }
  19. }

面试题 17.11.单词距离 类似合并两个有序数组

区间指针

  1. class Solution {
  2.     public int findClosest(String[] words, String word1, String word2) {
  3.         int size = words.length;
  4.         int i = 0, j = 0, shortestDist = Integer.MAX_VALUE;
  5.         while(i < size && !words[i].equals(word1)) {
  6.             i++;
  7.         }
  8.         while(j < size && !words[j].equals(word2)) {
  9.             j++;
  10.         }
  11.         while(i < size && j < size) {
  12.             if(i > j) {
  13.                 shortestDist = Math.min(shortestDist, i - j);
  14.                 j++;
  15.                 while(j < size && !words[j].equals(word2)) {
  16.                     j++;
  17.                 }
  18.             } else {
  19.                 shortestDist = Math.min(shortestDist, j - i);
  20.                 i++;
  21.                 while(i < size && !words[i].equals(word1)) {
  22.                     i++;
  23.                 }
  24.             }
  25.         }
  26.         return shortestDist;
  27.     }
  28. }

滑动窗口

剑指Offer 57 - II.和为s的连续正数序列（例题1）

滑动窗口-双指针

  1. class Solution {
  2.     public int[][] findContinuousSequence(int target) {
  3.         int start = 1, end = 2, sum = 3;
  4.         if(target < 2) {
  5.             return new int[0][0];
  6.         }
  7.         List<int[]> list = new ArrayList<>();
  8.         while(end < target) {
  9.             if(sum == target) {
  10.                 int size = end - start + 1;
  11.                 int[] temp = new int[size];
  12.                 int t = start;
  13.                 for(int i = 0; i < size; i++) {
  14.                     temp[i] = t++;
  15.                 }
  16.                 list.add(temp);
  17.                 sum -= start;
  18.                 start++;
  19.                 end++;
  20.                 sum += end;
  21.             } else if(sum < target) {
  22.                 end++;
  23.                 sum += end;
  24.             } else {
  25.                 sum -= start;
  26.                 start++;
  27.             }
  28.         }
  29.         return list.toArray(new int[list.size()][]);
  30.     }
  31. }

滑动窗口-双指针-代码简化

  1. class Solution {
  2.     public int[][] findContinuousSequence(int target) {
  3.         int s = 1, e = 2;
  4.         if(target < 2) {
  5.             return new int[0][0];
  6.         }
  7.         List<int[]> result = new ArrayList<>();
  8.         while(s < e) {
  9.             // 等差数列求和 = （首项 + 末项） * 项数 / 2
  10.             int sum = (s + e) * (e - s + 1) / 2;
  11.             if(sum == target) {
  12.                 int[] res = new int[e - s + 1];
  13.                 for(int i = s; i <= e; i++) {
  14.                     res[i - s] = i;
  15.                 }
  16.                 result.add(res);
  17.                 s++;
  18.                 e++;
  19.             } else if (sum < target) {
  20.                 e++;
  21.             } else {
  22.                 s++;
  23.             }
  24.         }
  25.         return result.toArray(new int[result.size()][]);
  26.     }
  27. }

剑指Offer 48.最长不含重复字符的子字符串（例题2）

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         // 维护一个不重复字符的集合
  4.         Set<Character> set = new HashSet<>();
  5.         int l = 0, r = 0, max = Integer.MIN_VALUE;
  6.         while(r < s.length()) {
  7.             char c = s.charAt(r);
  8.             if(set.contains(c)) {
  9.                 max = Math.max(max, set.size());
  10.                 while(set.contains(c)) {
  11.                     set.remove(s.charAt(l));
  12.                     l++;
  13.                 }
  14.             }
  15.             set.add(c);
  16.             r++;
  17.         }
  18.         return Math.max(max, set.size());
  19.     }
  20. }

438.找到字符串中所有字母异位词

滑动窗口

  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String p) {
  3.         int size = p.length(), l = 0, r = size - 1;
  4.         List<Integer> result = new ArrayList<>();
  5.         int[] map = new int[27];
  6.         // 初始化异位词的map
  7.         for(int i = 0; i < size; i++) {
  8.             map[p.charAt(i) - 'a']++;
  9.         }
  10.         while(r < s.length()) {
  11.             if(compare(l, r, s, map)) {
  12.                 result.add(l);
  13.             } 
  14.             l++;
  15.             r++;
  16.         }
  17.         return result;
  18.     }
  20.     boolean compare(int l, int r, String s, int[] map) {
  21.         int[] temp = new int[27];
  22.         for(int i = l; i <= r; i++) {
  23.             temp[s.charAt(i) - 'a']++; 
  24.         }
  26.         for(int i = 0; i < map.length; i++) {
  27.             if(temp[i] != map[i]) {
  28.                 return false;
  29.             }
  30.         }
  31.         return true;
  32.     }
  33. }

滑动窗口-代码优化

  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String p) {
  3.         if(s.length() < p.length()) {
  4.             return new ArrayList<>();
  5.         }
  6.         int pLen = p.length();
  7.         List<Integer> result = new ArrayList<>();
  8.         int[] map = new int[27];
  9.         int[] temp = new int[27];
  10.         // 初始化异位词的map
  11.         for(int i = 0; i < pLen; i++) {
  12.             map[p.charAt(i) - 'a']++;
  13.             temp[s.charAt(i) - 'a']++;
  14.         }
  15.         if(compare(temp, map)) {
  16.             result.add(0);
  17.         }
  18.         for(int i = pLen; i < s.length(); i++) {
  19.             temp[s.charAt(i - pLen) - 'a']--;
  20.             temp[s.charAt(i) - 'a']++;
  21.             if(compare(temp, map)) {
  22.                 result.add(i - pLen + 1);
  23.             } 
  24.         }
  25.         return result;
  26.     }
  28.     boolean compare(int[] temp, int[] map) {
  29.         for(int i = 0; i < map.length; i++) {
  30.             if(temp[i] != map[i]) {
  31.                 return false;
  32.             }
  33.         }
  34.         return true;
  35.     }
  36. }

76.最小覆盖子串


前缀后缀统计

121.买卖股票的最佳时机（例题1）

后缀和

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int n = prices.length;
  4.         // 定义后缀和数组，max[i] 表示第 i+1 ~ n 天之间的最大值
  5.         int[] max = new int[n];
  6.         int curMaX = 0;
  7.         // 计算后缀和
  8.         for(int i = n - 1; i >= 0; i--) {
  9.             max[i] = curMaX;
  10.             curMaX = Math.max(prices[i], curMaX);
  11.         }
  12.         int result = 0;
  13.         for(int i = 0; i < n - 1; i++) {
  14.             result = Math.max(result, max[i] - prices[i]);
  15.         }
  16.         return result;
  17.     }
  18. }

单次遍历

解题思路：
遍历数组，记录历史最低点，然后考虑如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         int minPrices = Integer.MAX_VALUE, maxProfit = Integer.MIN_VALUE;
  4.         for(int i = 0; i < prices.length; i++) {
  5.             minPrices = Math.min(minPrices, prices[i]);
  6.             maxProfit = Math.max(maxProfit, prices[i] - minPrices);
  7.         }
  8.         return maxProfit;
  9.     }
  10. }

238.除自身以外数组的乘积（例题2）

前缀积和后缀积

解题思路：
假设 leftProduct[i] 表示 nums[0 ~ i-1] 的元素乘积，rightProduct[i] 表示 nums[i+1 ~ n] 的元素乘积，那么 leftProduct[i] * rightProduct[i] 则表示除 nums[i] 之外其余各元素的乘积。
由于题目限制，空间复杂度要在 O(n)，那么可以重用结果集来做。

  1. class Solution {
  2.     public int[] productExceptSelf(int[] nums) {
  3.         int n = nums.length;
  4.         int[] result = new int[n];
  5.         int leftProduct = 1;
  6.         for(int i = 0; i < n; i++) {
  7.             result[i] = leftProduct;
  8.             leftProduct *= nums[i];
  9.         }
  10.         int rightProduct = 1;
  11.         for(int i = n - 1; i >= 0; i--) {
  12.             result[i] = rightProduct * result[i];
  13.             rightProduct *= nums[i];
  14.         }
  15.         return result;
  16.     }
  17. }

面试题05.03.翻转数位

位运算

  1. class Solution {
  2.     public int reverseBits(int num) {
  3.         int cur = 0, res = 1, insert = 0;
  4.         for(int i = 0; i < 32; i++) {
  5.             if((num & 1) == 1) {
  6.                 cur++;
  7.                 insert++;
  8.             } else {
  9.                 insert = cur + 1;
  10.                 cur = 0;
  11.             }
  12.             res = Math.max(res, insert);
  13.             num = num >> 1;
  14.         } 
  15.         return res;
  16.     }
  17. }

42. 接雨水

暴力破解

  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int ans = 0, size = height.length;
  4.         for(int i = 0; i < size; i++) {
  5.             int maxLeft = 0, maxRigth = 0;
  6.             for(int j = i; j >= 0; j--) {
  7.                 maxLeft = Math.max(maxLeft, height[j]);    
  8.             }
  10.             for(int j = i; j < size; j++) {
  11.                 maxRigth = Math.max(maxRigth, height[j]);
  12.             }
  13.             ans += Math.min(maxLeft, maxRigth) - height[i];
  14.         }
  15.         return ans;
  16.     }
  17. }

双指针

  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int left = 0, right = height.length - 1;
  4.         int leftMax = 0, rightMax = 0, ans = 0;
  5.         while(left < right) {
  6.             leftMax = Math.max(leftMax, height[left]);
  7.             rightMax = Math.max(rightMax, height[right]);
  8.             if(height[left] < height[right]) {
  9.                 ans += leftMax - height[left];
  10.                 left++;
  11.             } else {
  12.                 ans += rightMax - height[right];
  13.                 right--;
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. }

53.最大子序和

前缀和

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int n = nums.length;
  4.         // 前缀和
  5.         int[] prefixSum = new int[n];
  6.         int sum = 0;
  7.         for(int i = 0; i < n; i++) {
  8.             prefixSum[i] = sum + nums[i];
  9.             sum = prefixSum[i];
  10.         } 
  11.         int maxSum = Integer.MIN_VALUE;
  12.         for(int i = 0; i < n; i++) {
  13.             for(int j = 0; j <= i; j++) {
  14.                 maxSum = Math.max(maxSum, prefixSum[i] - prefixSum[j] + nums[j]);
  15.             }
  16.         }
  17.         return maxSum;
  18.     }
  19. }

动态规划

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         // 定义 dp[i] 为 第i个数结尾的连续子数组的最大和，那么dp[i] 的状态只能由 dp[i - 1] 或者 第 i 个数自身（nums[i]）转移而来
  4.         // 状态转移方程： dp[i] = max(dp[i - 1] + nums[i], nums[i]);
  5.         int n = nums.length;
  6.         int[] dp = new int[n];
  7.         dp[0] = nums[0];
  8.         int max = Integer.MIN_VALUE;
  9.         for(int i = 1; i < n; i++) {
  10.             dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
  11.             max = Math.max(max, dp[i]);
  12.         }
  13.         return Math.max(dp[0], max);
  14.     }
  15. }

位运算

191.位1的个数（例题1）

  1. public class Solution {
  2.     // you need to treat n as an unsigned value
  3.     public int hammingWeight(int n) {
  4.         int count = 0, mark = 1;
  5.         for(int i = 0; i < 32; i++) {
  6.             if((n & mark) != 0) {
  7.                 count++;
  8.             }
  9.             mark <<= 1;
  10.         }
  11.         return count;
  12.     }
  13. }

461.汉明距离（例题2）

  1. class Solution {
  2.     public int hammingDistance(int x, int y) {
  3.         // 先异或，求出来的二进制中 1 的个数代表汉明距离
  4.         int p = x ^ y;
  5.         int dist = 0, mask = 1;
  6.         for(int i = 0; i < 32; i++) {
  7.             if((p & mask) != 0) {
  8.                 dist++;
  9.             }
  10.             mask <<= 1;
  11.         }
  12.         return dist;
  13.     }
  14. }

面试题05.06.整数转换

  1. class Solution {
  2.     public int convertInteger(int A, int B) {
  3.         int count = 0, p = A ^ B, mark = 1;
  4.         for(int i = 0; i < 32; i++) {
  5.             if((p & mark) != 0) {
  6.                 count++;
  7.             }
  8.             mark <<= 1;
  9.         }
  10.         return count;
  11.     }
  12. }

面试题05.07.配对交换

  1. class Solution {
  2.     public int exchangeBits(int num) {
  3.         int ret = 0;
  4.         for(int i = 0; i <= 30; i+=2) {
  5.             int a = num & (1 << i);
  6.             int b = num & (1 << (i+1));
  7.             if(a != 0) {
  8.                 ret += (1 << (i + 1));
  9.             }
  10.             if(b != 0) {
  11.                 ret += 1 << i;
  12.             }
  13.         }
  14.         return ret;
  15.     }
  16. }

面试题05.01.插入

  1. class Solution {
  2.     public int insertBits(int N, int M, int i, int j) {
  3.         // 将i ~ j 范围的数取0
  4.         for(int k = i; k <= j; k++) {
  5.             N ^= (N & (1 << k));
  6.         }
  7.         // M 左移 i 位
  8.         M <<= i;
  9.         // 进行或运算
  10.         return N | M;
  11.     }
  12. }

面试题17.04.消失的数字

  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         int n = nums.length;
  4.         int ret = 0, i = 0;
  5.         while(i < n) {
  6.             ret ^= i ^ nums[i];
  7.             i++;
  8.         }
  9.         return ret ^ n;
  10.     }
  11. }

剑指Offer 56 - I.数组中数字出现的次数

题解思路：

已知：两数相等异或结果为0，一个数与0异或结果就等于其本身。 所以如果数组中只有一个出现一次的数，那么就只需要对所有的数进行异或就可以得到这个只出现一次的数，而本题中出现一次的数有两个。 所以所有数异或的结果就是那两个只出现一次的数异或的结果。 所以根据这个特性，我们就可以采用分组的方法解决此问题。且分组要满足两个条件： 1、两个相同的数必须出现在同一组。

2、那两个只出现一次的数必须分配在不同的组。

这样我们分别对这两组数进行异或，就可以得到两个出现一次的数。

那么，究竟应该怎么分组呢？

例如【4,1,4,6】:全部异或的结果就是1和6异或的结果。就是0001和0110异或的结果0111。其实我们不难发现。将该两个相同的数分配在一组是很容易实现的。我们只需要固定一个二进制位，若这两个数在这个二进制位上的数是相同的。我们就把他分在同一组。但是难点还是在如何实现将两个子出现一次的数分配在不同的组里面。

继续往下分析，1和6异或结果就是0111，0111这个二进制数中是1的二进制位暗含了什么个意思呢？

分析不难知道，二进制位是1，就表示1和6在这个二进制位上的数是不同的。所以，这就是我们划分两个数到不同组的依据。

因为0111有三个二进制位都是1，分别是第一位、第二位、第三位。这就表示了1和6的二进制数在第一、二、三位上的数是不同的。我们假设就以第一个二进制位为划分标准。当数组中的数的第一个二进制位是1的就分为第一组。数组中的数第一个二进制位是0的就划分为第二组。这样就成功的将1和6分到了不同的组别中，而相同的数例如4，因为4和4的第一个二进制位是必然相等的，这样也就实现了将两个相同的数划分到同一组。最后只需要分别将这两个组进行异或，就可以得到我们要求的答案。

摘自：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-by-leetcode/ 三生烟火 网友的回答

  1. class Solution {
  2.     public int[] singleNumbers(int[] nums) {
  3.         int xOrResult = 0;
  4.         int n = nums.length;
  5.         for(int i = 0; i < n; i++) {
  6.             xOrResult ^= nums[i];
  7.         }
  8.         int tag = 1;
  9.         // 找出第一位为1的位数，作为分隔符
  10.         while((xOrResult & tag) == 0) {
  11.             tag <<= 1;
  12.         }
  13.         int a = 0, b = 0;
  14.         for(int i = 0; i < n; i++) {
  15.             if((tag & nums[i]) == 0) {
  16.                 a ^= nums[i];
  17.             } else {
  18.                 b ^= nums[i];
  19.             }
  20.         }
  21.         return new int[]{a, b};
  22.     }
  23. }

剑指Offer 56 - II.数组中数字出现的次数II

  1. class Solution {
  2.     public int singleNumber(int[] nums) {
  3.         int[] bits = new int[32];
  4.         for(int i = 0; i < bits.length; i++) {
  5.             int tag = 1 << i;
  6.             for(int num : nums) {
  7.                 if((num & tag) != 0) {
  8.                     bits[i] = (bits[i] + 1) % 3;
  9.                 }
  10.             }
  11.         }
  12.         int result = 0;
  13.         int mark = 1;
  14.         for(int i = 0; i < bits.length; i++) {
  15.             result += bits[i] * mark;
  16.             mark <<= 1;
  17.         }
  18.         return result;
  19.     }
  20. }

面试题16.01.交换数字

解题思路：有两个数，分别为 a、b，经过 a = a^b ， b = a^b , a = a^b 后，a 与 b 的值互换。

  1. class Solution {
  2.     public int[] swapNumbers(int[] numbers) {
  3.         if(numbers[0] == numbers[1]) {
  4.             return numbers;
  5.         }
  6.         numbers[0] ^= numbers[1];
  7.         numbers[1] ^= numbers[0];
  8.         numbers[0] ^= numbers[1];
  9.         return numbers;
  10.     }
  11. }

231. 2的幂

  1. class Solution {
  2.     public boolean isPowerOfTwo(int n) {
  3.         return n > 0 && (n & (n - 1)) == 0;
  4.     }
  5. }