阅读 612

前端工程师的 LeetCode 之旅 -- 周赛 183




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
往期精彩回顾