问题描述：给定一个整数数组 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：反转字符串
问题描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组形式给出。
解题思路：双指针法。设置两个指针分别指向字符串的首尾，交换两指针对应的字符，直到两指针相遇。
Python代码示例:
def reverseString(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right - 1
return s题目3：无重复字符的最长子串
问题描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
解题思路：滑动窗口。使用两个指针定义一个窗口，不断移动右指针扩大窗口，同时用哈希表记录窗口内字符出现情况，当窗口内有重复字符时，移动左指针缩小窗口。
Python代码示例:
def lengthOfLongestSubstring(s):
char_map = {}
left, max_len = 0, 0
for right, char in enumerate(s):
if char in char_map and char_map[char] >= left:
left = char_map[char] + 1
char_map[char] = right
max_len = max(max_len, right - left + 1)
return max_len题目4：合并两个有序链表
问题描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：迭代或递归。迭代法中，创建一个哑节点作为新链表的头，然后比较两个链表的节点值，将较小的节点接到新链表上，直到一个链表为空，再将另一个链表剩下的部分接到新链表后面。
Python代码示例:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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：最长公共前缀
问题描述：编写一个函数来查找字符串数组中的最长公共前缀。
解题思路：水平扫描。依次比较每个字符串同一位置的字符，直到找到第一个不匹配的字符或遍历完最短的字符串。
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]
return prefix题目6：跳跃游戏
问题描述：给定一个非负整数数组，你最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
解题思路：贪心算法。维护一个变量来跟踪当前能到达的最远位置，逐步向前推进。
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题目7：最长递增子序列
问题描述：给定一个无序的整数数组，找到其中最长递增子序列的长度。
解题思路：动态规划。维护一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
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)题目8：合并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题目9：回文链表
问题描述：判断一个链表是否是回文链表。
解题思路：快慢指针找到中点，然后反转后半部分链表，最后比较前后两半是否相等。
Python代码示例:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second_half = reverseList(slow)
first_half_iter = head
while second_half:
if first_half_iter.val != second_half.val:
return False
first_half_iter = first_half_iter.next
second_half = second_half.next
return True
def reverseList(head):
prev, curr = None, head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev题目10：最长连续序列
问题描述：给定一个未排序的整数数组，找出最长连续序列的长度。
解题思路：哈希表。遍历数组，使用哈希表记录每个数字出现的情况，然后检查每个数字的连续性。
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题目11：岛屿数量
问题描述：给定一个二维网格地图，’1′ 表示陆地，’0′ 表示水域，计算岛屿的数量。一个岛屿是由四面相连的陆地组成，水平或垂直相邻。
解题思路：深度优先搜索（DFS）。遍历网格，遇到陆地（’1’）时，进行DFS标记已访问过的陆地为水域，以避免重复计数。
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题目12：括号生成
问题描述：给定一个整数 n，生成所有可能的由 n 对括号组成的合法组合。
解题思路：回溯算法。递归生成括号序列，每次添加左括号或右括号时确保序列保持合法性（左括号数量大于等于右括号数量）。
Python代码示例:
def generateParenthesis(n):
def backtrack(left, right, path, res):
if left == right == 0:
res.append(path)
return
if left > 0:
backtrack(left - 1, right, path + '(', res)
if right > left:
backtrack(left, right - 1, path + ')', res)
res = []
backtrack(n, n, '', res)
return res题目13：子集
问题描述：给定一个整数数组 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 = []
nums.sort()
backtrack(0, [])
return res题目14：最接近的三数之和
问题描述：给定一个包括 n 个整数的数组 nums 和一个目标值 target，找出 nums 中和为目标值的那三个整数，返回这三个数的和。你可以假设每组输入只对应唯一的解，且同样的元素不能被重复利用。
解题思路：排序 + 双指针。首先对数组进行排序，然后遍历数组，固定一个数，使用双指针对剩下的数进行搜索，找到最接近目标值的三数之和。
Python代码示例:
def threeSumClosest(nums, target):
nums.sort()
closest_sum = float('inf')
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if abs(target - current_sum) < abs(target - closest_sum):
closest_sum = current_sum
if current_sum < target:
left += 1
else:
right -= 1
return closest_sum题目15：最大子序和
问题描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解题思路：动态规划。使用一个变量记录当前子数组的最大和以及全局最大和，遍历数组更新这两个值。
Python代码示例:
def maxSubArray(nums):
current_max = global_max = nums[0]
for num in nums[1:]:
current_max = max(num, current_max + num)
global_max = max(global_max, current_max)
return global_max题目16：合并两个有序链表
问题描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：迭代或递归。创建一个哑节点作为新链表的起点，比较两个链表的节点值，将较小的节点接到新链表上，然后移动对应链表的指针。
Python代码示例（迭代法）:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next题目17：二叉树的最近公共祖先
问题描述：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
解题思路：从根节点开始递归，如果当前节点是p或q中的任意一个，或者当前节点的左右子树分别包含了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)题目18：最长公共前缀
问题描述：编写一个函数来查找字符串数组中的最长公共前缀。
解题思路：横向扫描。比较字符串数组中每个字符串的相同位置字符，直到出现不匹配为止。
Python代码示例:
def longestCommonPrefix(strs):
if not strs:
return ""
prefix, count = strs[0], len(strs)
for i in range(1, count):
prefix = prefix[:min(len(prefix), len(strs[i]))]
for j in range(len(prefix)):
if prefix[j] != strs[i][j]:
prefix = prefix[:j]
break
if not prefix:
break
return prefix题目19：多数元素
问题描述：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 n/2 的元素。
解题思路：摩尔投票法。维护一个候选元素及其计数，遍历数组，如果遇到与候选元素相同的就增加计数，不同则减少计数。当计数为0时，更换候选元素。
Python代码示例:
def majorityElement(nums):
candidate, count = 0, 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate题目20：ZigZag Conversion
问题描述：将一个给定字符串根据给定的行数，以从上往下、从左到右的方式 ZigZag 地排列成新的字符串。
解题思路：模拟。按行构建结果字符串，注意当到达每一行的边界时改变方向。
原创文章，作者：guozi，如若转载，请注明出处：https://www.sudun.com/ask/78960.html
