1. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
出处：
https://edu.csdn.net/practice/24500500
代码1： 递归
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def isSymmetric(self, root: TreeNode) -> bool: def judge(left, right): if not left and not right: return True elif not left or not right: return False else: return left.val == right.val and judge(left.right, right.left) and judge(left.left, right.right) return judge(root, root) def listToTree(lst: list) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root if __name__ == '__main__': s = Solution() nums = [1,2,2,3,4,4,3] root = listToTree(nums) print(s.isSymmetric(root)) null = None nums = [1,2,2,null,3,null,3] root = listToTree(nums) print(s.isSymmetric(root))
输出：
True
False
代码2： 递归
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def isSymmetric(self, root: TreeNode) -> bool: if not root: return True queue = [root.left, root.right] while queue: left = queue.pop(0) right = queue.pop(0) if not left and not right: continue if not left or not right or left.val != right.val: return False queue.append(left.left) queue.append(right.right) queue.append(left.right) queue.append(right.left) return True def listToTree(lst: list) -> TreeNode: if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root if __name__ == '__main__': s = Solution() nums = [1,2,2,3,4,4,3] root = listToTree(nums) print(s.isSymmetric(root)) null = None nums = [1,2,2,null,3,null,3] root = listToTree(nums) print(s.isSymmetric(root))
输出：
True
False
2. 输出整数的全排列
输入整数n（3<=n<=7），编写程序输出1，2，....，n整数的全排列，按字典序输出。
输入样例：
输入：3
输出：123 132 213 231 312 321
出处：
https://edu.csdn.net/practice/24500501
代码：
import random n = int(input()) t = list() t1 = set() for i in range(1,n+1): t.append(str(i)) while True: sum = 1 for i in range(1, n + 1): sum *= i if len(t1) >= sum: break random.shuffle(t) t1.add("".join(t)) s = sorted(t1) for i in s: print(i,end=" ")
输入输出：
3
123 132 213 231 312 321
3. 盛最多水的容器
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2
提示：
n = height.length
2 <= n <= 3 * 10^4
0 <= height[i] <= 3 * 10^4
出处：
https://edu.csdn.net/practice/24500502
代码1：
from typing import List class Solution: def maxArea(self, height: List[int]) -> int: N = len(height) i = 0 j = N-1 max_area = 0 while i < j: c = (j-i)*min(height[i], height[j]) if c > max_area: max_area = c if height[i] > height[j]: j -= 1 else: i += 1 return max_area # %% s = Solution() print(s.maxArea([1,8,6,2,5,4,8,3,7])) print(s.maxArea([1,1])) print(s.maxArea([4,3,2,1,4])) print(s.maxArea([1,2,1]))
输出：
49
1
16
2
代码2：
from typing import List class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) ans = 0 for i in range(n): for j in range(i + 1, n): area = min(height[i], height[j]) * (j - i) ans = max(ans, area) return ans # %% s = Solution() print(s.maxArea([1,8,6,2,5,4,8,3,7])) print(s.maxArea([1,1])) print(s.maxArea([4,3,2,1,4])) print(s.maxArea([1,2,1]))
代码3：
from typing import List class Solution: def maxArea(self, height: List[int]) -> int: n = len(height) ans = 0 i, j = 0, n - 1 while i < j: area = min(height[i], height[j]) * (j - i) ans = max(ans, area) if height[i] < height[j]: i += 1 else: j -= 1 return ans # %% s = Solution() print(s.maxArea([1,8,6,2,5,4,8,3,7])) print(s.maxArea([1,1])) print(s.maxArea([4,3,2,1,4])) print(s.maxArea([1,2,1]))
