题目1：两数之和
问题描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
解题思路：使用哈希表来存储已遍历过的元素及其下标，以便快速查找目标值的补数。
Python代码示例
def twoSum(nums, target):
hash_map = {}
for index, num in enumerate(nums):
complement = target - num
if complement in hash_map:
return [hash_map[complement], index]
hash_map[num] = index
return []题目2：有效的括号
问题描述：给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否有效。
解题思路：使用栈来跟踪括号的开闭状态。
Python代码示例
def isValid(s):
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack题目3：最长公共前缀
问题描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
解题思路：比较所有字符串的前缀，逐字符检查。
Python代码示例
def longestCommonPrefix(strs):
if not strs: return ""
prefix = strs[0]
for i in range(1, len(strs)):
while strs[i].find(prefix) != 0:
prefix = prefix[:-1]
if not prefix: return ""
return prefix题目4：合并两个有序数组
问题描述：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。
解题思路：从后往前遍历两个数组，将较大的数放入 nums1 的末尾。
Python代码示例
def merge(nums1, m, nums2, n):
while m > 0 and n > 0:
if nums1[m-1] > nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
while n > 0:
nums1[n-1] = nums2[n-1]
n -= 1题目5：搜索插入位置
问题描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
解题思路：使用二分查找定位插入位置。
Python代码示例
def searchInsert(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left题目6：数组中的逆序对
问题描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
解题思路：使用归并排序，统计逆序对数目。
Python代码示例
def inversePairs(data):
if not data:
return 0
copy = [0 for _ in range(len(data))]
count = mergeSort(data, copy, 0, len(data) - 1)
return count % 1000000007
def mergeSort(data, copy, start, end):
if start == end:
copy[start] = data[start]
return 0
mid = (start + end) // 2
leftCount = mergeSort(data, copy, start, mid)
rightCount = mergeSort(data, copy, mid + 1, end)
i, j = mid, end
indexCopy = end
number = 0
while i >= start and j >= mid + 1:
if data[i] > data[j]:
copy[indexCopy] = data[i]
indexCopy -= 1
i -= 1
number += j - mid
else:
copy[indexCopy] = data[j]
indexCopy -= 1
j -= 1
for k in range(i, start - 1, -1):
copy[indexCopy] = data[k]
indexCopy -= 1
for k in range(j, mid, -1):
copy[indexCopy] = data[k]
indexCopy -= 1
for k in range(start, end + 1):
data[k] = copy[k]
return leftCount + rightCount + number题目7：链表中环的入口节点
问题描述：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
解题思路：使用快慢指针找到环中的任意一点，然后从起点和环中点出发，再次相遇即为环的入口。
Python代码示例
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow题目8：字符串的排列
问题描述：输入一个字符串，打印出该字符串中字符的所有排列。
解题思路：使用回溯算法，递归生成所有可能的排列。
Python代码示例
def permutation(s):
def backtrack(start):
if start == len(s) - 1:
res.append(''.join(s))
for i in range(start, len(s)):
if i > start and s[i] == s[start]:
continue
s[start], s[i] = s[i], s[start]
backtrack(start + 1)
s[start], s[i] = s[i], s[start]
s = list(s)
s.sort()
res = []
backtrack(0)
return res题目9：二叉树的最近公共祖先
问题描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
解题思路：递归遍历二叉树，寻找目标节点，利用递归返回值传递信息。
Python代码示例
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)
if not left:
return right
if not right:
return left
return root题目10：最长上升子序列
问题描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。
解题思路：动态规划，使用一个数组记录以每个元素结尾的最长上升子序列的长度。
Python代码示例
def lengthOfLIS(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)题目11：搜索旋转排序数组
问题描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。请你在旋转排序数组中搜索给定的目标值 target，如果数组中存在这个目标值 target ，则返回它的索引，否则返回 -1。
解题思路：二分查找，需要处理好边界条件和旋转情况。
Python代码示例
def search(nums, target):
if not nums:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1题目12：最佳买卖股票时机含手续费
问题描述：给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回最大可以得到利润。
解题思路：动态规划，定义 hold 表示持有股票的最大收益，not_hold 表示不持有股票的最大收益。
Python代码示例
def maxProfit(prices, fee):
hold, not_hold = -prices[0], 0
for price in prices[1:]:
hold = max(hold, not_hold - price)
not_hold = max(not_hold, hold + price - fee)
return not_hold题目13：岛屿数量
问题描述：给你一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，请你计算网格中岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
解题思路：深度优先搜索（DFS），对于每一个陆地位置，使用DFS标记并计数。
Python代码示例
def numIslands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
def dfs(x, y):
if x < 0 or y < 0 or x >= m or y >= n or grid[x][y] == '0':
return
grid[x][y] = '0'
dfs(x+1, y)
dfs(x-1, y)
dfs(x, y+1)
dfs(x, y-1)
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count题目14：单词接龙
问题描述：给出两个单词 beginWord 和 endWord 和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
解题思路：广度优先搜索（BFS），构建图的邻接表，然后使用 BFS 寻找最短路径。
Python代码示例
from collections import deque, defaultdict
def findLadders(beginWord, endWord, wordList):
wordList = set(wordList)
if endWord not in wordList:
return []
layer = {}
layer[beginWord] = [[beginWord]]
while layer:
newLayer = defaultdict(list)
for word in layer:
if word == endWord:
return layer[word]
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
newWord = word[:i] + c + word[i+1:]
if newWord in wordList:
newLayer[newWord] += [j + [newWord] for j in layer[word]]
wordList -= set(newLayer.keys())
layer = newLayer
return []题目15：全拼
问题描述：给定一个字符串 s，返回所有可能的全拼组合。输入字符串将只包含小写字母。你可以按任意顺序返回答案。
解题思路：使用哈希表存储字母与数字的对应关系，然后使用递归来生成所有可能的组合。
Python代码示例
def letterCombinations(digits):
if not digits:
return []
phoneMap = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
ans = []
def backtrack(index, path):
if len(path) == len(digits):
ans.append("".join(path))
return
for option in phoneMap[digits[index]]:
path.append(option)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return ans题目16：跳跃游戏 II
问题描述：给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
解题思路：贪心算法，记录当前能够达到的最远位置和每次跳跃后能够达到的最远位置。
Python代码示例
def jump(nums):
jumps = 0
current_jump_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_jump_end:
jumps += 1
current_jump_end = farthest
if current_jump_end >= len(nums) - 1:
break
return jumps题目17：接雨水
问题描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算在下雨之后，能够接多少雨水。
解题思路：动态规划，分别从左向右和从右向左计算左右两侧的最大高度。
Python代码示例
def trap(height):
if not height:
return 0
left_max = [0] * len(height)
right_max = [0] * len(height)
left_max[0] = height[0]
for i in range(1, len(height)):
left_max[i] = max(left_max[i-1], height[i])
right_max[-1] = height[-1]
for i in range(len(height)-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
ans = sum(min(left_max[i], right_max[i]) - height[i] for i in range(len(height)))
return ans题目18：最小路径和
问题描述：给定一个 m x n 的网格 grid，其中每个单元格都含有非负整数，找到一条从左上角到右下角的路径，使得路径上的数字之和最小。
解题思路：动态规划，更新每个位置的最小路径和。
Python代码示例
def minPathSum(grid):
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
elif i == 0:
grid[i][j] += grid[i][j-1]
elif j == 0:
grid[i][j] += grid[i-1][j]
else:
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]题目19：合并区间
问题描述：给出一系列区间，合并所有重叠的区间。
解题思路：先对区间按照起点进行排序，然后遍历区间，如果当前区间的终点大于等于下一个区间的起点，则需要合并这两个区间。
Python代码示例
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged题目20：二叉树的最近公共祖先
问题描述：给定一棵二叉树，找到两个节点的最近公共祖先。
解题思路：递归，从根节点开始向下查找两个节点，当遇到一个节点时，检查它的左右子树是否同时包含这两个节点。
Python代码示例
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def lowestCommonAncestor(root, p, q):
if root is None or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left is not None and right is not None:
return root
return left if left is not None else right原创文章，作者：guozi，如若转载，请注明出处：https://www.sudun.com/ask/90734.html
