跳至主要內容

算法三-7月28

hahg大约 30 分钟

算法三-7月28

十八、 最接近的三数之和

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484458&idx=2&sn=60450b940e15b4e20026aa0f496c9cb1&chksm=fd9caf35caeb2623c907517b4d3328c6aba56ed1ed386a996fd174ce00c44ecb446734c95768&cur_album_id=1715134171561410565&scene=189#wechat_redirect

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。

假定每组输入只存在唯一答案。

示例：

  • 输入：nums = [-1,2,1,-4], target = 1
  • 输出：2
  • 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

  • 3 <= nums.length <= 103
  • -103 <= nums[i] <= 103
  • -104 <= target <= 104

（1）略解1

这个和三数之和一样的思路，需要：这里是最接近目标数，所以更新最终结果之前，需要判断是否比现在的结果更接近。

class Solution {
  public int threeSumClosest(int[] nums, int t) {
		// 排序数组
    Arrays.sort(nums);
    // 初始化答案，用于比较是否最接近target
    int ans = nums[0] + nums[1] + nums[2];
    int n = nums.length;
    
    for (int i = 0; i < n-2; i++) {
      // 去除重复数字
      if (i > 0 && nums[i] == nums[i - 1]) continue;
      // 初始化左右两个指针
      int j = i + 1, k = n - 1;
      while (j < k) {
        int sum = nums[i] + nums[j] + nums[k];
        // 判断当前是否最接近目标数
        if (Math.abs(sum - t) < Math.abs(ans - t)) ans = sum;
        
        // 如果相等直接结束函数
        if (ans == t) {
          return t;
        } else if (sum > t) {
          // 大于target则移动k
          k--;
        } else if (sum < t) {
          // 小于target则移动j
          j++;
        }
      }
    }
    return ans;
  }
}

时间复杂度：排序的复杂度为 O ( logn ) ，对于每个 i 而言，最坏的情况 j 和 k 都要扫描一遍数组的剩余部分，复杂度为 O ( n2 )。整体复杂度为 O ( n2 )

空间复杂度：O ( 1 )

十九、托普利茨矩阵

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484556&idx=2&sn=7f2aabbcb2362eb3ccadb401c96c2ea7&chksm=fd9caf93caeb2685ce46cdeed4f4d266b96978f3aec9cf4bd0ba51ce8d12975a44eaf66c4401&cur_album_id=1715134171561410565&scene=189#wechat_redirect

给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。

如果矩阵上 每一条 由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

  • 输入：matrix =
[
	[1, 2, 3, 4],
	[5, 1, 2, 3],
	[9, 5, 1, 2]
]
  • 输出：true
  • 解释：在上述矩阵中, 其对角线为: "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。 各条对角线上的所有元素均相同, 因此答案是 True 。

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 20
  • 0 <= matrix[i][j] <= 99

进阶：

  • 如果矩阵存储在磁盘上，并且内存有限，以至于一次最多只能将矩阵的一行加载到内存中，该怎么办？
  • 如果矩阵太大，以至于一次只能将不完整的一行加载到内存中，该怎么办？

（1）略解1

最直观的方式就是向我们平常那样扫描每一个对角线。

class Solution {
  public boolean isToeplitzMatrix(int[][] matrix) {

    // 在第1行向右扫描数字
    for(int i = 0 ; i < matrix[0].length ; i++) {
      // 记录对角线上的第1个数
      int first = matrix[0][i];
      // 然后向右下角遍历
      for (int j = 0 ; j < matrix.length && j + i < matrix[0].length ; j++) {
        if (first != matrix[j][j + i]) {
          return false;
        }
      }
    }
    
    // 在第1列向下扫描数字
    for(int i = 1 ; i < matrix.length ; i++) {
      // 记录对角线上的第1个数
      int first = matrix[i][0];
      // 然后向右下角遍历 
      for (int j = 0 ; j < matrix[0].length && j + i < matrix.length ; j++) {
        if(first != matrix[j + i][j]) {
          return false;
        }
      }
    }
    return true;
  }
}

（2）略解2

但这样太麻烦，我们需要找到其中的规律，利用好循环这个特点。

做法：每次遍历的时候，判断左上角的数和当前的数是否相等。

原理：只要对角线上有不同的数字，遍历每个数字的时候必然会发现。

class Solution {
  public boolean isToeplitzMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    // 从第2行开始遍历
    for (int i = 1; i < m; i++) {
      // 每行从第2列遍历
      for (int j = 1; j < n; j++) {
        if (matrix[i][j] != matrix[i - 1][j - 1]) return false;
      }
    }
    return true;
  }
}

（3）略解3

第 3 个解法就很妙，但代码不太好实现。

