力扣刷题Java

### 关于 LeetCode Java 解题方法及示例代码 #### 常见的 LeetCode Java 题目类型概述 LeetCode 上的 Java 题目涵盖了多种算法和数据结构，主要包括数组、链表、字符串、哈希表、动态规划、回溯法等。这些题目通常会考察基本的数据结构操作以及高级算法的应用能力[^1]。 以下是几个典型的 LeetCode Java 题目及其解决方案： --- #### 示例一：两数之和 (Two Sum) 这是一个经典的入门级问题，目标是从数组中找到两个相加等于特定值 `target` 的索引。 ##### 思路 通过使用 HashMap 来存储已经遍历过的数值及其对应的索引位置，可以有效地减少时间复杂度到 O(n)。 ##### 实现代码 ```java import java.util.HashMap; public class TwoSum { public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } } ``` --- #### 示例二：移除元素 (Remove Element) 此问题是要求删除数组中的指定元素并返回新长度。 ##### 思路 利用双指针技术，在原地修改数组的同时保持空间复杂度为 O(1)，并通过一次遍历来完成任务[^4]。 ##### 实现代码 ```java public class RemoveElement { public int removeElement(int[] nums, int val) { int k = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] != val) { nums[k++] = nums[i]; } } return k; } } ``` --- #### 示例三：组合总和 (Combination Sum) 该问题的目标是找出所有满足条件的不同整数组合，使得它们的和等于目标值。 ##### 思路 采用递归的方式解决这个问题，并结合剪枝优化来提高效率。注意这里的输入保证了不同的组合数量不会超过 150 种[^3]。 ##### 实现代码 ```java import java.util.ArrayList; import java.util.List; public class CombinationSum { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); backtrack(result, new ArrayList<>(), candidates, target, 0); return result; } private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) { if (remain < 0) return; else if (remain == 0) result.add(new ArrayList<>(tempList)); else { for (int i = start; i < candidates.length; i++) { tempList.add(candidates[i]); backtrack(result, tempList, candidates, remain - candidates[i], i); tempList.remove(tempList.size() - 1); } } } } ``` --- #### 示例四：队列的最大值 (Max Queue) 这是另一个涉及设计自定义数据结构的问题，目的是支持快速获取最大值的操作。 ##### 怋想 可以通过维护一个辅助队列来跟踪当前窗口内的最大值，从而达到常数时间内查询的效果[^5]。 ##### 实现代码 ```java class MaxQueue { Deque<Integer> queue; Deque<Integer> maxDeque; public MaxQueue() { this.queue = new LinkedList<>(); this.maxDeque = new LinkedList<>(); } public int max_value() { if (!maxDeque.isEmpty()) { return maxDeque.peekFirst(); } else { return -1; } } public void push_back(int value) { while (!maxDeque.isEmpty() && maxDeque.peekLast() < value) { maxDeque.pollLast(); } maxDeque.offer(value); queue.offer(value); } public int pop_front() { if (queue.isEmpty()) { return -1; } int front = queue.poll(); if (front == maxDeque.peekFirst()) { maxDeque.pollFirst(); } return front; } } ``` --- #### 注意事项 在实际编写代码过程中需要注意细节处理，比如 Map 中键类型的正确选择应为 `Character` 而不是原始类型 `char`，这是因为后者无法自动装箱成对象形式用于集合类容器中[^2]。 此外，熟悉 String 类常用方法如 replace 和其他工具函数也是很有帮助的，尤其是在面对大量字符串相关题目时能够更加得心应手。 ---