对于比较难的回溯、动态规划等问题也做了集中的归纳总结，一些常见的数据处理类型的题目也需要一些巧思，在这里做一下归纳

1. 位运算

常用位运算：

除以2：>>1; 乘以2：<<1;
List的扩容方式：old+old>>1;
HashMap的扩容方式：old<<1;

灵活运用java中的位运算符，可以更巧妙地解决问题

先复习下正反补的关系：

总结：可以看出负数的补码对应的模是刚好比它绝对值大的二进制数！！符号位保持不变（如下面的-10的补码不考虑符号位就是6）

通过补码进行二进制的加法运算：

可以看到补码运算的最高位即符号位，负数补码高位补1，正数补码高位补0，对运算结果并没有影响！！

1. 二进制中1的个数

n & n-1：将二进制的最后一位1变为0！！

public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while(n != 0){
            n &= n-1;
            ++ans;
        }
        return ans;
    }
}

2.不用加减乘除做加法

所有数都是以补码的形式存储在计算机中
两个数的和可以转换为这两个数的异或（该位值）+这两个数的与（进位值）

实例：

此时就可以通过循环的方式来求解：

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

理解：

（a&b）<<1：表示进位结果

a^b：表示无进位的结果

进位结果与无进位的结果的和又=两者的进位结果+无进位结果！！

由于int类型的值是由符号位填充至32位，超出32位自动舍弃，则直到进位结果中的1全都溢出范围（也就是b==0），此时剩下的无进位结果就表示两数的和

QQ图片20210501093915

2. 链表

1. 反转链表（双指针）

双指针解法：

注意在链接断开时先用一个temp变量存放pre.next

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

3. 数组

3.1 套路

1. 数组中出现次数超过一半的数字

前提：数组非空且多数数一定存在

排序（找规律）

对于排序后的数组，中间的数字必然是超过一半的数字

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

哈希表

public int majorityElement(int[] nums) {
    Map<Integer,Integer> numMap = new HashMap<>();
    for(int i=0; i<nums.length; ++i){
        if(numMap.containsKey(nums[i])){
            int value = numMap.get(nums[i]);
            if(value>nums.length/2) return nums[i];
            else numMap.put(nums[i], numMap.get(nums[i])+1);
		}else{
            numMap.put(nums[i], 1);
        }
	}
    return 0;
}

摩尔投票法

核心原理：

设第一个数为curNum，再指定一个vote变量=1；之后每个与curNum不同的投负票（-1），与curNum相同的投正票（+1）

假如在第a个数（a<nums.length），vote又=0，说明a个数中多的数和非多的数肯定是1：1，将curNum置为a下标对应的值，

数组遍历完时，curNum的值即返回值（因为无论哪个少数数的+1票都会被多数数的-1票给中和为0，所以只可能是多数数撑到左后）

class Solution {
    public int majorityElement(int[] nums) {
		int curNum = nums[0], votes = 1,i=1;
            while(i<nums.length){
                if(votes == 0){
                    curNum = nums[i];
                }
                if(nums[i] != curNum){
                    --votes;
                }else{
                    ++votes;
                }
                ++i;
            }
            return curNum;
        }
}

3.2 二分法

对于有序数组中的查找类问题，首先想到二分法

1. 在排序数组中查找数字 I（二分法）

注意：这题的关键不在于找到目标数，而在于找到目标数的边界

关注的就是用二分法找到边界和找到目标值的区别

二分法的准备工作：(定义二分区域及中点)

1 2	int i = 0; int j = nums.length-1; int m = (i+j)/2;

不断缩小区域逼近目标值，以寻找右边界为例(左边界同理)
1
2
3
4
5
6
7
8
9
while(i<=j){
if(nums[m]<=target){
//右边界在右半区
i = m+1;
}else{
//右边界在左半区
j = m-1;
}
}
此时可以看出i和j一次只能移动1位

如果数组包含target，选择的半区一定是包含target（nums[m]！=target），或者大于target且刚好和target差1位（nums[m]==target），此时的半区可能包含target，也可能不包含！如果不包含，则j会不断朝左移动，直到跑到i的左边，循环结束，此时nums[j]==target。

如果数组不包含target，则最终也是向最接近target的值逼近！！但是最终nums[j]!=target。

循环的终点必然是i>j，如果数组中有目标值，则此时的j必然对应目标值，i必然对应右边界！！！

//如果j<0，则右边界为0，等会求数的时候一定为0
//如果nums[j]！=target，则这个数组中一定不存在target！！
if(j>=0 && nums[j]！=target){
    return 0;
}
//确立右边界
int right = i;

