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 <= 25s由小写英文字母以及括号'('和')'组成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 <= 10num仅含数字-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 每日一练 专栏 |