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

news/2024/11/25 23:54:06/

代码随想录拓展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的宾馆管理系统的设计和实现

作者主页&#xff1a;Designer 小郑 作者简介&#xff1a;Java全栈软件工程师一枚&#xff0c;来自浙江宁波&#xff0c;负责开发管理公司OA项目&#xff0c;专注软件前后端开发&#xff08;Vue、SpringBoot和微信小程序&#xff09;、系统定制、远程技术指导。CSDN学院、蓝桥云…

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

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

ThreadLocal

ThreadLocal是什么ThreadLocal&#xff0c;本地线程变量&#xff0c;ThreadLocal中填充的是当前线程的变量&#xff0c;该变量对其他线程来说是封闭且隔离的。ThreadLocal的静态内部类ThreadLocalMap为每个Thread都维护了一个数组table&#xff0c;ThreadLocal确定了一个数组下…

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

最近在一堆DDL和一群羊中夹缝求生。坐在回家的车上&#xff0c;那就小写这姗姗来迟的年末summary和年初plan~ 纷纷扰扰的2022在“低气压”的12月里进入尾声。年末”盘库存“&#xff0c;虽然一些目标和任务未能达成&#xff0c;但这也算是充实有成长的一年。“转换”的一年&am…

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

Aspose.Words 是一种高级Word文档处理API&#xff0c;用于执行各种文档管理和操作任务。API支持生成&#xff0c;修改&#xff0c;转换&#xff0c;呈现和打印文档&#xff0c;而无需在跨平台应用程序中直接使用Microsoft Word。此外&#xff0c; Aspose API支持流行文件格式处…

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

目录 一、栈 1、栈的概念及结构 2、如何实现栈 3、代码实现 3.1 栈的定义 3.2 栈中将要实现的函数 3.3 函数实现 二、队列 1、队列的概念及结构 2、如何实现队列 3、代码实现 3.1 队列定义 3.2 队列中将要实现的函数 3.3 函数实现 一、栈 1、栈的概念及结构 栈&am…

【Linux】权限理解(粘滞位设置)

目  录1 权限的概念2 权限管理2.1 文件类型及其访问权限2.2 文件权限值的表示方法2.3 文件访问权限设置2.4 目录权限&#xff08;粘滞位&#xff09;1 权限的概念 所谓权限&#xff0c;实际上是对人的约束&#xff0c;在Linux中&#xff0c;是对普通用户的约束。一件事情&…

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

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