数组与贪心算法——649、678、420 数字与贪心 343（3中1难）
649. Dota2 参议院(中等)
Dota2 的世界里有两个阵营：
Radiant（天辉）和Dire（夜魇）Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：
- 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
- 宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。
给你一个字符串
senate代表每个参议员的阵营。字母'R'和'D'分别代表了Radiant（天辉）和Dire（夜魇）。然后，如果有n个参议员，给定字符串的大小将是n。以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是
"Radiant"或"Dire"。
解法一、计数法
对于任何一种可以求出阵营的状况，最终都会有一轮全部是R/全部是D。所以，根据这一轮判断是否全禁即可。设置r为d禁r的数量，设置d为r禁d的数量。我们不妨假设每个议员都会禁他后面最近的敌对议员。而对于x轮偏后处R禁偏前处D（或D禁R）的情况，则会累积，在x+1轮处处理。
class Solution {
public static String predictPartyVictory(String senate) {
int r = 0,d = 0;
while(true){
StringBuilder sb = new StringBuilder();
for(int i = 0;i < senate.length();i++){
if(senate.charAt(i) == 'R'){
if(r != 0){
r--;
}else{
d++;
sb.append("R");
}
}else{
if(d != 0){
d--;
}else{
r++;
sb.append("D");
}
}
}
senate = sb.toString();
if(r >= senate.length()){
return "Dire";
}else if (d >= senate.length()){
return "Radiant";
}
}
}
}
解法二、队列
遇D弹R队首，遇R弹D队首，行使完权利那个+n放最后。
class Solution {
public String predictPartyVictory(String senate) {
int n = senate.length();
Queue<Integer> radiant = new LinkedList<Integer>();
Queue<Integer> dire = new LinkedList<Integer>();
for (int i = 0; i < n; ++i) {
if (senate.charAt(i) == 'R') {
radiant.offer(i);
} else {
dire.offer(i);
}
}
while (!radiant.isEmpty() && !dire.isEmpty()) {
int radiantIndex = radiant.poll(), direIndex = dire.poll();
if (radiantIndex < direIndex) {
radiant.offer(radiantIndex + n);
} else {
dire.offer(direIndex + n);
}
}
return !radiant.isEmpty() ? "Radiant" : "Dire";
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/dota2-senate/solutions/517088/dota2-can-yi-yuan-by-leetcode-solution-jb7l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
678. 有效的括号字符串（中等）
给你一个只包含三种字符的字符串，支持的字符类型分别是
'('、')'和'*'。请你检验这个字符串是否为有效字符串，如果是 有效 字符串返回true。有效 字符串符合如下规则：
- 任何左括号
'('必须有相应的右括号')'。- 任何右括号
')'必须有相应的左括号'('。- 左括号
'('必须在对应的右括号之前')'。'*'可以被视为单个右括号')'，或单个左括号'('，或一个空字符串""。
解法一、栈
存一个左括栈下标，一个星号栈下标，右侧优先和左括匹配。最后再检测栈里空不空
class Solution {
public boolean checkValidString(String s) {
Deque<Integer> leftStack = new LinkedList<Integer>();
Deque<Integer> asteriskStack = new LinkedList<Integer>();
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') {
leftStack.push(i);
} else if (c == '*') {
asteriskStack.push(i);
} else {
if (!leftStack.isEmpty()) {
leftStack.pop();
} else if (!asteriskStack.isEmpty()) {
asteriskStack.pop();
} else {
return false;
}
}
}
while (!leftStack.isEmpty() && !asteriskStack.isEmpty()) {
int leftIndex = leftStack.pop();
int asteriskIndex = asteriskStack.pop();
if (leftIndex > asteriskIndex) {
return false;
}
}
return leftStack.isEmpty();
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/valid-parenthesis-string/solutions/992347/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。解法二、动态规划
下略
class Solution {
public boolean checkValidString(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '*') {
dp[i][i] = true;
}
}
for (int i = 1; i < n; i++) {
char c1 = s.charAt(i - 1), c2 = s.charAt(i);
dp[i - 1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*');
}
for (int i = n - 3; i >= 0; i--) {
char c1 = s.charAt(i);
for (int j = i + 2; j < n; j++) {
char c2 = s.charAt(j);
if ((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
dp[i][j] = dp[i + 1][j - 1];
}
for (int k = i; k < j && !dp[i][j]; k++) {
dp[i][j] = dp[i][k] && dp[k + 1][j];
}
}
}
return dp[0][n - 1];
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/valid-parenthesis-string/solutions/992347/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。解法三、贪心
设一个最小左括号数，一个最大左括号数（最小+星），如果最小的等于零，即可以用。
class Solution {
public boolean checkValidString(String s) {
int minCount = 0, maxCount = 0;
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') {
minCount++;
maxCount++;
} else if (c == ')') {
minCount = Math.max(minCount - 1, 0);
maxCount--;
if (maxCount < 0) {
return false;
}
} else {
minCount = Math.max(minCount - 1, 0);
maxCount++;
}
}
return minCount == 0;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/valid-parenthesis-string/solutions/992347/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。解法四、双向遍历
一次确认右都有，一次确认左都有
class Solution {
public:
bool checkValidString(string s) {
int n = s.length();
int l = 0, m = 0;
for(int i = 0; i < n; ++i){
if(s[i] == '('){
l++;
}
else if(s[i] == ')'){
l--;
}
else{
m++;
}
if(l < 0){
m--;
l++;
}
if(m < 0){
return false;
}
}
int r = 0;
m = 0;
for(int i = n-1; i >=0; --i){
if(s[i] == ')'){
r++;
}
else if(s[i] == '('){
r--;
}
else{
m++;
}
if(r < 0){
m--;
r++;
}
if(m < 0){
return false;
}
}
return true;
}
};```420. 强密码检验器（困难）
满足以下条件的密码被认为是强密码：
- 由至少
6个，至多20个字符组成。- 包含至少 一个小写 字母，至少 一个大写 字母，和至少 一个数字 。
- 不包含连续三个重复字符 (比如
"Baaabb0"是弱密码, 但是"Baaba0"是强密码)。给你一个字符串
password，返回 将password修改到满足强密码条件需要的最少修改步数。如果password已经是强密码，则返回0。在一步修改操作中，你可以：
- 插入一个字符到
password，- 从
password中删除一个字符，或- 用另一个字符来替换
password中的某个字符。
解法一、分类讨论+模拟
- 6-，只需要替换或者添加，添加优先。尽可能往连续的里面插入，答案取 6−n 与 3−(字符种类) 中的较大值
- 6-20，只需要替换，答案取 所有的 ⌊k/3⌋ 之和)与 3−(字符种类) 中的较大值。。
- 21+，只需要替换或者删除，删除优先。这里要考虑三个东西，一是长度（最后得到n-20）,二是连续（根据K%3答案的不同，一次删除分别能抵消1、 1/2 、 1/3个替换），三是字符种类。用长度所需抵完连续，然后情况类似情况二，取最大值。
class Solution {
public int strongPasswordChecker(String password) {
int n = password.length();
int hasLower = 0, hasUpper = 0, hasDigit = 0;
for (int i = 0; i < n; ++i) {
char ch = password.charAt(i);
if (Character.isLowerCase(ch)) {
hasLower = 1;
} else if (Character.isUpperCase(ch)) {
hasUpper = 1;
} else if (Character.isDigit(ch)) {
hasDigit = 1;
}
}
int categories = hasLower + hasUpper + hasDigit;
if (n < 6) {
return Math.max(6 - n, 3 - categories);
} else if (n <= 20) {
int replace = 0;
int cnt = 0;
char cur = '#';
for (int i = 0; i < n; ++i) {
char ch = password.charAt(i);
if (ch == cur) {
++cnt;
} else {
replace += cnt / 3;
cnt = 1;
cur = ch;
}
}
replace += cnt / 3;
return Math.max(replace, 3 - categories);
} else {
// 替换次数和删除次数
int replace = 0, remove = n - 20;
// k mod 3 = 1 的组数，即删除 2 个字符可以减少 1 次替换操作
int rm2 = 0;
int cnt = 0;
char cur = '#';
for (int i = 0; i < n; ++i) {
char ch = password.charAt(i);
if (ch == cur) {
++cnt;
} else {
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
// 如果是 k % 3 = 0 的组，那么优先删除 1 个字符，减少 1 次替换操作
--remove;
--replace;
} else if (cnt % 3 == 1) {
// 如果是 k % 3 = 1 的组，那么存下来备用
++rm2;
}
// k % 3 = 2 的组无需显式考虑
}
replace += cnt / 3;
cnt = 1;
cur = ch;
}
}
if (remove > 0 && cnt >= 3) {
if (cnt % 3 == 0) {
--remove;
--replace;
} else if (cnt % 3 == 1) {
++rm2;
}
}
replace += cnt / 3;
// 使用 k % 3 = 1 的组的数量，由剩余的替换次数、组数和剩余的删除次数共同决定
int use2 = Math.min(Math.min(replace, rm2), remove / 2);
replace -= use2;
remove -= use2 * 2;
// 由于每有一次替换次数就一定有 3 个连续相同的字符（k / 3 决定），因此这里可以直接计算出使用 k % 3 = 2 的组的数量
int use3 = Math.min(replace, remove / 3);
replace -= use3;
remove -= use3 * 3;
return (n - 20) + Math.max(replace, 3 - categories);
}
}
}343. 整数拆分（中等）
给定一个正整数
n，将其拆分为k个 正整数 的和（k >= 2），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。
解法一、数学幂
2/3分别讨论，4及以上，3的倍数是倍数次幂，模3得1（3m+1）则3^（m-1)+4,模3得2(3m+2)则m^3+2
class Solution {
public int integerBreak(int n) {
if (n <= 3) {
return n - 1;
}
int quotient = n / 3;
int remainder = n % 3;
if (remainder == 0) {
return (int) Math.pow(3, quotient);
} else if (remainder == 1) {
return (int) Math.pow(3, quotient - 1) * 4;
} else {
return (int) Math.pow(3, quotient) * 2;
}
}
}碎碎念
- 649感觉还好，678的贪心实在是很灵活···想到了栈，没做出来，原来要双向。dp还挺难的。。420是分类讨论+细节题。很好想，但是不太好写，需要理清楚思路。343感觉是数学题。。。发现规律就好做，发现不了就得dp，dp太难了看了眼放那吧，感觉真写到dp专题也离死没多远了