题目1：两数之和
问题描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
解题思路：哈希表。遍历数组，对于每个元素，检查哈希表中是否存在目标值与当前元素的差值，如果存在则返回两个下标，否则将当前元素存入哈希表。
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：有效的括号
问题描述：给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。
解题思路：栈。遍历字符串，遇到左括号入栈，遇到右括号检查栈顶元素是否匹配，如果匹配则弹出栈顶元素，否则返回 false。
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 ""
shortest = min(strs, key=len)
for i, char in enumerate(shortest):
for other in strs:
if other[i] != char:
return shortest[:i]
return shortest题目4：二叉树的前序遍历
问题描述：给定一个二叉树的根节点，返回它的前序遍历。
解题思路：递归。按照“根->左子树->右子树”的顺序遍历二叉树，将遍历到的节点值加入结果列表。
Python代码示例:
# 假设 TreeNode 类已经定义
def preorderTraversal(root):
def dfs(node):
if node:
result.append(node.val)
dfs(node.left)
dfs(node.right)
result = []
dfs(root)
return result题目5：跳跃游戏
问题描述：给定一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
解题思路：贪心算法。维护一个可到达的最远位置，每次更新这个最远位置，如果这个最远位置能覆盖数组的最后一个位置，则可以到达终点。
Python代码示例:
def canJump(nums):
max_pos = 0
for i, jump in enumerate(nums):
if i > max_pos:
return False
max_pos = max(max_pos, i + jump)
return True题目6：反转链表
问题描述：给定一个单链表的头节点 head ，反转链表并返回新的头节点。
解题思路：迭代。使用三个指针 prev、curr 和 next，分别指向当前节点的前一个节点、当前节点和当前节点的下一个节点。在遍历过程中，不断更新这三个指针的位置，将当前节点的 next 指向前一个节点，实现链表的反转。
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题目7：二叉树的层次遍历
问题描述：给定一个二叉树的根节点，返回其按层次顺序遍历的结果，同一层的节点按照从左到右的顺序收集。
解题思路：广度优先搜索（BFS）。使用队列来存储每一层的节点，依次处理每一层的节点并将其子节点加入队列。
Python代码示例:
# 假设 TreeNode 类已经定义
def levelOrder(root):
if not root:
return []
queue, result = [root], []
while queue:
temp = []
for _ in range(len(queue)):
node = queue.pop(0)
temp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(temp)
return result题目8：字母异位词分组
问题描述：给定一个字符串数组，将属于同一字母异位词的字符串分组。
解题思路：哈希表。对于每一个字符串，将其排序后作为键，原字符串作为值存储在字典中，最终返回字典的所有值。
Python代码示例:
def groupAnagrams(strs):
from collections import defaultdict
ans = defaultdict(list)
for s in strs:
ans[tuple(sorted(s))].append(s)
return list(ans.values())题目9：文本左右对齐
问题描述：给定一个单词数组 words 和一个长度 maxWidth，重新排版单词，使得每行恰好有 maxWidth 个字符，且除最后一行外，每行都达到左右对齐的效果。
解题思路：模拟。按行处理，对于每行，计算单词间需要的空格总数，然后分配给单词间。
Python代码示例:
def fullJustify(words, maxWidth):
def justify(words, width):
if len(words) == 1:
return words[0] + ' ' * (width - len(words[0]))
spaces = width - sum(len(word) for word in words)
gaps = len(words) - 1
avg_spaces, extra_spaces = divmod(spaces, gaps)
line = ''
for i, word in enumerate(words):
line += word + ' ' * (avg_spaces + (1 if i < extra_spaces else 0))
return line.rstrip()
lines = []
current_line = []
current_width = 0
for word in words:
if current_width + len(word) + len(current_line) > maxWidth:
lines.append(justify(current_line, maxWidth))
current_line = []
current_width = 0
current_line.append(word)
current_width += len(word)
last_line = ' '.join(current_line).ljust(maxWidth)
lines.append(last_line)
return lines题目10：旋转图像
问题描述：给定一个 n×n 的二维矩阵表示一个图像，将图像顺时针旋转 90 度。
解题思路：原地旋转。先将矩阵转置，再翻转每一行，即可实现顺时针旋转 90 度。
Python代码示例:
def rotate(matrix):
n = len(matrix)
# Transpose the matrix
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse each row
for i in range(n):
matrix[i].reverse()
return matrix题目11：最小路径和
问题描述：给定一个 m x n 的网格 grid ，每个单元格中都有非负整数。从左上角开始，每一步只能向下或向右移动，找到一条路径使得路径上的数字之和最小，并返回这个最小的和。
解题思路：动态规划。创建一个与 grid 同样大小的 dp 数组，dp[i][j] 表示从 (0,0) 到达 (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]题目12：乘积小于 K 的子数组
问题描述：给定一个正整数数组 nums 和一个整数 k ，返回 nums 中乘积小于 k 的连续子数组的个数。
解题思路：滑动窗口。使用一个窗口，窗口内元素的乘积小于 k，当乘积大于等于 k 时，窗口左端向右移动，减少乘积。
Python代码示例:
def numSubarrayProductLessThanK(nums, k):
if k <= 1:
return 0
prod = 1
ans = left = 0
for right, val in enumerate(nums):
prod *= val
while prod >= k:
prod /= nums[left]
left += 1
ans += right - left + 1
return ans题目13：平衡二叉树
问题描述：给定一个二叉树，判断它是否是一个高度平衡的二叉树。高度平衡二叉树定义为：任意一个节点的两个子树的高度差不超过 1。
解题思路：自底向上递归。递归计算每个节点的左右子树高度，如果左右子树高度差超过 1 或者任一子树不是平衡的，则该节点也不是平衡的。
Python代码示例:
# 假设 TreeNode 类已经定义
def isBalanced(root):
def check(root):
if not root:
return 0
left = check(root.left)
right = check(root.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return 1 + max(left, right)
return check(root) != -1题目14：二进制手表
问题描述：二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。给出一个非负整数 n ，表示当前 LED 亮着的数量，返回所有可能的时间。
解题思路：枚举。枚举所有可能的时间组合，统计小时和分钟 LED 亮着的数量是否等于 n。
Python代码示例:
def readBinaryWatch(num):
def countBits(n):
return bin(n).count('1')
times = []
for h in range(12):
for m in range(60):
if countBits(h) + countBits(m) == num:
times.append(f'{h}:{m:02d}')
return times题目15：删除链表的倒数第 N 个结点
问题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
解题思路：双指针。使用快慢两个指针，快指针先走 n 步，然后两个指针同时移动，当快指针到达链表尾部时，慢指针指向待删除节点的前一个节点。
Python代码示例:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
first = head
second = dummy
for i in range(n):
first = first.next
while first:
first = first.next
second = second.next
second.next = second.next.next
return dummy.next题目16：搜索旋转排序数组
问题描述：假设你有一个数组，它最初是升序排序的，但在某个未知的转折点处被旋转了。例如，数组 [0,1,2,4,5,6,7] 可能在未知的转折点处被旋转成 [4,5,6,7,0,1,2]。给定这样的一个数组 nums 和一个目标值 target ，写一个函数来判断 target 是否存在于 nums 中。
解题思路：二分查找。由于数组是旋转后的升序数组，可以通过比较中间值和两端值的关系来确定 target 可能存在的那一半。
Python代码示例:
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[mid] >= nums[left]:
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 False题目17：二叉树的直径
问题描述：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
解题思路：深度优先搜索。在递归求解节点深度的过程中，更新路径长度的最大值。
Python代码示例:
# 假设 TreeNode 类已经定义
class Solution:
def diameterOfBinaryTree(self, root):
self.ans = 0
def depth(p):
if not p:
return 0
left, right = depth(p.left), depth(p.right)
self.ans = max(self.ans, left + right)
return 1 + max(left, right)
depth(root)
return self.ans题目18：单词接龙
问题描述：给定两个单词 beginWord 和 endWord，以及一个单词列表 wordList。找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须在字典 wordList 中。
解题思路：广度优先搜索。从 beginWord 开始，将所有可以通过一次变换得到的单词加入队列，直到找到 endWord。
Python代码示例:
from collections import deque
def ladderLength(beginWord, endWord, wordList):
wordList = set(wordList)
queue = deque([(beginWord, 1)])
while queue:
word, length = queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in wordList:
wordList.remove(next_word)
queue.append((next_word, length + 1))
return 0题目19：接雨水
问题描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解题思路：动态规划。维护两个数组 left_max 和 right_max，分别表示当前位置左侧和右侧的最大高度，最后遍历数组，对于每个位置 i，能接的雨水量等于 min(left_max[i], right_max[i]) – height[i]。
Python代码示例:
def trap(height):
if not height:
return 0
left_max, right_max = [0] * len(height), [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])
return sum(min(left_max[i], right_max[i]) - height[i] for i in range(len(height)))题目20：课程表 II
问题描述：现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1] 。给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
解题思路：拓扑排序。使用入度数组和队列实现拓扑排序，如果可以完成所有课程，则队列最终会包含所有节点。
Python代码示例:
from collections import deque
def findOrder(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
indegrees = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegrees[course] += 1
queue = deque([i for i in range(numCourses) if indegrees[i] == 0])
order = []
while queue:
course = queue.popleft()
order.append(course)
for next_course in graph[course]:
indegrees[next_course] -= 1
if indegrees[next_course] == 0:
queue.append(next_course)
return order if len(order) == numCourses else []原创文章，作者：guozi，如若转载，请注明出处：https://www.sudun.com/ask/87955.html
