Python每日一练(20230401)

1. 最大子序和 ????

2. 从前序与中序遍历序列构造二叉树 ????????

3. 岛屿数量 ????????

1. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [0]
输出：0

示例 4：

输入：nums = [-1]
输出：-1

示例 5：

输入：nums = [-100000]
输出：-100000

提示：

1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

出处：

https://edu.csdn.net/practice/24394323

代码：

class Solution(object):
    def maxSubArray(self, nums):
        maxEndingHere = maxSofFar = nums[0]
        for i in range(1, len(nums)):
            maxEndingHere = max(maxEndingHere + nums[i], nums[i])
            maxSofFar = max(maxEndingHere, maxSofFar)
        return maxSofFar
# %%
s = Solution()
print(s.maxSubArray(nums = [-2,1,-3,4,-1,2,1,-5,4]))

输出：

分治法：

思路是将数组分成两部分，分别计算左半部分最大连续子序列和、右半部分最大连续子序列和以及跨越中间元素的最大连续子序列和，然后取三者的最大值即可。递归终止条件是分到只剩下一个元素的时候，此时最大连续子序列和就是该元素的值。

def maxSubArray(nums):
    if len(nums) == 1: return nums[0]
    mid = len(nums)//2
    left_sum = maxSubArray(nums[:mid])
    right_sum = maxSubArray(nums[mid:])
    cross_sum = crossSubArray(nums, mid)
    return max(left_sum, right_sum, cross_sum)

def crossSubArray(nums, mid):
    Infinity = float('-inf')
    left_sum, left_max = 0, Infinity
    for i in range(mid-1, -1, -1):
        left_sum += nums[i]
        left_max = max(left_max, left_sum)
        right_sum, right_max = 0, Infinity
        for i in range(mid, len(nums)):
            right_sum += nums[i]
            right_max = max(right_max, right_sum)
    return left_max + right_max

nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSubArray(nums))

2. 从前序与中序遍历序列构造二叉树

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

示例 1:

Python每日一练(20230401)

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均无重复元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

出处：

https://edu.csdn.net/practice/24394324

代码1：递归法

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        i = inorder.index(root.val)
        root.left = self.buildTree(preorder[1 : i + 1], inorder[:i])
        root.right = self.buildTree(preorder[i + 1 :], inorder[i + 1 :])
        return root

def levelOrder(root):
    if not root: return []
    res, que = [], [root]
    while que:
        cur = que.pop(0)
        if cur:
            res.append(cur.val) 
            que.append(cur.left)
            que.append(cur.right)
        else:
            res.append(None)
    while res[-1] is None:
        res.pop()
    return res

s = Solution()
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = s.buildTree(preorder, inorder)
print(levelOrder(root))

输出：

[3, 9, 20, None, None, 15, 7]

代码2：迭代法

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    def levelOrder(self):
        if not root: return []
        res, que = [], [self]
        while que:
            cur = que.pop(0)
            if cur:
                res.append(cur.val) 
                que.append(cur.left)
                que.append(cur.right)
            else:
                res.append(None)
        while res[-1] is None:
            res.pop()
        return res

class Solution:
    def buildTree(self, preorder, inorder):
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        cur, stack = 0, [root]
        for i in range(1, len(preorder)):
            node = TreeNode(preorder[i])
            if stack[-1].val != inorder[cur]:
                stack[-1].left = node
            else:
                while stack and stack[-1].val == inorder[cur]:
                    parent = stack.pop()
                    cur += 1
                parent.right = node
            stack.append(node)
        return root

s = Solution()
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
root = s.buildTree(preorder, inorder)
print(root.levelOrder())

3. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

出处：

https://edu.csdn.net/practice/24394325

代码1： DFS

遍历所有相邻的陆地，并将它们标记为已访问，直到遍历完整个岛屿。统计访问的岛屿数量，最终输出。

from typing import List
class Solution:
    def depthSearch(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
            return
        if grid[i][j] == "0":
            return
        grid[i][j] = "0"
        self.depthSearch(grid, i - 1, j)
        self.depthSearch(grid, i + 1, j)
        self.depthSearch(grid, i, j - 1)
        self.depthSearch(grid, i, j + 1)
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        w, h = len(grid[0]), len(grid)
        cnt = 0
        for i in range(h):
            for j in range(w):
                if grid[i][j] == "1":
                    self.depthSearch(grid, i, j)
                    cnt += 1
        return cnt

# %%
s = Solution()
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]]
print(s.numIslands(grid))

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]
print(s.numIslands(grid))

输出：

1
3

闭包函数形式：

def numIslands(grid):
    if not grid: return 0
    row, col = len(grid), len(grid[0])
    count = 0
    def dfs(i, j):
        if not (0<=i<row and 0<=j<col and grid[i][j] == '1'):
            return
        grid[i][j] = '0'
        dfs(i-1, j)
        dfs(i+1, j)
        dfs(i, j-1)
        dfs(i, j+1)
    for i in range(row):
        for j in range(col):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

代码2： BFS

用队列遍历所有相邻的陆地，并将它们标记为已访问，直到遍历完整个岛屿。

from collections import deque
def numIslands(grid):
    if not grid: return 0
    row, col = len(grid), len(grid[0])
    count = 0
    queue = deque()
    direct = [(0,1), (0,-1), (1,0), (-1,0)]
    for i in range(row):
        for j in range(col):
            if grid[i][j] == '1':
                count += 1
                queue.append((i, j))
                grid[i][j] = '0'
                while queue:
                    p, q = queue.popleft()
                    for d in direct:
                        x, y = p + d[0], q + d[1]
                        if 0<=x<row and 0<=y<col and grid[x][y] == '1':
                            queue.append((x, y))
                            grid[x][y] = '0'
    return count

grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]]
print(numIslands(grid))

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]
print(numIslands(grid))

代码3：并查集

将所有陆地的坐标看作节点，相邻陆地之间就是边。利用并查集将所有相邻的陆地节点进行合并，最终统计联通块的数量就是岛屿的数量。

class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.count = 0
        self.parent = [-1] * (m * n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self.parent[i * n + j] = i * n + j
                    self.count += 1
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            self.parent[rooty] = rootx
            self.count -= 1

def numIslands(grid):
    if not grid:
        return 0
    uf = UnionFind(grid)
    m, n = len(grid), len(grid[0])
    direct = [(0,1), (0,-1), (1,0), (-1,0)]
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                for d in direct:
                    x, y = i + d[0], j + d[1]
                    if 0<=x<m and 0<=y<n and grid[x][y] == '1':
                        uf.union(i * n + j, x * n + y)
    return uf.count

grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]]
print(numIslands(grid))

grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]]
print(numIslands(grid))

???? 每日一练刷题专栏 ????

✨ 持续，努力奋斗做强刷题搬运工！

???? 点赞，你的认可是我坚持的动力！

???? 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！

☸ 主页：https://hannyang.blog.csdn.net/

	Golang每日一练专栏
	Python每日一练专栏
	C/C++每日一练专栏
	Java每日一练专栏

秒客网

Python每日一练(20230401)

1. 最大子序和

2. 从前序与中序遍历序列构造二叉树

3. 岛屿数量

???? 每日一练刷题专栏 ????

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

相关文章

Python每日一练(20230401)

1. 最大子序和

2. 从前序与中序遍历序列构造二叉树

3. 岛屿数量

???? 每日一练刷题专栏 ????

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

相关文章

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