Leetcode方法总结

数组/字符串⁍

区间问题⁍

• 数组不变，区间查询：前缀和、树状数组、线段树；
• 数组单点修改，区间查询：树状数组、线段树；
• 数组区间修改，单点查询：差分、线段树； ✔
• 数组区间修改，区间查询：线段树。

前缀和⁍

思路⁍

区间和 --》前缀和

• 定义 prefixSum 数组，prefixSum[x]：第 0 项到 第 x 项 的和。
  $$prefixSum[x] = nums[0] + nums[1] +…+nums[x]$$
• nums 的某项 = 两个相邻前缀和的差：
  $nums[x] = prefixSum[x] - prefixSum[x - 1]$
• nums 的 第 i 到 j 项 的和 ，有：
  $$nums[i] +…+nums[j]=prefixSum[j] - prefixSum[i - 1]$$

例题⁍

2055. 蜡烛之间的盘子 (leetcode-cn.com)⁍

class Solution:
    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:
        # count the plates , preSum
        countPlates = [0]*len(s)
        i = 0
        for item in s:
            if i==0:
                countPlates[0] = 0 if item =='|' else 1
            elif item == '*':
                countPlates[i] = countPlates[i-1] + 1
            else:
                countPlates[i] = countPlates[i-1]
            i += 1
        # find the nearest candle from the right
        n = len(s)
        right = [n]*n # right[n-1] = n
        if s[n-1] == '|':
            right[n-1] = n-1
        for j in range(n-2,-1,-1):
            if s[j] == '|':
                right[j] = j
            else:
                right[j] = right[j+1]
                print(j)
        # find the nearest candle from the left
        left = [-1]*n
        if s[0] == '|':
            left[0] = 0
        for j in range(1,n):
            if s[j] == '|':
                left[j] = j
            else:
                left[j] = left[j-1]
        
        # check the query
        res = []
        for query in queries:
            m = right[query[0]]
            n = left[query[1]]
            if n<=m:
                res.append(0)
            else:
                res.append(countPlates[n]-countPlates[m])
        return res

差分数组⁍

「差分」可以看做是求「前缀和」的逆向过程。

对于一个「 将区间$[l,r]$ 整体增加一个值$v$ 」操作，我们可以对差分数组$c$ 的影响看成两部分：

• 对 $c[l]+=v$ ：由于差分是前缀和的逆向过程，这个操作对于将来的查询而言，带来的影响是对于所有的下标 大于等于 $l$ 的位置都增加了值 $v$ ；
• 对 $c[r+1]-=v$ ：由于我们期望只对$[l,r]$产生影响，因此需要对下标大于$r$的位置进行减值操作，从而抵消“影响”。

对于最后的构造答案，可看做是对每个下标做“单点查询”操作，只需要 对差分数组求前缀和 即可。

例题⁍

1109. 航班预订统计 - 力扣（LeetCode） (leetcode-cn.com)

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0]*n
        for booking in bookings:
            i = booking[0] - 1
            j = booking[1] - 1
            diff[i] += booking[2]
            if j+1 < n:
                diff[j+1] -= booking[2]
        
        ans = [0]*n
        ans[0] = diff[0]
        for i in range(1, n):
            ans[i] += ans[i-1]+diff[i]
        return ans

滑动窗口⁍

class Solution:
    def problemName(self, s: str) -> int:
        # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)
        x, y = ..., ...

        # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
        start = 0
        for end in range(len(s)):
            # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
            x = new_x
            if condition:
                y = new_y
			# 举例
            hashmap[s[end]] = hashmap.get(s[end], 0) + 1
            if len(hashmap) == end - start + 1:
                max_len = max(max_len, end - start + 1)

            '''
            ------------- 下面是两种情况，读者请根据题意二选1 -------------
            '''
            # Step 4 - 情况1
            # 如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否达到了限定长度 
            # 如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变, 
            # 左指针移动之前, 先更新Step 1定义的(部分或所有)维护变量 
            if 窗口长度达到了限定长度:
                # 更新 (部分或所有) 维护变量 
                # 窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变

            # Step 4 - 情况2
            # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
            # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
            # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
            while 不合法:
                # 更新 (部分或所有) 维护变量 
                # 不断移动窗口左指针直到窗口再次合法
            # 举例
            while end - start + 1 > len(hashmap):
                head = s[start]
                hashmap[head] -= 1
                if hashmap[head] == 0:
                    del hashmap[head]
                start += 1


        # Step 5: 返回答案
        return ...

