题目复习

滑动窗口

  • 模版总结

    • 一定是条件满足时，更新最终结果
    • 首先最外部的循环while (j < len)
    • 接着内部有一个while循环，需要在里面压缩i
      • 条件成立进while：最小窗口；更新值；更新条件；i++
      • 条件不成立进while：最大窗口；更新条件；i++
    • 接着走出while循环
      • j++

  • 破题思路：窗口应该满足什么条件 or 不满足什么条件！！！

  • 904.水果成篮，结合题解，深入理解：

    • 最大滑动窗口 - 模版 
      1
      2
      3
      4
      5
      6
      while j < len(nums):
          // 判断[i, j]是否满足条件
          while 不满足条件：
              i += 1 //（最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）
          // 不断更新结果（注意在while外更新！）
          j += 1
    • 最小滑动窗口 - 模版 
      1
      2
      3
      4
      5
      6
      while j < len(nums):
          // 判断[i, j]是否满足条件
          while 满足条件：
              // 不断更新结果(注意在while内更新！)
              i += 1 //（最大程度的压缩i，使得滑窗尽可能的小）
          j += 1
    • 确实，有了模版后，遇到滑窗问题，思路更加清晰了

  • 1838.最高频元素的频数

    • 需要动脑思考一下，察觉为使用滑动窗口
    • 而且在做减法的时候有一个溢出问题：啊啊啊啊啊！！！

字符串哈希

  • 字符串哈希：使用hash映射，减小索引的存储消耗！！！参考

    1. 选取一个大于字符集大小的质数作为base
    2. 将字符映射为小于base的数：int fx = map(x)
    3. "abccd" = map(a)*base^0 + map(b)*base^1 + map(c)*base^2 + map(c)*base^3 + map(d)*base^4
    4. 参考

  • 3137. K 周期字符串需要的最少操作次数

    • 这个题目比较典型，再复习一下cpp中的数据类型及范围
    • 尝试使用long long但是超出了范围
    • 该用string直接作为哈希key，但是时间性能较差
    • 尝试使用double，因为其采用浮点表示法，范围更大但是精度差点；有些案例过不去
    • 使用unsigned long long，这是能表示的最大整数范围了，通过了
    • 没必要使用map，改为使用unorder_map，时间性能有提升

  • 939. 最小面积矩形

    • 对二维坐标点进行hash
      • 题目规定坐标值的范围在[0, 40000]
      • 因此选取质数40001作为hash的底
      • 直接选pair<int, int>作为key

  • 最大/小子序和

    • 通过取相反数，将最小子序和转化为最大字序和问题
    • 前缀和法
    • 贪心 + dp 法 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      class Solution {
      public:
          int maxScore(vector<int>& cardPoints) {
              auto maxSubArray = [](vector<int>& nums) {
                  //实现1：前缀和
                  // int res = INT_MIN, pre_sum = 0, min_pre_sum = 0;
                  // for (auto& x : nums) {
                  //     pre_sum += x;
                  //     res = max(res, pre_sum - min_pre_sum);
                  //     min_pre_sum = min(min_pre_sum, pre_sum);
                  // }
                  // return res;

                  //实现2：贪心 + dp
                  //s = 0考虑了k = 0时的情况
                  int res = INT_MIN, s = 0;
                  for (auto& x : nums) {
                      if (s <= 0) s = 0;
                      s += x;
                      res = max(res, s);
                  }
                  return res;
              };
              //累加总和为s
              int s = accumulate(cardPoints.begin(), cardPoints.end(), 0);
              //将数组的每个元素乘以-1, 用来求连续子数组的最大和
              transform(cardPoints.begin(), cardPoints.end(), cardPoints.begin(), [](int x) { return -x; });
              //答案 = 总和 - 连续子数组的最小和
              return s - (-maxSubArray(cardPoints));
          }
      };

