> For the complete documentation index, see [llms.txt](https://syjohnson11.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://syjohnson11.gitbook.io/leetcode/0.-introduction/0.1_yixiesuanfa.md).

# 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**](https://syjohnson.gitbooks.io/leetcode/content/permutation.html)
* **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;
    }
}
```