1. AI技术聚合首页
  2. IT

【算法专题】动态规划之子数组和子串系列

乘风 • • IT • 阅读 32

动态规划4.0

  • 动态规划 – – – 子数组、子串系列（数组中连续的一段）
    • 1. 最大子数组和
    • 2. 环形子数组的最大和
    • 3. 乘积最大子数组
    • 4. 乘积为正数的最长子数组长度
    • 5. 等差数列划分
    • 6. 最长湍流子数组
    • 7. 单词拆分
    • 8. 环绕字符串中唯一的子字符串

动态规划 – – – 子数组、子串系列（数组中连续的一段）

1. 最大子数组和

题目链接 -> Leetcode -53.最大子数组和

Leetcode -53.最大子数组和

题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：
输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6
解释：连续子数组[4, -1, 2, 1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5, 4, -1, 7, 8]
输出：23

提示：

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

思路：

  1. 状态表示：这里我们选择比较常用的⽅式，以「某个位置为结尾」，结合「题目要求」，定义一个状态表示：dp[i] 表示：以 i 位置元素为结尾的「所有子数组」中和的最大和。

  2. 状态转移方程：dp[i] 的所有可能可以分为以下两种：

  • 子数组的长度为 1 ：此时 dp[i] = nums[i] ；
  • 子数组的长度大于 1 ：此时 dp[i] 应该等于 以 i – 1 做结尾的「所有子数组」中和的最大值再加上 nums[i] ，也就是 dp[i – 1] + nums[i] 。

由于我们要的是「最大值」，因此应该是两种情况下的最大值，因此可得转移大程：dp[i] = max(nums[i], dp[i – 1] + nums[i]) 。

  1. 返回值：状态表示为「以 i 为结尾的所有子数组」的最大值，但是最大子数组和的结尾我们是不确定的。因此我们需要返回整个 dp 表中的最大值。

代码如下：

		class Solution {
		public:
		    int maxSubArray(vector<int>& nums)
		    {
		        // dp[i] 表⽰：以 i 位置元素为结尾的「所有⼦数组」中和的最⼤和
		        int n = nums.size();
		        vector<int> dp(n);
		        dp[0] = nums[0];
		
		        for (int i = 1; i < n; i++)
		            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
		        
		        int ret = INT_MIN;
		        for (int i = 0; i < n; i++) ret = max(ret, dp[i]);
		
		        // 返回 dp 数组中的最大值即可
		        return ret;
		    }
		};

2. 环形子数组的最大和

题目链接 -> Leetcode -918.环形子数组的最大和

Leetcode -918.环形子数组的最大和

题目：给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i – 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：
输入：nums = [1, -2, 3, -2]
输出：3
解释：从子数组[3] 得到最大和 3

示例 2：
输入：nums = [5, -3, 5]
输出：10
解释：从子数组[5, 5] 得到最大和 5 + 5 = 10

示例 3：
输入：nums = [3, -2, 2, -3]
输出：3
解释：从子数组[3] 和[3, -2, 2] 都可以得到最大和 3

提示：

  • n == nums.length
  • 1 <= n <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4​​​​​​​

思路：本题与「最大子数组和」的区别在于，考虑问题的时候不仅要分析「数组内的连续区域」，还要考虑「数组⾸尾相连」的⼀部分。结果的可能情况分为以下两种：

  • 结果在数组的内部，包括整个数组；
  • 结果在数组首尾相连的一部分上。

其中，对于第一种情况，我们仅需按照「最大子数组和」的求法就可以得到结果，记为 fmax 。对于第二种情况，我们可以分析一下：

  • 如果数组首尾相连的一部分是最大的数组和，那么数组中间就会空出来一部分；
  • 因为数组的总和 sum 是不变的，那么中间连续的一部分的和一定是最小的；

因此，我们就可以得出一个结论，对于第二种情况的最大和，应该等于 sum – gmin ，其中 gmin 表示数组内的「最小子数组和」。两种情况下的最大值，就是我们要的结果。

但是，由于数组内有可能全部都是负数，第一种情况下的结果是数组内的最大值（是个负数），第二种情况下的 gmin == sum ，求的得结果就会是 0 。若直接求两者的最大值，就会是 0 。但是实际的结果应该是数组内的最大值。对于这种情况，我们需要特殊判断一下。

