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 每日一练 ​专栏