代码随想录拓展day7 649. Dota2 参议院；1221. 分割平衡字符串；5.最长回文子串；132. 分割回文串 II；673.最长递增子序列的个数

news/2024/11/15 6:17:45/

代码随想录拓展day7 649. Dota2 参议院；1221. 分割平衡字符串；5.最长回文子串；132. 分割回文串 II；673.最长递增子序列的个数

贪心和动态规划的题目。因为贪心其实没什么规律，所以就简要记录了。

649. Dota2 参议院

https://leetcode.cn/problems/dota2-senate/

使用flag标记前后的方式很巧妙。

思路

这道题 题意太绕了，我举一个更形象的例子给大家捋顺一下。

例如输入"RRDDD"，执行过程应该是什么样呢？

  • 第一轮：senate[0]的R消灭senate[2]的D，senate[1]的R消灭senate[3]的D，senate[4]的D消灭senate[0]的R，此时剩下"RD"，第一轮结束！
  • 第二轮：senate[0]的R消灭senate[1]的D，第二轮结束
  • 第三轮：只有R了，R胜利

估计不少同学都困惑，R和D数量相同怎么办，究竟谁赢，其实这是一个持续消灭的过程！ 即：如果同时存在R和D就继续进行下一轮消灭，轮数直到只剩下R或者D为止！

那么每一轮消灭的策略应该是什么呢？

例如：RDDRD

第一轮：senate[0]的R消灭senate[1]的D，那么senate[2]的D，是消灭senate[0]的R还是消灭senate[3]的R呢？

当然是消灭senate[3]的R，因为当轮到这个R的时候，它可以消灭senate[4]的D。

所以消灭的策略是，尽量消灭自己后面的对手，因为前面的对手已经使用过权利了，而后序的对手依然可以使用权利消灭自己的同伴！

那么局部最优：有一次权利机会，就消灭自己后面的对手。全局最优：为自己的阵营赢取最大利益。

局部最优可以退出全局最优，举不出反例，那么试试贪心。

代码实现

实现代码，在每一轮循环的过程中，去过模拟优先消灭身后的对手，其实是比较麻烦的。

这里有一个技巧，就是用一个变量记录当前参议员之前有几个敌对对手了，进而判断自己是否被消灭了。这个变量我用flag来表示。

C++代码如下：

class Solution {
public:string predictPartyVictory(string senate) {// R = true表示本轮循环结束后，字符串里依然有R。D同理bool R = true, D = true;// 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭Rint flag = 0;while (R && D) { // 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了R = false;D = false;for (int i = 0; i < senate.size(); i++) {if (senate[i] == 'R') {if (flag < 0) senate[i] = 0; // 消灭R，R此时为falseelse R = true; // 如果没被消灭，本轮循环结束有Rflag++;}if (senate[i] == 'D') {if (flag > 0) senate[i] = 0;else D = true;flag--;}}}// 循环结束之后，R和D只能有一个为truereturn R == true ? "Radiant" : "Dire";}
};

1221. 分割平衡字符串

https://leetcode.cn/problems/split-a-string-in-balanced-strings/

非常简单粗暴，从头开始遇到平衡字符串计数就行了。唯一的trick就是用一个count来判断平衡字符串。

思路

这道题目看起来好像很复杂，其实是非常简单的贪心。

从前向后遍历，只要遇到平衡子串，计数就+1，遍历一遍即可。

局部最优：从前向后遍历，只要遇到平衡子串 就统计

全局最优：统计了最多的平衡子串。

局部最优可以推出全局最优，举不出反例，那么就试试贪心。

例如，LRLR 这本身就是平衡子串 , 但要遇到LR就可以分割。

C++代码如下：

class Solution {
public:int balancedStringSplit(string s) {int result = 0;int count = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == 'R') count++;else count--;if (count == 0) result++;}return result;}
};

5.最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/

和回文子串的长度相似，只不过这次要记录最大长度。

动态规划

动规五部曲：

  1. 确定dp数组（dp table）以及下标的含义

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

  1. 确定递推公式

在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

  • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
  • 情况二：下标i 与 j相差为1，例如aa，也是文子串
  • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

以上三种情况分析完了，那么递归公式如下：

if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三dp[i][j] = true;}
}

注意这里我没有列出当s[i]与s[j]不相等的时候，因为在下面dp[i][j]初始化的时候，就初始为false。

在得到[i,j]区间是否是回文子串的时候，直接保存最长回文子串的左边界和右边界，代码如下：

if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三dp[i][j] = true;}
}
if (dp[i][j] && j - i + 1 > maxlenth) {maxlenth = j - i + 1;left = i;right = j;
}
  1. dp数组如何初始化

dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。

所以dp[i][j]初始化为false。

  1. 确定遍历顺序