思路：遍历每行，将当前行的倒数第 1 个元素去掉，比较下一行去掉第 1 个元素的数组。其实就是第 1 个解法的集体版，一次性将当前行的所有对角进行比较。

但在 Java 里不太好删除第 1 个元素和倒数第 1 个元素，我们可以使用 Javascript 来解决（最近好久没有写前端，有点生疏了。。。。）

  • 第 3 行和第 6 行：使用了 ES6 的扩展运算符，目的是将数组内容复制出来，不然在删除元素时，会影响到原数组。使用其他方法也可以。
  • 比较数组：因为数组里 都是基本类型，而且顺序都一致，所以可以投机，将数组转成字符串后直接比较。
const isToeplitzMatrix = function(matrix) {
  for (let i = 0; i < matrix.length - 1; i++) {
    let top = [...matrix[i]]
    top.pop()

    let bottom = [...matrix[i + 1]]
    bottom.shift()

    if (top.toString() != bottom.toString()) {
      return false
    }
  }
  return true
};

（4）进阶

  • 如果矩阵存储在磁盘上，并且内存有限，以至于一次最多只能将矩阵的一行加载到内存中，该怎么办？

在覆盖上一行之前进行判断即可。

  • 如果矩阵太大，以至于一次只能将不完整的一行加载到内存中，该怎么办？

存储的时候按照「数组」的形式进行存储（行式存储），然后读取的时候计算偏移量直接读取其「左上角」或者「右下角」的值。

二十、 四数之和

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484556&idx=1&sn=8fd60c49374a3e46115bde19ae385b6e&chksm=fd9caf93caeb268545fbbb031ad7d3230cc85cd64a4875d79dcd7e4749f3cec77e5f6062d08c&cur_album_id=1715134171561410565&scene=189#wechat_redirect

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？

找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例：

  • 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
  • 满足要求的四元组集合为：[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

（1）略解1

四数之和与之前的三数之和的思路一样，不过是多了一层循环。i 和 j 循环每一个字符，然后 k 和 p 作为两个指针进行移动。

class Solution {
  public List<List<Integer>> fourSum(int[] nums, int t) {
    Arrays.sort(nums);
    int n = nums.length;
    List<List<Integer>> ans = new ArrayList<>();
    // 确定第一个数
    for (int i = 0; i < n; i++) { 
      // 对第一个数进行去重（相同的数只取第一个）
      if (i > 0 && nums[i] == nums[i - 1]) continue; 
      // 确定第二个数
      for (int j = i + 1; j < n; j++) { 
        // 对第二个数进行去重（相同的数只取第一个）
        if (j > i + 1 && nums[j] == nums[j - 1]) continue; 
        
        // 确定k和p两个指针，即第三个数和第四个数
        int k = j + 1, p = n - 1;
        while (k < p) {

          // 对第三个数进行去重（相同的数只取第一个）
          while (k > j + 1 && k < n && nums[k] == nums[k - 1]) k++; 
          
          // 如果 k 跳过相同元素之后的位置超过了 p，本次循环结束
          if (k >= p) break;

          // 计算总和
          int sum = nums[i] + nums[j] + nums[k] + nums[p];
          // 如果相等则添加到答案里
          if (sum == t) {
            ans.add(Arrays.asList(nums[i], nums[j], nums[k], nums[p]));
            // 然后移动左指针
            k++;
          } else if (sum > t) {
            // 如果大了移动右指针
            p--;
          } else if (sum < t) {
            // 如果小了移动左指针
            k++;
          }
        }
      }
    }
    return ans;
  }
}
  • 时间复杂度：i 和 j 是直接枚举确定，复杂度为 ，当确定下来 i 和 j 之后，通过双指针确定 k 和 p ，也就是对于每一组 i 和 j 而言复杂度为 O ( n ) 。总的复杂度为 O ( n3 )
  • 空间复杂度：O( n2 )

（2）总结普遍情况

在力扣评论里，有老哥已经总结了 n 数之和问题的通解。

例如：https://leetcode.cn/problems/4sum/solution/2sum-3sum-4sum-nsum-by-23wewerwer/

二十一、猜字谜

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484598&idx=1&sn=36c9bf700771fd84ebf1ad11300260dc&chksm=fd9cafa9caeb26bf620abe89f79f4dd225e0c01dcec59965e1f9f7f75860e84695205b732282&cur_album_id=1715134171561410565&scene=189#wechat_redirect

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

  • 单词 word 中包含谜面 puzzle 的第一个字母。
  • 单词 word 中的每一个字母都可以在谜面 puzzle 中找到。

例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）都不能作为谜底。

返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

示例：

  • 输入：words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
  • 输出：[1,1,3,2,4,0]
  • 解释：
    • 1 个单词可以作为 "aboveyz" 的谜底 : "aaaa"
    • 1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
    • 3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
    • 2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
    • 4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。

提示：

  • 1 <= words.length <= 105
  • 4 <= words[i].length <= 50
  • 1 <= puzzles.length <= 104
  • puzzles[i].length == 7
  • words[i][j], puzzles[i][j] 都是小写英文字母。
  • 每个 puzzles[i] 所包含的字符都不重复。

（1）略解1

这道题是困难题，所以暴力解法一定行不同。那先看下暴力解法。

题目简单来说就是谜面的第 1 个字符要在谜底里，而且谜底的全部字符在谜面里。

所以直接遍历两个数组，数组里再有个循环，来判断谜面的所有字符是否在谜底里。

class Solution {
  public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
    List<Integer> ans = new ArrayList<>();
    // 遍历谜面数组
    for (int i = 0; i < puzzles.length; i++) {
      // 用于存放当前谜面所对应谜底的数量
      int wNum = 0;
      String pTemp = puzzles[i];
      // 取出谜面的第1个字符
      char pFisrtWord = pTemp.charAt(0);
      
      // 遍历谜底数组
      for (int j = 0; j < words.length; j++) {
        String wTemp = words[j];
				// 判断是否符合开头标准
        if (wTemp.contains(pFisrtWord + "" )) {
          StringBuilder sb = new StringBuilder(wTemp);
          boolean flag = true;
          // 遍历谜底的所有字符
          while (sb.length() > 0) {
            // 如果谜底里有1个字符不存在于谜面中，则直接退出循环
            if (!pTemp.contains(sb.substring(0, 1))) {
              flag = false;
              break;
            } else {
              sb.deleteCharAt(0);
            }
          }
          // 如果遍历完成后，每个字符都存在谜面中，则记录当前的谜底
          if (flag) {
            wNum++;
          }
        }
      }
      ans.add(wNum);
    }
    return ans;
  }
}
  • 时间复杂度：O( words.length * puzzles.length * words[i].length )，遍历谜面数组需要 105 ，遍历谜底数组需要 104 ，单单两层遍历就已经 109 ，远大于 107 ，这还没加上遍历字符串的字符，所以必定超时。
  • 空间复杂度：O ( puzzles.length )

