面试150题-滑动窗口+哈希表
📕文章题目选自LeetCode面试150题-滑动窗口+哈希表
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/
滑动窗口
LeetCode150-长度最小的子数组-LC209
/**
* 题目：长度最小的子数组
* 算法：滑动窗口
* 解题思路：1.初始窗口大小为0 start end 都是从0开始
* 2.while循环中end一直向右移动并且 当sum > target，start向右移动缩小窗口大小
* 3.ans记录最小值
*/
public class LC209 {
public static void main(String[] args) {
int[] nums = {2,3,1,2,4,3};
int target = 7;
System.out.println(minSubArrayLen(target,nums));
}
public static int minSubArrayLen(int target, int[] nums) {
int len = nums.length;
int start = 0;
int end = 0;//end值不能设为1 否则无法添加第一个元素
int sum = 0;
int ans = Integer.MAX_VALUE;
while(end < len){
sum += nums[end];
while(sum >= target){
ans = Math.min(ans,end - start + 1);
sum-=nums[start++];
}
end++;
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
LeetCode150-无重复字符的最长子串-LC209
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length() == 1) return 1;
int maxLength = 0;
int right = -1;
Set<Character> set = new HashSet<Character>();
for(int left = 0; left < s.length() - 1;left++){
if(left != 0){
set.remove(s.charAt(left - 1));
}
while(right + 1 < s.length() && !set.contains(s.charAt(right + 1))){
set.add(s.charAt(right + 1));
right++;
}
maxLength = Math.max(maxLength,right - left + 1);
}
return maxLength;
}
}LeetCode150-串联所有单词的子串-LC30
package cn.dsxriiiii.LeetCode.LC150;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* @ProjectName: Mounts
* @Author: DSXRIIIII
* @CreateDate: 2024/6/16 16:32
* @Email: lihh53453@hundsun.com
* @Description: 串联所有单词的子串
* 思路：滑动窗口
* 1.确定滑动窗口起始位置left，right
* 2.right不断右移，移动条件为right+单个单词长度不超过s.length()
* 3.left不断右移，移动条件为
* 1.right右移产生的单词在字符串中不存在 此时需要将map清空 left = right count计数器 =0
* 2.right右移产生单个单词数超过了words中的数量 此时while循环会判断当前right右移产生单个单词数是否一直超过了words中的数量
* true:count(用来计数判断的有效个数)--,left移动
*/
public class LC30 {
public static void main(String[] args) {
String s = "foobarfoobarfoothe";
String[] words = {"foo","bar","foo","the"};
System.out.println(findSubstring(s,words));
}
public static List<Integer> findSubstring(String s,String[] words){
Map<String,Integer> map = new HashMap<>();
List<Integer> res = new ArrayList<>();
if(s.isEmpty() || words.length == 0) return res;
for(String word:words){
if(!s.contains(word)) return res;
map.put(word,map.getOrDefault(word,0) + 1);
}
int oneWordLength = words[0].length();
int wordsLength = oneWordLength * words.length;
if(wordsLength > s.length()) return res;
for(int i = 0;i < words[0].length();i++){
int left = i;
int right = i;
int count = 0;
Map<String,Integer> subMap = new HashMap<>();
while(right + oneWordLength <= s.length()){
String newWordByRight = s.substring(right,right+oneWordLength);
right = right + oneWordLength;
if(!map.containsKey(newWordByRight)){
subMap.clear();
left = right;
count = 0;
}else{
subMap.put(newWordByRight,subMap.getOrDefault(newWordByRight,0) + 1);
count++;
while(subMap.getOrDefault(newWordByRight,0) > map.getOrDefault(newWordByRight,0)){
String newWordByLeft = s.substring(left,left + oneWordLength);
subMap.put(newWordByLeft,subMap.getOrDefault(newWordByLeft,0) - 1);
count--;
left = left + oneWordLength;
}
if(count == words.length){
res.add(left);
}
}
}
}
return res;
}
public static List<Integer> solution2(String s, String[] words) {
List<Integer> res = new ArrayList<>();
Map<String, Integer> wordsMap = new HashMap<>();
if (s.isEmpty() || words.length == 0) return res;
for (String word: words) {
// 主串s中没有这个单词，直接返回空
if (!s.contains(word)) return res;
// map中保存每个单词，和它出现的次数
wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
}
// 每个单词的长度， 总长度
int oneLen = words[0].length(), wordsLen = oneLen * words.length;
// 主串s长度小于单词总和，返回空
if (wordsLen > s.length()) return res;
// 只讨论从0，1，...， oneLen-1 开始的子串情况，
// 每次进行匹配的窗口大小为 wordsLen，每次后移一个单词长度，由左右窗口维持当前窗口位置
for (int i = 0; i < oneLen; ++i) {
// 左右窗口
int left = i, right = i, count = 0;
// 统计每个符合要求的word
Map<String, Integer> subMap = new HashMap<>();
// 右窗口不能超出主串长度
while (right + oneLen <= s.length()) {
// 得到一个单词
String word = s.substring(right, right + oneLen);
// 有窗口右移
right += oneLen;
// words[]中没有这个单词，那么当前窗口肯定匹配失败，直接右移到这个单词后面
if (!wordsMap.containsKey(word)) {
left = right;
// 窗口内单词统计map清空，重新统计
subMap.clear();
// 符合要求的单词数清0
count = 0;
} else {
// 统计当前子串中这个单词出现的次数
subMap.put(word, subMap.getOrDefault(word, 0) + 1);
++count;
// 如果这个单词出现的次数大于words[]中它对应的次数，又由于每次匹配和words长度相等的子串
// 如 ["foo","bar","foo","the"] "| foobarfoobar| foothe"
// 第二个bar虽然是words[]中的单词，但是次数抄了，那么右移一个单词长度后 "|barfoobarfoo|the"
// bar还是不符合，所以直接从这个不符合的bar之后开始匹配，也就是将这个不符合的bar和它之前的单词(串)全移出去
while (subMap.getOrDefault(word, 0) > wordsMap.getOrDefault(word, 0)) {
// 从当前窗口字符统计map中删除从左窗口开始到数量超限的所有单词(次数减一)
String w = s.substring(left, left + oneLen);
subMap.put(w, subMap.getOrDefault(w, 0) - 1);
// 符合的单词数减一
--count;
// 左窗口位置右移
left += oneLen;
}
// 当前窗口字符串满足要求
if (count == words.length) res.add(left);
}
}
}
return res;
}
}
LeetCode150-最小覆盖子串-LC76
package cn.dsxriiiii.LeetCode.LC150;
/**
* @ProjectName: Mounts
* @Author: DSXRIIIII
* @CreateDate: 2024/6/17 9:55
* @Email: lihh53453@hundsun.com
* @Description: 最小覆盖子串
* 思路：滑动窗口
* 1.维护两个数组保存128位(包含大小写)
* 2.包含函数 判断s中所有的字符数量比t的所有字符数量多
* 3.右移条件：走到s串的结尾
* 4.左移条件：使用包含函数 不断左指针右移 并且在数组中减少字符--;
* 5.此时左右指针维护的最小字串长度判断并且不断更新
*/
public class LC76 {
public static void main(String[] args) {
String s = "aaaaaaaaaaaabbbbbcdd";
String t = "abcdd";
System.out.println(minWindow(s,t));
}
public static String minWindow(String s, String t) {
char[] charArray = s.toCharArray();
int nowLeft = -1;
int nowRight = s.length();
int left = 0;
int[] arrT = new int[128];
int[] arrS = new int[128];
for(char c : t.toCharArray()){
arrT[c]++;
}
for (int right = 0; right < s.length(); right++) {
arrS[charArray[right]]++;
while(isCover(arrS,arrT)){
if(right - left < nowRight - nowLeft){
nowRight = right;
nowLeft = left;
}
arrS[charArray[left++]]--;
}
}
return nowLeft < 0 ? "" : s.substring(nowLeft,nowRight+1);
}
private static boolean isCover(int[] s, int[] t) {
for(int i = 'A';i <= 'Z';i++){
if(s[i] < t[i]){
return false;
}
}
for(int i = 'a';i <= 'z';i++){
if(s[i] < t[i]){
return false;
}
}
return true;
}
}
滑动窗口总结
1.长度最小的子数组
初始窗口大小为0 start end 都是从0开始
while循环中end一直向右移动并且 当sum > target，start向右移动缩小窗口大小
ans记录最小值
2,.无重复字符的最长子串
遍历字符串，每次移动左指针时从集合中移除相应字符，并且将left-1的字符移除
right从-1开始
哈希表
LeetCode150-赎金信-LC383
/**
* @ProjectName: Mounts
* @Description: LC383 赎金信
* @Author: DSXRIIIII
* @CreateDate: 2024/5/24 17:02
* @Email: lihh53453@hundsun.com
*
* 解题思路：字母数组++和--
**/
public class LC383 {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()){
return false;
}
int[] charArr = new int[26];
for(char a : magazine.toCharArray()){
charArr[a -'a']++;
}
for(char b : ransomNote.toCharArray()){
--charArr[b - 'a'];
if(charArr[b - 'a'] < 0){
return false;
}
}
return true;
}
}
LeetCode150-同构字符串-LC205
import java.util.HashMap;
import java.util.Map;
/**
* @ProjectName: Mounts
* @Description: LC205 同构字符串
* @Author: DSXRIIIII
* @CreateDate: 2024/5/24 17:12
* @Email: lihh53453@hundsun.com
*
* 思路一：两个HashMap
**/
public class LC205 {
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Character> mapS = new HashMap<>();
Map<Character, Character> mapT = new HashMap<>();
for (int index = 0; index < s.length(); index++) {
char charS = s.charAt(index);
char charT = t.charAt(index);
if (!mapS.containsKey(charS)) {
mapS.put(charS, charT);
}
if (!mapT.containsKey(charT)) {
mapT.put(charT, charS);
}
if (mapS.get(charS) != charT || mapT.get(charT) != charS) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s = "paper";
String t = "title";
LC205 lc205 = new LC205();
System.out.println(lc205.isIsomorphic(s, t));
}
}
LeetCode150-单词规律-LC290
public class LC290 {
public static boolean wordPattern(String pattern, String s) {
String[] words = s.split(" ");
Map<Character,String> map =new HashMap<>();
Map<String,Character> map2 =new HashMap<>();
for (int i = 0; i < pattern.length(); i++) {
if(map.containsKey(pattern.charAt(i)) && !map.get(pattern.charAt(i)).equals(words[i])){
return false;
}
if(map2.containsKey(words[i]) && !map2.get(words[i]).equals(pattern.charAt(i))){
return false;
}
map.put(pattern.charAt(i),words[i]);
map2.put(words[i],pattern.charAt(i));
}
return true;
}
public static void main(String[] args) {
String pattern = "abba";
String s = "dog cat cat dog";
System.out.println(wordPattern(pattern, s));
}
}
LeetCode150-有效的字母异位词-LC242
/**
* @ProjectName: Mounts
* @Description: 数组++ -- 即可
* @Author: DSXRIIIII
* @CreateDate: 2024/6/5 17:18
* @Email: lihh53453@hundsun.com
**/
public class LC242 {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;
int[] c = new int[26];
for (int i = 0; i < s.length(); i++) {
c[s.charAt(i) - 'a']++;
c[t.charAt(i) - 'a']--;
}
for (int i = 0; i < 26; i++) {
if(c[i] != 0){
return false;
}
}
return true;
}
}LeetCode150-字母异位词分组-LC49
/**
* 将str->char数组->打乱->String
* 排序的String转换成key存储在map中 用来匹配 将匹配的结果放到list中
* @ProjectName: Mounts
* @Description: 字母异位词分组
* @Author: DSXRIIIII
* @CreateDate: 2024/6/5 17:28
* @Email: lihh53453@hundsun.com
**/
public class LC49 {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str:strs){
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String key = new String(charArray);
List<String> list = map.getOrDefault(key,new ArrayList<>());
list.add(str);
map.put(key,list);
}
return new ArrayList<List<String>>(map.values());
}
}
LeetCode150-有效的数独-LC38
/**
* @ProjectName: Mounts
* @Description: 有效的数独
* @Author: DSXRIIIII
* @CreateDate: 2024/6/18 13:40
* @Email: lihh53453@hundsun.com
*/
public class LC38 {
public boolean isValidSudoku(char[][] board) {
int[][] arr1 = new int[9][9];
int[][] arr2 = new int[9][9];
int[][][] arr3 = new int[3][3][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
int index = c - '0' - 1;
arr1[i][index]++;//保存列的个数
arr2[j][index]++;//保存行的个数
arr3[i / 3][j / 3][index]++;//保存单个3*3模块的个数
if (arr1[i][index] > 1 || arr2[j][index]++ > 1 || arr3[i / 3][j / 3][index] > 1) {
return false;
}
}
}
}
return true;
}
}
LeetCode150- 螺旋矩阵-LC38
package cn.dsxriiiii.LeetCode.LC150;
import java.util.ArrayList;
import java.util.List;
/**
* @ProjectName: Mounts
* @Description: 螺旋矩阵
* @Author: DSXRIIIII
* @CreateDate: 2024/6/18 14:00
* @Email: lihh53453@hundsun.com
* 方法与螺旋矩阵II类似
*/
public class LC54 {
public static void main(String[] args) {
int[][] arr = {{2,5,8},{4,0,-1}};
System.out.println(spiralOrder(arr));
}
public static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int up = 0;
int down = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
while(true){
for(int i = left;i <= right;i++) res.add(matrix[up][i]);
if(++up > down) break;
for (int j = up; j <= down; j++) res.add(matrix[j][right]);
if(--right < left) break;
for (int m = right; m >= left ; m--) res.add(matrix[down][m]);
if(--down < up) break;
for (int n = down; n >= up; n--) res.add(matrix[n][left]);
if(++left > right) break;
}
return res;
}
}
LeetCode150- 旋转图像-LC48
package cn.dsxriiiii.LeetCode.LC150;
/**
* @ProjectName: Mounts
* @Description: 旋转图像
* @Author: DSXRIIIII
* @CreateDate: 2024/6/18 14:47
* @Email: lihh53453@hundsun.com
*/
public class LC48 {
public void rotate(int[][] matrix) {
int len = matrix.length;
int[][] new_matrix = new int[len][len];
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
new_matrix[j][len - i - 1] = matrix[i][j]; //找到此处的数学规律即可
}
}
for (int i = 0; i < len; i++) {
System.arraycopy(new_matrix[i], 0, matrix[i], 0, len);
}
}
}
LeetCode150- 矩阵置零-LC73
package cn.dsxriiiii.LeetCode.LC150;
import java.util.ArrayList;
import java.util.List;
/**
* @ProjectName: Mounts
* @Description: 矩阵置零
* @Author: DSXRIIIII
* @CreateDate: 2024/6/18 14:53
* @Email: lihh53453@hundsun.com
*/
public class LC73 {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
//boolean[][] arr = new boolean[len][len];
boolean[] col = new boolean[n];
boolean[] row = new boolean[m];
//原本的想法是按照注释的那种 但是如果是对单行单列操作只需要一位数组就行了
List<List<int[]>> list = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(matrix[i][j] == 0){
col[j] = true;
row[i] = true;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(col[j] || row[i]){
matrix[i][j] = 0;
}
}
}
}
}
LeetCode150- 字母异位词分组-LC49
package cn.dsxriiiii.LeetCode.LC150;
import java.util.*;
/**
* @ProjectName: Mounts
* @Description: 字母异位词分组
* @Author: DSXRIIIII
* @CreateDate: 2024/6/5 17:28
* @Email: lihh53453@hundsun.com
* 思路：哈希表
* 1.将每个字符串排列之后得到的key是一样的
* 2.依次放入map中的list
* 3.最后return new ArrayList<List<String>>(map.values());将map转化为ArrayList
**/
public class LC49 {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str:strs){
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
String key = new String(charArray);
List<String> list = map.getOrDefault(key,new ArrayList<>());
list.add(str);
map.put(key,list);
}
return new ArrayList<List<String>>(map.values());
}
}
LeetCode150- 字母异位词分组-LC49
package cn.dsxriiiii.LeetCode.LC150;
import java.util.HashMap;
import java.util.Map;
/**
* @ProjectName: Mounts
* @Description:
* @Author: DSXRIIIII
* @CreateDate: 2024/6/19 14:11
* @Email: lihh53453@hundsun.com
* 思路：哈希表
* 1.把值和index绑定在hashmap中
* 2.注意匹配 两数之和即 target - 其中一数
*/
public class LC1 {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < nums.length;i++){
if(map.containsKey(target - nums[i])){
return new int[]{i,map.get(target - nums[i])};
}
map.put(nums[i],i);
}
return new int[0];
}
}
LeetCode150- 两数之和-LC1
package cn.dsxriiiii.LeetCode.LC150;
import java.util.HashMap;
import java.util.Map;
/**
* @ProjectName: Mounts
* @Description: 两数之和
* @Author: DSXRIIIII
* @CreateDate: 2024/6/19 14:11
* @Email: lihh53453@hundsun.com
* 思路：哈希表
* 1.把值和index绑定在hashmap中
* 2.注意匹配 两数之和即 target - 其中一数
*/
public class LC1 {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < nums.length;i++){
if(map.containsKey(target - nums[i])){
return new int[]{i,map.get(target - nums[i])};
}
map.put(nums[i],i);
}
return new int[0];
}
}
LeetCode150- 快乐数-LC202
package cn.dsxriiiii.LeetCode.LC150;
import java.util.HashSet;
import java.util.Set;
/**
* @ProjectName: Mounts
* @Description: 快乐数 1**2 + 9**2 = 82
* 8**2 + 2**2 = 68
* 6**2 + 8**2 = 100
* 1**2 + 0**2 + 0**2 = 1
* @Author: DSXRIIIII
* @CreateDate: 2024/6/19 14:39
* @Email: lihh53453@hundsun.com
* 技巧：快乐树会形成一个循环
* 例如：4 最终会回到4
* 最大的数999999999 也会回到810 最后811次循环就会回到起点
* 思路：1.字符串分解 ？ -> 会死循环
* 2.怎么跳出死循环 ？
* 3.哈希Set 把每个数都放到set中 当set有重复值则会退出循环
* 4.快慢指针 当快指针指向慢指针说明此时走了一个循环周期 要判断这个循环是不是1引起的
*/
public class LC202 {
public static int GetNext(int n){
int total = 0;
while(n != 0){
int num = n % 10;
total += num * num;
n = n / 10;
}
return total;
}
public boolean isHappyBySet(int n) {
Set<Integer> set = new HashSet<>();
while(n != 1 && !set.contains(n)){
set.add(n);
n = GetNext(n);
}
return n == 1;
}
public boolean isHappyByHash(int n) {
int slow = n,fast = n;
do{
slow = GetNext(slow);
fast = GetNext(fast);
fast = GetNext(fast);
}while(slow != fast);
return slow == 1;
}
public static void main(String[] args) {
//System.out.println(GetNext(12));
}
}
LeetCode150- 存在重复元素 II-LC129
/**
* @ProjectName: Mounts
* @Description: 存在重复元素 II
* @Author: DSXRIIIII
* @CreateDate: 2024/8/2 21:05
* @Email: lihh53453@hundsun.com
* 哈希表和滑动数组解决
* 1.哈希表可以保存数据坐标值和数组值相互对应上
* 2.看到固定距离就要想到滑动窗口 而滑动窗口要想到set集合 或者队列
*/
public class LC219 {
public boolean containsNearbyDuplicate_byMap(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i]) && i - map.get(nums[i]) <= k){
return true;
}
map.put(nums[i],i);
}
return false;
}
/**
* 假设为4 位置i = 3 5 - 4 - 1 只有比窗口大的时候才会有减的空间 因为i-k限定了
* 0 1 2 3 4
* 1 2 3 4 -> 3
* 2 3 4 5
* @param nums 初始数组
* @param k 滑动窗口大小
* @return boolean
*/
public boolean containsNearbyDuplicate(int[] nums, int k) {
int length = nums.length;
Set<Integer> set = new HashSet<>();
for (int i = 0; i < length; i++) {
if(i > k){
set.remove(nums[i - k - 1]);
}
if(!set.add(nums[i])){
return true;
}
}
return false;
}
}LeetCode150-最长连续序列-LC128
/**
* @ProjectName: Mounts
* @Description:LeetCode150-最长连续序列-LC128
* @Author: DSXRIIIII
* @CreateDate: 2024/8/2 21:28
* @Email: lihh53453@hundsun.com
* 可以将set想象成一个桶 不断++取得新的数字
*/
public class LC128 {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
//初始长度为0 因为要对空的数组判断
int result = 0;
for (int num : nums) {
set.add(num);
}
// for (int num : nums) {
// int locLen = 1;
// int currentNum = num;
// while (!set.contains(currentNum - 1)) {
// currentNum += 1;
// locLen += 1;
// }
// result = Math.max(locLen, result);
// }
// return result;
for (int num : nums) {
//上面的方法缺少对这个数是不是最底层的数的判断
//因为题目要求连续那么只能是一直加1连续的数 那么-1判断的逻辑就不能少
if(!set.contains(num - 1)){
//有数字 保底就是1
int locLen = 1;
int currentNum = num;
//不断往前走的逻辑 只要set有+1的数 就是连续并且满足条件的
while (set.contains(currentNum + 1)) {
currentNum += 1;
locLen += 1;
}
result = Math.max(locLen, result);
}
}
return result;
}
}区间
LeetCode150-汇总区间-LC228
/**
* @ProjectName: Mounts
* @Description: 汇总区间-LC228
* @Author: DSXRIIIII
* @CreateDate: 2024/8/2 21:48
* @Email: lihh53453@hundsun.com
* 思路：记录初始位置值 并且不断index++即可
* 要注意while循环条件下
* 1.确保循环条件
* 2.确保不要死循环
*/
public class LC228 {
public List<String> summaryRanges(int[] nums) {
if(nums.length == 0) return new ArrayList<>();
List<String> res = new ArrayList<>();
int index = 0;
while(index < nums.length){
int start = index;
index++;
// while(nums[index - 1] + 1 == nums[index]){
// index+=1;
// }
//这里要添加限定的范围否则index会一直增加
while(index < nums.length && nums[index - 1] + 1 == nums[index]){
index+=1;
}
int location = index - 1;
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(nums[start]);
if(start<location){
stringBuilder.append("->");
stringBuilder.append(nums[location]);
}
res.add(stringBuilder.toString());
}
return res;
}
}LeetCode150-合并区间-LC56
/**
* @ProjectName: Mounts
* @Description: 合并区间-LC56
* @Author: DSXRIIIII
* @CreateDate: 2024/8/3 14:02
* @Email: lihh53453@hundsun.com
* 将新的加入结果集
* 并且与容器内的数组进行比对
*/
public class LC56 {
public int[][] merge(int[][] intervals) {
if(intervals.length == 0) return new int[0][0];
Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
List<int[]> list = new ArrayList<>();
for(int[] arr:intervals){
int left = arr[0],right = arr[1];
if(list.isEmpty() || list.get(list.size() - 1)[1] < left){
list.add(new int[]{left,right});
}else{
list.get(list.size() - 1)[1] = Math.max(right,list.get(list.size() - 1)[1]);
}
}
return list.toArray(new int[list.size()][]);
}
public static void main(String[] args) {
int [][] arr = {{1,2},{2,3}};
List<int[]> arrayList = new ArrayList<>();
arrayList.add(new int[]{1,2});
arrayList.add(new int[]{2,3});
/* 输出结果为
* [[1, 2], [2, 3]]
* [[I@3b07d329
* [[1, 2], [2, 3]]
*/
System.out.println(Arrays.deepToString(arr));
System.out.println(arrayList.toArray(new int[arrayList.size()][]));
System.out.println(Arrays.deepToString(arrayList.toArray(new int[arrayList.size()][])));
}
}
LeetCode150-插入区间-LC57
/**
* @ProjectName: Mounts
* @Description: 插入区间-LC57
* @Author: DSXRIIIII
* @CreateDate: 2024/8/3 14:41
* @Email: lihh53453@hundsun.com
* 这里选择最简单的插入然后排序的方法
* 在排序的过程中也可以选择二分法将nlog(n) -> log(n)
*/
public class LC57 {
public int[][] insert(int[][] intervals, int[] newInterval) {
int[][] arr = Arrays.copyOf(intervals, intervals.length + 1);
arr[arr.length - 1] = new int[2];
arr[arr.length - 1][0] = newInterval[0];
arr[arr.length - 1][1] = newInterval[1];
//Arrays.sort(arr,(num1,num2)->num1[0] - num2[0]);
Arrays.sort(arr, Comparator.comparingInt(num -> num[0]));
List<int[]> res = new ArrayList<>();
for(int[] array:arr){
int left = array[0],right = array[1];
if(res.isEmpty() || res.get(res.size() - 1)[1] < left){
res.add(new int[]{left,right});
}else {
res.get(res.size() - 1)[1] = Math.max(right,res.get(res.size() - 1)[1]);
}
}
return res.toArray(new int[res.size()][]);
}
public static void main(String[] args) {
int[][] arr1 = {{1,2},{2,3}};
int[][] arr2 = Arrays.copyOf(arr1, arr1.length + 1);
System.out.println(Arrays.deepToString(arr2));
}
}LeetCode150-用最少数量的箭引爆气球-LC452
/**
* @ProjectName: Mounts
* @Description: LC452-用最少数量的箭引爆气球
* @Author: DSXRIIIII
* @CreateDate: 2024/8/3 15:04
* @Email: lihh53453@hundsun.com
* 这一题也可以为合并区间的一种写法 采用交集
*/
public class LC452 {
public int[][] findMinArrowShots(int[][] points) {
Arrays.sort(points, Comparator.comparingInt(i -> i[1]));//并交集不同之处 确保不比对的值为最小
List<int[]> res = new ArrayList<>();
for(int[] arr: points){
int left = arr[0],right = arr[1];
if(res.isEmpty() || res.get(res.size() - 1)[1] < left){
res.add(new int[]{left,right});
}else {
res.get(res.size() - 1)[0] = Math.min(res.get(res.size() - 1)[0],left);//并交集不同之处
}
}
return res.toArray(new int[res.size()][]);
}
public static void main(String[] args) {
int[][] arr = {{3,9},{7,12},{3,8},{6,8},{9,10},{2,9},{0,9},{3,9},{0,6},{2,8}};
Arrays.sort(arr, Comparator.comparingInt(i -> i[1]));
System.out.println(Arrays.deepToString(arr));
LC452 lc452 = new LC452();
System.out.println(Arrays.deepToString(lc452.findMinArrowShots(arr)));
}
}
总结
做区间题时需要考虑并交集的选择
- 首先为了方便插入数据，需要创建一个List数组
- 在根据不同并交集的选择 对一号位或者二号位排序
- 当数组列表为空或者右边界比新值小就添加到结果列表
- 否则更新左边界(交集,边界值取最小)/右边界(并集,边界值取最大)
1.将列表转换成int[][]方法res.toArray(new int[res.size()][])
2.排序方法Arrays.sort(points, Comparator.comparingInt(i -> i[1]));
或者Arrays.sort(intervals, (o1, o2) -> o1[0] – o2[0])
推荐使用Comparator