**剩下的步骤就是求「最大子数组和」和 「最小子数组和」了，由于上题已经讲过思路，这里就不再讲了，「最小子数组和」的思路和「最大子数组和」也是类似的。 **

代码如下：

		class Solution {
		public:
		    // 求最大子数组之和
		    int maxSum(vector<int>& nums)
		    {
		        int n = nums.size();
		        vector<int> dp(n + 1);
		        int ret = INT_MIN;
		
		        for(int i = 1; i <= n; i++)
		        {
		            dp[i] = max(dp[i - 1] + nums[i - 1], nums[i - 1]);
		            ret = max(ret, dp[i]);
		        }
		
		        return ret;
		    }
		
		    // 求最小子数组之和
		    int minSum(vector<int>& nums)
		    {
		        int n = nums.size();
		        vector<int> dp(n + 1);
		        int ret = INT_MAX;
		
		        for(int i = 1; i <= n; i++)
		        {
		            dp[i] = min(dp[i - 1] + nums[i - 1], nums[i - 1]);
		            ret = min(ret, dp[i]);
		        }
		
		        return ret;
		    }
		
		    int maxSubarraySumCircular(vector<int>& nums) 
		    {
		        int sum = 0;
		
		        // 求数组总和
		        for(int i = 0; i < nums.size(); i++) sum += nums[i];
		
		        // 求出最大子数组总和在数组内部的情况
		        int _sum = maxSum(nums);
		
		        // 用数组总和减去最小子数组之和即为最大子数组总和
		        int circularSum = sum - minSum(nums);
		
		        // 我们最终要返回上面两种情况的最大值
		        // 特判 sum - minSum(nums) 是否等于 0，即原数组中是否全是负数
		        return circularSum == 0? _sum : max(_sum, circularSum);
		    }
		};

3. 乘积最大子数组

题目链接 -> Leetcode -152.乘积最大子数组

Leetcode -152.乘积最大子数组

题目：给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32 – 位 整数。

子数组 是数组的连续子序列。

示例 1：
输入: nums = [2, 3, -2, 4]
输出 : 6
解释 : 子数组[2, 3] 有最大乘积 6。

示例 2 :
输入 : nums = [-2, 0, -1]
输出 : 0
解释 : 结果不能为 2, 因为[-2, -1] 不是子数组。

提示 :

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • nums 的任何前缀或后缀的乘积都 保证 是一个 32 – 位 整数

思路：

由于正负号的存在，我们很容易就可以得到，如果只用一个状态表示 dp[i] 的值是不正确的。因为 dp[i – 1] 的信息并不能让我们得到 dp[i] 的正确值。比如数组 [-2, 5, -2] ，用上述状态转移得到的 dp数组为 [-2, 5, -2] ，最大乘积为 5 。但是实际上的最大乘积应该是所有数相乘，结果为 20 。

究其原因，就是因为我们在求 dp[2] 的时候，因为 nums[2] 是一个负数，因此我们需要的是「 i – 1 位置结尾的最小的乘积 （-10） 」，这样一个负数乘以「最小值」，才会得到真实的最大值。

因此，我们不仅需要一个「乘积最大值的 dp 表」，还需要⼀个「乘积最小值的 dp 表」。

  1. 状态表示：
  • f[i] 表示：以 i 结尾的所有子数组的最大乘积；
  • g[i] 表示：以 i 结尾的所有子数组的最小乘积；
  1. 状态转移方程：遍历每一个位置的时候，我们要同步更新两个 dp 数组的值。
  • 对于 f[i] ，也就是「以 i 为结尾的所有子数组的最大乘积」，对于所有子数组，可以分为下面三种形式：
    i. 子数组的长度为 1 ，也就是 nums[i] ；
    ii. 子数组的长度大于 1 ，但 nums[i] > 0 ，此时需要的是 i – 1 为结尾的所有子数组的最大乘积 f[i – 1] ，再乘上 nums[i] ，也就是 nums[i] * f[i – 1] ；
    iii. ⼦数组的长度大于 1 ，但 nums[i] < 0 ，此时需要的是 i – 1 为结尾的所有子数组的最小乘积 g[i – 1] ，再乘上 nums[i] ，也就是 nums[i] * g[i – 1] ；

