Python每日一练(20230306)
目录
1. 翻转二叉树 ★★
2. 最长公共前缀 ★★
3. 2的幂 ★
1. 翻转二叉树
翻转一棵二叉树。
示例 1:
输入:
4/ \\2 7/ \\ / \\ 1 3 6 9
输出:
4/ \\7 2/ \\ / \\ 9 6 3 1
示例 2:
输入:
1/ \\2 3/ / \\4 5 6\\7
输出:
1/ \\3 2/ \\ \\6 5 4/7
代码:
class TreeNode:def __init__(self, val):self.val = valself.left = Noneself.right = Noneclass Solution(object):def invertTree(self, root):""":type root: TreeNode:rtype: TreeNode"""if not root:return Noneroot.left, root.right = root.right, root.leftself.invertTree(root.left)self.invertTree(root.right)return rootdef listToTree(lst: list) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return rootdef inorderTraversal(root: TreeNode) -> list:if not root:return []res = []res += inorderTraversal(root.left)res.append(root.val)res += inorderTraversal(root.right)return res# %%
s = Solution()lst = [4, 2, 7, 1, 3, 6, 9]
root = listToTree(lst)
print(inorderTraversal(root))
root = s.invertTree(root)
print(inorderTraversal(root))lst = [1, 2, 3, 4, None, 5, 6, None, None, None, None, None, 7]
root = listToTree(lst)
print(inorderTraversal(root))
root = s.invertTree(root)
print(inorderTraversal(root))
输出:
[1, 2, 3, 4, 6, 7, 9]
[9, 7, 6, 4, 3, 2, 1]
[4, 2, 1, 5, 3, 6, 7]
[7, 6, 3, 5, 1, 2, 4]
翻转二叉树的非递归实现:
def invertTree(root: TreeNode) -> TreeNode:
if not root:
return None
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack.append(node.left)
stack.append(node.right)
return root
2. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""
。
示例 1:
输入:strs = ["flower","flow","flight"] 输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"] 输出:"" 解释:输入不存在公共前缀。
提示:
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]
仅由小写英文字母组成
代码:
from typing import Listclass Solution:def longestCommonPrefix(self, strs: List[str]) -> str:if len(strs) == 0:return ''i = 0lcp = []while True:done = Falseif i >= len(strs[0]):breakj = 0while j < len(strs):if i < len(strs[j]):if strs[j][i] != strs[0][i]:done = Truebreakelse:done = Truebreakj += 1if not done:lcp.append(strs[0][i])i += 1else:breakreturn ''.join(lcp)# %%
s = Solution()
print(s.longestCommonPrefix(strs = ["flower","flow","flight"]))
输出:
fl
3. 2的幂
给你一个整数 n
,请你判断该整数是否是 2 的幂次方。如果是,返回 true
;否则,返回 false
。
如果存在一个整数 x
使得 n == 2^x
,则认为 n
是 2 的幂次方。
示例 1:
输入:n = 1 输出:true 解释:20 = 1
示例 2:
输入:n = 16 输出:true 解释:24 = 16
示例 3:
输入:n = 3 输出:false
示例 4:
输入:n = 4 输出:true
示例 5:
输入:n = 5 输出:false
提示:
-2^31 <= n <= 2^31 - 1
进阶:你能够不使用循环/递归解决此问题吗?
代码:
class Solution:def isPowerOfTwo(self, n):z = bin(n)[2:]if z[0] != "1":return Falsefor item in z[1:]:if item != "0":return Falsereturn True# %%
s = Solution()print(s.isPowerOfTwo(1))
print(s.isPowerOfTwo(16))
print(s.isPowerOfTwo(3))
print(s.isPowerOfTwo(4))
print(s.isPowerOfTwo(5))
输出:
True
True
False
True
False
🌟 每日一练刷题专栏
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
★ 收藏,你的青睐是我努力的方向!
✏️ 评论,你的意见是我进步的财富!
C/C++ 每日一练 专栏 |
|
|
Python 每日一练 专栏 |