当前位置：首页 > news >正文

徐城乡建设局网站今日头条普通版

news 2025/7/21 20:42:03

徐城乡建设局网站,今日头条普通版,亚马逊网站特点,中国徐州网官网目录 1. 翻转二叉树 ★★ 2. 最长公共前缀 ★★ 3. 2的幂 ★ 1. 翻转二叉树翻转一棵二叉树。示例 1： 输入： 4/ \2 7/ \ / \ 1 3 6 9 输出： 4/ \7 2/ \ / \ 9 6 3 1示例 2： 输入： 1…

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"]))

输出：

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