每日一题：LeetCode：1332.删除回文子序列 & 1246.删除回文子数组

---

• 每日一题：LeetCode：1332.删除回文子序列

  • 时间：2022-01-22
  • 力扣难度：Easy
  • 个人难度：Easy
  • 数据结构：字符串、回文子序列

• 每日一题：LeetCode：1246.删除回文子数组

  • 时间：2022-01-22
  • 力扣难度：Hard
  • 个人难度：Hard
  • 数据结构：回文子数组、子序列
  • 算法：记忆化搜索、DFS、动态规划(区间DP)

---

2022-01-22：LeetCode：1332.删除回文子序列

1. 题目描述

• 题目：原题链接

  • 给你一个字符串 s，它仅由字母 ‘a’ 和 ‘b’ 组成。
  • 每一次删除操作都可以从 s 中删除一个回文子序列
  • 返回删除给定字符串中所有字符（字符串为空）的最小删除次数。
  • 「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。
  • 「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。
  • 1 <= s.length <= 1000
  • s 仅包含字母 'a' 和 'b'

• 输入输出规范

  • 输入：字符串

  • 输出：整型，表示删除所需的次数

• 输入输出示例

  • 输入：s = “baabb”
  • 输出：2

---

2. 方法：仔细审题：脑筋急转弯

• 思路

  • 本题最重要的就是仔细审题
    • 字符串只有两种字符
    • 每次操作可以删除一个回文子序列
  • 注意：回文子序列是可以不连续的，与必须连续的回文子串不同，即本题可以删除同一种字符，一定是回文子序列
  • 因此，本题只需要判断字符串是否回文，回文就一次删完，返回1，不回文就一次删a，一次删b，两次删完，返回2

• 题解

  public int removePalindromeSub(String s) {
  
      if(s == null || s.length() == 0) return 0;
      int n = s.length();
      for(int i = 0; i < n/2; i++) {
          if(s.charAt(i) != s.charAt(n - i - 1)) return 2;
      }
      return 1;
  }

• 复杂度分析：n 是字符串的大小

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

• 扩展：删除回文子串、子数组

  • 如果题目没有限制只有两种字符，而是小写字母甚至更多字符组成的字符串
  • 每次删除一个回文子串，而不是子序列，最终需要几次

---

3. 扩展：LC1246：删除回文子数组

3.1 题目描述

• 题目：原题链接：LeetCode1246.删除回文子数组

  • 给你一个整数数组 arr，每一次操作你都可以选择并删除它的一个回文子数组 arr[i], arr[i+1], …, arr[j]（ i <= j）。
  • 注意，每当你删除掉一个子数组，右侧元素都会自行向前移动填补空位。
  • 请你计算并返回从数组中删除所有数字所需的最少操作次数。
  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 20

• 输入输出规范

  • 输入：数组

  • 输出：整型，表示删除所需的次数

• 输入输出示例

  • 输入：arr = [1, 3, 4, 1, 5]
  • 输出：3

---

3.2 方法一：DFS & 记忆化搜索 & 双指针 & 分治

• 思路

  • 首先，对于数组中的每一个元素，都只有两种情况
    • 情况一：需要被单独删除
    • 情况二：可以构成一个回文串被删除
  • 那么，我们就可以维护两个指针 left 和 right，同时从数组的首末元素开始DFS搜索，然后分别对两种情况进行讨论
    • 单独删除：left 到 right 需要的次数 = (left + 1) 到 right 的次数 + 1
    • 回文子串删除：此时会搜索 left 到 right 子数组，找到 arr[i] == arr[left]，因为这是构成回文子数组的必要条件，此时根据分治的思想，将数组从 i 分割成两部分，分别搜索 left + 1 到 i - 1 部分和 i + 1 到 right 部分
    • 每次搜索中，将次数更新为两种情况中的最小值
  • 由于暴力DFS很可能TLE超时，所以需要通过记忆化搜索来避免重复计算，二维数组 memo[left][right] 就表示索引从 left 到 right 的子数组的最少删除次数
  • 注意：对于搜索过程中的第二种情况，如果 arr[i] == arr[left]，并不表示 left 到 i 构成一个回文子数组，因为中间元素不确定，但是至少将中间元素删除后，left 和 i 两个元素是相同的，构成一个回文子数组，实际上，此时分为两个数组去搜索就会逐级判断中间元素的情况
  • 此外：当 left + 1 == i 时，即这两个相同元素相邻，此时因为只能拆分出一个子数组，另一个是空的(left + 1, i - 1)，所以此时次数还需要加1，表示删除 left 和 i 元素的操作