（2）状态压缩

这道题需要使用状态压缩。根据题目可知，谜面的长度只有 7，而谜底的长度高达 50。

所以不妨将谜面的所有组合遍历出来，然后再对比谜底，再对比谜底数组，就能知道有多少谜底对应了。

假设 puzzle 是 gabc ，则取重复字符的谜底有可能为几类呢？

  • 排列组合一下： g、ga、gb、gc、gab、gac、gbc、gabc

  • 我们需要状态压缩下，使用 0 和 1 代替，只保留字符是否存在的信息。

    • 例如 g ：1000（对应原字符串）
    • ga ：1100
    • gab ：1110

  • 然后我们将谜面也可以这样表示

谜面可以出现重复字符而且字符顺序可以改变。我们使用位运算来记录所出现的字符。

  • t >> u & 1 ：
    • t >> u ：将 t 向右位移到 u 指向的位置
    • & 1 ：与 1 比较，如果是 0 则返回 0 ；如果是 1 返回 1。用于判断当前位是否等于 1
  • t += 1 << u ：将指定位为 1
  • 最后返回的是记录了当前字符串，26 个字母所出现的情况
// 将 str 所包含的字母用二进制标识
// 如果 str = abz 则对应的二进制为 100...011 (共 26 位，从右往左是 a - z)
int getBin(String str) {
  int t = 0;
  char[] cs = str.toCharArray();
  for (char c : cs) {
    // 每一位字符所对应二进制数字中哪一位
    int u = c - 'a';
    // 如果当前位置为 0，代表还没记录过，则进行记录 (不重复记录)
    if ((t >> u & 1) == 0) t += 1 << u;
  }
  return t;
}

然后将每个这个变量存在 map 里，key 为字母出现情况，value 为出现次数。如果有一样的字母出现情况就加 1 。最后就需要将字母出现情况和谜面比较。

public List<Integer> findNumOfValidWords(String[] ws, String[] ps) {
  // 转用 「哈希表」来统计出所有的 word 所对应的二进制数值
  Map<Integer, Integer> map = new HashMap<>();
  for (String w : ws) {
    int t = getBin(w);
    map.put(t, map.getOrDefault(t, 0) + 1);
  }
  // 判定每个 puzzle 有多少个谜底
  List<Integer> ans = new ArrayList<>();
  for (String p : ps) ans.add(getCnt(map, p));
  return ans;
}