如果 nums[i] = 0 ，所有⼦数组的乘积均为 0 ，三种情况其实都包含了；综上所述， f[i] = max(nums[i], max(nums[i] * f[i – 1], nums[i] * g[i – 1]) )。

  • 对于 g[i] ，也就是「以 i 为结尾的所有子数组的最小乘积」，对于所有子数组，可以分为下面三种形式：
    i. 子数组的长度为 1 ，也就是 nums[i] ；
    ii. 子数组的长度大于 1 ，但 nums[i] > 0 ，此时需要的是 i – 1 为结尾的所有子数组的最小乘积 g[i – 1] ，再乘上 nums[i] ，也就是 nums[i] * g[i – 1] ；
    iii. 子数组的长度大于 1 ，但 nums[i] < 0 ，此时需要的是 i – 1 为结尾的所有子数组的最大乘积 f[i – 1] ，再乘上 nums[i] ，也就是 nums[i] * f[i – 1] ；

如果 nums[i] = 0 ，所有子数组的乘积均为 0 ，三种情况其实都包含了；综上所述， g[i] = min(nums[i], min(nums[i] * f[i – 1], nums[i] * g[i – 1])) 。

3. 返回值：返回 f 表中的最大值；

代码如下：

		class Solution {
		public:
		    int maxProduct(vector<int>& nums)
		    {
		        int n = nums.size();
		        vector<int> f(n + 1), g(n + 1); // f[i] 存到i位置的最大值，g[i]存到i位置的最小值 
		        f[0] = 1, g[0] = 1;
		
		        int ret = INT_MIN;
		        for (int i = 1; i <= n; i++)
		        {
		            // 正数
		            if (nums[i - 1] > 0)
		            {
		                f[i] = max(f[i - 1] * nums[i - 1], nums[i - 1]);
		                g[i] = min(g[i - 1] * nums[i - 1], nums[i - 1]);
		            }
		
		            // 负数
		            else
		            {
		                f[i] = max(g[i - 1] * nums[i - 1], nums[i - 1]);
		                g[i] = min(f[i - 1] * nums[i - 1], nums[i - 1]);
		            }
		
		            // 取最大值
		            ret = max(ret, f[i]);
		        }
		        return ret;
		    }
		};

4. 乘积为正数的最长子数组长度

题目链接 -> Leetcode -1567.乘积为正数的最长子数组长度

Leetcode -1567.乘积为正数的最长子数组长度

题目：给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。

示例 1：
输入：nums = [1, -2, -3, 4]
输出：4
解释：数组本身乘积就是正数，值为 24 。

示例 2：
输入：nums = [0, 1, -2, -3, -4]
输出：3
解释：最长乘积为正数的子数组为[1, -2, -3] ，乘积为 6 。
注意，我们不能把 0 也包括到子数组中，因为这样乘积为 0 ，不是正数。

示例 3：
输入：nums = [-1, -2, -3, 0, 1]
输出：2
解释：乘积为正数的最长子数组是[-1, -2] 或者[-2, -3] 。

提示：

  • 1 <= nums.length <= 10 ^ 5
  • -10 ^ 9 <= nums[i] <= 10 ^ 9

思路：本题的分析方法与上题的类似，所以在这不再作分析，可以参考代码中的注释。

代码如下：

		class Solution {
		public:
		    int getMaxLen(vector<int>& nums) 
		    {
		        int n = nums.size();
		
		        // g[i] 存放以 i 位置为结尾中，乘积为负数的最长子数组长度
		        // f[i] 存放以 i 位置为结尾中，乘积为正数的最长子数组长度
		        vector<int> f(n + 1), g(n + 1);
		        int ret = INT_MIN;
		
		        for(int i = 1; i <= n; i++)
		        {
		            // nums[i - 1] == 0 的情况可以忽略，因为0不是正数
		
		            if(nums[i - 1] > 0)
		            {
		                f[i] = f[i - 1] + 1;
		
		                // 当 nums[i - 1] 大于 0，如果 g[i - 1] 等于 0，nums[i - 1] 在 g[i] 中无效，所以为 0
		                g[i] = g[i - 1] == 0? 0: g[i - 1] + 1;
		            }
		
		            else if(nums[i - 1] < 0)
		            {
		                // 当 nums[i - 1] 小于 0，如果 g[i - 1] 等于 0，nums[i - 1] 在 f[i] 中无效，所以为 0
		                f[i] = g[i - 1] == 0? 0 : g[i - 1] + 1;
		                g[i] = f[i - 1] + 1;
		            }
		
		            ret = max(ret, f[i]);
		        }
		
		        return ret;
		    }
		};

