算法刷题总结

**算法刷题总结**

作为一个程序员，算法刷题是我们每天的必修课。通过刷题，我们不仅可以提高编程能力，还能锻炼逻辑思维、问题解决等能力。然而，很多人在刷题时可能会遇到一些困难，例如如何选择合适的数据结构、如何优化算法效率等。在本文中，我们将总结一些常见的算法刷题类型和对应的解决方案。

**一、数组相关问题**

###1.1 查找给定值在数组中的位置* **描述**: 给定一个有序数组和一个目标值，要求找到该值在数组中的索引。
* **示例代码**:

def search(nums, target):
 left, right =0, len(nums) -1 while left <= right:
 mid = (left + right) //2 if nums[mid] == target:
 return mid elif nums[mid] < target:
 left = mid +1 else:
 right = mid -1 return -1# 测试用例nums = [1,3,5,7,9]
target =5print(search(nums, target)) # 输出:2

###1.2 移除数组中的重复元素* **描述**: 给定一个有序数组，要求移除其中的重复元素。
* **示例代码**:

def removeDuplicates(nums):
 if not nums:
 return0 i =0 for j in range(1, len(nums)):
 if nums[j] != nums[i]:
 i +=1 nums[i], nums[j] = nums[j], nums[i]
 return i +1# 测试用例nums = [1,2,3,4,5,6,7,8,9]
print(removeDuplicates(nums)) # 输出:9

###1.3 最长连续子序列* **描述**: 给定一个有序数组，要求找到其中最长的连续子序列。
* **示例代码**:

def longestConsecutive(nums):
 if not nums:
 return0 num_set = set(nums)
 max_length =0 for num in num_set:
 if num -1 not in num_set: # 如果当前数字是连续序列的第一个数字 current_num = num current_length =1 while current_num +1 in num_set: # 找到该连续序列的长度 current_num +=1 current_length +=1 max_length = max(max_length, current_length)
 return max_length# 测试用例nums = [1,9,3,10,4,20,2]
print(longestConsecutive(nums)) # 输出:5

**二、链表相关问题**

###2.1 合并两个有序链表* **描述**: 给定两个有序链表，要求合并成一个新的有序链表。
* **示例代码**:

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef mergeTwoLists(l1, l2):
 dummy = ListNode(0)
 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# 测试用例l1 = ListNode(1)
l1.next = ListNode(3)
l1.next.next = ListNode(5)

l2 = ListNode(2)
l2.next = ListNode(4)
l2.next.next = ListNode(6)

print(mergeTwoLists(l1, l2)) # 输出: [1,2,3,4,5,6]

###2.2 删除链表中的重复元素* **描述**: 给定一个有序链表，要求删除其中的重复元素。
* **示例代码**:

def deleteDuplicates(head):
 dummy = ListNode(0)
 current = dummy while head:
 if not (head.next and head.val == head.next.val): # 如果当前数字不是连续序列的第一个数字 current.next = head current = current.next head = head.next current.next = None return dummy.next# 测试用例l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(3)
l1.next.next.next = ListNode(4)

print(deleteDuplicates(l1)) # 输出: [1,3]

###2.3 最长回文链表* **描述**: 给定一个有序链表，要求找到其中最长的回文子链表。
* **示例代码**:

def longestPalindrome(head):
 def isPalindrome(node, length):
 if length < 2:
 return True elif length ==2:
 return node.val == node.next.val else:
 return (node.val == node.next.val and isPalindrome(node.next.next, length -2))

 slow = fast = head while fast and fast.next:
 slow = slow.next fast = fast.next.next if isPalindrome(head, slow.val):
 return True else:
 return False# 测试用例l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(3)

print(longestPalindrome(l1)) # 输出: False

**三、树相关问题**

###3.1 最小深度二叉树* **描述**: 给定一个有序链表，要求找到其中最小的深度二叉树。
* **示例代码**:

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef minDepth(root):
 if not root:
 return0 elif not root.left and not root.right:
 return1 else:
 left_depth = minDepth(root.left)
 right_depth = minDepth(root.right)
 return min(left_depth, right_depth) +1# 测试用例root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(minDepth(root)) # 输出:2

###3.2 最大深度二叉树* **描述**: 给定一个有序链表，要求找到其中最大深度二叉树。
* **示例代码**:

def maxDepth(root):
 if not root:
 return0 elif not root.left and not root.right:
 return1 else:
 left_depth = maxDepth(root.left)
 right_depth = maxDepth(root.right)
 return max(left_depth, right_depth) +1# 测试用例root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(maxDepth(root)) # 输出:4

###3.3 最大路径和* **描述**: 给定一个有序链表，要求找到其中最大路径和。
* **示例代码**:

def maxPathSum(root):
 def max_gain(node):
 nonlocal max_sum if not node:
 return0 left_gain = max(max_gain(node.left),0)
 right_gain = max(max_gain(node.right),0)
 price_newpath = node.val + left_gain + right_gain max_sum = max(max_sum, price_newpath)
 return node.val + max(left_gain, right_gain)

 max_sum = float('-inf')
 max_gain(root)
 return max_sum# 测试用例root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

print(maxPathSum(root)) # 输出:6

**四、图相关问题**

###4.1 最短路径* **描述**: 给定一个有序链表，要求找到其中最短的路径。
* **示例代码**:

from collections import dequedef shortestPath(grid, start, end):
 rows, cols = len(grid), len(grid[0])
 directions = [(0,1), (0, -