01
非递增顺序的最小子序列
题目描述【Easy】
给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。
注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
示例：
输入：nums = [4,3,10,9,8]
输出：[10,9]
解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。
本题需要用到贪心算法：只有保证优先取最大的值，才能保证和值最大并且子序列长度最短。
接下来只需要在遍历的过程比较当前累计和和总和的关系即可。
时间复杂度 O(nlogn)，空间复杂度 O(n)。
02
将二进制减到1的步骤数
题目描述【Medium】
给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：
如果当前数字为偶数，则将其除以 2 。
如果当前数字为奇数，则将其加上 1 。
题目保证你总是可以按上述规则将测试用例变为 1 。
示例：
输入：s = "1101"
输出：6
解释："1101" 表示十进制数 13 。
Step 1) 13 是奇数，加 1 得到 14
Step 2) 14 是偶数，除 2 得到 7
Step 3) 7 是奇数，加 1 得到 8
Step 4) 8 是偶数，除 2 得到 4
Step 5) 4 是偶数，除 2 得到 2
Step 6) 2 是偶数，除 2 得到 1
本道题字符串的长度在 [1, 500] 区间内，所以不能直接通过 Number.parseInt 将字符串转为十进制获取结果。
那么就需要针对字符串来模拟二进制的除法和加法操作。
在二进制运算中，除 2 就是将二进制数右移一位，这里直接去掉字符串的最后一位即可。
加 1 操作就相对比较复杂一点，需要由低位向高位处理进位。
接下来，直接按照规则运算即可。
时间复杂度 O(n^2)，空间复杂度 O(n)。
03
最长快乐字符串
题目描述【Medium】
如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
s 是一个尽可能长的快乐字符串。
s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
s 中只含有 'a'、'b' 、'c' 三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 ""。
示例：
输入：a = 1，b = 1，c = 7
输出：'ccaccbcc'
解释：'ccbccacc' 也是正确答案
本道题也需要用到贪心算法：优先选择数量最多的字符。
但是在选择的过程中需要细节拉满：
- 记录前一个字符的状态，避免字符连续出现三次
- 记录前一个字符的数量，如果其数量大于本次字符的数量，那么本次应该只拿一个字符，确保后面帮助前一个字符分割，从而确保长度尽可能长
时间复杂度 O(n)，空间复杂度 O(1)。
04
石头游戏III
题目描述【Hard】
Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。
Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。
每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。
假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，平局（分数相同）返回 "Tie" 。
示例：
输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。
本题可以采用动态规划解决，定义状态 dp[i] 表示从下标 i 开始选择产生的最大差值。（两位玩家都采取最佳策略）
对于任意下标 i 存在以下三种情况：
- 玩家在下标 i 处只拿了第一堆，此时的差值为 stoneValue[i] - dp[i + 1]
- 玩家在下标 i 处拿了前两堆，此时的差值为 stoneValue[i] + stoneValue[i + 1] - dp[i + 2]
- 玩家在下标 i 处拿了前三堆，此时的差值为 stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3]
那么 dp[i] 应该为这三种情况的最大值。
因为 Alice 先手，所以在 dp[0] 大于 0 的情况下，他是可以赢得比赛的。
时间复杂度 O(n)，空间复杂度 O(n)。
05
往期精彩回顾
- 前端工程师的 LeetCode 之旅 -- 周赛 182
- 前端工程师的 LeetCode 之旅 -- 周赛 181
- 前端工程师的 LeetCode 之旅 -- 周赛 180
- 前端工程师的 LeetCode 之旅 -- 周赛 179
- 前端工程师的 LeetCode 之旅 -- 周赛 178
你点的每个赞，我都认真当成了喜欢