Python代码示例:
def twoSum(nums, target):
hashmap = {}
for index, num in enumerate(nums):
complement = target - num
if complement in hashmap:
return [hashmap[complement], index]
hashmap[num] = index
return None题目2：有效的括号
问题描述：给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。
解题思路：栈。遍历字符串，遇到左括号就将其压入栈，遇到右括号则检查栈顶的左括号是否匹配，匹配则弹出栈顶元素，否则返回 False。最后，如果栈为空则说明字符串有效。
Python代码示例:
def isValid(s):
bracket_map = {")": "(", "}": "{", "]": "["}
stack = []
for char in s:
if char in bracket_map:
top_element = stack.pop() if stack else '#'
if bracket_map[char] != top_element:
return False
else:
stack.append(char)
return not stack题目3：无重复字符的最长子串
问题描述：给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
解题思路：滑动窗口。使用双指针定义一个窗口，不断向右扩展窗口直到遇到重复字符，此时窗口左边界向右移动一位，同时更新最长子串的长度。
Python代码示例:
def lengthOfLongestSubstring(s):
char_index_map = {}
left = 0
max_length = 0
for right, char in enumerate(s):
if char in char_index_map and char_index_map[char] >= left:
left = char_index_map[char] + 1
char_index_map[char] = right
max_length = max(max_length, right - left + 1)
return max_length题目4：寻找两个正序数组的中位数
问题描述：给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2。请你找出这两个正序数组的中位数。
解题思路：二分查找。合并两个数组会超时，故采用二分查找思想在较小的数组中寻找合适的分割点，使得左边部分的元素数量等于右边部分，从而找到中位数。
Python代码示例:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
x, y = len(nums1), len(nums2)
low = 0
high = x
while low <= high:
partitionX = (low + high) // 2
partitionY = (x + y + 1) // 2 - partitionX
maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
minRightX = float('inf') if partitionX == x else nums1[partitionX]
maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
minRightY = float('inf') if partitionY == y else nums2[partitionY]
if maxLeftX <= minRightY and maxLeftY <= minRightX:
if (x + y) % 2 == 0:
return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
else:
return max(maxLeftX, maxLeftY)
elif maxLeftX > minRightY:
high = partitionX - 1
else:
low = partitionX + 1
return 0题目5：最长回文子串
问题描述：给定一个字符串 s，找到这个字符串中最长的回文子串。
解题思路：动态规划或中心扩散法。动态规划方法中，定义一个二维数组 dp，其中 dp[i][j] 表示字符串区间 [i, j] 是否为回文串。中心扩散法则从每个字符出发，向两边扩展，记录最长的回文子串。
Python代码示例（动态规划法）:
def longestPalindrome(s):
if not s:
return ""
n = len(s)
dp = [[False]*n for _ in range(n)]
start = 0
maxLength = 1
for i in range(n):
dp[i][i] = True
for L in range(2, n+1):
for i in range(n-L+1):
j = i + L - 1
if s[i] == s[j] and (L == 2 or dp[i+1][j-1]):
dp[i][j] = True
if L > maxLength:
maxLength = L
start = i
return s[start:start+maxLength]题目6：岛屿数量
问题描述：给定一个二维网格地图，用字符 ‘1’ 表示陆地，’0′ 表示水域，请计算网格中岛屿的数量。岛屿是由水平或垂直相邻的陆地组成的，并且相邻的陆地不能通过水域相连接。
解题思路：深度优先搜索（DFS）或广度优先搜索（BFS）。遍历整个网格，遇到陆地（’1’）时，进行深度或广度优先遍历，将访问过的陆地标记为已访问（例如标记为’0’），以避免重复计数。
Python代码示例（DFS）:
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] = '0'
dfs(grid, i + 1, j)
dfs(grid, i - 1, j)
dfs(grid, i, j + 1)
dfs(grid, i, j - 1)
def numIslands(grid):
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题目7：合并区间
问题描述：给定一个区间的列表，请合并所有重叠的区间。
解题思路：排序 + 贪心。首先按照区间的起始位置对所有区间进行排序，然后遍历排序后的区间列表，对于每个区间，如果它与上一个区间重叠，则合并这两个区间，否则将当前区间加入结果列表。
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题目8：括号生成
问题描述：给定一个整数 n，生成所有可能的由 n 对括号组成的合法组合。
解题思路：回溯算法。通过递归生成所有可能的组合，同时保证在任何时候左括号的数量都不小于右括号的数量，以保证生成的括号组合是合法的。
Python代码示例:
def generateParenthesis(n):
def backtrack(S='', left=0, right=0):
if len(S) == 2*n:
res.append(S)
return
if left < n:
backtrack(S+'(', left+1, right)
if right < left:
backtrack(S+')', left, right+1)
res = []
backtrack()
return res题目9：最接近的三数之和
问题描述：给定一个包括 n 个整数的数组 nums 和一个目标值 target，找出 nums 中和为目标值的那三个整数，返回这三个数的和。你可以假设每个输入都只有一个答案，且同样的元素不能被重复利用。
解题思路：排序 + 双指针。首先对数组进行排序，然后遍历数组，对于每个元素，使用双指针找到剩下元素中和最接近 target 的两个元素。
Python代码示例:
def threeSumClosest(nums, target):
nums.sort()
closest = sum(nums[:3])
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
while left < right:
cur_sum = nums[i] + nums[left] + nums[right]
if abs(cur_sum - target) < abs(closest - target):
closest = cur_sum
if cur_sum < target:
left += 1
elif cur_sum > target:
right -= 1
else:
return closest
return closest题目10：跳跃游戏
问题描述：给定一个非负整数数组，你最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
解题思路：贪心算法。维护一个可达到的最大位置，每次更新这个最大位置，如果这个最大位置能覆盖数组的最后一个位置，则可以到达终点。
Python代码示例:
def canJump(nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1:
return True
return False题目11：最长公共前缀
问题描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
解题思路：横向扫描。比较字符串数组中每个字符串的对应字符，逐步缩小公共前缀的候选范围。
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题目12：有效的括号
问题描述：给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。
解题思路：栈。遍历字符串，遇到左括号入栈，遇到右括号检查栈顶元素是否匹配，匹配则弹出栈顶元素，不匹配或栈为空则字符串无效。
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题目13：二叉树的最大深度
问题描述：给定一个二叉树，找出其最大深度。二叉树的深度是指从根节点到最远叶子节点的最长路径上的节点数。
解题思路：递归。递归计算左右子树的最大深度，然后取较大者加一。
Python代码示例（假设已定义好TreeNode类）:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if not root:
return 0
else:
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1题目14：反转链表
问题描述：给你单链表的头节点 head ，反转链表，并返回反转后的链表。
解题思路：迭代或递归。迭代法中，使用三个指针（prev、curr、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题目15：最长连续序列
问题描述：给定一个未排序的整数数组 nums ，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。
解题思路：哈希表。遍历数组，对于每个元素，检查其减一的元素是否存在，若不存在，则以其为起点开始新的连续序列计数，同时更新全局最长连续序列长度。
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题目16：最大子序和
问题描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。
解题思路：动态规划。使用一个变量 current_sum 来追踪当前子数组的和，另一个变量 max_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题目17：合并K个排序链表
问题描述：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
解题思路：分治法/优先队列。可以用优先队列（小顶堆）存储链表的头节点，每次从堆中取出当前最小的节点，然后把该节点的下一个节点加入堆中，直到堆为空。
Python代码示例（使用优先队列）:
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
dummy = ListNode()
current = dummy
heap = []
for head in lists:
if head:
heapq.heappush(heap, (head.val, head))
while heap:
val, node = heapq.heappop(heap)
current.next = ListNode(val)
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, node.next))
return dummy.next题目18：四数之和
问题描述：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
解题思路：排序 + 四指针。首先对数组进行排序，然后使用四个指针遍历和调整，类似于三数之和的扩展。
Python代码示例:
def fourSum(nums, target):
nums.sort()
n = len(nums)
result = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left, right = j + 1, n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
result.append([nums[i], nums[j], 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 result题目19：二叉搜索树的最近公共祖先
问题描述：给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。
解题思路：二叉搜索树特性。由于二叉搜索树的特性（左子树所有节点小于根，右子树所有节点大于根），可以从根节点开始，根据两个节点值与当前节点值的关系，决定是在左子树还是右子树中继续查找。
Python代码示例:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def lowestCommonAncestor(root, p, q):
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
return None题目20：滑动窗口最大值
问题描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
解题思路：双端队列。维护一个单调递减的双端队列，队列中存放的是数组的索引，队首元素始终是当前窗口内的最大值。
Python代码示例:
from collections import deque
def maxSlidingWindow(nums, k):
deq = deque()
result = []
for i in range(len(nums)):
while deq and nums[i] > nums[deq[-1]]:
deq.pop()
deq.append(i)
if i >= k - 1:
result.append(nums[deq[0]])
if deq[0] == i - k + 1:
deq.popleft()
return result原创文章，作者：guozi，如若转载，请注明出处：https://www.sudun.com/ask/88105.html
