LeetCode 热题100（JAVA）
LeetCode 热题100（JAVA）
哈希
1. 两数之和
给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，
并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
暴力解法
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; i++) {
//1.避免重复使用同一个元素 2.避免重复计算同一对数
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
/*等同于
int[] arr = new int[2];
arr[0] = i;
arr[1] = j;
return arr;*/
return new int[]{-1, -1};
}
}
HashMap
核心思想：遍历当前元素时，在 HashMap 中查找“我需要的另一个数”是否已经出现过，如果出现过就直接返回答案，否则把当前元素存起来。
目标：nums[i] + nums[j] = target
如果当前数是 x，那我需要找的另一个数是：target - x
HashMap<Integer, Integer>
Key(键)：数组中某个数 Value（值）：这个数的下标
例如：nums = [2, 7, 11, 15]
{2 -> 0}
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
// 创建 HashMap：
// key -> 数组中的值
// value -> 该值对应的下标
HashMap<Integer, Integer> map = new HashMap<>();
// 一次遍历数组，i 是当前元素的下标
for (int i = 0; i < nums.length; i++) {
// 当前遍历到的元素值
int num = nums[i];
// 计算还需要的那个数，使得：
// num + need = target
int need = target - num;
// containsKey：判断 HashMap 中是否已经存在 need
// 如果存在，说明之前遍历过的某个数 + 当前数 = target
if (map.containsKey(need)) {
// 通过 key（need）拿到它对应的下标
int index = map.get(need);
return new int[]{index, i};
}
// 如果没找到需要的数
// 把当前数和它的下标存入 HashMap
// 供后续元素查找
map.put(num, i);
}
return new int[0];
}
}
2.字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
思想：
找分类标准，给每个字符串找一个标识，只要两个字符串的标识一样，它们就应该进同一组。
class Solution{
public List<List<String>> groupAnagrams(String[] strs){
Map<String,List<String>> map = new HashMap<>();
/*遍历
语法结构:for (元素类型 变量名 : 可迭代对象/数组)
不用下标，直接一个个取元素。
*/
for(String str : strs){
//字符串转换为字符数组
char[] chars = str.toCharArry();
Arrays.sort(chars);
//排序后结果作为key "标识"
String key = new String(chars);
//如果这个 key 还没有对应的列表，就先创建
if(!map.containsKey(key)){
map.put(key,new ArrayList<>())
}
map.get(key).add(str);
}
return new ArrayList<>(map.values());
}
}
3.最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：
输入：nums = [1,0,1,2]
输出：3
思想
题目本质：给你一个无序数组，要你找最长的“值连续”的序列长度。不要求数组原位置连续。
解法思路：（1）把所有数组元素放入HashSet中。（2）遍历每个元素。（3）如果数组元素num - 1 不存在，说明它是起点，从这个起点开始不断查 num + 1, num + 2 …（4）统计这一段长度，更新最大值。
class Solution {
public int longestConsecutive(int[] nums) {
// 1. 先把所有数字放进 HashSet，方便 O(1) 查询，同时自动去重
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
// 2. 遍历集合中的每个数字
for (int num : set) {
// 3. 只有当前数字是连续序列起点时，才开始往后扩展
if (!set.contains(num - 1)) {
int currentNum = num;
int currentLen = 1;
// 4. 不断查找下一个连续数字
while (set.contains(currentNum + 1)) {
currentNum++;
currentLen++;
}
// 5. 更新最长长度
maxLen = Math.max(maxLen, currentLen);
}
}
return maxLen;
}
}
双指针
双指针常见有三种
- 左右夹逼型：一个指针在左边，一个指针在右边。每一步根据某种规则，移动左边或右边，让搜索范围不断缩小。
- 快慢指针型：两个指针通常都朝同一个方向移动，但职责不同：fast：负责扫描 / 探路 / 查找，slow：负责写入 / 保留 / 跟踪某种位置。
- 滑动窗口型：维护一个连续区间 [left, right]，让这个区间满足某种条件。就像是用两个指针圈出一个“窗口”，窗口在数组/字符串上滑动。
1. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
思想
题目本质：把所有非零元素稳定的（原来谁在前，最后还得谁在前）压缩到前面，再把后面补 0。
解法思路：使用快慢指针，一个位置负责找元素，一个位置负责放元素。
fast：负责往前扫描，寻找非零元素，扫到一个非零元素，它应该被放到当前最靠前的空位，这个空位就是 slow
slow：负责维护下一个应该填的位置
交换版双指针
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
}
}
}
覆盖版双指针
//先把所有非零元素按顺序覆盖到前面 再把剩余位置补 0
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
// 先把非零元素依次放到前面
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
}
// 剩下的位置补 0
while (slow < nums.length) {
nums[slow] = 0;
slow++;
}
}
}
2.盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i,height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。
输入：[1,8,6,2,5,4,8,3,7] 输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2： 输入：height = [1,1] 输出：1
思想
题目本质：最大水量=面积=长*宽。宽=两数下标距离差值，高=两数中较小的。
解题思路：使用双指针，left、right分别从两边遍历，对比数值较小的进行移动，确保面积达到最大。
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while(left < right){
// 当前宽度
int width = right - left;
// 当前高度
int h = Math.min(height[left], height[right]);
// 当前面积
int area = width * h;
// 更新最大面积
maxArea = Math.max(maxArea, area);
// 移动较矮的一边
if(height[left] < height[right]){
left++;
}else{
right--;
}
}
return maxArea;
}
}
3.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2： 输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3： 输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
思想
题目本质：三数之和为0，并且三数不能重复。
解题思路：排序+固定数+双指针+去重。固定 i,使用双指针left、right。使得两数之和L+R以及i的值相加为0。
移动指针：排序后从小到大，当sum<0时说明两数之和小，L++,sum>0，两数之和大，R- -。
去重：i 去重，防止“第一个数”重复。left/right 去重，防止找到答案后，第二、第三个数重复
import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// 排序
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// 第一个数去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(
nums[i],
nums[left],
nums[right]
));
// left 去重
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// right 去重
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
4.接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
思想
题目本质：计算每个位置能接多少雨水，当前位置接水量由左右两边最高柱子中的较小值决定。
解题思路：双指针 + 记录左右最大高度。定义 left、right，同时维护 leftMax、rightMax。
当前接水量=min(左边最高, 右边最高) - 当前柱子高度。
左右判断：哪边当前柱子更矮，就先处理哪边。因为另一边已经有更高的柱子作为边界，所以当前这一侧能接多少水只需要看这一侧之前的最高柱子。
class Solution {
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int water = 0;
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right--;
}
}
return water;
}
}
滑动窗口
1.无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
思想
题目本质：找一个连续子串，要求里面不能有重复字符，并且长度最大。
解题思路：HashSet（去重）+ 滑动窗口（双指针）。left先固定，right++进行遍历，当有重复值时去掉left再进行left++。
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<>();
int left = 0;
int maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
while (set.contains(c)) {
set.remove(s.charAt(left));
left++;
}
set.add(c);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
2.找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
思想
题目本质：维护一个固定长度的滑动窗口，比较窗口中的字符频率和 p 的字符频率是否一样。
解题思路：双指针固定窗口长度：
右边加入一个字符
左边移除一个字符
窗口始终保持长度 = p.length()
频率对比：用长度 26 的数组建立“字母 → 出现次数”的映射。pCount 记录 p 的字符频率，windowCount 记录当前窗口字符频率；窗口右侧进入字符次数 +1，左侧离开字符次数 -1。最后用 Arrays.equals() 判断 26 个字母的出现次数是否完全相同。
import java.util.*;
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int[] pCount = new int[26];
int[] windowCount = new int[26];
// 统计 p 中每个字符出现次数
for (char c : p.toCharArray()) {
pCount[c - 'a']++;
}
int left = 0;
for (int right = 0; right < s.length(); right++) {
// 右边字符进入窗口
windowCount[s.charAt(right) - 'a']++;
// 如果窗口太大，删除左边字符
if (right - left + 1 > p.length()) {
windowCount[s.charAt(left) - 'a']--;
left++;
}
// 窗口长度等于 p，并且字符次数完全一样
if (right - left + 1 == p.length()
&& Arrays.equals(pCount, windowCount)) {
result.add(left);
}
}
return result;
}
}
字串
1.和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
思路
题目本质：统计连续子数组的和是否等于 k
解题思路：子数组的和 = 后面的前缀和 - 前面的前缀和
前缀和：记录到当前位置的总和
HashMap：保存历史前缀和出现次数
找 k：看以前有没有 sum-k，判断没有子数组和为K
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
// 前缀和为0出现一次
map.put(0,1);
int sum = 0;
int count = 0;
for(int num : nums){
// 当前前缀和
sum += num;
// 查找之前是否存在 sum-k
if(map.containsKey(sum-k)){
count += map.get(sum-k);
}
// 保存当前前缀和
map.put(sum, map.getOrDefault(sum,0)+1);
}
return count;
}
}
2.滑动窗口最大值
思路
题目本质：求每个固定大小窗口中的最大值。
解题思路：滑动窗口 + 单调队列。使用 Deque 保存窗口中可能成为最大值的元素下标，并保持队列从大到小排列。
Deque队头 = 最大值
加入新元素：
删除已存在的比它小的，保持队头最大，保留小于队头的元素
窗口移动：
删除过期下标
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n-k+1];
Deque<Integer> deque = new LinkedList<>();
int index = 0;
for(int right = 0; right < n; right++){
// 删除队列中比当前值小的元素
while(!deque.isEmpty()
&& nums[deque.peekLast()] <= nums[right]){
deque.pollLast();
}
// 加入当前元素下标
deque.offerLast(right);
// 删除已经离开窗口的元素
if(deque.peekFirst() <= right-k){
deque.pollFirst();
}
// 窗口形成后记录最大值
if(right >= k-1){
result[index++] = nums[deque.peekFirst()];
}
}
return result;
}
}
3.最小覆盖字串
给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 “”。
测试用例保证答案唯一。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
示例 2：
输入：s = “a”, t = “a”
输出：“a”
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
思路
题目本质：整个字符串中找满足条件的最小长度字串
解题思路：[left … right]，不断移动 right 扩大窗口。
当窗口满足：
已经包含 t 的所有字符，然后移动 left 缩小窗口。找到满足条件的最短窗口。
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> window = new HashMap<>();
int left = 0;
int right = 0;
int valid = 0;
int start = 0;
int len = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
while (valid == need.size()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
普通数组
1.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
思路
题目本质：在数组中找一个连续子数组，使它的和最大。
解题思路：计算“以当前位置结尾”的最大和，记录全局最大值
public int maxSubArray(int[] nums) {
// current表示：以当前位置结尾的连续子数组最大和
// 因为子数组至少包含一个元素，所以不能初始化为0
int current = nums[0];
// max记录整个遍历过程中出现过的最大子数组和
int max = nums[0];
// 从下标1开始，因为nums[0]已经作为初始值
for (int i = 1; i < nums.length; i++) {
// 两种选择：
// 1. 接着前面的连续子数组：current + nums[i]
// 2. 放弃前面的子数组，从当前nums[i]重新开始
current = Math.max(current + nums[i], nums[i]);
// 更新全局最大值
max = Math.max(max, current);
}
return max;
}
2.合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
思路
题目本质：不同数组范围有重叠，合并重叠的一部分区间
解题思路：先排序，再线性扫描。排序后只需要判断当前区间和已经合并后的区间有无重叠部分。
判断区间是否重叠：如果当前区间的star小于上一个区间end，表示重叠。大于即不重叠。
public int[][] merge(int[][] intervals) {
// Arrays.sort可以对二维数组排序
// (a, b) -> Integer.compare(a[0], b[0])表示按照每个区间的起点a[0]从小到大排序
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// List<int[]>用于动态保存合并后的区间
// 因为最终区间数量不确定，所以先使用List
List<int[]> result = new ArrayList<>();
// 遍历排序后的所有区间
for (int[] interval : intervals) {
// result.isEmpty()判断结果集合是否为空
// 如果为空，说明这是第一个区间，直接加入
// 或者当前区间起点 > 上一个区间终点，说明不重叠，也直接加入
if (result.isEmpty() || interval[0] > result.get(result.size() - 1)[1]) {
result.add(interval);
} else {
// result.size() - 1表示最后一个元素的下标
// result.get(...)获取最后一个已经合并好的区间
int[] last = result.get(result.size() - 1);
// 当前区间与last重叠
// 合并时起点不变，只需要把终点更新成两者较大的那个
last[1] = Math.max(last[1], interval[1]);
}
}
// List<int[]>转换成int[][]
// new int[result.size()][]表示创建一个行数确定、每行长度暂未指定的二维数组
return result.toArray(new int[result.size()][]);
}
3.轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
思路
题目本质：把数组切成两段，然后交换两段的位置。
解题思路：三次反转。第一次整体反转，第二次反转前K个元素，第三次反转剩余元素。
public void rotate(int[] nums, int k) {
// 数组长度
int n = nums.length;
// 如果k超过数组长度，没有必要完整移动n次
// 例如长度7，移动10次等价于移动3次
k = k % n;
// 第一步：整体反转
reverse(nums, 0, n - 1);
// 第二步：反转前k个元素
reverse(nums, 0, k - 1);
// 第三步：反转剩余元素
reverse(nums, k, n - 1);
}
// 反转数组指定范围
private void reverse(int[] nums, int left, int right) {
// 双指针交换
while (left < right) {
// 保存左边元素
int temp = nums[left];
// 左边放右边元素
nums[left] = nums[right];
// 右边放原来的左边元素
nums[right] = temp;
// 左指针向右移动
left++;
// 右指针向左移动
right--;
}
}
4.除了自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
思路
题目本质：返回一个新数组，每个位置的值等于 其他所有元素相乘，不包括自己
解题思路：将除自身以外的元素分成左右两部分，分别计算前缀积和后缀积，最后将两者相乘。
class Solution {
public int[] productExceptSelf(int[] nums) {
// nums.length：获取数组长度
int n = nums.length;
// new int[n]：创建长度为n的整数数组，默认元素都是0
// answer[i]用来保存除nums[i]之外其他元素的乘积
int[] answer = new int[n];
// left表示当前元素左边所有元素的乘积
// 初始化为1，因为乘法中1不会改变结果
int left = 1;
// 第一遍：从左向右遍历，计算每个位置的前缀积
for (int i = 0; i < n; i++) {
// 先保存左边的乘积，不包括当前位置nums[i]
answer[i] = left;
// 再把当前位置元素乘进去，为下一个位置做准备
// *=表示乘法赋值，相当于left = left * nums[i]
left *= nums[i];
}
// right表示当前元素右边所有元素的乘积
int right = 1;
// 第二遍：从右向左遍历，计算后缀积
// i--表示每次循环结束后i减1
for (int i = n - 1; i >= 0; i--) {
// answer[i]原来保存的是左边的乘积
// 再乘以右边的乘积，就得到除自身以外的乘积
answer[i] *= right;
// 将当前元素乘进right，供下一个位置使用
right *= nums[i];
}
// 返回计算完成的一维数组
return answer;
}
}
5.缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。
思路
题目本质：从正数最小开始，找到未在数组内出现的数。
解题思路：原地哈希，数字 x 应该放在下标 x-1 的位置，放好以后再找第一个没有正确归位的位置。
class Solution {
public int firstMissingPositive(int[] nums) {
// nums.length：获取数组长度
int n = nums.length;
// 遍历数组，尽可能把数字x放到下标x-1的位置
for (int i = 0; i < n; i++) {
// &&表示逻辑与，所有条件都满足才执行循环
// nums[i] > 0：排除0和负数
// nums[i] <= n：排除大于数组长度的数字
// nums[i] != nums[nums[i]-1]：数字还没放到正确位置，并避免重复数字死循环
while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
// 计算当前数字应该放在哪个下标
// 例如nums[i]=3，那么正确下标就是2
int correctIndex = nums[i] - 1;
// 使用temp临时保存当前数字，防止交换时丢失数据
int temp = nums[i];
// 把目标位置原来的数字放到当前下标
nums[i] = nums[correctIndex];
// 把当前数字放到它应该在的位置
nums[correctIndex] = temp;
}
}
// 交换结束后，再从左向右寻找第一个位置不正确的元素
for (int i = 0; i < n; i++) {
// 下标i应该存放数字i+1
// 如果不相等，说明i+1这个正整数缺失
if (nums[i] != i + 1) {
return i + 1;
}
}
// 如果1到n全部在正确位置，最小缺失正整数就是n+1
return n + 1;
}
}
矩阵
1.矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
思路
先用第一行、第一列记录哪些行列需要清零，再统一修改矩阵，最后单独处理第一行和第一列。
class Solution {
public void setZeroes(int[][] matrix) {
// matrix.length：获取二维数组的行数
int m = matrix.length;
// matrix[0].length：获取第0行的长度，也就是列数
int n = matrix[0].length;
// boolean是布尔类型，只能存true或false
// 记录第一行和第一列原本是否包含0
boolean firstRowZero = false;
boolean firstColZero = false;
// 第一步：检查第一行是否有0
for (int j = 0; j < n; j++) {
// matrix[0][j]表示第0行、第j列的元素
if (matrix[0][j] == 0) {
firstRowZero = true;
break; // 找到0后退出当前for循环
}
}
// 检查第一列是否有0
for (int i = 0; i < m; i++) {
// matrix[i][0]表示第i行、第0列的元素
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}
// 第二步：遍历内部元素，记录哪些行和列需要置零
// 从1开始，跳过用来保存标记的第一行和第一列
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
// 第i行需要置零，标记在这一行的第0列
matrix[i][0] = 0;
// 第j列需要置零，标记在第0行的这一列
matrix[0][j] = 0;
}
}
}
// 第三步：根据标记，将内部对应元素设置为0
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// ||表示逻辑或，只要其中一个条件成立就执行
// matrix[i][0]==0：当前行需要置零
// matrix[0][j]==0：当前列需要置零
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// 第四步：如果第一行原本有0，就将整行设置为0
if (firstRowZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
// 如果第一列原本有0，就将整列设置为0
if (firstColZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
// 方法返回类型为void，直接修改原矩阵，无需return
}
}
2.螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
思路
题目本质：从左上角开始，按照顺时针方向，依次访问矩阵中的所有元素，最后返回一个一维列表。
解题思路：首先设置矩阵的上、下、左、右四个边界，分别表示当前尚未遍历的矩阵范围。然后在剩余区域不为空的情况下，按照顺时针方向依次遍历最上面一行、最右边一列、最下面一行和最左边一列。
每完成一个方向的遍历，就收缩对应的边界，进入下一圈。为了避免矩阵只有一行或一列时重复访问元素，在遍历最下面一行和最左边一列之前，需要额外判断剩余区域是否仍然存在。
当边界交错、没有剩余元素时，结束遍历并返回结果集合。
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
// 创建一个List，用来按照螺旋顺序保存遍历结果
List<Integer> result = new ArrayList<>();
// matrix.length表示矩阵的行数
int m = matrix.length;
// matrix[0].length表示矩阵的列数
int n = matrix[0].length;
// 设置四个边界，数组下标从0开始
int top = 0;
int bottom = m - 1;
int left = 0;
int right = n - 1;
// 只要剩余区域还有行和列，就继续遍历
while (top <= bottom && left <= right) {
// 第一步：从左向右遍历最上面一行
for (int j = left; j <= right; j++) {
result.add(matrix[top][j]);
}
// 最上面一行已经遍历完成，边界向下移动
top++;
// 第二步：从上向下遍历最右边一列
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
// 最右边一列已经遍历完成，边界向左移动
right--;
// 第三步：如果还有剩余行，就从右向左遍历最下面一行
if (top <= bottom) {
for (int j = right; j >= left; j--) {
result.add(matrix[bottom][j]);
}
// 最下面一行已经遍历完成，边界向上移动
bottom--;
}
// 第四步：如果还有剩余列，就从下向上遍历最左边一列
if (left <= right) {
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
// 最左边一列已经遍历完成，边界向右移动
left++;
}
}
// 返回按照顺时针顺序排列的所有元素
return result;
}
}
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
12
0- 0
已为社区贡献1条内容
所有评论(0)