Python每日一练(20230310)

目录

1. 爬楼梯  ★

2. 删除无效的括号  ★★★

3. 给表达式添加运算符   ★★★

🌟 每日一练刷题专栏

C/C++ 每日一练 ​专栏

Python 每日一练 专栏

---

1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

代码：

class Solution(object):def climbStairs(self, n):if n <= 1:return 1dp = [1] * 2for i in range(2, n + 1):dp[1], dp[0] = dp[1] + dp[0], dp[1]return dp[1]
# %%
s = Solution()
print(s.climbStairs(2))
print(s.climbStairs(3))
print(s.climbStairs(7))

输出：

2
3
21

注：本题实质就是斐波那契数列。

---

2. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = "()())()"
输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")("
输出：[""]

提示：

• 1 <= s.length <= 25
• s 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

代码：

class Solution:def removeInvalidParentheses(self, s: str) -> list:left, right = 0, 0for c in s:if c == "(":left += 1elif c == ")":if left == 0:right += 1else:left -= 1else:passdef is_valid(s):level = 0for c in s:if c == "(":level += 1elif c == ")":if level == 0:return Falseelse:level -= 1else:passreturn level == 0def dfs(s, index, left, right, res):"""from index to find ( or ),left and right means how many ( and ) to remove"""if (left == 0) and (right == 0) and is_valid(s):res.append(s)returnfor i in range(index, len(s)):c = s[i]if c in ["(", ")"]:if (i > 0) and (c == s[i - 1]):continueif (c == ")") and (right > 0):dfs(s[:i] + s[i + 1 :], i, left, right - 1, res)elif (c == "(") and (left > 0):dfs(s[:i] + s[i + 1 :], i, left - 1, right, res)else:passres = []dfs(s, 0, left, right, res)return list(set(res))if __name__ == '__main__':s = Solution()print(s.removeInvalidParentheses(s = "()())()"))print(s.removeInvalidParentheses(s = "(a)())()"))print(s.removeInvalidParentheses(s = ")("))

输出：

['()()()', '(())()']
['(a)()()', '(a())()']
['']

---

3. 给表达式添加运算符

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

示例 1:

输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"] 

示例 2:

输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]

示例 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

代码：

class Solution:def __init__(self):self.size = 0self.num = []self.now = []self.sign = []def addOperators(self, num: str, target: int) -> list: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()if __name__ == '__main__':s = Solution()print(s.addOperators(num = "123", target = 6))s = Solution()print(s.addOperators(num = "232", target = 8))s = Solution()print(s.addOperators(num = "105", target = 5))s = Solution()print(s.addOperators(num = "00", target = 0))s = Solution()print(s.addOperators(num = "3456237490", target = 9191))s = Solution()print(s.addOperators(num = "3335", target = 24))

输出：

['1+2+3', '1*2*3']
['2+3*2', '2*3+2']
['1*0+5', '10-5']
['0+0', '0-0', '0*0']
[]
['3*3+3*5']

注：这个可以做简单的“算24”小游戏

---

🌟 每日一练刷题专栏

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

★ 收藏，你的青睐是我努力的方向！ 

✏️ 评论，你的意见是我进步的财富！  

​​	C/C++ 每日一练 ​专栏
​​​	Python 每日一练 专栏