然后我们需要固定谜底的首字符，然后通过循环计算出可能的谜面。

  • 第 10 行 i < (1 << (m - 1) ：1 << (m-1) 相当于 2m-1 ，因为考虑到其他字符的两种状态（取或者不取）。
  • 第 16 行 if (((i >> (j - 1)) & 1) != 0) u += 1 << (cs[j] - 'a'); ：
    • i >> (j - 1) ：我们使用 i 变量的二进制，来表示谜面的字母情况，然后取出变量 i 的指定位置的数字（j-1）
    • (i >> (j - 1)) & 1) != 0 ：判断指定位（j-1）是否等于 1
    • (cs[j] - 'a') ：找到当前字母在 26 个字母的位置
    • u += 1 << (cs[j] - 'a'); ：将指定位置的数字置为 1 ，即更新当前字符串字母出现的情况。
  • 第 19 行 if (map.containsKey(u)) ans += map.get(u);
    • map.containsKey(u) ：变量 u 表示的是谜底 26 个字母出现的情况，然后在 map 查找是否有谜底相同
    • ans += map.get(u) ：如果在 map 查找到则将出现的次数相加，最后得到的是所有谜面所对应的谜底情况。
int getCnt(Map<Integer, Integer> map, String str) {
  int ans = 0;
  int m = str.length();
  char[] cs = str.toCharArray();
  // 当前 puzzle 的首个字符在二进制数值中的位置
  int first = cs[0] - 'a';
  // 我们需要先固定 puzzle 的首位字母，然后枚举剩余的 6 位是否保留
  // 由于是二进制，每一位共有 0 和 1 两种选择，因此共有 2^6 种可能性，也就是 2^6 = 1 << (7 - 1) = 64 种
  // i 代表了所有「保留首个字母」的子集的「后六位」的二进制表示
  for (int i = 0; i < (1 << (m - 1)); i++) {
    // u 代表了当前可能的谜底。先将首字母置为1
    int u = 1 << first;
    // 枚举谜面的「首个字母」之后的位数
    for (int j = 1; j < m; j++) {
      // 如果当前位为 1，代表该位置要保留，将该位置的字母追加到谜底 u 中
      if (((i >> (j - 1)) & 1) != 0) u += 1 << (cs[j] - 'a');
    }
    // 查询这样的字符是否出现在 `words` 中，出现了多少次
    if (map.containsKey(u)) ans += map.get(u);
  }
  return ans;
}
  • 时间复杂度：
    • 首先遍历 words 的数组，然后遍历每一个 word 的全部字符，来计算出字母出现情况。
    • 接着遍历 puzzles 的数组，然后遍历每一个 puzzle，因为 puzzle 最长为 7，所以可以看作常数。
    • 则相加起来为：O( words.length * words[i].length + puzzles.length )
  • 空间复杂度：word 和 puzzle 分别具有最大长度和固定长度，使用空间主要取决于量数组的长度。复杂度：O( words.length + puzzles.length )

二十二、删除链表的倒数第 N 个结点

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484598&idx=2&sn=eba1872ff8297ce0bebe36736b76eb87&chksm=fd9cafa9caeb26bfdcf240996d22e3be915ef666e3c2b543ce5975e39c1307a8fb92d1bc6ecf&cur_album_id=1715134171561410565&scene=189#wechat_redirect

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

  • 输入：head = [1,2,3,4,5], n = 2
  • 输出：[1,2,3,5]

示例 2：

  • 输入：head = [1], n = 1
  • 输出：[]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

（1）快慢指针

这道题难度是中等，其实思路很简单，有点简单题的趋势。使用的是快慢指针。

因为在现实生活中，可能会遇到类似的问题。例如短的尺子量长的东西，尺子不断移动，最后移动到最后就是倒数长度，尺子头尾就类似于快慢指针。

这里设计到指针，在之前有提过，遇到链表问题，建议设置空的头指针，可以简化边界值判断。

  • 如果链表长度为 1 ，则需要判断 if (head.next == null) return null;
  • 如果链表长度为 2，并且 n = 2，即删除的是第 1 个元素，尾指针会指向 null，则不能执行第 10 行 last.next != null ，需要额外判断该种情况。当尾指针指向 null 时，直接返回 first.next
  • 如果加上空的头指针：
    • 长度为 1，头指针指向空头指针，尾指针指向链表元素，然后删除元素—— first.next = first.next.next，这时 first.next.next 是可以取到 null，而不是报错。
    • 长度为 2，并且 n = 2，这时尾指针会指向链表最后一个元素，第 10 行 last.next 不会报错。
class Solution {
  public ListNode removeNthFromEnd(ListNode head, int n) {
    // 新建空的头指针
    ListNode empty = new ListNode();
    // 将空头指针连接上原来链表
    empty.next = head;
    // 将头尾指针指向空头指针
    ListNode first = empty;
    ListNode last = empty;
    
    // 移动尾指针
    for (int i = 0 ; i < n ; i++) {
      last = last.next;
    }
    
    // 同时移动头尾指针
    while (last.next != null) {
      first = first.next;
      last = last.next;
    }

    // 删除元素
    first.next = first.next.next;

    return empty.next;
  }
}
  • 时间复杂度：需要扫描的长度为链表的长度。复杂度为 O ( n )
  • 空间复杂度：O ( 1 )