5. 等差数列划分

题目链接 -> Leetcode -413.等差数列划分

Leetcode -413.等差数列划分

题目：如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和[3, -1, -5, -9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。

示例 1：
输入：nums = [1, 2, 3, 4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和[1, 2, 3, 4] 自身。

示例 2：
输入：nums = [1]
输出：0

提示：

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000
  1. 状态表示：
    由于我们的研究对象是「一段连续的区间」，如果我们状态表示定义成 [0, i] 区间内一共有多少等差数列，那么我们在分析 dp[i] 的状态转移时，会无从下手，因为我们不清楚前面那么多的「等差数列都在什么位置」。所以说，我们定义的状态表示必须让等差数列「有迹可循」，让状态转移的时候能找到「大部队」。因此，我们可以「固定死等差数列的结尾」，定义下面的状态表示：
  • dp[i] 表示必须「以 i 位置的元素为结尾」的等差数列有多少种；
  1. 状态转移方程：我们需要了解一下等差数列的性质：如果 a b c 三个数成等差数列，这时候来了⼀个 d ，其中 b c d 也能构成一个等差数列，那么 a b c d 四个数能够成等差序列吗？答案是：显然的。因为他们之间相邻两个元素之间的差值都是一样的。有了这个理解，我们就可以转而分析我们的状态转移方程了。

对于 dp[i] 位置的元素 nums[i] ，会与前⾯的两个元素有下⾯两种情况：

  • nums[i – 2], nums[i – 1], nums[i] 三个元素不能构成等差数列：那么以
    nums[i] 为结尾的等差数列就不存在，此时 dp[i] = 0 ；
  • nums[i – 2], nums[i – 1], nums[i] 三个元素可以构成等差数列：那么以 nums[i – 1] 为结尾的所有等差数列后面填上一个 nums[i] 也是一个等差数列，此时dp[i] = dp[i – 1] 。但是，因为 nums[i – 2], nums[i – 1], nums[i] 三者又能构成一个新的等差数列，因此要在之前的基础上再添上一个等差数列，于是dp[i] = dp[i – 1] + 1；

综上所述：状态转移方程为：

  • 当： nums[i – 2] + nums[i] != 2 * nums[i – 1] 时， dp[i] = 0；
  • 当： nums[i – 2] + nums[i] == 2 * nums[i – 1] 时， dp[i] = 1 + dp[i – 1]
  1. 返回值：因为我们要的是所有的等差数列的个数，因此需要返回整个 dp 表里面的元素之和；

代码如下：

		class Solution {
		public:
		    int numberOfArithmeticSlices(vector<int>& nums) 
		    {
		        int n = nums.size();
		        if(n == 1 || n == 2) return 0;
		        
		        vector<int> dp(n);
		        dp[0] = dp[1] = 0;
		        int ans = 0;
		
		        // dp[i] 表示「以 i 位置的元素为结尾」的等差数列有多少种
		        for(int i = 2; i < n; i++)
		        {
		            if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])
		            {
		                dp[i] = dp[i - 1] + 1;
		            }
		            ans += dp[i];
		        }
		
		        return ans;
		    }
		};

6. 最长湍流子数组

题目链接 -> Leetcode -978.最长湍流子数组

Leetcode -978.最长湍流子数组

题目：给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。

如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。

更正式地来说，当 arr 的子数组 A[i], A[i + 1], …, A[j] 满足仅满足下列条件时，我们称其为湍流子数组：

若 i <= k < j ：
当 k 为奇数时， A[k] > A[k + 1]，且
当 k 为偶数时，A[k] < A[k + 1]；
或 若 i <= k < j ：
当 k 为偶数时，A[k] > A[k + 1] ，且
当 k 为奇数时， A[k] < A[k + 1]。

示例 1：
输入：arr = [9, 4, 2, 10, 7, 8, 8, 1, 9]
输出：5
解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

