讨论/题目交流/🏆 第 183 场力扣周赛/
🏆 第 183 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

4 分 - 非递增顺序的最小子序列
4 分 - 将二进制表示减到 1 的步骤数
6 分 - 最长快乐字符串
7 分 - 石子游戏 III

展开讨论

分享一下 183 场比赛的个人题解,关注文章末尾的微信公众号能获得完整代码哦

A: 非递增顺序的最小子序列

使用贪心的策略,优先选最大的数。
可以先对元素排序,然后从最大的开始逐一选取,直到选出来的元素的和大于没选的元素的和。

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

首先注意到,二进制串的位数太多了,有 500 位,因此不能将其转化为十进制数,int64 存不下。

另一个想法:在二进制串上模拟 加1 和 除2 的操作。这可以,但没必要。

加1 or 除2 操作,是根据该数的奇偶性决定的。一个二进制数的奇偶性只取决于最后一位。

对于二进制偶数而言,对其 除2,就是将其右移一位。
对于二进制奇数而言,首先要 加1,随即变为一个偶数;紧接下来就是 除2。因此对于奇数而言,它实际上包含了两个操作,第二个操作也是右移一位。

但还要注意另外一点,奇数加1,可能导致进位。因此不能直接以某个位上的值来判断其奇偶性,而是要加上进位值再判断,同时要一直维护进位值。

综上所述,得出最后的算法:

  1. value = 最后一位的值 + 进位值;以 value 判断奇偶性
  2. 若 value 为奇数,操作计数加一,且 value 本身自增 1
  3. 以 value 计算下一轮的进位值,进位值 = value / 2
  4. 右移一位,操作计数加一
  5. 重复步骤 1

C: 最长快乐字符串

这是个构造问题,可以采用贪心的策略。

很容易想到一点,最终构造出来的字符串长度,取决于 a b c 字符中个数最少的那个。因此我们总是先使用个数最多的字符,以保证数量最少的字符不会先用完。

另外,按题目要求,相同的字符不能连着出现 3 次,换言之,一个字符只能连续出现 1 次或 2 次。让一个字符连续出现一次是最优的,这样也保证了一种字符不会先被用完。

当剩余 3 种或 2 种字符时,可以轮流使用它们,交替构造。当只剩下 1 种字符后,只能用于填充 —— 之前构造时,总是使用 1 个连续的字符,因此可以找到同类字符,在它们后面再接 1 个,尽可能使用完剩下的字符。

D: 石子游戏 3

注意到取石头的一个关键条件:只能从最左边的石头堆开始取,不能挑中间的某堆:

  1. 初始石头堆标号为 [0, n-1],Alice 取前 a 个,使得自己得分最大
  2. 剩余石头堆标号为 [a, n-1],Bob 取前 b 个,使得自己得分最大
  3. 剩余石头堆标号为 [a+b, n-1],Alice 取前 c 个,使得自己得分最大
  4. ......

由此可见,步骤 1、2、3、4 ...... 都是同类问题,利用动态规划,定义好状态即可解决:

  1. dp[i][k] 表示当前轮到第 i 个人取,剩下的石头堆为 [k, n-1],能得到的最大分数;其中 i 等于 0 或 1,分别表示 Alice 和 Bob;k 的取值范围是 [0, n-1]
  2. 因为 Alice 是先手,因此 dp[0][0] 就是她最终能得到的最大分数
  3. Bob 能得到的最大分数为 总分 - dp[0][0]
  4. 比较两者得分大小即可得到赢家

而状态转移方程也不难得到:dp[i][k] = max(sum[k, j] + dp[1-i][j+1])

  1. sum[k, j] 表示 [k, j] 堆石头的总和,因为每次只能取 1,2,3 堆石头,所以 j - k <= 2
  2. dp[1-i][j+1] 表示轮到对方取,面对的石头堆为 [j+1, n-1] 能得到的最大分数

关注订阅号一起讨论更多算法问题:
p.PNG

16
展开全部 22 讨论