遍历顺序可有有点讲究了。

首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：

在这里插入图片描述

如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。

所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j - 1]都是经过计算的。

代码如下：

for (int i = s.size() - 1; i >= 0; i--) { // 注意遍历顺序for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三dp[i][j] = true;}}if (dp[i][j] && j - i + 1 > maxlenth) {maxlenth = j - i + 1;left = i;right = j;}}}
  1. 举例推导dp数组

举例，输入：“aaa”，dp[i][j]状态如下：

在这里插入图片描述

注意因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。

以上分析完毕，C++代码如下：

class Solution {
public:string longestPalindrome(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));int maxlenth = 0;int left = 0;int right = 0;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j < s.size(); j++) {if (s[i] == s[j]) {if (j - i <= 1) { // 情况一 和 情况二dp[i][j] = true;} else if (dp[i + 1][j - 1]) { // 情况三dp[i][j] = true;}}if (dp[i][j] && j - i + 1 > maxlenth) {maxlenth = j - i + 1;left = i;right = j;}}}return s.substr(left, right - left + 1);}
};

或者也可以在更新dp的时候，就把当前起止位置的最大回文串长度作为dp值更新。

class Solution {
public:string longestPalindrome(string s) {vector<vector<int>> dp(s.size(), vector<int> (s.size(), 0));int maxLength = 0;int left = 0;for(int i = s.size()-1; i>=0; i--){for(int j = i; j<s.size(); j++){ if(s[i] == s[j]){if(j-i == 0){dp[i][j] = 1;} else if (j-i == 1){dp[i][j] = 2;} else if (dp[i+1][j-1] != 0) {dp[i][j] = dp[i+1][j-1] + 2;}}if(dp[i][j] > maxLength){left = i;maxLength = dp[i][j];}}}return s.substr(left, maxLength);}
};

132. 分割回文串 II

https://leetcode.cn/problems/palindrome-partitioning-ii/

这个dp的递推公式不是很好想到，在代码中的实现也要多注意。当0到 i 是回文字符串的时候，最小切割次数就是0了，也就是不用切割。

思路

本题呢其实也可以使用回溯法，只不过会超时！（通过记忆化回溯，也可以过，感兴趣的同学可以自行研究一下）

我们来讲一讲如何使用动态规划，来解决这道题目。

动规五部曲分析如下：

  1. 确定dp数组（dp table）以及下标的含义

dp[i]：范围是[0, i]的回文子串，最少分割次数是dp[i]。

  1. 确定递推公式

来看一下由什么可以推出dp[i]。

如果要对长度为[0, i]的子串进行分割，分割点为j。

那么如果分割后，区间[j + 1, i]是回文子串，那么dp[i] 就等于 dp[j] + 1。

这里可能有同学就不明白了，为什么只看[j + 1, i]区间，不看[0, j]区间是不是回文子串呢？

那么在回顾一下dp[i]的定义： 范围是[0, i]的回文子串，最少分割次数是dp[i]。

[0, j]区间的最小切割数量，我们已经知道了就是dp[j]。

此时就找到了递推关系，当切割点j在[0, i] 之间时候，dp[i] = dp[j] + 1;

本题是要找到最少分割次数，所以遍历j的时候要取最小的dp[i]。

所以最后递推公式为：dp[i] = min(dp[i], dp[j] + 1);

注意这里不是要 dp[j] + 1 和 dp[i]去比较，而是要在遍历j的过程中取最小的dp[i]！

可以有dp[j] + 1推出，当[j + 1, i] 为回文子串

  1. dp数组如何初始化

首先来看一下dp[0]应该是多少。

dp[i]： 范围是[0, i]的回文子串，最少分割次数是dp[i]。

那么dp[0]一定是0，长度为1的字符串最小分割次数就是0。这个是比较直观的。

在看一下非零下标的dp[i]应该初始化为多少？

在递推公式dp[i] = min(dp[i], dp[j] + 1) 中我们可以看出每次要取最小的dp[i]。

那么非零下标的dp[i]就应该初始化为一个最大数，这样递推公式在计算结果的时候才不会被初始值覆盖！

如果非零下标的dp[i]初始化为0，在那么在递推公式中，所有数值将都是零。

非零下标的dp[i]初始化为一个最大数。

代码如下：

vector<int> dp(s.size(), INT_MAX);
dp[0] = 0;

其实也可以这样初始化，更具dp[i]的定义，dp[i]的最大值其实就是i，也就是把每个字符分割出来。

所以初始化代码也可以为：

vector<int> dp(s.size());
for (int i = 0; i < s.size(); i++) dp[i] = i;
  1. 确定遍历顺序

根据递推公式：dp[i] = min(dp[i], dp[j] + 1);

j是在[0，i]之间，所以遍历i的for循环一定在外层，这里遍历j的for循环在内层才能通过 计算过的dp[j]数值推导出dp[i]。

代码如下：

for (int i = 1; i < s.size(); i++) {if (isPalindromic[0][i]) { // 判断是不是回文子串dp[i] = 0;continue;}for (int j = 0; j < i; j++) {if (isPalindromic[j + 1][i]) {dp[i] = min(dp[i], dp[j] + 1);}}
}

大家会发现代码里有一个isPalindromic函数，这是一个二维数组isPalindromic[i][j]，记录[i, j]是不是回文子串。

所以先用一个二维数组来保存整个字符串的回文情况。

代码如下：

vector<vector<bool>> isPalindromic(s.size(), vector<bool>(s.size(), false));
for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j < s.size(); j++) {if (s[i] == s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])) {isPalindromic[i][j] = true;}}
}
  1. 举例推导dp数组

