Python每日一练(20230402)

发布人：shili8 发布时间：2023-04-12 03:25 阅读次数：37

1. 对称二叉树??🌟

2. 输出整数的全排列??🌟

3. 盛最多水的容器??🌟🌟

🌟 每日一练刷题专栏?🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树?[1,2,2,3,4,4,3]?是对称的。

但是下面这个?[1,2,2,null,3,null,3]?则不是镜像对称的:

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

出处：

/caseinfo/link/c7a91d069495453d863535db2be5d0a7

代码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

出处：

/caseinfo/link/4ee2495307de427cadc39fb412ec6dda

代码：

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

出处：

/caseinfo/link/9c9144135ed045509f3d9896c5acc3fd

代码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]))