• 题解

  // 记忆化搜索
  int[][] memo;
  public int minimumMoves(int[] arr) {
      if (arr == null || arr.length == 0) return 0;
      int n = arr.length;
      if (n == 1) return 1;
      memo = new int[n][n];
      return dfs(arr, 0, n - 1);
  }
  
  private int dfs(int[] arr, int left, int right) {
      if (left > right) return 0;
      if(memo[left][right] != 0) return memo[left][right];
      int count = 0;
      // 第一种情况，单独删除
      count = dfs(arr, left + 1, right) + 1;
      // 第二种情况，构成回文串删除
      for (int i = left + 1; i <= right; i++) {
          if (arr[i] == arr[left]) {
              // 取两种情况中的最小值，且第二种情况是将数组拆分开来分别计算的
              count = Math.min(count, dfs(arr, left + 1, i - 1) + dfs(arr, i + 1, right));
              // 第二种情况中的特殊情况：两个相同元素相邻
              count += left == i - 1 ? 1 : 0;
          }
      }
      memo[left][right] = count;
      return count;
  }

• 复杂度分析：n 是数组的大小

  • 时间复杂度：$O(n^3)$，相当于暴搜，实际上会对每个元素单独删除搜一遍，再搜一遍能否构成回文串
  • 空间复杂度：$O(n^2)$，记忆化搜索

---

3.3 方法二：动态规划 & 区间DP

• 思路

  • 对于子数组、子序列问题，动态规划也是一种常用的解决方案，尤其是可以使用记忆化搜索的DFS问题，基本上都可以转换为DP问题
  • 本题是一个区间DP问题，即DP数组是表示一段区间的某个情况、状态，实际上，方法一中的记忆化数组memo就可以理解为DP数组
  • DP数组的含义：dp[i][j]表示区间[i, j]构成的子数组的最少删除次数
  • 边界条件：可以初始化为 j - i + 1，即对应单独删除的情况，或者将dp[i][i]初始化为 1

• 状态转移方程分析

  • 当 i < j 时，不存在子数组，返回 0
  • 当 i == j 时，只有一个元素，返回 1
  • 当 i + 1 == j 时，两个元素，两者相等返回 1 ，不等返回2
  • 当 i + 1 < j 时，至少三个元素，此时分为两种情况
    • 最优操作不进行拆分：如果两个边界相等，则这两个元素可以和中间最后一次删除操作一起删除，有：dp[i][j] = Math.min(dp[i][j],dp[i+1][j-1])
    • 最优操作进行拆分：无论边界是否相等，最优操作都可能是将该区间拆分成两个，然后分别删除，即：dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j])

• 图解

  

• 题解

  public int minimumMovesDP(int[] arr) {
      if (arr == null || arr.length == 0) return 0;
      int n = arr.length;
      if (n == 1) return 1;
      int[][] dp = new int[n][n];
      for (int i = 0; i < n; i++) {
          Arrays.fill(dp[i], Integer.MAX_VALUE);
          dp[i][i] = 1; // i == j
      }
      for (int j = 1; j < n; j++) {
          for (int i = j - 1; i >= 0; i--) {
              // 元素相邻的情况
              if (i == j - 1) {
                  dp[i][j] = arr[i] == arr[j] ? 1 : 2;
                  continue;
              }
              // 两端元素相等的情况
              if (arr[i] == arr[j]) {
                  dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
              }
              // 
              for (int k = i; k < j; k++) {
                  dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
              }
          }
      }
      return dp[0][n - 1];
  }

• 复杂度分析：n 是数组的大小

  • 时间复杂度：$O(n^3)$，三重遍历
  • 空间复杂度：$O(n^2)$

本文作者： Chthollists
发布时间： 2022-01-22 15:54:26
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题：LeetCode：1332.删除回文子序列 & 1246.删除回文子数组
本文链接： https://chthollists.github.io/post/e3e5908b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！

支持

感谢您的支持

支付宝

微信