数据结构Leecode刷题技巧学习总结

跟着labuladong刷leecode，框架来源：拉不拉东的算法笔记

一、数组篇

前缀和差分

1.前缀主要针对一个数组中 频繁查询某个区间的累加和；
构造前缀和数组int []prefix;
Leecode 第303题 区间内的元素和

2.差分主要针对一个数组中某个区间的元素进行递减；
构造差分数组 int [] diff;
Leecode 第1109题 航班预订统计

二分搜索

二分查找分为三种问题
关键是 ：
自变量是谁
单调函数是谁
目标值是谁
之后就是写出单调函数，套框架的问题。
（1） 寻找目标值值，返回角标 左闭右闭，遇到相等，即返回
（2）寻找左侧边间值 即最小值（在f（x）是递增的情况下）左闭右开，遇到相等，即更新mid，返回left
（3）寻找右侧边界值，即最大值（在f(x）是递增的情况下）左开右闭，遇到相等，即更新mid（关键怎么更新），返回right。

int binarySearch(int[] nums, int target){
	int left = 0, right = ...;
	while(...) {
		int mid = left + (right - left) / 2;
		if (nums[mid] == target) {
			...
		} else if (nums[mid] < target) {
			left = ...
		} else if (nums[mid] > target) {
			right = ...
		}
	}
	return ...;
}

二分查找问题是单调函数寻找目标值问题，这时候就是要写出单调函数f(x);
代替上面的数组即可。

// 函数 f 是关于⾃变量 x 的单调递增函数
int f(int x, int[] nums) {
	return nums[x];
}
int left_bound(int[] nums, int target) {
	if (nums.length == 0) return -1;
	int left = 0, right = nums.length;
	while (left < right) {
		int mid = left + (right - left) / 2;
		if (f(mid, nums) == target) {
			// 当找到 target 时，收缩右侧边界
			right = mid;
		} else if (f(mid, nums) < target) {
			left = mid + 1;
		} else if (f(mid, nums) > target) {
			right = mid;
		}
	}
	return left;
}

Leecode 第1011题 在D填内送达的包裹数 关键在于写出f(x)

滑动窗口

Leecode 第567题判断 s2 是否包含 s1 的排列
双指针

/* 滑动窗⼝算法框架 */
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();

        for(int i = 0;i < s1.length();i++){
           char c = s1.charAt(i);
                need.put(c, need.getOrDefault(c, 0)+1);    
        }

        int left = 0;
        int right =0;
        int vaild = 0;
        int len = s1.length();

        while(right < s2.length() ){
            char c = s2.charAt(right);
            right++;

            if(need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0)+1);    
                if(window.get(c).equals(need.get(c))){
                    vaild++;
                }
            }

            while(vaild == need.size()){
                if(right - left  == len){
                    return true;
                }
                char ch = s2.charAt(left);
                left++;

                if(need.containsKey(ch)){
                    if(window.get(ch).equals(need.get(ch))){
                        vaild--;
                    }
                    window.put(ch, window.get(ch)-1);  
                    // 注意get（只是得到而已不能处理，不等同加减在赋值）和 getOrDefault
                }
            }
        }
        return false;
    }

滑动窗⼝算法的思路：
1、我们在字符串 S 中使⽤双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间[left, right) 称为⼀个「窗⼝」。
2、我们先不断地增加 right 指针扩⼤窗⼝ [left, right)，直到窗⼝中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停⽌增加 right，转⽽不断增加 left 指针缩⼩窗⼝ [left, right)，直到窗⼝中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新⼀轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
框架

    public boolean checkInclusion(String s1, String s2) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        for(int i = 0;i < s1.length();i++){
           char c = s1.charAt(i);
           need.put(c, need.getOrDefault(c, 0)+1);    
        }
        
        int left = 0;
        int right =0;

        while(right < s2.length() ){
        	// c 是将移⼊窗⼝的字符
            char c = s2.charAt(right);
			// 右移窗⼝
			right++;
			// 进⾏窗⼝内数据的⼀系列更新
			...
			/*** debug 输出的位置 ***/
			System.out.println("window: [%d, %d)\n", left, right);
			/********************/
			// 判断左侧窗⼝是否要收缩
			while (window needs shrink) {
				// d 是将移出窗⼝的字符
				char d = s2.charAt(left);
				// 左移窗⼝
				left++;
				// 进⾏窗⼝内数据的⼀系列更新
				...
			}
		}
	}