回文串

  • 最长回文子串
    • 加深理解：如果字串长度为奇数，则只能为aba类型；但是当字串长度为偶数时，可以为aa，也可以为abaaba！！！
    • 自己想到了使用dp数组，记忆化遍历，以减小重复遍历。但是时间表现还是很差❗️❗️
    • 注意到回文串的中间部分一定是由连续且相同的字符串组成，因此可以定位到中间字符，再左右扩展查询，参考❗️
      • 这样中间部分根据奇偶，可以统一处理 
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        class Solution {
            public String longestPalindrome(String s) {
                if (s == null || s.length() == 0) {
                    return "";
                }
        //         保存起始位置，测试了用数组似乎能比全局变量稍快一点
                int[] range = new int[2];
                char[] str = s.toCharArray();
                for (int i = 0; i < s.length(); i++) {
        //             把回文看成中间的部分全是同一字符，左右部分相对称
        //             找到下一个与当前字符不同的字符
                    i = findLongest(str, i, range);
                }
                return s.substring(range[0], range[1] + 1);
            }
            
            public static int findLongest(char[] str, int low, int[] range) {
        //         查找中间部分
                int high = low;
                while (high < str.length - 1 && str[high + 1] == str[low]) {
                    high++;
                }
        //         定位中间部分的最后一个字符
                int ans = high;
        //         从中间向左右扩散
                while (low > 0 && high < str.length - 1 && str[low - 1] == str[high + 1]) {
                    low--;
                    high++;
                }
        //         记录最大长度
                if (high - low > range[1] - range[0]) {
                    range[0] = low;
                    range[1] = high;
                }
                return ans;
            }
        }

记忆化搜索

常用技巧

  • 得先想出递归的完整方案
  • 将递归的参数引入记忆化搜索中
  • 记忆化搜索key压缩技术

经典问题

  • 3154. 到达第 K 级台阶的方案数
    • 想到了递归方案 -> 但是边界条件的处理不适合转化为记忆化
      • 想到的递归没有带返回值
    • 但是没有想出如何进行递归话搜索
    • 边界条件处理的逻辑
    • 还是子问题的逻辑没有想好

动态规划

解题参考

  • 从寻找子问题的思路出发

  • 找到dfs各参数

  • 子序列 DP 的思考套路

    • 子序列 + 不考虑相邻元素：选或不选。代表题目：494. 目标和（0-1 背包）
      • 到达该stage时，该stage对应的结果为下面两种情况的叠加
        • 选择该stage代表的内容
        • 不选择该stage代表的内容
      • 自己想到了全量的递推做法
      • 可以采用数学推导：target确定时，前面为+的和也就确定了，因此题目转化为找物品塞满背包的方法有多少种
    • 子序列 + 考虑相邻元素：枚举选哪个。代表题目：300. 最长递增子序列
      • 到达某个stage时，在前面哪个状态的基础上转移到该状态是最好的？需要枚举选择状态最好的
    • 300. 最长递增子序列
    • 2901. 最长相邻不相等子序列 II
      • 下面这个题目只想到了子序列的回溯做法，但是超时了
      • 这两个题目很像，思路很像。第二个题目只是将条件严格递增简单的替换为一个比较复杂的条件；其余思路都是一样的
      • 记录节点路径的方法值得仔细回味

经典问题

匹配 + 全排列

具有明显的匹配意味，使用next_permutation()对其中一个求取全排列，并与另一个进行组合，记录最值

单调栈

杂项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object): 
	def longestConsecutive(self, nums):
		hash_dict = dict()
		max_length = 0
		for num in nums:
			if num not in hash_dict:
				left = hash_dict.get(num - 1, 0)
				right = hash_dict.get(num + 1, 0)
				cur_length = 1 + left + right
				if cur_length > max_length:
					max_length = cur_length
				hash_dict[num] = cur_length
				hash_dict[num - left] = cur_length
				hash_dict[num + right] = cur_length
		return max_length

对一个数组求子序列的两种回溯方法差异

  • 3098. 求出所有子序列的能量和

  • 不使用for

  • 使用for

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    class Solution {
    public:
        int result = 0;
        void traversal(
    		    vector<int>& nums, int start, int left, int m_min, int last)
        {
            if (left <= 0)
            {
    	        result += m_min;
    	        result %= (1000000000 + 7); 
    	        return;
    	    }

            for (int i = start; i < nums.size(); i++)
            {
                if (i + left > nums.size()) break;
                int n_min = m_min;
                if (last >= 0)
                {
                    n_min = min(m_min, nums[i] - nums[last]);
                }
                // 注意这里每一次递归都表示选当前元素
                traversal(nums, i+1, left-1, n_min, i);
                // 针对每个i，到这里都表示不选当前元素
            }

        }

        int sumOfPowers(vector<int>& nums, int k) {
            int n = nums.size();
            sort(nums.begin(), nums.end());
            traversal(nums, 0, k, INT32_MAX, -1);

            return result;
        }
    };

刷题记录
题目复习
http://example.com/2024/07/04/题目复习/
作者
Cyokeo
发布于
2024年7月4日
许可协议