以输入：“aabc” 为例：

在这里插入图片描述

以上分析完毕，代码如下：

class Solution {
public:int minCut(string s) {vector<vector<bool>> isPalindromic(s.size(), vector<bool>(s.size(), false));for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j < s.size(); j++) {if (s[i] == s[j] && (j - i <= 1 || isPalindromic[i + 1][j - 1])) {isPalindromic[i][j] = true;}}}// 初始化vector<int> dp(s.size(), 0);for (int i = 0; i < s.size(); i++) dp[i] = i;for (int i = 1; i < s.size(); i++) {if (isPalindromic[0][i]) {dp[i] = 0;continue;}for (int j = 0; j < i; j++) {if (isPalindromic[j + 1][i]) {dp[i] = min(dp[i], dp[j] + 1);}}}return dp[s.size() - 1];}
};

673.最长递增子序列的个数

https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

第一次遇到两个dp数组的题目。自己基本没想到。记录一下。

思路

  1. 确定dp数组（dp table）以及下标的含义

这道题目我们要一起维护两个数组。

dp[i]：i之前（包括i）最长递增子序列的长度为dp[i]

count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]

  1. 确定递推公式

在300.最长上升子序列 中，我们给出的状态转移是：

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

即：位置i的最长递增子序列长度 等于j从0到i-1各个位置的最长升序子序列 + 1的最大值。

本题就没那么简单了，我们要考虑两个维度，一个是dp[i]的更新，一个是count[i]的更新。

那么如何更新count[i]呢？

以nums[i]为结尾的数组，最长递增子序列的个数为count[i]。

那么在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列。

那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子序列的最长递增子序列的个数，即：count[i] = count[j]。

在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列。

那么以i为结尾的子串的最长递增子序列的个数 就应该加上以j为结尾的子序列的最长递增子序列的个数，即：count[i] += count[j];

代码如下：

if (nums[i] > nums[j]) {if (dp[j] + 1 > dp[i]) {count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {count[i] += count[j];}dp[i] = max(dp[i], dp[j] + 1);
}

当然也可以这么写：

if (nums[i] > nums[j]) {if (dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1; // 更新dp[i]放在这里，就不用max了count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {count[i] += count[j];}
}

这里count[i]记录了以nums[i]为结尾的字符串，最长递增子序列的个数。dp[i]记录了i之前（包括i）最长递增序列的长度。

题目要求最长递增序列的长度的个数，我们应该把最长长度记录下来。

代码如下：

for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {if (dp[j] + 1 > dp[i]) {count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {count[i] += count[j];}dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > maxCount) maxCount = dp[i]; // 记录最长长度}
}
  1. dp数组如何初始化

再回顾一下dp[i]和count[i]的定义

count[i]记录了以nums[i]为结尾的字符串，最长递增子序列的个数。

那么最少也就是1个，所以count[i]初始为1。

dp[i]记录了i之前（包括i）最长递增序列的长度。

最小的长度也是1，所以dp[i]初始为1。

代码如下：

vector<int> dp(nums.size(), 1);
vector<int> count(nums.size(), 1);

其实动规的题目中，初始化很有讲究，也很考察对dp数组定义的理解。

  1. 确定遍历顺序

dp[i] 是由0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。

j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层，代码如下：

for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {if (dp[j] + 1 > dp[i]) {count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {count[i] += count[j];}dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > maxCount) maxCount = dp[i];}
}

最后还有再遍历一遍dp[i]，把最长递增序列长度对应的count[i]累计下来就是结果了。

代码如下：

for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {if (dp[j] + 1 > dp[i]) {count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {count[i] += count[j];}dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > maxCount) maxCount = dp[i];}
}
int result = 0; // 统计结果
for (int i = 0; i < nums.size(); i++) {if (maxCount == dp[i]) result += count[i];
}

