以下是十个经典的算法题及其解析，适用于Java、C和Python。这些题目涵盖了基础数据结构、排序、搜索及其他常用算法。

1. 反转链表

   • 问题描述：给定一个单链表，反转链表并输出新链表的头结点。
   • 解析：使用三个指针遍历链表，一个指针指向当前节点，一个指向前一个节点，一个指向下一个节点，逐步反转链表链接。

   • Python示例：

     class ListNode:  
      def __init__(self, val=0, next=None):  
          self.val = val  
          self.next = next  
     def reverseList(head: ListNode) -> ListNode:  
      prev = None  
      current = head  
      while current:  
          next_node = current.next  
          current.next = prev  
          prev = current  
          current = next_node  
      return prev  

2. 二分查找

   • 问题描述：在一个有序数组中查找某个元素的索引。
   • 解析：通过对数组进行分割，逐步缩小搜索范围直至找到目标元素。
   • Java示例：
     public int binarySearch(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }

3. 常见排序算法：快速排序

   • 问题描述：实现快速排序。
   • 解析：选择一个基准元素，通过分区过程将小于基准的元素放在左边，大于基准的元素放在右边，然后递归地对两个分区进行排序。

   • C示例：

     void quickSort(int* arr, int low, int high) {  
      if (low < high) {  
          int pi = partition(arr, low, high);  
          quickSort(arr, low, pi - 1);  
          quickSort(arr, pi + 1, high);  
      }  
     }  
     int partition(int* arr, int low, int high) {  
      int pivot = arr[high];  
      int i = (low - 1);  
      for (int j = low; j <= high - 1; j++) {  
          if (arr[j] < pivot) {  
              i++;  
              swap(&arr[i], &arr[j]);  
          }  
      }  
      swap(&arr[i + 1], &arr[high]);  
      return (i + 1);  
     }  
     void swap(int* a, int* b) {  
      int t = *a;  
      *a = *b;  
      *b = t;  
     }  

4. 合并两个有序数组

   • 问题描述：将两个升序排列的数组合并为一个新的升序数组。
   • 解析：使用双指针遍历，同时比较两个数组的元素，将较小的元素加入新的数组中。
   • Python示例：
     def merge(nums1, m, nums2, n): p1, p2, p = m - 1, n - 1, m + n - 1 while p1 >= 0 and p2 >= 0: if nums1[p1] < nums2[p2]: nums1[p] = nums2[p2] p2 -= 1 else: nums1[p] = nums1[p1] p1 -= 1 p -= 1 nums1[:p2 + 1] = nums2[:p2 + 1]

5. 寻找字符串中的最长无重复子串

   • 问题描述：找到一个字符串中最长的无重复字符的子串。
   • 解析：使用滑动窗口技巧维护一个窗口来记录当前子串及其长度。
   • Java示例：
     public int lengthOfLongestSubstring(String s) { int[] index = new int[128]; int maxLength = 0; for (int i = 0, j = 0; j < s.length(); j++) { i = Math.max(index[s.charAt(j)], i); maxLength = Math.max(maxLength, j - i + 1); index[s.charAt(j)] = j + 1; } return maxLength; }

6. 判断括号有效性

   • 问题描述：判断一个包含()、{}、[]三种括号的字符串是否有效。
   • 解析：使用栈数据结构将左括号压入栈中，当遇到右括号时检查匹配。
   • C示例：
     bool isValid(char * s) { char stack[10000]; int top = -1; for (int i = 0; s[i] != '\0'; i++) { char c = s[i]; if (c == '(' || c == '{' || c == '[') { stack[++top] = c; } else { if (top == -1) return false; char pop = stack[top--]; if ((c == ')' && pop != '(') || (c == '}' && pop != '{') || (c == ']' && pop != '[')) { return false; } } } return top == -1; }

7. 合并区间

   • 问题描述：给定多个区间，合并所有重叠的区间。
   • 解析：先按区间起始位置排序，然后迭代合并重叠区间。
   • 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

8. 找出第一个缺失的正整数

   • 问题描述：给定一个未排序的整数数组，找出其中没有出现的最小正整数。
   • 解析：使用置换的方法将每个整数放到对应索引上，然后检测哪个索引没有正确的整数。
   • Python示例：
     def firstMissingPositive(nums): n = len(nums) for i in range(n): while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1

9. 在排序数组中查找元素的第一个和最后一个位置

   • 问题描述：找到一个排序数组中给定元素的起始和结束位置。
   • 解析：使用二分查找分别查找第一个和最后一个位置。

   • Java示例：

     public int[] searchRange(int[] nums, int target) {  
      int[] result = {-1, -1};  
      result[0] = findFirst(nums, target);  
      result[1] = findLast(nums, target);  
      return result;  
     }  
     private int findFirst(int[] nums, int target) {  
      int index = -1, left = 0, right = nums.length - 1;  
      while (left <= right) {  
          int mid = left + (right - left) / 2;  
          if (nums[mid] >= target) right = mid - 1;  
          else left = mid + 1;  
          if (nums[mid] == target) index = mid;  
      }  
      return index;  
     }  
     private int findLast(int[] nums, int target) {  
      int index = -1, left = 0, right = nums.length - 1;  
      while (left <= right) {  
          int mid = left + (right - left) / 2;  
          if (nums[mid] <= target) left = mid + 1;  
          else right = mid - 1;  
          if (nums[mid] == target) index = mid;  
      }  
      return index;  
     }  

10. 爬楼梯问题

    • 问题描述：你正在爬楼梯。需要n阶你才能到达楼顶。每次可以爬1或2阶，有多少种不同的方法可以爬到楼顶？
    • 解析：这相当于斐波那契数列的变种问题。使用动态规划或递归来解决。
    • Python示例：
      def climbStairs(n): if n <= 2: return n first, second = 1, 2 for i in range(3, n + 1): first, second = second, first + second return second

通过这些经典算法题的练习，可以掌握许多常见的算法技巧和思路，为解决更复杂的问题打下基础。