二十三、 至少有K个重复字符的最长子串

原题链接： https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484728&idx=1&sn=c72b71bc0b6fce4cf29ca756a8a4eb36&chksm=fd9cae27caeb2731b785e76ae1966688f6a6661977916e25926a357117b7932caa3b51815361&cur_album_id=1715134171561410565&scene=189#wechat_redirect

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。

返回这一子串的长度。

示例 1：

  • 输入：s = "aaabb", k = 3
  • 输出：3
  • 解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2：

  • 输入：s = "ababbc", k = 2
  • 输出：5
  • 解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

提示：

  • 1 <= s.length <= 104
  • s 仅由小写英文字母组成
  • 1 <= k <= 105

（1）略解1

这道题用的思路和困难题有的一拼。

难点：无论是加上字符还删除字符，都有可能使子串变得符合要求或者不符合要求，没有普遍情况。

例如：

  • 加上了 额外的 1 种字符，子串为【aabb】，n = 2，加上 1 个 “ c ”，变得【aabbc】这时该子串就不符合要求了。
  • 这时再加上 1 个 “ c ”，变得【aabbcc】，就符合要求了
  • 所以这时不能直接使用滑动窗口

根据上面的例子，知道可以从字符种数入手。从移动指针后判断是否符合要求，到判断是否符合字符种数。

当我们使用双指针的时候：

  1. 右端点往右移动必然会导致字符类型数量增加（或不变）
  2. 左端点往右移动必然会导致字符类型数量减少（或不变）

这样就有了 二段性质 ，同时本题说明，字符串只有 26 种小写字母，所以从字符种数入手是可行的。

具体代码如下：

class Solution {
  public int longestSubstring(String s, int k) {
    int ans = 0;
    int n = s.length();
    char[] cs = s.toCharArray();
    int[] cnt = new int[26];
    
    // 遍历26次，每次加多1种字符
    for (int p = 1; p <= 26; p++) {
      Arrays.fill(cnt, 0);
      // tot 代表 [j, i] 区间所有的字符种类数量；sum 代表满足要求的字符种数
      for (int i = 0, j = 0, tot = 0, sum = 0; i < n; i++) {
        // 计算当前字符在数组中的位置
        int u = cs[i] - 'a';
        cnt[u]++;
        
        // 如果添加到 cnt 之后为 1，说明字符总数 +1
        if (cnt[u] == 1) tot++;
        // 如果添加到 cnt 之后等于 k，说明该字符从不达标变为达标，达标数量 + 1
        if (cnt[u] == k) sum++;
        
        // 当区间所包含的字符种类数量 tot 超过了当前限定的数量 p，那么我们要删除掉一些字母，即「左指针」右移
        while (tot > p) {
          int t = cs[j++] - 'a';
          cnt[t]--;
          // 如果添加到 cnt 之后为 0，说明字符总数-1
          if (cnt[t] == 0) tot--;
          // 如果添加到 cnt 之后等于 k - 1，说明该字符从达标变为不达标，达标数量 - 1
          if (cnt[t] == k - 1) sum--;
        }
        
        // 如果符合要求的字符种数等于当前所限制的字符种数，
        // 则代表当前子串符合标准
        if (tot == sum) ans = Math.max(ans, i - j + 1);
      }
    }
    return ans;
  }
}

（2）总结

题目的要求是每个字符的数量符合目标。当加上字符时，需要同时计算字符种数和该字符的数量。

这时就需要限制字符种数来计算字符数量。即枚举每种字符种数，来不断判断是否符合题目要求。这道题目和猜字谜的思路一样，都是根据枚举少的来去判断多的

二十四、最长有效括号

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484728&idx=2&sn=c1f24a09cf6cfa7d6637ef11c98a8cc8&chksm=fd9cae27caeb2731858e5d1b9b42963a7dace00d7dc9dd8613f7f752e1d446aadaced81bca91&cur_album_id=1715134171561410565&scene=189#wechat_redirect

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

  • 输入：s = "(()"
  • 输出：2
  • 解释：最长有效括号子串是 "()"

示例 2：

  • 输入：s = ")()())"
  • 输出：4
  • 解释：最长有效括号子串是 "()()"

提示：

  • 0 <= s.length <= 3 * 104
  • s[i] 为 '(' 或 ')'

（1）栈解法

这道题主要思路不难，就是使用栈来解决。但里面还需要额外加上指针。