统计结果，可能有的同学又有点看懵了，那么就再回顾一下dp[i]和count[i]的定义。

  1. 举例推导dp数组

输入：[1,3,5,4,7]

在这里插入图片描述

如果代码写出来了，怎么改都通过不了，那么把dp和count打印出来看看对不对！

以上分析完毕，C++整体代码如下：

class Solution {
public:int findNumberOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);vector<int> count(nums.size(), 1);int maxCount = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {if (dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {count[i] += count[j];}}if (dp[i] > maxCount) maxCount = dp[i];}}int result = 0;for (int i = 0; i < nums.size(); i++) {if (maxCount == dp[i]) result += count[i];}return result;}
};
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n)

还有O(nlog n)的解法，使用树状数组。


http://www.ppmy.cn/news/9451.html

相关文章

基于Vue和SpringBoot的宾馆管理系统的设计和实现

基于Vue和SpringBoot的宾馆管理系统的设计和实现

作者主页&#xff1a;Designer 小郑 作者简介&#xff1a;Java全栈软件工程师一枚&#xff0c;来自浙江宁波&#xff0c;负责开发管理公司OA项目&#xff0c;专注软件前后端开发&#xff08;Vue、SpringBoot和微信小程序&#xff09;、系统定制、远程技术指导。CSDN学院、蓝桥云…
阅读更多...
CAS 的使用场景 CAS的ABA问题的优化 以及 synchronized 的三大优化

CAS 的使用场景 CAS的ABA问题的优化 以及 synchronized 的三大优化

目录 &#x1f388;专栏链接:多线程相关知识详解 一.什么是CAS 二.CAS最常用的两个场景 Ⅰ.实现原子类 Ⅱ.实现自旋锁 三.CAS的ABA问题 四.优化解决CAS的ABA问题 五.synchronized的优化 Ⅰ.锁升级/锁膨胀 Ⅱ.锁消除 Ⅲ.锁粗化 一.什么是CAS CAS&#xff08;Compar…
阅读更多...
ThreadLocal

ThreadLocal

ThreadLocal是什么ThreadLocal&#xff0c;本地线程变量&#xff0c;ThreadLocal中填充的是当前线程的变量&#xff0c;该变量对其他线程来说是封闭且隔离的。ThreadLocal的静态内部类ThreadLocalMap为每个Thread都维护了一个数组table&#xff0c;ThreadLocal确定了一个数组下…
阅读更多...
sum and plan | 要温和有力量地长途旅行~

sum and plan | 要温和有力量地长途旅行~

最近在一堆DDL和一群羊中夹缝求生。坐在回家的车上&#xff0c;那就小写这姗姗来迟的年末summary和年初plan~ 纷纷扰扰的2022在“低气压”的12月里进入尾声。年末”盘库存“&#xff0c;虽然一些目标和任务未能达成&#xff0c;但这也算是充实有成长的一年。“转换”的一年&am…
阅读更多...
Word处理控件Aspose.Words功能演示：使用 C# 将 Word 转换为 HTML

Word处理控件Aspose.Words功能演示：使用 C# 将 Word 转换为 HTML

Aspose.Words 是一种高级Word文档处理API&#xff0c;用于执行各种文档管理和操作任务。API支持生成&#xff0c;修改&#xff0c;转换&#xff0c;呈现和打印文档&#xff0c;而无需在跨平台应用程序中直接使用Microsoft Word。此外&#xff0c; Aspose API支持流行文件格式处…
阅读更多...
【数据结构】C语言实现栈和队列

【数据结构】C语言实现栈和队列

目录 一、栈 1、栈的概念及结构 2、如何实现栈 3、代码实现 3.1 栈的定义 3.2 栈中将要实现的函数 3.3 函数实现 二、队列 1、队列的概念及结构 2、如何实现队列 3、代码实现 3.1 队列定义 3.2 队列中将要实现的函数 3.3 函数实现 一、栈 1、栈的概念及结构 栈&am…
阅读更多...
【Linux】权限理解（粘滞位设置）

【Linux】权限理解（粘滞位设置）

目  录1 权限的概念2 权限管理2.1 文件类型及其访问权限2.2 文件权限值的表示方法2.3 文件访问权限设置2.4 目录权限&#xff08;粘滞位&#xff09;1 权限的概念 所谓权限&#xff0c;实际上是对人的约束&#xff0c;在Linux中&#xff0c;是对普通用户的约束。一件事情&…
阅读更多...
【1803. 统计异或值在范围内的数对有多少】

【1803. 统计异或值在范围内的数对有多少】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个整数数组 nums &#xff08;下标 从 0 开始 计数&#xff09;以及两个整数&#xff1a;low 和 high &#xff0c;请返回 漂亮数对 的数目。 漂亮数对 是一个形如 (i, j) 的数对&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023