Hot100 参考解法01
哈希
1 两数之和
数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];//结果数组：都是下标
Map<Integer,Integer> map=new HashMap<>();
//key: temp数组中的值 value :对应下标
for(int i=0;i<nums.length;i++){
int temp=target-nums[i]; // 遍历当前元素，并在map中寻找是否有匹配的key
if(map.containsKey(temp)){
res[1]=i; //当前元素索引
res[0]=map.get(temp); //差值元素值的下标
//满足判断条件，并在循环中需要跳出循环
break;
}
map.put(nums[i],i); // 如果没找到匹配对，就把访问过的元素和下标加入到map中 值作为key
}
return res;
}
}49 字母异位词分组 （处理字符：标准化）
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 创建一个哈希表，用于存储分组后的字母异位词
Map<String, List<String>> map = new HashMap<>();
// 遍历给定的字符串数组
for (String str : strs) {
// 将当前字符串转换为字符数组，并对字符数组进行排序
char[] array = str.toCharArray();
Arrays.sort(array);
// 将排序后的字符数组转换为字符串，作为哈希表的键
String key = new String(array);
// 在哈希表中查找以当前键为索引的列表，如果不存在则创建一个新的列表
List<String> list = map.getOrDefault(key, new ArrayList<String>());
// 将当前字符串添加到对应的列表中
list.add(str);
// 将更新后的列表存回哈希表
map.put(key, list);
}
// 返回哈希表中的所有值，即分组后的字母异位词列表
return new ArrayList<List<String>>(map.values());
}
}128 最长连续序列 + （先找开头元素，然后递增） Hashset
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n)的算法解决此问题。
class Solution {
public int longestConsecutive(int[] nums) {
// 转化成哈希集合，方便快速查找是否存在某个元素
HashSet<Integer> set = new HashSet<Integer>();
//将数组值放入集合中
for (int num : nums) {
set.add(num);
}
//序列数不连续，只查找是不是存在
int res = 0;
for (int num : set) {
if (set.contains(num - 1)) {
// num 不是连续子序列的第一个，跳过
continue;
}
// num 是连续子序列的第一个，开始向上计算连续子序列的长度
int curNum = num;
int curLen = 1;
while (set.contains(curNum + 1)) {
curNum += 1;
curLen += 1;
}
// 更新最长连续序列的长度
res = Math.max(res, curLen);
}
return res;
}
}双指针
283 移动零 （数组）
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
/*时间复杂度：
该算法的时间复杂度为 O(n)，因为每个元素最多被遍历两次（一次移动非零值，一次置零）。
空间复杂度：
空间复杂度为 O(1)，因为该算法只使用了常数级别的额外空间（即两个指针）。*/
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++; // 慢指针前进
}
}
// 第二遍遍历：将剩余部分置零
for (; slow < nums.length; slow++) {
nums[slow] = 0; // 将后面的元素全部置为零
}
}
}11 盛最多水的容器 +(从两边往中间)
right-left：索引范围 right-left+1：元素个数
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int res = 0;
while (left < right) {
// [left, right] 之间的矩形面积 由较低的一方决定
int cur_area = Math.min(height[left], height[right]) * (right - left);
res = Math.max(res, cur_area);
// 双指针技巧，移动较低的一边
if (height[left] < height[right]) { //高度比较
left++;
} else {
right--;
}
}
return res;
}
}
//时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被访问一次。
//空间复杂度：O(1)，只使用了常数级别的额外空间。15 三数之和 （排序 + 双指针）剪枝三次
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res=new ArrayList<>();
Arrays.sort(nums);
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for(int i=0;i<nums.length;i++){
// if(nums[i]>0){
// return res;
//}
//去重a
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int left=i+1;
int right=nums.length-1;
while(right>left){
int sum=nums[i]+nums[left]+nums[right];
if(sum>0){
right--;
}else if(sum<0){
left++;
}
else{
//根据返回条件：列表
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
//还是要去重，否则有样例不通过
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
//找到符合条件的一组，继续迭代
right--;
left++;
}
}
}
return res;
}
}42 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
class Solution {
int trap(int[] height) {
int left = 0, right = height.length - 1;
//左右两端较高的 先进行初始化
int l_max = 0, r_max = 0;
//结果
int res = 0;
while (left < right) {
//两个定值
l_max = Math.max(l_max, height[left]);
r_max = Math.max(r_max, height[right]);
// res += min(l_max, r_max) - height[i]
//比较左右两边谁高 由低的决定 低的减去每一个位置高度，是当前坐标的水量
if (l_max < r_max) {
res += l_max - height[left];//左边低，由低的决定
left++;
} else {
res += r_max - height[right];
right--;
}
}
return res;
}
}滑动窗口
3 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution {
int lengthOfLongestSubstring(String s) {
//key:字符，value:次数
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int res = 0; // 记录结果
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
window.put(c, window.getOrDefault(c, 0) + 1);
// 判断左侧窗口是否要收缩
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
window.put(d, window.get(d) - 1);
}
// 在这里更新答案 在收缩窗口完成后更新 res,无重复字符
res = Math.max(res, right - left);
}
return res;
}
}438 找到字符串中所有字母异位词(返回起始索引)
给定两个字符串 s 和 p，找到 s中所有 p的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (int i = 0; i < p.length(); i++) {
char c = p.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
List<Integer> res = new ArrayList<>(); // 记录结果
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 (right - left >= p.length()) {
// 当窗口符合条件时，把起始索引加入 res
if (valid == need.size()) {
res.add(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 res;
}
}子串
560 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k的子数组的个数 。
子数组是数组中元素的连续非空序列。
前缀和解法 （可以使用前缀和 子区间的和，遍历求出子区间的和后，再利用双指针）
public class Solution {
public int subarraySum(int[] nums, int k) {
int res= 0;
int[] sum = new int[nums.length + 1];
sum[0] = 0;//初始化前缀和为0
//前缀和 数组下标比原始数组多1
for (int i = 0; i < nums.length; i++) {
sum[i + 1] = sum[i] + nums[i];
}
//前后双指针遍历
for (int i = 0; i < sum.length; i++) {
for (int j = i + 1; j < sum.length; j++) {
if (sum[j] - sum[i] == k) {
res++;
}
}
}
return res;
}
}239 滑动窗口最大值 （单调栈）
使用一种新的队列结构，既能够维护队列元素「先进先出」的时间顺序，又能够正确维护队列中所有元素的最值，这就是「单调队列」结构。
class Solution {
/* 单调队列的实现 */
class MonotonicQueue {
LinkedList<Integer> q = new LinkedList<>();
public void push(int n) {
// 循环来删除队列中所有小于 n 的元素。循环条件为
//!q.isEmpty() && q.getLast() < n，即队列不为空且最后一个元素小于 n。
while (!q.isEmpty() && q.getLast() < n) {
q.pollLast();
}
// 然后将 n 加入尾部
q.addLast(n);
}
public int max() {
return q.getFirst();
}
public void pop(int n) {
if (n == q.getFirst()) {
q.pollFirst();
}
}
}
/* 解题函数的实现 */
public int[] maxSlidingWindow(int[] nums, int k) {
MonotonicQueue window = new MonotonicQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i < k - 1) {
//先填满窗口的前 k - 1
window.push(nums[i]);
} else {
// 窗口向前滑动，加入新数字
window.push(nums[i]);
// 记录当前窗口的最大值
res.add(window.max());
// 移出旧数字
window.pop(nums[i - k + 1]);
}
}
// 需要转成 int[] 数组再返回
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
}76 最小覆盖子串 （返回值是子串）
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
class Solution {
public String minWindow(String s, String t) {
// 用于记录需要的字符和窗口中的字符及其出现的次数
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
// 统计 t 中各字符出现次数
for (char c : t.toCharArray())
need.put(c, need.getOrDefault(c, 0) + 1);
int left = 0, right = 0;
int valid = 0; // 窗口中满足需要的字符个数
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 扩大窗口
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);//统计c出现的次数
if (window.get(c).equals(need.get(c)))
valid++; // 只有当 window[c] 和 need[c] 对应的出现次数一致时，才能满足条件，valid 才能 +1
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {
// 更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是将移出窗口的字符
char d = s.charAt(left);
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d)))
valid--; // 只有当 window[d] 内的出现次数和 need[d] 相等时，才能 -1
window.put(d, window.get(d) - 1);
}
}
}
// 返回最小覆盖子串
return len == Integer.MAX_VALUE ?
"" : s.substring(start, start + len);
}
}普通数组
53 最大子数组和 （动归 普通数组部分）
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
class Solution {
public int maxSubArray(int[] nums) {
// 贪心算法
int max = Integer.MIN_VALUE;
int sum = 0;
for (int num : nums) {
sum = sum > 0 ? sum + num : num;
max = Math.max(max, sum);
}
return max;
}
}56 合并区间（贪心）
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start(i), end(i)] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
class Solution {
//贪心算法
public int[][] merge(int[][] intervals) {
List<int[]> res=new LinkedList<>();
//按照左边界进行排序
Arrays.sort(intervals,(x,y)->Integer.compare(x[0],y[0]));
int start=intervals[0][0];
int right=intervals[0][1];
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>right)
{
//没有重叠部分，输出当前区间
res.add(new int[]{start,right});
//更新坐标
start=intervals[i][0];
right=intervals[i][1];
}
else{
//有重叠部分，更新右边界
right=Math.max(right,intervals[i][1]);
}
}
res.add(new int[]{start,right});
return res.toArray(new int[res.size()][]);
}
}189 轮转数组（数学问题） 处理数组和字符串都可使用 向右轮转
给定一个整数数组 nums，将数组中的元素向右轮转k个位置，其中 k是非负数。
class Solution {
4321567
4321765
5672134
public void rotate(int[] nums, int k) {
// 三次翻转 1.翻转（0，k-1）2.(k,nums.length-1) 3.全部翻转 可以自己模拟一下 顺序是可以变得
//k的长度超过数组大小 没有意义 取模
k %= nums.length;
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
reverse(nums, 0, nums.length - 1);
}
public void reverse(int[] nums, int s, int e) {
//双指针
while (s < e) {
int temp = nums[s];
nums[s] = nums[e];
nums[e] = temp;
s++;
e--;
}
}
}238 除自身以外数组的乘积（前后缀和）
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
int[] g = new int[n + 1];//后缀 有效索引 0-n
g[n] = 1; // 后缀数组，表示[i, n-1]区间的乘积 最后一位（当前元素）右边没有元素，乘积设置为1
for (int i = n - 1; i >= 0; i--) {
g[i] = g[i + 1] * nums[i];
}
int pre = 1; // 表示区间[0, i-1]区间的乘积 求前缀乘积的时候顺便求了res 刨去当前元素
for (int i = 0; i < n; i++) {
res[i] = g[i + 1] * pre;
//先更新res，再更新pre 就是使用的[0,i-1]
pre *= nums[i];
}
return res;}}41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
// 第一遍遍历，将每个数放到它应在的位置上
// 将每个数放在它应在的位置上，比如1放在索引0，2放在索引1
for (int i = 0; i < n; i++) {
//确保当前的数字是一个正整数
//确保当前数字在数组的有效索引范围内
//确保当前数字 nums[i] 不在它正确的位置上
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// 交换 nums[i] 和 nums[nums[i] - 1]
int temp = nums[i];
nums[i] = nums[temp - 1];
nums[temp - 1] = temp;
}
}
// 第二遍遍历，找到第一个 nums[i] != i + 1 的位置
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 如果所有位置都正确，说明最小缺失正整数是 n + 1
return n + 1;
}
}矩阵
73 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
class Solution {
public void setZeroes(int[][] matrix) {
// 获取矩阵的行数和列数
int m = matrix.length, n = matrix[0].length;
// 创建两个布尔数组，分别标记哪一行和哪一列需要被置为0
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
// 第一次遍历矩阵，标记含0的行和列
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 检查当前元素是否为0
if (matrix[i][j] == 0) {
// 如果是0，标记所在的行和列
row[i] = col[j] = true;
}
}
}
// 第二次遍历矩阵，根据标记的行和列来设置0
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果行或列被标记为需要置0，就将当前元素设置为0
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
}54 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
List<Integer> res = new LinkedList<>();
// res.size() == m * n 则遍历完整个数组
while (res.size() < m * n) {
if (upper_bound <= lower_bound) {
// 在顶部从左向右遍历
for (int j = left_bound; j <= right_bound; j++) {
res.add(matrix[upper_bound][j]);
}
// 上边界下移
upper_bound++;
}
if (left_bound <= right_bound) {
// 在右侧从上向下遍历
for (int i = upper_bound; i <= lower_bound; i++) {
res.add(matrix[i][right_bound]);
}
// 右边界左移
right_bound--;
}
if (upper_bound <= lower_bound) {
// 在底部从右向左遍历
for (int j = right_bound; j >= left_bound; j--) {
res.add(matrix[lower_bound][j]);
}
// 下边界上移
lower_bound--;
}
if (left_bound <= right_bound) {
// 在左侧从下向上遍历
for (int i = lower_bound; i >= upper_bound; i--) {
res.add(matrix[i][left_bound]);
}
// 左边界右移
left_bound++;
}
}
return res;
}
}48 旋转图像
先把二维矩阵沿对角线反转，然后反转矩阵的每一行，结果就是顺时针反转整个矩阵。
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 先沿对角线反转二维矩阵
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// swap(matrix[i][j], matrix[j][i]);
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 然后反转二维矩阵的每一行
for (int[] row : matrix) {
reverse(row);
}
}
// 反转一维数组
void reverse(int[] arr) {
int i = 0, j = arr.length - 1;
while (j > i) {
// swap(arr[i], arr[j]);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
}240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
如果向左移动，元素在减小，如果向下移动，元素在增大
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
// 从右上角开始，规定只能向左或向下移动。
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] < target) {
i++;
} else {
j--;
}
}
return false;
}
}原文地址：https://blog.csdn.net/m0_50846237/article/details/140632900
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！