算法基础第四天

844. 比较含退格的字符串

退格，可以使用stack的特性来处理。也可以使用双指针来处理。。试了下栈的效率还是明显低于双指针的。

/**
 844. 比较含退格的字符串
 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

 注意：如果对空文本输入退格字符，文本继续为空。



 示例 1：

 输入：s = "ab#c", t = "ad#c"
 输出：true
 解释：s 和 t 都会变成 "ac"。
 示例 2：

 输入：s = "ab##", t = "c#d#"
 输出：true
 解释：s 和 t 都会变成 ""。
 示例 3：

 输入：s = "a#c", t = "b"
 输出：false
 解释：s 会变成 "c"，但 t 仍然是 "b"。


 提示：

 1 <= s.length, t.length <= 200
 s 和 t 只含有小写字母以及字符 '#'


 进阶：

 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

 * @author zeroheart
 *
 */
public class Question844 {
    public boolean backspaceCompare(String s, String t) {
        // equals()判断返回的两个字符串是否相等
        return changeString(s).equals(changeString(t));
    }

    public static String changeString (String str) {
        //https://leetcode-cn.com/problems/backspace-string-compare/solution/shuang-zhi-zhen-fa-si-lu-jian-dan-rong-y-bmn6/
        // 先将字符串转为数组，方便使用双指针法
        char[] x = str.toCharArray();
        int slow = 0;
        for (int fast = 0; fast < x.length; fast++) {
            // 当x[fast] != '#'时，x[fast]覆盖x[slow]，然后slow++
            if (x[fast] != '#'){
                x[slow++] = x[fast];
            } else if(x[fast] == '#' && slow != 0){
                // 当x[fast] = '#'且slow!=0时，slow--
                slow--;
            }
        }

        // 返回字符串
        return String.valueOf(x, 0, slow);

    }


    public boolean backspaceCompare1(String s, String t) {
        //https://leetcode-cn.com/problems/backspace-string-compare/solution/javazhan-jie-fa-by-ilovediana-tl5q/
        Stack<Character> st1 = new Stack<>();
        Stack<Character> st2 = new Stack<>();
        for (Character c : s.toCharArray()) {
            if (c != '#') {
                st1.push(c);
            }
            else if (!st1.isEmpty()) {
                st1.pop();
            }
        }
        for (Character c : t.toCharArray()) {
            if (c != '#') {
                st2.push(c);
            }
            else if (!st2.isEmpty()) {
                st2.pop();
            }
        }
        while (!st1.isEmpty() && !st2.isEmpty()) {
            if (st1.pop() != st2.pop()) {
                return false;
            }
        }
        return st1.isEmpty() && st2.isEmpty();
    }


    public static void main(String[] args) {
    }
}

986. 区间列表的交集

这个题目主要是归并区间，看题解吧。。

/**
 986. 区间列表的交集
 给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

 返回这 两个区间列表的交集 。

 形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

 两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。



 示例 1：


 输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
 输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
 示例 2：

 输入：firstList = [[1,3],[5,9]], secondList = []
 输出：[]
 示例 3：

 输入：firstList = [], secondList = [[4,8],[10,12]]
 输出：[]
 示例 4：

 输入：firstList = [[1,7]], secondList = [[3,10]]
 输出：[[3,7]]


 提示：

 0 <= firstList.length, secondList.length <= 1000
 firstList.length + secondList.length >= 1
 0 <= starti < endi <= 109
 endi < starti+1
 0 <= startj < endj <= 109
 endj < startj+1

 * @author zeroheart
 *
 */
public class Question986 {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        //https://leetcode-cn.com/problems/interval-list-intersections/solution/jiu-pa-ni-bu-dong-shuang-zhi-zhen-by-hyj8/
        /**
         * 怎么求交集区间
         * 注意绿色箭头，交集区间的 start 取的是 A、B 子区间中较大的左界。
         * 注意红色箭头，交集区间的 end 取的是 A、B 子区间中较小的右界。
         * 只要满足 start <= end，就形成了一个交集区间。
         *
         * 双指针移动的时机
         * 求完一个交集区间后，较早结束的子区间，不可能再和别的子区间重叠，它的指针要移动。
         * 较长的子区间还有可能和别人重叠，它的指针暂时不动。
         *
         */
        int i = 0;
        int j = 0;
        List<int[]> res = new ArrayList();
        while (i < firstList.length && j < secondList.length){
            int low = Math.max(firstList[i][0], secondList[j][0]);
            int high = Math.min(firstList[i][1], secondList[j][1]);

            if(low <= high){
                res.add(new int[]{low, high});
            }

            if(firstList[i][1] < secondList[j][1]){
                i++;// 谁先结束，谁的指针就步进，考察下一个子区间
            }else {
                j++;
            }
        }

        return res.toArray(new int[res.size()][]);

    }

    public static void main(String[] args) {
    }
}

11. 盛最多水的容器

/**
 11. 盛最多水的容器
 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

 返回容器可以储存的最大水量。

 说明：你不能倾斜容器。



 示例 1：



 输入：[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


 提示：

 n == height.length
 2 <= n <= 10^5
 0 <= height[i] <= 10^4

 * @author zeroheart
 *
 */
public class Question11 {
    public int maxArea(int[] height) {
        int len = height.length;
        int low = 0;
        int high = len - 1;
        int max = 0;
        while (low < high){
            max = Math.max(max, (high - low) * Math.min(height[low], height[high]));
            if(height[low] > height[high]){
                // 保留大的一边
                high --;
            }else {
                low ++;
            }
        }
        return max;
    }
    public static void main(String[] args) {
    }
}