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
你點的每個贊，我都認真當成了喜歡