【leetcode系列】【算法】第183场周赛

本文主要是介绍【leetcode系列】【算法】第183场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

 

题目一：非递增顺序的最小子序列

解题思路：

代码实现：

题目二：将二进制表示减到1的步骤数

解题思路：

方法一：

方法二：

代码实现：

方法一：

方法二：

题目三：最长快乐字符串

解题思路：

代码实现：

题目四：石子游戏 III

解题思路：

代码实现：

---

题目一：非递增顺序的最小子序列

题目链接： https://leetcode-cn.com/problems/minimum-subsequence-in-non-increasing-order/

 

解题思路：

排序，从后往前去数字，每取一个判断是否大于总和的一半

如果大于，则返回结果

 

代码实现：

class Solution:def minSubsequence(self, nums: List[int]) -> List[int]:nums.sort()total = sum(nums)res = []for index in range(len(nums) - 1, -1, -1):res.append(nums[index])if sum(res) > total / 2:breakreturn res

 

题目二：将二进制表示减到1的步骤数

题目链接： https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/

 

解题思路：

方法一：

将二进制字符串转成int型变量，按照规则模拟每一步，然后叠加次数

方法二：

从后向前遍历每一位，添加一个进位标识。遍历时加上进位标识，会有如下几种情况：

1. 0 : 说明是偶数，步数 + 1
2. 1 : 说明是奇数，需要对当前数字 + 1后除2，才能消除此位，步数 + 2，进位 = 1
3. 2 : 说明原本是奇数，但是加上进位之后变为偶数，步数 + 1，进位 = 1

 

代码实现：

方法一：

class Solution:def numSteps(self, s: str) -> int:num = int(s, 2)count = 0while num > 1:if num % 2 == 0:num //= 2else:num += 1count += 1return count

 

方法二：

class Solution:def numSteps(self, s: str) -> int:count = 0add_num = 0for index in range(len(s) - 1, -1, -1):num = int(s[index]) + add_numadd_num = 0if index == 0 and add_num == 0 and num == 1:breakif 0 == num:count += 1elif 1 == num:count += 2add_num = 1else:count += 1add_num = 1return count

 

题目三：最长快乐字符串

题目链接： https://leetcode-cn.com/problems/longest-happy-string/

 

解题思路：

按照当前剩余可拼接字符个数排序，从大到小判断当前字符是否可以拼接

如果可以拼接，则拼接单个字符，更新剩余个数

如果不可以拼接，按序获取下一个字符

直到所有字符均不可拼接或者所有字符用完

 

代码实现：

class Solution:def longestDiverseString(self, a: int, b: int, c: int) -> str:num_lst = {'a' : a, 'b' : b, 'c' : c}res = ''while sum(num_lst.values()) > 0:stop = Falsefor a in sorted(num_lst.items(), key = lambda item: item[1], reverse = True):if res[-2:] == a[0] * 2 or a[1] <= 0:stop = Truecontinueres += a[0]num_lst[a[0]] -= 1stop = Falsebreakif stop:breakreturn res

 

题目四：石子游戏 III

题目链接： https://leetcode-cn.com/problems/stone-game-iii/

 

解题思路：

博弈论类型的题，动态规划，从后向前递推

动态规划数组dp第index位保存的，是如果剩下从index到最后一堆石子时，能够获取的最大分数是多少

当剩下最后一位时，因为必须拿取一个，所以dp数组的最后一位，等于原数组的最后一位

之后向前递推，递推时添加从最后一位到当前位的总和，更新第index位动态规划数组时逻辑如下：

变量：

1. index : 当前递推到的下标
2. dp : 动态规划数组(比stoneValue多申请3位，数字均为0。这样可以不用对于下标进行特殊处理)
3. curr_sum : 从最后一位到index位的总和
4. stoneValue : 原始数组，此处假设数组为[1, 2, 3, -1, -2, -3, 7]

逻辑(从后向前遍历stoneValue)：

1. 更新curr_sum = curr_sum + stoneValue[index] = 0 + 7 = 7
2. 初始化dp[index] = float('-inf')无穷小
3. 更新dp[index]时的逻辑如下记表格，所以更新的式子为dp[index] = curr_sum - min(dp[index + 1], dp[index + 2], dp[index + 3])，目的是尽快能的使得自己获得的值最大

你的行为	对方开始的下标	对方的最大值	你的最大值
取1个	index + 1	dp[index + 1]	curr_sum - dp[index + 1]
取2个	index + 2	dp[index + 2]	curr_sum - dp[index + 2]
取3个	index + 3	dp[index + 3]	curr_sum - dp[index + 3]

持续上述步骤，直到遍历到dp[0]

因为Alice总是先开始，所以Alice可以获取到的最大分数为dp[0]，Bob可以获取到的最大分数为curr_sum - dp[0]

然后判断Alice和Bob的分数即可

 

代码实现：

class Solution:def stoneGameIII(self, stoneValue: List[int]) -> str:dp = [0] * (len(stoneValue) + 3)curr_sum = 0for index in range(len(stoneValue) - 1, -1, -1):dp[index] = float('-inf')curr_sum += stoneValue[index]dp[index] = curr_sum - min([dp[index + 1], dp[index + 2], dp[index + 3]])alice_score = dp[0]bob_score = curr_sum - dp[0]if alice_score > bob_score:return 'Alice'elif alice_score < bob_score:return 'Bob'return 'Tie'

 

这篇关于【leetcode系列】【算法】第183场周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---