此时的程序就好理解了：右边界-左边界-1

public int search(int[] nums, int target) {
    // 搜索右边界 right
    int i = 0, j = nums.length - 1;
    while(i <= j) {
        int m = (i + j) / 2;
        if(nums[m] <= target) i = m + 1;
        else j = m - 1;
    }
    int right = i;
    // 若数组中无 target ，则提前返回
    if(j >= 0 && nums[j] != target) return 0;
    // 搜索左边界 left
    i = 0;
    while(i <= j) {
        int m = (i + j) / 2;
        if(nums[m] < target) i = m + 1;
        else j = m - 1;
    }
    int left = j;
    return right - left - 1;
}

3.3 双指针

1. 和为s的两个数字（双指针）

首先看到是单调数组且又是求和，可以考虑采用类似滑动窗口的双指针套路解题，先看代码再说问题

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        int i = 0, j = nums.length-1;
		while(i<j){
            if(nums[i]+nums[j]>target){
                ++i;
            }else if(nums[i]+nums[j]<target){
                --j;
            }else{
                ans[0] = nums[i];
                ans[1] = nums[j];
                break;
            }
        }
        return ans;
    }
}

一上来感觉是有问题的，因为少了很多的计算值，但是仔细想想其实那些抛弃的值对结果并没有影响

状态 S(i,j)S(i, j)S(i,j) 切换至 S(i+1,j)S(i + 1, j)S(i+1,j) ，则会消去一行元素，相当于消去了状态集合 {S(i,i+1),S(i,i+2),…,S(i,j−2),S(i,j−1),S(i,j)S(i, i + 1), S(i, i + 2), …, S(i, j - 2), S(i, j - 1), S(i, j)S(i,i+1),S(i,i+2),…,S(i,j−2),S(i,j−1),S(i,j) } 。（由于双指针都是向中间收缩，因此这些状态之后不可能再遇到）。
由于 numsnumsnums 是排序数组，因此这些消去的状态都一定满足 S(i,j)<targetS(i, j) < targetS(i,j)<target ，即这些状态都不是解。
结论：以上分析已证明 “每次指针 iii 的移动操作，都不会导致解的丢失” ，即指针 iii 的移动操作是安全的；同理，对于指针 jjj 可得出同样推论；因此，此双指针法是正确的。

4. 二叉树

4.1 重建二叉树（递归+迭代）

递归解法：

class Slution{
    Map<Integer,Integer> m = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder){
        this.preorder = preorder;
    	for(int i=0; i<inorder.length; ++i){
            m.put(inorder[i], i);
        }
        return BuildTreeByInt(0,0,inorder.length-1);
	}
    //left和right分别是每一级preorder数组的左右边界
    public TreeNode BuildTreeByInt(int root, int left, int right){
		//终止条件
        if(left>right) return null;
        //创建当前等级的根节点
        TreeNode t = new TreeNode(preorder(root));
        //通过中序遍历中root的位置，判断root的左右范围！！
        int i = m.get(preorder(root));
        t.left = BuildTreeByInt(root+1, left, i-1);
        t.right = BuildTreeByInt(i+1, )
    }
}

5. 动态规划

5.1 正则表达式匹配（*）

方法1：dp

空串的情况

A空，B空：true

A空，B不空：算一下（比如：”a*b*c*“的情况）

A不空，B空：false
非空的dp思路

情况1：B的最后一个字符为正常字符，看A[n-1]是否等于B[m-1]，相等则都向前推1位（A[n-2] B[m-2]）

情况2：B的最后一个字符为’.’，直接向前推一位

情况3：B的最后一个字符为’*’
- 不看直接砍（这个不需要条件）：B的最后两位废掉，(A[n-1], B[m-3])
- 看一下（这个需要判断B的前一个字符是否和A的此位字符相同）:（A[n-2], B[m-1]）
转移方程

1和2：f[i][j] = f[i-1][j-1]

3：f[i][j] = f[i][j-2] 或者 f[i][j] = f[i-1][j] (以”abc”和”abc*“为例：A先把c砍了，B再把”c*“砍了)

class Solution {
    public boolean isMatch(String A, String B) {
        int n = A.length();
        int m = B.length();
 		boolean[][] dp = new boolean[n+1][m+1];
       	for(int i=0; i<n; ++i){
            for(int j=0; j<m; ++j){
                if(j==0){
                    dp[i][j] = i==0;
                }else{
                    
                }
            }
        }
    }
}

算法题整理