首先考虑栈里面有 “ ( ” 的情况：

  • 遍历完整个字符串后栈里依然有括号
    • 括号不影响与前面子串的联系：“ (() ”
    • 括号影响与前面子串的联系： “ ()(() ” ，遍历完整个字符串后，会发现存在的这个括号（第 3 个字符）会与前面的子串分隔开来，我们需要确定 前面的子串和后面的子串哪个长度大
    • 后面的子串计算长度需要：这个括号的下标和结束当前子串的下标

然后假设栈里面存的是每一个 “ ( ” 在字符串的下标，这个括号的下标就获取得到，使用变量 j 保存，那么如何确定什么情况当前子串结束？

答案是：很难确定，只有后面发现了分隔子串的括号，像上面的 “ ()(() ”，只有遍历全部字符串才能发现，后面 3 个字符 “ (() ” 不能与前面的 “ () ” 合并成一个子串。但有一种情况是必确定当前子串结束，栈空遇到 “ ) ”，这时直接更新变量 j

所以当栈不为空时，计算每一个出栈的子串长度，然后比较答案。

class Solution {
  public int longestValidParentheses(String s) {
    // 新建栈
    Deque<Integer> stack = new ArrayDeque<>();
    int ans = 0;
    
    for (int i = 0, j = -1; i < s.length(); i++) {
      // 如果为 ( 则进行入栈
      if (s.charAt(i) == '(') {
        stack.addLast(i);
      } else {
        // 如果栈不为空，则弹栈，否则更新变量j
        if (!stack.isEmpty()) {
          // 弹栈操作
          stack.pollLast();
          
          // 如果弹栈后栈不为空，则计算当前子串长度
          // 如果为空，就将指向空串
          int top = j;
          if (!stack.isEmpty()) top = stack.peekLast();
          ans = Math.max(ans, i - top);                   
        } else {
          j = i;
        }
      }
    }
    return ans;
  }
}

总结：虽然这道题核心思想不难，但要实现题目要求，要需要注意很多细节，例如上面代码第 19 ~ 23 行，如果不了解这几行代码的思想，就很难完美解出这道题。

  • 时间复杂度：每个字符最多进栈和出栈一次。复杂度为 O ( 1 )
  • 空间复杂度：O ( n )

二十五、有效的括号

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484862&idx=2&sn=191f7a472c03144c38e2d792a53287aa&chksm=fd9caea1caeb27b7115e1927d7130dcbebbf28c8b943420cec315d32f20a75cf42a38cc2cb0b&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「20. 有效的括号」**，难度为 Easy。

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

  • 输入: "()"
  • 输出: true

示例 2:

  • 输入: "()[]{}"
  • 输出: true

示例 3:

  • 输入: "(]"
  • 输出: false

（1）哈希表解法

这道题是当前一面德科时遇到的题目，如果知道 Java 的栈结构对象，就会很简单，否则就需要模拟栈。（当时就是模拟栈，然后模拟了很长时间，最后没完全做出来，真是蛋疼）

题目说明有三种括号的对应关系，对应关系就会想到可以使用哈希表解决。

思路：如果左括号入栈，否则出栈并与当前字符匹配

class Solution {
  public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<Character>();
    char[] charArray = s.toCharArray();
    // 建立哈希表
    Map<Character, Character> map = new HashMap<>(); 
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');
    
    for (int i = 0 ; i < charArray.length ; i++) {
      // 如果在哈希表中对应不上，则该字符是左括号，进行入栈
      if (map.get(charArray[i]) == null) {
        stack.add(charArray[i]);
      } else {
        // 遇到右括号则出栈，然后再判断是否对应
        if (stack.pollLast() != map.get(charArray[i])) { 
          return false;
        }
      }
    }
    
    //  如果循环结束了，栈不为空，则说明是无效括号
    //  这样写也可以 return d.isEmpty();
    if (stack.size() != 0) return false;
    return true;
  }
}
  • 时间复杂度：对字符串 s 扫描一遍。复杂度为 O ( n )
  • 空间复杂度：使用的哈希表空间固定，不随着样本数量变大而变大。复杂度为 O ( 1 )

（2）ASCII 差值解法

我们可以使用三个括号的 ASCII 码的规律来代替哈希表。

  • ( 和 ) 分别对应 -7 和 -8；

  • [ 和 ] 分别对应 43 和 45；

  • { 和 } 分别对应 75 和 77。

  • 规律：不同的括号之间差距很大，但左右括号之间最多差距 2

public static boolean isValid(String s) {
  Deque<Character> stack = new ArrayDeque<Character>();
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (c == '(' || c == '{' || c == '[') {
      stack.add(c);
    } else {
      // 根据差距来判断对应关系
      if (stack.peekLast() == null || Math.abs(stack.pollLast() - c) > 2) {
        return false;
      }
    }
  }
  
  if (stack.size() != 0) return false;
  return true;
}
  • 时间复杂度：对字符串 s 扫描一遍。复杂度为 O ( n )
  • 空间复杂度：O ( n )

二十六、有效的数独

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484943&idx=2&sn=ab31bfb50389d4faffe4eb2be89323c6&chksm=fd9cad10caeb2406316519444c08f1ba8817996e87e18b5c09eaa753be1cca654a911dd25327&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「36. 有效的数独」**，难度为 Medium。

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:[  
["5","3",".",".","7",".",".",".","."],  ["6",".",".","1","9","5",".",".","."],  [".","9","8",".",".",".",".","6","."],  ["8",".",".",".","6",".",".",".","3"],  ["4",".",".","8",".","3",".",".","1"],  ["7",".",".",".","2",".",".",".","6"],  [".","6",".",".",".",".","2","8","."],  [".",".",".","4","1","9",".",".","5"],  [".",".",".",".","8",".",".","7","9"]
]
输出: true

（1）哈希表解法

我们考虑到行下标与行数据的关系，所以使用哈希表。key 放的是 下标，value 放的是集合，list 和 set 都可以

然后在出现数字的位置，判断行、列和 9 * 9 区域是否有相同的数字。

  • 问题：给定一个位置，需要计算出是哪个 9 * 9 的区域

  • 答：行下标 【0-8】，列下标【0-8】。

    • 【0，1，2 列】的区域下标为 0。【3，4，5 列】区域下标为 1。可知区域的列下标确定为 j / 3，因为【0,1,2 / 3 = 0；3,4,5 / 3 = 1】
    • 【0，1，2 行】的区域下标为 0。【3，4，5 行】区域下标为 1。可知区域的列下标确定为 i / 3
    • 当知道了区域的行下标和列下标就知道了是哪个区域的：行下标 * 3 + 列下标，即 i / 3 * 3 + j / 3

详细代码如下：代码实现方面，和人做数独的方式有点不同。

  • 人判断数独是先拿到所有数字，再判断每一个数字是否重复
  • 而下面代码中，最开始是没有任何数字，先判断每一个数字是否重复，再添加到集合里。这种方式可以证明是正确的：
    • 如果有重复的数字，第 1 次出现不会发现，并添加到集合里；但第 2 次出现一定会与第 1 次比较一次，所以一定会发现
class Solution {
  public boolean isValidSudoku(char[][] board) {
    Map<Integer, Set<Integer>> row  = new HashMap<>(), col = new HashMap<>(), area = new HashMap<>();
    // 初始化每个数据
    for (int i = 0; i < 9; i++) {
      row.put(i, new HashSet<>());
      col.put(i, new HashSet<>());
      area.put(i, new HashSet<>());
    }
    
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        // 如果是"." 则不判断
        if (board[i][j] == '.') continue;
        // 取出board里的值
        int c = board[i][j] - '1';
        // 计算区域的下标
        int idx = i / 3 * 3 + j / 3;
        // 使用Set自带方法判断当前数字是否在集合里
        if (!row.get(i).contains(c) && !col.get(j).contains(c) && !area.get(idx).contains(c)) {
          // 如果不在则添加到集合里
          row.get(i).add(c);
          col.get(j).add(c);
          area.get(idx).add(c);
        } else {
          // 在的话就说明不是有效的数独
          return false;
        }
      }
    }
    return true;
  }
}

（2）数组解法

大多数的哈希表计数问题，都能转换为使用数组解决。

使用数组模拟哈希表就能实现题目。因为下标可以代表信息，数组里面的数据就可以 使用布尔值，代表当前格出现过数字。

class Solution {
  public boolean isValidSudoku(char[][] board) {
    // 存储每行、每列和每个区域
    boolean[][] row = new boolean[9][9], col = new boolean[9][9], area = new boolean[9][9];        
    
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        if (board[i][j] == '.') continue;
        int c = board[i][j] - '1';
        int idx = i / 3 * 3 + j / 3;
        if (!row[i][c] && !col[j][c] && !area[idx][c]) {
          // 将指定格设置为true
          row[i][c] = col[j][c] = area[idx][c] = true;
        } else {
          return false;
        }
      }
    }
    return true;
  }
}

  • 时间复杂度：因为数组是 9 * 9 ，不会改变的，所以两个解法的时间复杂度不会改变，都为 O ( 1 )

  • 空间复杂度：O ( 1 )

