0.1 一些算法技巧总结

• 处理duplicate的情况

  • InsertPos系列

  • k sum 和remove duplicate from sorted arrays类似

    • 先排序

    • 再找最后一个重复的数

    • ```while(i+1 < n && A[i] == A[i+1]) {

      i++;

      }```

  • Bakctracking(permutation, subset)里遇到重复

    • if(list.contains(A[i]) continue;

    • if(i > 0 && A[i] == A[i-1] && !used[i - 1]) continue;

• Quick Select---- O(N)时间内找到第K大(小)的数,但是没法解决找到前K大的数的问题

  • 215.Kth Largest element in the array

  • 324.Wiggle Sort II

  • 378.Kth smallest element in a sorted matrix

• Next Permutation

• Sliding Window

• Palindrome number(reverse integer)

获得当前digit value的小技巧，24071如何获得"7", factor = 10时

cur = (n % (factor * 10)) / factor

• n & (-n)就是找最右边的1所代表的数，比如n = 6(110), n & (-n) = 2(10)

• n & (n - 1) 效果为减去 n 的二进制表示中最右边为 1 的 bit,等效为n - n & (-n),n =6, n &(n-1) = 4

• n + (n & -n) 就是直接在最低位的 1 上做进位加法

Majority element

• majority vote algorithm 用time O(N) 和space O(1) 得到majority element

• 强记：https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html

class Solution {
    public int majorityElement(int[] nums) {
        //map->numToCount, Time: O(n), Space: O(n)
        //majority vote algorithm, Time: O(N), Space: O(1)
        if (nums == null || nums.length == 0) return -1;
        int candidate = nums[0], cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (cnt == 0) {
                candidate = nums[i];
                cnt++;
            } else {
                if (candidate == nums[i]) {
                    cnt++;
                } else {
                    cnt--;
                }
            }
        }
        return candidate;
    }
}