区间

1.汇总区间

1.答案

package com.sunxiansheng.classic150.g1;import java.util.ArrayList;
import java.util.List;/*** Description: 228. 汇总区间** @Author sun* @Create 2024/12/23 13:31* @Version 1.0*/
public class t228 {public static List<String> summaryRanges(int[] nums) {List<String> res = new ArrayList<>();if (nums == null || nums.length == 0) {return res;}// 滑动窗口定义：窗口内的元素需要是连续的int left = 0;for (int right = 0; right < nums.length; right++) {// 加入窗口// 如果发现是不连续的if (right > 0 && nums[right] != nums[right - 1] + 1) {extracted(nums, right, left, res);// 滑动窗口left = right;}}// 对最后一个元素进行操作extracted(nums, nums.length, left, res);return res;}private static void extracted(int[] nums, int right, int left, List<String> res) {// 合法的窗口右下标int wRight = right - 1;// 计算合法窗口元素int count = wRight - left + 1;// 构造结果String element = "";if (count == 1) {// 只有一个元素结果就是这个元素element = String.valueOf(nums[wRight]);} else {// 如果有多个元素，就需要拼接StringBuilder sb = new StringBuilder();sb.append(nums[left]);sb.append("->");sb.append(nums[wRight]);element = sb.toString();}// 添加到结果res.add(element);}public static void main(String[] args) {System.out.println("summaryRanges(new int[]{0,1,2,4,5,7}) = " + summaryRanges(new int[]{0,1,2,4,5,7}));}
}

2.思路

就是使用滑动窗口，窗口内的元素需要是连续的，当发现不合法时，对有一个元素和两个元素进行分别处理即可，并且最后一段需要单独处理

2.合并区间

1.答案

package com.sunxiansheng.classic150.g1;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;/*** Description: 56. 合并区间** @Author sun* @Create 2024/12/23 17:20* @Version 1.0*/
public class t56 {public static int[][] merge(int[][] intervals) {// 【1，6】【2，5】【3，4】【100，200】// 按照数组的第一个元素进行排序Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));List<int[]> list = new ArrayList<>();// 记录当前合并的数组int[] cur = new int[2];cur[0] = intervals[0][0];cur[1] = intervals[0][1];// 遍历二维数组for (int i = 1; i < intervals.length; i++) {// 能合就合并if (intervals[i][0] <= cur[1]) {cur[1] = Math.max(cur[1], intervals[i][1]);} else {// 不能合并就记录结果，并更新curlist.add(new int[]{cur[0], cur[1]});cur[0] = intervals[i][0];cur[1] = intervals[i][1];}}// 记录最后一个元素的结果list.add(new int[]{cur[0], cur[1]});return list.toArray(new int[0][0]);}
}

2.思路

使用一个临时变量去记录前一个合并后的数组，然后遍历二维数组，如果能合并就合并，不能合并就记录结果并更新cur

3.插入区间

1.答案

package com.sunxiansheng.classic150.g1;import java.util.ArrayList;
import java.util.List;/*** Description: 57. 插入区间** @Author sun* @Create 2024/12/23 18:27* @Version 1.0*/
public class t57 {public static int[][] insert(int[][] intervals, int[] newInterval) {if (intervals == null || intervals.length == 0) {int[][] res = new int[1][2];res[0] = newInterval;return res;}//【1，5】【0，3】int[][] newArr = null;// 寻找插入位置if (intervals[0][0] >= newInterval[0]) {newArr = new int[intervals.length + 1][2];newArr[0] = newInterval;for (int i = 0; i < intervals.length; i++) {newArr[i + 1] = intervals[i];}} else {int index = -1;for (int i = 0; i < intervals.length; i++) {if (i == intervals.length - 1 && index == -1) {index = i;break;}if (newInterval[0] >= intervals[i][0] && newInterval[0] <= intervals[i + 1][0]) {index = i;break;}}// 新数组newArr = new int[intervals.length + 1][2];for (int i = 0; i <= index; i++) {newArr[i] = intervals[i];}newArr[index + 1] = newInterval;if (index + 1 != newArr.length - 1) {for (int i = index + 1; i < intervals.length; i++) {newArr[i + 1] = intervals[i];}}}int[][] res = getInts(newArr);return res;}private static int[][] getInts(int[][] newArr) {// 对新数组进行合并区间List<int[]> list = new ArrayList<>();// 记录当前合并的数组int[] cur = new int[2];cur[0] = newArr[0][0];cur[1] = newArr[0][1];// 遍历二维数组for (int i = 1; i < newArr.length; i++) {// 能合就合并if (newArr[i][0] <= cur[1]) {cur[1] = Math.max(cur[1], newArr[i][1]);} else {// 不能合并就记录结果，并更新curlist.add(new int[]{cur[0], cur[1]});cur[0] = newArr[i][0];cur[1] = newArr[i][1];}}// 记录最后一个元素的结果list.add(new int[]{cur[0], cur[1]});int[][] res = list.toArray(new int[0][0]);return res;}public static void main(String[] args) {insert(new int[][]{{1, 5},}, new int[]{0, 3});}
}

2.思路

就是先插入到指定位置然后再对新数组进行合并区间

4.用最少数量的箭引爆气球

1.答案

package com.sunxiansheng.classic150.g1;import java.util.Arrays;
import java.util.Comparator;/*** Description: 452. 用最少数量的箭引爆气球** @Author sun* @Create 2024/12/24 08:46* @Version 1.0*/
public class t452 {public static int findMinArrowShots(int[][] points) {if (points.length == 1) {return 1;}// 首先根据数组的第一个元素进行从小到大的排序Arrays.sort(points, Comparator.comparingInt(a -> a[0]));int res = 0;// 记录前一个交集int[] prev = new int[2];prev[0] = points[0][0];prev[1] = points[0][1];// 遍历，有交集就求交集for (int i = 1; i < points.length; i++) {// 有交集if (points[i][0] <= prev[1]) {prev[0] = Math.max(prev[0], points[i][0]);prev[1] = Math.min(prev[1], points[i][1]);} else {// 没有交集，就记录结果res++;// 然后更新一下前一个交集为当前交集prev = points[i];}}// 需要将res加一，因为少算了最后一个结果return ++res;}
}

2.思路

就是跟合并区间类似的思路，不过这次换成了求交集而已

栈

1.有效的括号

1.答案

package com.sunxiansheng.classic150.g1;import java.util.Stack;/*** Description: 20. 有效的括号** @Author sun* @Create 2024/12/24 09:19* @Version 1.0*/
public class t20 {public static boolean isValid(String s) {// 左括号入栈，右括号匹配Stack<Character> stack = new Stack<>();// 遍历一下for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 左括号入栈if (c == '[' || c == '(' || c == '{') {stack.push(c);}// 右括号匹配if (c == ']' || c == ')' || c == '}') {// 如果栈为空，直接直接返回falseif (stack.isEmpty()) {return false;}// 栈不为空就匹配if (!match(stack.pop(), c)) {return false;}}}// 如果循环结束并且栈为空，就返回truereturn stack.isEmpty();}private static boolean match(Character characterA, Character characterB) {if (characterA == '(' && characterB != ')') {return false;}if (characterA == '[' && characterB != ']') {return false;}if (characterA == '{' && characterB != '}') {return false;}return true;}
}

2.思路

左括号入栈，右括号匹配，注意栈空的情况

2.简化路径

1.答案

package com.sunxiansheng.classic150.g1;import java.util.Arrays;
import java.util.Stack;/*** Description: 71. 简化路径** @Author sun* @Create 2024/12/24 09:28* @Version 1.0*/
public class t71 {public static String simplifyPath(String path) {// 以 / 进行分割String[] split = path.split("/+");System.out.println("split = " + Arrays.toString(split));Stack<String> stack = new Stack<>();// 遍历for (int i = 1; i < split.length; i++) {stack.push(split[i]);// 如果只包含点，就判断有几个点，有几个点就pop几次if (split[i].matches("\\.+")) {int length = split[i].length();// 如果length小于3才要popif (length < 3) {for (int j = 0; j < length; j++) {// 如果发现了栈都空了还pop，就直接breakif (stack.isEmpty()) {break;}stack.pop();}}}}// 如果目前栈就已经是空的了直接返回 /if (stack.isEmpty()) {return "/";}// 进行结果的拼接String s = putTogether(stack);return s;}/*** 递归拼接结果** @param stack* @return*/private static String putTogether(Stack<String> stack) {// 直到栈为空if (stack.isEmpty()) {return "";}// popString pop = stack.pop();String s = putTogether(stack);return s + "/" + pop;}public static void main(String[] args) {String s = simplifyPath("/../..ga/b/.f..d/..../e.baaeeh./.a");System.out.println("s = " + s);}
}

2.思路

思路很复杂，根据题意调试

3.最小栈

1.答案

package com.sunxiansheng.classic150.g1;import java.util.Stack;/*** Description: 155. 最小栈** @Author sun* @Create 2024/12/24 10:26* @Version 1.0*/
public class MinStack {// 一个最小栈一个辅助栈Stack<Integer> minStack;Stack<Integer> stack;public MinStack() {minStack = new Stack<>();stack = new Stack<>();// 最小栈先要加入一个最大的元素minStack.push(Integer.MAX_VALUE);}public void push(int val) {// 压栈压最小stack.push(val);minStack.push(Math.min(minStack.peek(), val));}public void pop() {// pop都出去stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

2.思路

压栈压最小，pop都出去

4.逆波兰表达式求值

1.答案

package com.sunxiansheng.classic150.g1;import java.util.Stack;/*** Description: 150. 逆波兰表达式求值** @Author sun* @Create 2024/12/24 10:48* @Version 1.0*/
public class t150 {public static int evalRPN(String[] tokens) {// 数字压栈，表达式求值Stack<Integer> stack = new Stack<>();for (int i = 0; i < tokens.length; i++) {if (isDigit(tokens[i])) {stack.push(Integer.valueOf(tokens[i]));} else {// 求值Integer right = stack.pop();Integer left = stack.pop();switch (tokens[i]) {case "+":stack.push(left + right);break;case "-":stack.push(left - right);break;case "*":stack.push(left * right);break;case "/":stack.push(left / right);break;default:break;}}}return stack.pop();}// 判断是否是数字private static boolean isDigit(String s) {return !"+".equals(s) && !"-".equals(s) && !"*".equals(s) && !"/".equals(s);}
}

2.思路

数字压栈，表达式求值