二十七、解数独

原题链接：https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247484943&idx=1&sn=1ab3463af9251e6be7579e013e8a92b5&chksm=fd9cad10caeb2406173821ba655513e20f86b304b335993f94a440e157ceed324f948c7130ad&cur_album_id=1715134171561410565&scene=189#wechat_redirect

这是 LeetCode 上的**「37. 解数独」**，难度为 Hard。

编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则：

  • 数字 1-9 在每一行只能出现一次。
  • 数字 1-9 在每一列只能出现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。空白格用 '.' 表示。
  • 提示：
    • 给定的数独序列只包含数字 1-9 和字符 '.' 。
    • 你可以假设给定的数独只有唯一解。
    • 给定数独永远是 9x9 形式的。

（1）回溯解法

写过数独的都应该很明白这道题的思路。笔写数独的时候，都会用铅笔，因为便于回溯，擦掉之前写过的数字。

但如果按照填数字、看是否重复、找下一个空位的循环来写代码，会有点麻烦。我在写代码中就遇到一些麻烦：

  • 找下一个空位时，需要两层循环来遍历数组，如果找到了就要退出两层循环，这里就要用到 一个额外的标志位。
  • 结果出来后如何退出所有递归？额外定义一个静态布尔类型变量，一旦找不到下一个空位时，就将变量置为 true，然后在递归和循环前面加上判断。
  • 总的来说，过于冗余，而且不符合之前所说的回溯模板。
