题目1：两数之和
问题描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
解题思路：使用哈希表。遍历数组，对于每个元素，检查 target - nums[i] 是否已经在哈希表中，如果在则找到了一对解，如果不在则将当前元素存入哈希表。
Python代码示例:
def twoSum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hashmap:
return [hashmap[complement], i]
hashmap[num] = i
return []题目2：反转链表
问题描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解题思路：迭代或递归。迭代法中，使用三个指针分别指向当前节点、前一个节点和后一个节点，逐步改变它们的指向来反转链表。
Python代码示例（迭代法）:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev题目3：最长公共前缀
问题描述：编写一个函数来查找字符串数组中的最长公共前缀。
解题思路：水平扫描。比较字符串数组中的每个字符串的相应字符，逐个字符向后移动，直到遇到不匹配的字符或扫描完最短的字符串。
Python代码示例:
def longestCommonPrefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
while s[:len(prefix)] != prefix and prefix:
prefix = prefix[:len(prefix)-1]
if not prefix:
break
return prefix题目4：合并两个有序链表
问题描述：将两个升序链表合并为一个新的升序链表并返回。
解题思路：创建虚拟头节点，定义指针比较两个链表的节点值，依次连接较小的节点到新链表，直至一个链表为空，然后将另一个链表剩余部分接到新链表末尾。
Python代码示例:
def mergeTwoLists(l1, l2):
dummy = ListNode()
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next题目5：最大子数组和
问题描述：给定一个整数数组，找到一个具有最大和的连续子数组，并返回其最大和。
解题思路：动态规划。用一个变量 current_sum 跟踪当前子数组的和，用 max_sum 记录到目前为止的最大子数组和。如果 current_sum 变负，则丢弃当前子数组，重新开始计算。
Python代码示例:
def maxSubArray(nums):
current_sum = max_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum题目6：买卖股票的最佳时机 II
问题描述：给定一个数组 prices，其中 prices[i] 是一支股票第 i 天的价格。设计一个算法来找到最大的可能利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。但是，你不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）。
解题思路：动态规划。遍历价格数组，只要后一天的价格比前一天高，就计入利润。
Python代码示例:
def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit题目7：最长回文子串
问题描述：给定一个字符串 s，找到 s 中最长的回文子串。
解题思路：动态规划或中心扩散法。可以使用二维动态规划预计算每个子串是否为回文，或从每个字符出发尝试扩大回文中心。
Python代码示例（中心扩散法）:
def longestPalindrome(s):
if not s:
return ""
start, end = 0, 0
for i in range(len(s)):
len1 = expandAroundCenter(s, i, i)
len2 = expandAroundCenter(s, i, i + 1)
max_len = max(len1, len2)
if max_len > end - start:
start = i - (max_len - 1) // 2
end = i + max_len // 2
return s[start:end+1]
def expandAroundCenter(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1题目8：合并区间
问题描述：以数组的形式给出一些不重叠的区间，请合并所有重叠的区间。
解题思路：排序后合并。首先按照区间的起始位置对所有区间进行排序，然后遍历排序后的区间，合并重叠的区间。
Python代码示例:
def merge(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for interval in intervals[1:]:
if interval[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], interval[1])
else:
merged.append(interval)
return merged题目9：岛屿数量
问题描述：给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边缘都被水包围。
解题思路：深度优先搜索。遍历网格，遇到陆地就进行深度优先搜索标记为已访问，并计数岛屿数量。
Python代码示例:
def numIslands(grid):
def dfs(i, j):
if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':
grid[i][j] = '0'
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count题目10：跳跃游戏 II
问题描述：给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
解题思路：贪心策略。维护一个变量 end 表示当前能够到达的最远位置，以及一个变量 farthest 记录在 end 内部能够到达的最远位置。每次更新 end 和 farthest，并前进到 end 处，直到到达数组末尾。
Python代码示例:
def jump(nums):
jumps = 0
end, farthest = 0, 0
n = len(nums)
for i in range(n):
if i + nums[i] > farthest:
farthest = i + nums[i]
if i == end:
jumps += 1
end = farthest
if end >= n - 1:
break
return jumps题目11：子集
问题描述：给定一个整数数组 nums ，返回该数组所有可能的子集（幂集）。
解题思路：回溯算法。递归地构建子集，对于每个元素，可以选择包含它或不包含它。
Python代码示例:
def subsets(nums):
def backtrack(start, path):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
res = []
backtrack(0, [])
return res题目12：括号生成
问题描述：给定一个整数 n ，生成所有由括号组成的合法组合，且满足括号对之间的嵌套关系。
解题思路：回溯算法。每次添加一个左括号或右括号，需保证任何时候左括号数量都大于等于右括号数量。
Python代码示例:
def generateParenthesis(n):
def backtrack(openN, closeN, path):
if openN == closeN == n:
res.append("".join(path))
return
if openN < n:
path.append("(")
backtrack(openN + 1, closeN, path)
path.pop()
if closeN < openN:
path.append(")")
backtrack(openN, closeN + 1, path)
path.pop()
res = []
backtrack(0, 0, [])
return res题目13：最长连续序列
问题描述：给定一个未排序的整数数组，找出最长连续序列的长度。
解题思路：哈希表。遍历数组，用哈希表记录每个数的存在，然后检查每个数的前驱和后继，扩展连续序列。
Python代码示例:
def longestConsecutive(nums):
num_set = set(nums)
longest_streak = 0
for num in num_set:
if num - 1 not in num_set:
current_num = num
current_streak = 1
while current_num + 1 in num_set:
current_num += 1
current_streak += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak题目14：岛屿数量 II
问题描述：在一个二维网格上，每个单元格可以是陆地（1）或水域（0）。网格的四条边均被水域包围。计算岛屿的数量，岛屿是由四面相连的陆地组成，并且水平或垂直相邻。
解题思路：深度优先搜索 + 按照高度排序。先按照每个岛的最低点排序，再遍历每个岛，用DFS标记访问过的位置。
部分Python代码示例:
from typing import List, Tuple
def sortIslandCells(grid: List[List[int]]) -> List[Tuple[int, int]]:
"""按高度排序所有岛屿单元格"""
cells = [(i, j, height) for i, row in enumerate(grid) for j, height in enumerate(row) if height > 0]
cells.sort(key=lambda x: x[2]) # 按高度排序
return cells
def dfs(grid: List[List[int]], visited: List[List[bool]], i: int, j: int) -> None:
"""深度优先搜索，标记访问过的岛屿"""
rows, cols = len(grid), len(grid[0])
if i < 0 or j < 0 or i >= rows or j >= cols or grid[i][j] == 0 or visited[i][j]:
return
visited[i][j] = True
dfs(grid, visited, i + 1, j)
dfs(grid, visited, i - 1, j)
dfs(grid, visited, i, j + 1)
dfs(grid, visited, i, j - 1)
def numIslands2(grid: List[List[int]]) -> int:
"""计算按高度访问时能形成的岛屿数量"""
if not grid or not grid[0]:
return 0
sortedCells = sortIslandCells(grid)
rows, cols = len(grid), len(grid[0])
visited = [[False] * cols for _ in range(rows)]
islandCount = 0
for cell in sortedCells:
i, j, _ = cell
if not visited[i][j]:
dfs(grid, visited, i, j)
islandCount += 1
return islandCount
# 示例使用
grid = [
[1, 2, 3],
[0, 0, 4],
[7, 6, 5]
]
print(numIslands2(grid))题目15：滑动窗口最大值
问题描述：给定一个数组 nums 和滑动窗口的大小 k，找出所有滑动窗口里的最大值。
解题思路：双端队列。维护一个单调递减的双端队列，队列中存储的是数组的索引，保证队头元素始终是窗口内的最大值。
Python代码示例:
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque()
res = []
for i in range(k):
while dq and nums[i] >= nums[dq[-1]]:
dq.pop()
dq.append(i)
for i in range(k, len(nums)):
res.append(nums[dq[0]])
while dq and dq[0] <= i - k:
dq.popleft()
while dq and nums[i] >= nums[dq[-1]]:
dq.pop()
dq.append(i)
res.append(nums[dq[0]])
return res题目16：合并区间
问题描述：给定一个区间的集合 intervals，其中 intervals[i] = [starti, endi]，合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
解题思路：排序 + 贪心。首先按区间的起始位置对所有区间进行排序，然后遍历排序后的区间，比较当前区间的结束位置与结果数组最后一个区间的结束位置，决定是否合并。
Python代码示例:
def merge(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for interval in intervals[1:]:
if interval[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], interval[1])
else:
merged.append(interval)
return merged题目17：最小路径和
问题描述：给定一个 m x n 的网格，每个单元格中的数字表示从该位置移动到右侧相邻单元格或下侧相邻单元格将会增加的成本。只允许向下或向右移动，找到从左上角到右下角的最小路径和。
解题思路：动态规划。创建一个与原矩阵相同大小的dp矩阵，dp[i][j]表示到达位置(i, j)的最小路径和。dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
Python代码示例
def minPathSum(grid):
m, n = len(grid), len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]题目18：最长公共前缀
问题描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
解题思路：水平扫描。逐字符比较字符串数组中的每个字符串的相应字符，直到发现不匹配的字符或遍历完最短字符串。
Python代码示例:
def longestCommonPrefix(strs):
if not strs:
return ""
for i, char in enumerate(min(strs, key=len)):
for string in strs:
if string[i] != char:
return strs[0][:i]
return min(strs, key=len)题目19：二叉树的最近公共祖先
问题描述：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
解题思路：递归。从根节点开始，如果当前节点是p或q，则返回当前节点；否则，递归查找左右子树，如果左右子树都能找到目标节点，则当前节点即为最近公共祖先。
Python代码示例:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def lowestCommonAncestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
return root if left and right else (left or right)题目20：跳跃游戏 II
问题描述：给定一个非负整数数组，你最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
解题思路：贪心。维护一个变量 end 表示当前能到达的最远位置，另一个变量 farthest 记录在 end 这一步中能到达的最远位置，遍历数组并更新这两个值，直到到达数组末尾。
Python代码示例:
def jump(nums):
jumps = 0
end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == end:
jumps += 1
end = farthest
return jumps原创文章，作者：guozi，如若转载，请注明出处：https://www.sudun.com/ask/78281.html