示例 2：
输入：arr = [4, 8, 12, 16]
输出：2

示例 3：
输入：arr = [100]
输出：1

提示：

  • 1 <= arr.length <= 4 * 10^4
  • 0 <= arr[i] <= 10^9

思路：

  1. 状态表示：我们先尝试定义状态表示为：dp[i] 表示「以 i 位置为结尾的最长湍流数组的长度」。但是，问题来了，如果状态表示这样定义的话，以 i 位置为结尾的最长湍流数组的长度我们没法从之前的状态推导出来。因为我们不知道前一个最长湍流数组的结尾处是递增的，还是递减的。因此，我们需要状态表示能表示多一点的信息：要能让我们知道这一个最长湍流数组的结尾是「递增」的还是「递减」的；

因此需要两个 dp 表：

  • f[i] 表示：以 i 位置元素为结尾的所有子数组中，最后呈现「上升状态」下的最长湍流数组的长度；
  • g[i] 表示：以 i 位置元素为结尾的所有子数组中，最后呈现「下降状态」下的最长湍流数组的长度；
  1. 状态转移方程：对于 i 位置的元素 arr[i] ，有下面两种情况：
  • arr[i] > arr[i – 1] ：如果 i 位置的元素比 i – 1 位置的元素大，说明接下来应该去找 i -1 位置结尾，并且 i – 1 位置元素比前一个元素小的序列，那就是 g[i – 1] 。更新 f[i] 位置的值： f[i] = g[i – 1] + 1 ；
  • arr[i] < arr[i – 1] ：如果 i 位置的元素比 i – 1 位置的元素小，说明接下来应该去找 i – 1 位置结尾，并且 i – 1 位置元素比前一个元素大的序列，那就是f[i – 1] 。更新 g[i] 位置的值： g[i] = f[i – 1] + 1 ；
  • arr[i] == arr[i – 1] ：不构成湍流数组；
  1. 返回值：应该返回「两个 dp 表里面的最大值」，我们可以在填表的时候，顺便更新⼀个最大值；

代码如下：

		class Solution {
		public:
		    int maxTurbulenceSize(vector<int>& arr) 
		    {
		        int n = arr.size();
		        if(n == 1) return 1;
		
		        // f[i] 表⽰：以 i 位置元素为结尾的所有⼦数组中，最后呈现「上升状态」下的最长湍流数组的长度；
		        // g[i] 表⽰：以 i 位置元素为结尾的所有⼦数组中，最后呈现「下降状态」下的最长湍流数组的长度
		        vector<int> f(n, 1), g(n, 1);
		
		        int ans = INT_MIN;
		
		        for(int i = 1; i < n; i++)
		        {
		            f[i] = arr[i - 1] < arr[i]? g[i - 1] + 1 : 1;
		            g[i] = arr[i - 1] > arr[i]? f[i - 1] + 1 : 1;
		
		            ans = max(ans, max(f[i], g[i]));
		        }
		
		        return ans;
		    }
		};

7. 单词拆分

题目链接 -> Leetcode -139.单词拆分

Leetcode -139.单词拆分

题目：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：
输入 : s = “leetcode”, wordDict = [“leet”, “code”]
输出 : true
解释 : 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2：
输入 : s = “applepenapple”, wordDict = [“apple”, “pen”]
输出 : true
解释 : 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重复使用字典中的单词。

示例 3：
输入 : s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出 : false

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

思路：

  1. 状态表示：dp[i] 表示： [0, i] 区间内的字符串，能否被字典中的单词拼接而成；
  2. 状态转移方程：对于 dp[i] ，为了确定当前的字符串能否由字典里面的单词构成，根据最后一个单词的起始位置 j ，我们可以将其分解为前后两部分：
  • 前面一部分 [0, j – 1] 区间的字符串；
  • 后面一部分 [j, i] 区间的字符串。

其中前面部分我们可以在 dp[j – 1] 中找到答案，后面部分的子串可以在字典里面找到。因此，我们得出一个结论：当我们在从 0 ~ i 枚举 j 的时候，只要 dp[j – 1] = true；并且后面部分的子串 s.substr(j, i – j + 1) 能够在字典中找到，那么 dp[i] = true ；

  1. 返回值：由「状态表示」可得：返回 dp[n] 位置的布尔值；

