LeetCode 第183场周赛

我不管我截图了🙃

第一题:非递增顺序的最小子序列

难度简单

题目描述

给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

如果存在多个解决方案,只需返回 长度最小 的子序列。如果仍然有多个解决方案,则返回 元素之和最大 的子序列。

与子数组不同的地方在于,「数组的子序列」不强调元素在原数组中的连续性,也就是说,它可以通过从数组中分离一些(也可能不分离)元素得到。

注意,题目数据保证满足所有约束条件的解决方案是 唯一 的。同时,返回的答案应当按 非递增顺序 排列。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 100

题目链接

https://leetcode-cn.com/problems/minimum-subsequence-in-non-increasing-order/

思路:

  从大到小取,大于nums所有元素和的一半即可。

代码:

第二题:将二进制表示减到 1 的步骤数

难度中等

题目描述

给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数:

  • 如果当前数字为偶数,则将其除以 2 。
  • 如果当前数字为奇数,则将其加上 1 。

题目保证你总是可以按上述规则将测试用例变为 1 。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= s.length <= 500
  • s 由字符 '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)转成十进制;
  ② 按题意进行操作,计算次数。

代码:

第三题:最长快乐字符串

难度中等

题目描述

如果字符串中不含有任何 'aaa''bbb''ccc' 这样的字符串作为子串,那么该字符串就是一个「快乐字符串」。

给你三个整数 abc,请你返回 任意一个 满足下列全部条件的字符串 s

  • s 是一个尽可能长的快乐字符串。
  • s最多a 个字母 'a'b 个字母 'b'c 个字母 'c'
  • s中只含有 'a''b''c' 三种字母。

如果不存在这样的字符串 s ,请返回一个空字符串 ""

示例 1:

示例 2:

示例 3:

提示:

  • 0 <= a, b, c <= 100
  • a + b + c > 0

题目链接

https://leetcode-cn.com/problems/longest-happy-string/

思路:

  这题我真是*了,取字母的逻辑就是:
  ① abc中字母最多的取2个;
  ② 如果此时字母最多的变了,则重复①,如果此时字母最多的没变,随便取一个另外的字母,再重复①;
  ③ 如果②中随便取一个另外的字母没有字母可以取了,结束循环。
  比赛的时候心态一慌真是不好写,看我的代码就知道了🤦‍♂️

代码:

第四题:石子游戏 III

难度困难

题目描述

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分,得分最高的选手将会赢得比赛,比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” Bob 赢了就返回 “Bob”,平局(分数相同)返回 “Tie”

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 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)

代码: