算法解析-经典150（区间、栈）

区间

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 {
                // 不能合并就记录结果，并更新cur
                list.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 {
                // 不能合并就记录结果，并更新cur
                list.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 == '}') {
                // 如果栈为空，直接直接返回false
                if (stack.isEmpty()) {
                    return false;
                }
                // 栈不为空就匹配
                if (!match(stack.pop(), c)) {
                    return false;
                }
            }
        }
        // 如果循环结束并且栈为空，就返回true
        return 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才要pop
                if (length < 3) {
                    for (int j = 0; j < length; j++) {
                        // 如果发现了栈都空了还pop，就直接break
                        if (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 "";
        }
        // pop
        String 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.思路

数字压栈，表达式求值