代码如下：

		class Solution {
		public:
		    bool wordBreak(string s, vector<string>& wordDict) 
		    {
		        // 去重 + 插入方便寻找
		        unordered_set<string> hash;
		        for(const auto& str : wordDict) hash.insert(str);
		
		        // dp[i] 表示： [0, i] 区间内的字符串，能否被字典中的单词拼接⽽成
		        int n = s.size();
		        vector<bool> dp(n + 1); // 不给值默认初始化为 false
		        dp[0] = true; // 为了不影响后面的填表
		        s = ' ' + s; // 使字符串下标统一 +1
		
		        for(int i = 1; i <= n; i++)
		        {
		            for(int j = i; j >= 1; j--)
		            {
		                // j 寻找一个单词的起始位置
		                if(dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
		                {
		                    dp[i] = true;
		                    break;
		                }
		            }
		        }
		        return dp[n];
		    }
		};

8. 环绕字符串中唯一的子字符串

题目链接 -> Leetcode -467.环绕字符串中唯一的子字符串

Leetcode -467.环绕字符串中唯一的子字符串

题目：定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串，所以 base 看起来是这样的：

“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”.
给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

示例 1：
输入：s = “a”
输出：1
解释：字符串 s 的子字符串 “a” 在 base 中出现。

示例 2：
输入：s = “cac”
输出：2
解释：字符串 s 有两个子字符串(“a”, “c”) 在 base 中出现。

示例 3：
输入：s = “zab”
输出：6
解释：字符串 s 有六个子字符串(“z”, “a”, “b”, “za”, “ab”, and “zab”) 在 base 中出现。

提示：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成

思路：

  1. 状态表示：dp[i] 表示：以 i 位置的元素为结尾的所有子串里面，有多少个在 base 中出现过；
  2. 状态转移方程：对于 dp[i] ，我们可以根据子串的「长度」划分为两类：
  • 子串的长度等于 1 ：此时这一个字符会出现在 base 中；
  • 子串的长度大于 1 ：如果 i 位置的字符和 i – 1 位置上的字符组合后，出现在 base中的话，那么 dp[i – 1] 里面的所有子串后面填上一个 s[i] 依旧在 base 中出现。因此 dp[i] = dp[i – 1] 。

综上， dp[i] = 1 + dp[i – 1] ，其中 dp[i – 1] 是否加上需要先做一下判断；

  1. 返回值：这里不能直接返回 dp 表里面的和，因为会有重复的结果。在返回之前，我们需要先「去重」：
  • 相同字符结尾的 dp 值，我们仅需保留「最大」的即可，其余 dp 值对应的子串都可以在最大的里面找到；
  • 可以创建一个大小为 26 的数组，统计所有字符结尾的最大 dp 值。

最后返回「数组中所有元素的和」即可；

代码如下：

		class Solution {
		public:
		    int findSubstringInWraproundString(string s) 
		    {
		        // dp[i] 表⽰：以 i 位置的元素为结尾的所有⼦串⾥⾯，有多少个在 base 中出现过
		        int n = s.size();
		        vector<int> dp(n + 1, 1);
		        s = ' ' + s;
		
		        //  利⽤ dp 求出每个位置结尾的最⻓连续⼦数组的⻓度
		        for(int i = 1; i <= n; i++)
		        {
		            // 判断相邻
		            if(s[i - 1] + 1 == s[i] || (s[i - 1] == 'z'&& 'a' == s[i]))
		            {
		                dp[i] = dp[i - 1] + 1;
		            }
		        }
		
		        // 去重，以相同字符结尾的字符串，我们取 dp 值较大的那一个即可
		        int hash[26] = {0}, ans = 0;
		        for(int i = 1; i <= n; i++) 
		            hash[s[i] - 'a'] = max(dp[i], hash[s[i] - 'a']);
		        
		        // 返回数组中的总和
		        for(int i = 0; i < 26; i++) ans += hash[i];
		
		        return ans;
		    }
		};

版权声明：本文为博主作者：YoungMLet原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/YoungMLet/article/details/134469354

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
乘风的头像乘风管理团队
0
上一篇 2024年2月19日
下一篇 2024年2月19日

相关推荐