作者：eason734
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/yi-ge-mo-ban-miao-sha-10dao-zhong-deng-n-sb0x/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二分查找⁍

十分好用的二分查找法模板（Python 代码、Java 代码） - 简书 (jianshu.com)

找第一个大于target的数⁍

34. 在排序数组中查找元素的第一个和最后一个位置⁍

将问题转化为 找 target-1和target的最右侧值a和b，最后的区间是（a+1,b）。需要思考的是，此处的target-1代表的是仅次于target大小的数（也有可能是target-2之类的），故binarySearch寻找的是第一个大于target的数，接收完返回值只需-1即可

注意细节（转化后的问题可以理解为35. 搜索插入位置）

class Solution {

  public int[] searchRange(int[] nums, int target) {
    int a = -1;
    int b = -1;

    a = binaryFind(nums, target - 1); //target的左界=第一个大于target-1的数
    b = binaryFind(nums, target) - 1; //target的右界=第一个大于target的数-1
    if (a <= b && nums[b] == target) return new int[] { a, b };
    // a<b的情况，low>high（空集）时，res直接返回
    return new int[] { -1, -1 };
  }

  public int binaryFind(int[] nums, int target) {
    //返回第一个大于target的数的下标
    int low = 0;
    int high = nums.length - 1;
    int res = nums.length; //考虑到空集的情况，结果还要-1，故这里取nums.length

    while (low <= high) {
      int mid = (high + low) / 2;
      if (nums[mid] > target) {
        high = mid - 1; //不断向target逼近，若此时刚好跳出，则mid比target坐标刚好大1
        res = mid;
      } else {
        low = mid + 1;
      }
    }
    return res;
  }
}

回溯⁍

回溯法模板⁍

回溯法解决的问题都可以抽象为树形结构，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

分类⁍

• 组合问题：N个数里面按一定规则找出k个数的集合

  •   public void backtracking(int n, int k, int startIndex) {
        if (comb.size() == k) {
          res.add(new ArrayList<>(comb));
          return;
        }
        for (int i = startIndex; i <= n - (k - comb.size()) + 1; i++) {
          comb.add(i);
          backtracking(n, k, i + 1);
          comb.removeLast();
        }
      }
    - [切割问题](#切割问题)：一个字符串按一定规则有几种切割方式
    
      - 从startIndex循环，确定长度
    
        切割条件的判断，不满足条件就continue
    
    - [子集问题](#子集问题)：一个N个数的集合里有多少符合条件的子集
    
      - 组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点
    
    - [排列问题](#排列问题)：N个数按一定规则全排列，有几种排列方式
    
      - 不需要startIndex，但是要去重，记录哪些元素用过了(?)
    
    - [棋盘问题](#棋盘问题)：N皇后，解数独等等
    
    #### 去重
    
    - 对于排序后的数组，有重复的话就去掉与上个一样的数
    
      - ```java
        for (int i = startIndex; i < nums.length; i++) {
          if (i > startIndex && nums[i] == nums[i - 1]) { //去重
            continue;
          }
          path.add(nums[i]);
          backtracking(nums, i + 1);
          path.removeLast();
        }
    
    

• 记录有没有被访问过（注意在哪里更新visited表）

  • 递增子序列

  •     int[] visited = new int[201]; //记录数是否被访问过，访问过的(数+100)对应置1
    
        for (int i = startIndex; i < nums.length; i++) {
          if (
            !path.isEmpty() &&
            nums[i] < path.getLast() ||
            (visited[nums[i] + 100] == 1)
          ) {
            continue;
          }
          visited[nums[i] + 100] = 1;
          path.add(nums[i]);
          backtracking(nums, i + 1);
          path.removeLast();
        }
      }