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]))
输出：
6
分治法：
思路是将数组分成两部分，分别计算左半部分最大连续子序列和、右半部分最大连续子序列和以及跨越中间元素的最大连续子序列和，然后取三者的最大值即可。递归终止条件是分到只剩下一个元素的时候，此时最大连续子序列和就是该元素的值。
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:
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 <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均无重复元素inorder均出现在preorderpreorder保证为二叉树的前序遍历序列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 self: 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.lengthn == grid[i].length1 <= m, n <= 300grid[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/
