Python代码示例:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
carry = 0
dummy_head = ListNode(0)
current = dummy_head
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
carry, out = divmod(val1 + val2 + carry, 10)
current.next = ListNode(out)
current = current.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy_head.next题目2：二叉树的锯齿形层次遍历
问题描述：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历）
解题思路：使用队列进行层次遍历，每遍历完一层，判断是否需要反转这一层的顺序。
Python代码示例:
# 假设 TreeNode 类已经定义
def zigzagLevelOrder(root):
if not root:
return []
result, queue, flag = [], deque([root]), 1
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level[::flag])
flag *= -1
return result题目3：岛屿数量
问题描述：给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
解题思路：深度优先搜索（DFS）。遍历整个网格，遇到陆地就进行一次深度优先搜索，标记访问过的陆地，每进行一次搜索就说明发现了一个岛屿。
Python代码示例:
def numIslands(grid):
if not grid:
return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
dfs(grid, i, j)
count += 1
return count
def dfs(grid, i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '#' # Mark as visited
dfs(grid, i + 1, j)
dfs(grid, i - 1, j)
dfs(grid, i, j + 1)
dfs(grid, i, j - 1)题目4：字符串的排列
问题描述：输入一个字符串，打印出该字符串中字符的所有排列。
解题思路：回溯算法。通过交换字符并递归生成所有可能的排列，同时避免重复。
Python代码示例:
def permutation(s):
def backtrack(start):
if start == len(s):
res.append(''.join(s))
for i in range(start, len(s)):
if i > start and s[i] == s[start]: # Skip duplicates
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题目5：有效的字母异位词
问题描述：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
解题思路：使用哈希表或数组记录字符出现次数，对比两个字符串的字符计数是否一致。
Python代码示例:
def isAnagram(s, t):
if len(s) != len(t):
return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
return all(x == 0 for x in count)题目6：旋转数组
问题描述：给定一个数组，将数组中的元素向右移动 k 位，其中 k 是非负数。
解题思路：可以先反转整个数组，再反转前 k 个元素，最后反转剩下的元素。
Python代码示例
def rotate(nums, k):
k %= len(nums)
nums.reverse()
nums[:k] = reversed(nums[:k])
nums[k:] = reversed(nums[k:])题目7：三数之和
问题描述：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
解题思路：先对数组进行排序，然后使用双指针法查找符合条件的三元组。
Python代码示例
def threeSum(nums):
nums.sort()
res = []
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]: continue
left, right = i+1, len(nums)-1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s < 0:
left +=1
elif s > 0:
right -= 1
else:
res.append((nums[i], nums[left], nums[right]))
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1; right -= 1
return res题目8：有效的括号
问题描述：给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
解题思路：使用栈来存储左括号，遇到右括号时检查栈顶元素是否匹配。
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题目9：合并区间
问题描述：给出一个区间的集合，请合并所有重叠的区间。
解题思路：首先按区间起始点排序，然后遍历区间，若当前区间与下一个区间有重叠，则合并；否则直接添加到结果中。
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题目10：子集
问题描述：给定一组不含重复元素的整数数组 nums，返回其所有可能的子集（幂集）。
解题思路：递归生成子集，每次可以选择将当前元素加入或不加入结果子集中。
Python代码示例
def subsets(nums):
def backtrack(start=0, curr=[]):
output.append(curr[:])
for i in range(start, len(nums)):
curr.append(nums[i])
backtrack(i+1, curr)
curr.pop()
output = []
backtrack()
return output题目11：最长公共前缀
问题描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
解题思路：比较字符串数组中的第一个和最后一个字符串，因为最长公共前缀一定在这两个字符串中。逐字符比较，直到不匹配为止。
Python代码示例
def longestCommonPrefix(strs):
if not strs: return ""
first, last = min(strs), max(strs)
for i, char in enumerate(first):
if char != last[i]:
return first[:i]
return first题目12：两数相加
问题描述：给定两个非空链表来表示两个非负的整数。数字最高位位于链表的首位。将它们相加，并以同样的形式返回结果。
解题思路：遍历两个链表同时计算进位，注意处理长度不同的情况。
Python代码示例
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
dummy = ListNode(0)
p, q, current = l1, l2, dummy
carry = 0
while p is not None or q is not None:
x = p.val if p is not None else 0
y = q.val if q is not None else 0
sum = carry + x + y
carry = sum // 10
current.next = ListNode(sum % 10)
current = current.next
if p is not None: p = p.next
if q is not None: q = q.next
if carry > 0:
current.next = ListNode(carry)
return dummy.next题目13：搜索旋转排序数组
问题描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。搜索给定的目标值，如果数组中存在这个目标值，返回它的索引，否则返回 -1。
解题思路：使用二分查找，找到旋转点，然后在适当的部分进行标准的二分查找。
Python代码示例
def search(nums, target):
if not nums: return -1
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
if nums[low] <= nums[mid]:
if nums[low] <= target < nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] < target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1题目14：无重复字符的最长子串
问题描述：给定一个字符串，找到其中没有重复字符的最长子串的长度。
解题思路：使用滑动窗口，记录每个字符最后一次出现的位置，维护窗口内无重复字符。
Python代码示例
def lengthOfLongestSubstring(s):
start = maxLength = 0
usedChar = {}
for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
usedChar[s[i]] = i
return maxLength题目15：最小覆盖子串
问题描述：给定一个字符串 S 和一个字符串 T，找到 S 中包含 T 所有字符的最小子串。
解题思路：使用滑动窗口，统计T中每个字符的数量，然后在S中移动窗口，直到包含T的所有字符，然后尝试缩小窗口。
Python代码示例
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def inorderTraversal(root):
res, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return res
node = stack.pop()
res.append(node.val)
root = node.right
return res题目16：二叉树的层次遍历
问题描述：给定一个二叉树，返回其节点值的层次遍历。从左到右，逐层遍历。
解题思路：使用队列进行广度优先搜索（BFS）。
Python代码示例
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
def levelOrder(root):
if not root: return []
queue, result = deque([root]), []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result题目17：二叉树的中序遍历
问题描述：给定一个二叉树的根节点，返回它的中序遍历。
解题思路：使用递归或栈进行中序遍历。
Python代码示例
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def inorderTraversal(root):
res, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
return res
node = stack.pop()
res.append(node.val)
root = node.right
return res题目18：两数相除
问题描述：实现 int divide(int dividend, int divisor)，要求不得使用乘法、除法和 mod 运算符。
解题思路：使用减法和位移运算。
Python代码示例
def divide(dividend, divisor):
if dividend == -2147483648 and divisor == -1:
return 2147483647
a, b, res = abs(dividend), abs(divisor), 0
for x in range(31, -1, -1):
if (a >> x) - b >= 0:
res += 1 << x
a -= b << x
return res if (dividend > 0) == (divisor > 0) else -res题目19：有效的数独
问题描述：请编写一个函数，验证一个给定的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。
解题思路：使用哈希表记录行、列和宫内的数字。
Python代码示例
def isValidSudoku(board):
rows = [{} for i in range(9)]
columns = [{} for i in range(9)]
boxes = [{} for i in range(9)]
for i in range(9):
for j in range(9):
num = board[i][j]
if num != '.':
box_index = (i // 3) * 3 + j // 3
rows[i][num] = rows[i].get(num, 0) + 1
columns[j][num] = columns[j].get(num, 0) + 1
boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
return False
return True题目20：合并两个有序链表
问题描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：使用递归或迭代方法，比较两个链表的节点值，较小的节点链接到结果链表。
Python代码示例
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
def mergeTwoLists(l1, l2):
if not l1: return l2
if not l2: return l1
if l1.val < l2.val:
l1.next = mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = mergeTwoLists(l1, l2.next)
return l2原创文章，作者：guozi，如若转载，请注明出处：https://www.sudun.com/ask/89362.html
