数组与贪心算法——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;}}
}