每日一练 — 2022.02.27

一，戳气球

1，程序简介

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

• 输入：nums = [3,1,5,8]
• 输出：167
• 解释：
  nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
  coins = 315 + 358 + 138 + 181 = 167

示例 2：

• 输入：nums = [1,5]
• 输出：10

提示：

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

2，程序代码

"""
时间：2022年2月27日
作者：小梁aixj
功能：戳气球
"""
class Solution:def maxCoins(self, nums: [int]) -> int:n=len(nums)+2nums=[1]+nums+[1]dp=[[0]*n for _ in range(n)]for i in range(n-1,-1,-1):for j in range(i,n):if j-i>1:for k in range(i+1,j):dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j])return dp[0][n-1]
#%%
s = Solution()
print(s.maxCoins(nums = [3,1,5,8]))  

3，运行结果

二，给表达式添加运算符

1，程序简介

给定一个仅包含数字 0-9 的字符串 num 和一个目标值整数 target ，在 num 的数字之间添加 二元 运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。

示例 1:

• 输入: num = “123”, target = 6
• 输出: [“1+2+3”, “123”]

示例 2:

• 输入: num = “232”, target = 8
• 输出: [“23+2", "2+32”]

示例 3:

• 输入: num = “105”, target = 5
• 输出: [“1*0+5”,“10-5”]

示例 4:

• 输入: num = “00”, target = 0
• 输出: [“0+0”, “0-0”, “0*0”]

示例 5:

• 输入: num = “3456237490”, target = 9191
• 输出: []

提示：

• 1 <= num.length <= 10
• num 仅含数字
• $-2^{31}<=target<=2^{31}-1$

2，程序代码

"""
时间：2022年2月27日
作者：小梁aixj
功能：给表达式添加运算符
"""
class Solution:def __init__(self):self.size = 0self.num = []self.now = []self.sign = []def addOperators(self, num: str, target: int) -> [str]:if not num:return []self.size = len(num)self.num = numself.now.append(num[0])self.dfs(0, num[0] == "0")ans = []for ss in self.sign:if eval(ss) == target:ans.append(ss)return ansdef dfs(self, i, zero_start):if i == self.size - 1:self.sign.append("".join(self.now))else:self.now.extend(["+", self.num[i + 1]])self.dfs(i + 1, self.num[i + 1] == "0")self.now.pop()self.now.pop()self.now.extend(["-", self.num[i + 1]])self.dfs(i + 1, self.num[i + 1] == "0")self.now.pop()self.now.pop()self.now.extend(["*", self.num[i + 1]])self.dfs(i + 1, self.num[i + 1] == "0")self.now.pop()self.now.pop()if not zero_start:self.now.extend([self.num[i + 1]])self.dfs(i + 1, False)self.now.pop()
#%%                
s = Solution()
print(s.addOperators(num = "232", target = 8))

3，运行结果

三，只出现一次的数字 II

1，程序简介

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

• 输入：nums = [2,2,3,2]
• 输出：3

示例 2：

• 输入：nums = [0,1,0,1,0,1,99]
• 输出：99

提示：

• 1 <= nums.length <= 3 * 104
• $-2^{31}<=nums[i]<=2^{31}-1$
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

进阶：

• 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

2，程序代码

"""
时间：2022年2月27日
作者：小梁aixj
功能：只出现一次的数字 II
"""
class Solution(object):def singleNumber(self, nums):""":type nums: List[int]:rtype: int"""res = 0for i in range(32):bitnum = 0bit = 1 << ifor num in nums:if num & bit:bitnum += 1if bitnum % 3 != 0:res ^= bitreturn res
#%%
s = Solution()
print(s.singleNumber(nums = [2,2,3,2]))

3，运行结果