void dfs(路径, 选择列表, 结果集):
if (满足结束条件) {
  结果集.add(路径);
  return;
}

for (选择 in 选择列表) {
  做选择，修改路径;
  dfs(路径’, 选择列表, 结果集);
  撤销选择，撤回修改;
}

那么下面开始设计总体代码：

  • 递归函数的 参数：
    • 路径——当前的坐标 int x, int y ；
    • 选择列表——原二维数组 char[][] board ；
    • 结果集——无，直接填写到选择列表里
  • 退出当前递归的条件：
    • 判断当前格不可以填数字
    • 当行下标为 9 时
    • 列下标为 9 时，退出递归并换行操作
  • 传递是否结束：
    • 使用返回布尔值来告诉之前的代码递归的结果。例如下面代码，如果当前不可以填数字，则将下一个空格的返回值作为自己的返回值
// 列下标为 9 时，换行操作
if (y == 9) return dfs(board, x + 1, 0);
// 行下标为 9 时结束
if (x == 9) return true;
// 如果不可以填数字，则判断下一个空格
if (board[x][y] != '.') return dfs(board, x, y + 1);
  • 填数字的规则：
    • 如果当前数字在往后递归的路途中，证明了当前数字不适合，则将需要撤销选择，如第 8 ~ 9 行
    • 如果已经知道结束了，就需要退出循环，迅速退出每一个递归函数。如第 5 ~ 6 行
    • 如果 9 个数字都循环完毕，则说明需要返回到上一层，即返回 false，但这个 false 不能写死，因为填写完全部数字也是要退出循环。 根据第 1 小点，可知如果数字不适合，是要撤销选择，所以在最后可以 判断当前空格是否为数字，如果是数字则代表已经填完全部数字，否则代表 9 个数字不适合这个空格。return board[x][y] != '.';
for (int i = 0; i < 9; i++) {
  if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
    // 将数字填入表格中
    board[x][y] = (char)(i + '1');
    // 更新状态位
    row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
    // 根据之后的结果来执行不同的操作
    if (dfs(board, x, y + 1)) {
      // 如果返回true则代表已经填完整个数独，直接退出循环
      break;
    } else {
      // 否则将清空当前位置，继续填写下一个数字
      board[x][y] = '.';
      row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
    }
  }
}

return board[x][y] != '.';

（2）完整代码

class Solution {
  boolean[][] row = new boolean[9][9];
  boolean[][] col = new boolean[9][9];
  boolean[][][] cell = new boolean[3][3][9];
  public void solveSudoku(char[][] board) {
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        if (board[i][j] != '.') {
          int t = board[i][j] - '1';
          row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
        }
      }
    }
    dfs(board, 0, 0);
  }
  boolean dfs(char[][] board, int x, int y) {
    if (y == 9) return dfs(board, x + 1, 0);
    if (x == 9) return true;
    if (board[x][y] != '.') return dfs(board, x, y + 1);
    for (int i = 0; i < 9; i++) {
      if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
        board[x][y] = (char)(i + '1');
        row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
        if (dfs(board, x, y + 1)) {
          break;
        } else {
          board[x][y] = '.';
          row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
        }
      }
    }
    return board[x][y] != '.';
  }
}
  • 时间复杂度：在固定 9 * 9 的棋盘里，具有一个枚举方案的最大值（极端情况，假设我们的棋盘刚开始是空的，这时候每一个格子都要枚举，每个格子都有可能从 1 枚举到 9，所以枚举次数为 9 * 9 * 9 = 729），即复杂度不随数据变化而变化。复杂度为 O ( 1 )
  • 空间复杂度：在固定 9*9 的棋盘里，复杂度不随数据变化而变化。复杂度为 O ( 1 )
默认页脚
Copyright © 2024 hahg