我不管我截图了🙃 
第一题：非递增顺序的最小子序列
难度简单
题目描述
给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。
注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
示例 1：
|
1 2 3 4 |
输入：nums = [4,3,10,9,8] 输出：[10,9] 解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。 |
示例 2：
|
1 2 3 4 |
输入：nums = [4,4,7,6,7] 输出：[7,7,6] 解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。 |
示例 3：
|
1 2 3 |
输入：nums = [6] 输出：[6] |
提示：
1 <= nums.length <= 5001 <= nums[i] <= 100
题目链接
https://leetcode-cn.com/problems/minimum-subsequence-in-non-increasing-order/
思路:
从大到小取，大于nums所有元素和的一半即可。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution: def minSubsequence(self, nums: List[int]) -> List[int]: n = len(nums) if not n: return [] nums.sort(reverse=True) sums = sum(nums) temp = 0 ans = [] for num in nums: temp += num ans.append(num) if temp > sums // 2: return ans |
第二题：将二进制表示减到 1 的步骤数
难度中等
题目描述
给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：
- 如果当前数字为偶数，则将其除以 2 。
- 如果当前数字为奇数，则将其加上 1 。
题目保证你总是可以按上述规则将测试用例变为 1 。
示例 1：
|
1 2 3 4 5 6 7 8 9 10 |
输入：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 |
示例 2：
|
1 2 3 4 5 |
输入：s = "10" 输出：1 解释："10" 表示十进制数 2 。 Step 1) 2 是偶数，除 2 得到 1 |
示例 3：
|
1 2 3 |
输入：s = "1" 输出：0 |
提示：
1 <= s.length <= 500s由字符'0'或'1'组成。s[0] == '1'
题目链接
https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/
思路:
① 用int(num, base=2)转成十进制；
② 按题意进行操作，计算次数。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def numSteps(self, s: str) -> int: num = int(s, base=2) ans = 0 while num != 1: if num % 2 == 0: num = num // 2 elif num % 2 == 1: num += 1 ans += 1 return ans |
第三题：最长快乐字符串
难度中等
题目描述
如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
s是一个尽可能长的快乐字符串。s中 最多 有a个字母'a'、b个字母'b'、c个字母'c'。s中只含有'a'、'b'、'c'三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 ""。
示例 1：
|
1 2 3 4 |
输入：a = 1, b = 1, c = 7 输出："ccaccbcc" 解释："ccbccacc" 也是一种正确答案。 |
示例 2：
|
1 2 3 |
输入：a = 2, b = 2, c = 1 输出："aabbc" |
示例 3：
|
1 2 3 4 |
输入：a = 7, b = 1, c = 0 输出："aabaa" 解释：这是该测试用例的唯一正确答案。 |
提示：
0 <= a, b, c <= 100a + b + c > 0
题目链接
https://leetcode-cn.com/problems/longest-happy-string/
思路:
这题我真是*了，取字母的逻辑就是：
① abc中字母最多的取2个；
② 如果此时字母最多的变了，则重复①，如果此时字母最多的没变，随便取一个另外的字母，再重复①；
③ 如果②中随便取一个另外的字母没有字母可以取了，结束循环。
比赛的时候心态一慌真是不好写，看我的代码就知道了🤦♂️
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
class Solution: def longestDiverseString(self, a: int, b: int, c: int) -> str: ans = '' conflict = '' while a or b or c: m = max(a, b, c) # m > 0 if m == a and conflict != 'a': conflict = 'a' if a >= 2: ans += 'aa' a -= 2 elif a==1: ans += 'a' a -= 1 elif m == b and conflict != 'b': conflict = 'b' if b >= 2: ans += 'bb' b -= 2 elif b==1: ans += 'b' b -= 1 elif m ==c and conflict != 'c': conflict = 'c' if c >= 2: ans += 'cc' c -= 2 elif c==1: ans += 'c' c -= 1 else: if conflict == 'a': if b: conflict = 'b' ans += 'b' b -= 1 elif c: conflict = 'c' ans += 'c' c -= 1 else: break elif conflict == 'b': if a: conflict = 'a' ans += 'a' a -= 1 elif c: conflict = 'c' ans += 'c' c -= 1 else: break elif conflict == 'c': if a: conflict = 'a' ans += 'a' a -= 1 elif b: conflict = 'b' ans += 'b' b -= 1 else: break return ans |
第四题：石子游戏 III
难度困难
题目描述
Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。
Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。
每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。
假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” ，Bob 赢了就返回 “Bob”，平局（分数相同）返回 “Tie” 。
示例 1：
|
1 2 3 4 |
输入：values = [1,2,3,7] 输出："Bob" 解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。 |
示例 2：
|
1 2 3 4 5 6 7 |
输入：values = [1,2,3,-9] 输出："Alice" 解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。 如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。 如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。 注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。 |
示例 3：
|
1 2 3 4 |
输入：values = [1,2,3,6] 输出："Tie" 解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。 |
示例 4：
|
1 2 3 |
输入：values = [1,2,3,-1,-2,-3,7] 输出："Alice" |
示例 5：
|
1 2 3 |
输入：values = [-1,-2,-3] 输出："Tie" |
提示：
1 <= values.length <= 50000-1000 <= values[i] <= 1000
题目链接
https://leetcode-cn.com/problems/stone-game-iii/
思路:
动态规划。
假设dp[i]表示某个人从stones[i]开始取，能够获得的最大得分；
某一时刻，Alice的得分等于Alice取石子的得分 – Bob取石子的得分；
Alice有三种选择：
① 取一个石子，得分为 stones[i]，Bob最多得分为dp[i+1]，Alice净得分pt1 = stones[i] - dp[i+1]；
② 取两个石子，得分为 stones[i] + stones[i+1]，Bob最多得分为dp[i+2]，Alice净得分pt2 = stones[i] + stones[i+1] - dp[i+2]；
③ 取三个石子，得分为stones[i] + stones[i+1] + stones[i+2]，Bob最多得分为dp[i+3]，Alice净得分pt3 = stones[i] + stones[i+1] + stones[i+2] - dp[i+3]；
最终Alice的选择是净得分最多的，因此dp[i] = max(pt1, pt2, pt3)。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
sys.setrecursionlimit(1000000000) from functools import lru_cache class Solution: def stoneGameIII(self, stoneValue: List[int]) -> str: stones = stoneValue ls = len(stoneValue) if not ls: return 'Tie' # 没有石子 dp = [0 for i in range(ls+3)] dp[ls-1] = stones[-1] if ls >= 2: # 超过2个石子 if stones[-1] >= 0: dp[ls-2] = stones[-2] + stones[-1] else: dp[ls-2] = stones[-2] - stones[-1] # 只拿一个 for i in range(ls-3, -1, -1): pt1 = stones[i] - dp[i+1] pt2 = stones[i] + stones[i+1] - dp[i+2] pt3 = stones[i]+ stones[i+1]+ stones[i+2] - dp[i+3] dp[i] = max(pt1, pt2, pt3) score = dp[0] if score == 0: return 'Tie' elif score > 0: return 'Alice' elif score < 0: return 'Bob' |
