欢迎大家加QQ群：623375442，可以方便群里面交流。
100324. Clear Digits
给你一个字符串 s 。
你的任务是重复以下操作删除 所有 数字字符：
- 删除 第一个数字字符 以及它左边 最近 的 非数字 字符。
请你返回删除所有数字字符以后剩下的字符串。
测试样例：
输入：s = "abc"
输出："abc"
解释：字符串中没有数字。
解答：用栈记录所有非数字字符。按照题意，碰到一个数字字符，那就从栈中弹出一个元素，这个元素就是最近的非数字字符。
class Solution {
public String clearDigits(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); ++i) {
if (Character.isDigit(s.charAt(i))) {
stack.pop();
} else {
stack.push(s.charAt(i));
}
}
StringBuilder res = new StringBuilder();
for (char c : stack) {
res.append(c);
}
return res.toString();
}
}100297. Find The First Player to win K Games in a Row
有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。
给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i] 是第 i 位玩家的技能等级。skills 中所有整数 互不相同 。
所有玩家从编号 0 到 n - 1 排成一列。
比赛进行方式如下：
- 队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
- 比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。
这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。
请你返回这个比赛的赢家编号。
测试样例：
输入：skills = [4,2,6,3,9], k = 2
输出：2
解释：
一开始，队列里的玩家为 [0,1,2,3,4] 。比赛过程如下：
- 玩家 0 和 1 进行一场比赛，玩家 0 的技能等级高于玩家 1 ，玩家 0 胜出，队列变为 [0,2,3,4,1] 。
- 玩家 0 和 2 进行一场比赛，玩家 2 的技能等级高于玩家 0 ，玩家 2 胜出，队列变为 [2,3,4,1,0] 。
- 玩家 2 和 3 进行一场比赛，玩家 2 的技能等级高于玩家 3 ，玩家 2 胜出，队列变为 [2,4,1,0,3] 。
- 玩家 2 连续赢了 k = 2 场比赛，所以赢家是玩家 2 。
解答：本质上只要遍历一次数组。如果遍历一次数组，都没发现连续赢下K场的玩家，那么这个时候对头已经是最大值的玩家，只要玩下去，她一定是赢家。否则在一次遍历中，一定能发现某个特殊赢家。
class Solution {
public int findWinningPlayer(int[] skills, int k) {
int win = 0, ed = 1;
int count = 0;
while (ed < skills.length) {
if (skills[win] > skills[ed]) {
++count;
} else {
win = ed;
count = 1;
}
if (count >= k) {
return win;
}
++ed;
}
return win;
}
}100327. Find the Maximum Length of a Good Subsequence II
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。
请你返回 nums 中 好 子序列 的最长长度
测试样例：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：最长好子序列为 [1,2,1,1] 。
解答：第三题和第四题题目完全一样，只有范围不一样，所以我就只写一下第四题的解法。首先需要考虑到，这题我们得用动态规划，我们利用动态规划记录每个位置的，0-k个不同情况下，最长序列长度。然后重点就在于怎么优化动态规划。关键在于seq[i] != seq[i + 1]，所以我们记录每个数字的最长队列和当前最长队列。最后遍历计算最佳结果。
class Solution {
public int maximumLength(int[] nums, int k) {
int len = nums.length, res = 0;
int[] mem = new int[k + 1];
HashMap<Integer, int[]> bestShoot = new HashMap<>();
for (int i = 0; i < len; ++i) {
int[] curBest = new int[k + 1];
// 相同数字下，最好的情况。
if (bestShoot.containsKey(nums[i])) {
int[] old = bestShoot.get(nums[i]);
for (int j = 0; j <= k; ++j) {
curBest[j] = old[j] + 1;
}
}
// 不同数字下，最好的情况。（虽然可能是最佳情况就是当前数字，无论如何，我们都认为是不同数字，bestShoot已经cover相同数字的情况了）
for (int j = 0; j < k; ++j) {
curBest[j + 1] = Math.max(curBest[j + 1], mem[j] + 1);
}
curBest[0] = Math.max(curBest[0], 1);
bestShoot.put(nums[i], curBest);
for (int j = 0; j <= k; ++j) {
mem[j] = Math.max(mem[j], curBest[j]);
res = Math.max(res, mem[j]);
}
}
return res;
}
}