'数据结构与算法 训练营一期'

训练营一期

窗口滑动

滑动窗口是什么？

滑动窗口是一种想象出来的数据结构：
滑动窗口有左边界L和有边界R
在数组或者字符串或者一个序列上，记为S，窗口就是S[L..R]这一部分
L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
L和R都只能往右滑

滑动窗口能做什么？
滑动窗口、首尾指针等技巧，说白了是一种求解问题的流程设计。

滑动内最大值和最小值的更新结构:
窗口不管L还是R滑动之后，都会让窗口呈现新状况，
如何能够更快的得到窗口当前状况下的最大值和最小值？
最好平均下来复杂度能做到O(1)
利用单调双端队列！

思想：使用单调双端队列（头部由大到小）(队列里存储的是数组下标)
当R新增的值V比队列尾部的最小值X大，则弹出X，再次比较，直到队列的尾部数据比V大，或者队列为空，压入V值。
当L移动时，比较当前下标和队列下标，若相等，则弹出。
获取滑动窗口内当前最大值：peek队列头部

总代价：O(N) 每次平均：O(1)

题目一:
假设一个固定大小为W的窗口，依次划过arr，
返回每一次滑出状况的最大值
例如，arr = [4,3,5,4,3,3,6,7], W = 3
返回：[5,5,5,4,6,7]

public static int[] getMaxWindow(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
        return null;
    }
    // 其中放的是位置，头代表 （大->小）尾
    LinkedList<Integer> qmax = new LinkedList<Integer>();
    int[] res = new int[arr.length - w + 1];
    int index = 0;
    // L...R
    //     i
    for (int R = 0; R < arr.length; R++) { // 当前让 i -> [i] 进窗口 ， i 就是 r
        // R -> 值  可以放在比他大的数后，或者空
        while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
            qmax.pollLast();
        }
        qmax.addLast(R);
        // 数进来了
        // 如果窗口没有形成W的长度之前，不弹出数字的
        if (qmax.peekFirst() == R - w) {
            qmax.pollFirst();
        }
        // 以上窗口更新做完了
        if (R >= w - 1) {
            res[index++] = arr[qmax.peekFirst()];
        }
    }
    return res;
}

题目二:
给定一个整型数组arr，和一个整数num
某个arr中的子数组sub，如果想达标，必须满足：
sub中最大值 – sub中最小值 <= num，
返回arr中达标子数组的数量

思路：
一个[L ~ R]窗口内，如果他达标，那么在[L ~ R]缩小范围内的子数组必定达标。
一个[L ~ R]窗口内，如果他不达标，那么在[L ~ R]扩大范围内的数组必定不达标。

两个滑动窗口，一个存储MAX，一个存储MIN，MAX - MIN <= num,一直滑动 (R = R +1)
当左闭右开区间：[L ~ R) 的 MAX-MIN>num 时停下来（R 进队列）
当前滑动的R - L就是当前以L开头达标的子数组数量
然后L + 1，再次判断 当前 L ~ R + 1的 Max-MIN > num ? 周而复始

public static int getNum(int[] arr, int num) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    LinkedList<Integer> qmin = new LinkedList<Integer>();
    LinkedList<Integer> qmax = new LinkedList<Integer>();
    int L = 0;
    int R = 0;
    // [L..R) -> [0,0) 窗口内无数 [1,1)
    // [0,1) -> [0~0]
    int res = 0;
    while (L < arr.length) { // L是开头位置，尝试每一个开头

        // 如果此时窗口的开头是L,下面的while工作:R向右扩到违规为止

        while (R < arr.length) { // R是最后一个达标位置的再下一个
            while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[R]) {
                qmin.pollLast();
            }
            qmin.addLast(R);
            // R -> arr[R],
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                qmax.pollLast();
            }
            qmax.addLast(R);
      
            //当不达标时break，结算达标的数据
            if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
                break;
            }
            R++;
        }

        // R是最后一个达标位置的再下一个，第一个违规的位置
        res += R - L;
    
        //L要向右移动，判断窗口内的数据index是否过期
        if (qmin.peekFirst() == L) {
            qmin.pollFirst();
        }
        if (qmax.peekFirst() == L) {
            qmax.pollFirst();
        }

        L++;

    }
    return res;
}

单调栈

单调栈是什么？

一种特别设计的栈结构，为了解决如下的问题：

给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息
1）arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪？
2）arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪？
如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。

那么到底怎么设计呢？

思想：一个栈，从栈底到栈顶由小到大，如果压入的值V比栈顶的X小，则弹出X， 
X左侧最近最小值则是栈中X下的值，X右侧最近最小值则是压入的V值
栈中可以通过存储一个数组（存储重复值的index）的形式（解决数据相等的问题）

时间复杂度：O(N)

// arr [3, 2, 1, 4, 5]
//      0  1  2  3  4

//  [
//    0 :  [-1,  1  ]
//    1 :  [-1,  2  ]
//    ...
//  ] 
//
public static int[][] getNearLess(int[] arr) {
    int[][] res = new int[arr.length][2];

    // List<Integer> -> 放的是位置，同样值的东西，位置压在一起
    // 代表值    底  ->  顶   小  -> 大
    Stack<List<Integer>> stack = new Stack<>();
    for (int i = 0; i < arr.length; i++) { // i -> arr[i] 进栈
        // 底 -> 顶， 小 -> 大
        //当栈中为空或者栈顶元素大于压入栈的元素时，弹出栈顶元素进行结算
        while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
            List<Integer> popIs = stack.pop();
            // 取位于下面位置的列表中，最晚加入的那个的数组index
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            //栈中相同值，不同index的数据，他们的答案都是一样的
            for (Integer popi : popIs) {
                res[popi][0] = leftLessIndex;
                res[popi][1] = i;
            }
        }
        // 如果压入的值和栈顶中的值相等的、加到栈顶的数组index列表中
        if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
            stack.peek().add(Integer.valueOf(i));
        } else {
            //如果压入的值比栈顶的值小，新开辟一个数组，压入栈
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            stack.push(list);
        }
    }
    //遍历结束，栈中还有元素，弹出结算
    while (!stack.isEmpty()) {
        List<Integer> popIs = stack.pop();
        // 取位于下面位置的列表中，最晚加入的那个
        int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
        for (Integer popi : popIs) {
            res[popi][0] = leftLessIndex;
            res[popi][1] = -1;
        }
    }
    return res;
}

题目三：
给定一个只包含正整数的数组arr，arr中任何一个子数组sub，
一定都可以算出(sub累加和 )* (sub中的最小值)是什么，
那么所有子数组中，这个值最大是多少？

public static int max(int[] arr) {
    int size = arr.length;
    int[] sums = new int[size];
    sums[0] = arr[0];
    for (int i = 1; i < size; i++) {
        sums[i] = sums[i - 1] + arr[i];
    }
    int max = Integer.MIN_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < size; i++) {
        //当arr[i]小于 栈顶元素时，结算栈中大于i的值，每次弹出一个值
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            int j = stack.pop();
            //以j下标的元素做最小值，计算[peck().... j ....i] 区间的结果
            max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int j = stack.pop();
        max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
    }
    return max;
}

斐波那契数列

10^75次方怎么计算最快？
75 = 64 + 8 + 2 + 1 = 1001011 

定义t = 10^1 ，每次循环，t = t * t， 二进制 1001011 位上为1，则result * t
所以10^75 = 10^64 * 10^8 * 10^2 * 10^1 其中 t自乘了6次
O(log75)

1）斐波那契数列的线性求解（O(N)）的方式非常好理解
2）同时利用线性代数，也可以改写出另一种表示
 | F(N) , F(N-1) | = | F(2), F(1) |  *  某个二阶矩阵的N-2次方
3）求出这个二阶矩阵，进而最快求出这个二阶矩阵的N-2次方

public static int f3(int n) {
    if (n < 1) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return 1;
    }
    // [ 1 ,1 ]
    // [ 1, 0 ]
    int[][] base = { 
        { 1, 1 }, 
        { 1, 0 } 
    };
    int[][] res = matrixPower(base, n - 2);
    return res[0][0] + res[1][0];
}

//求某个矩阵的 p次方
public static int[][] matrixPower(int[][] m, int p) {
    int[][] res = new int[m.length][m[0].length];
    for (int i = 0; i < res.length; i++) {
        res[i][i] = 1;
    }

    // res = 矩阵中的1 单位矩阵
    int[][] tmp = m;// 矩阵1次方
    for (; p != 0; p >>= 1) {
        if ((p & 1) != 0) {
            res = muliMatrix(res, tmp);
        }
        tmp = muliMatrix(tmp, tmp);
    }
    return res;
}

// 两个矩阵乘完之后的结果返回
public static int[][] muliMatrix(int[][] m1, int[][] m2) {
    int[][] res = new int[m1.length][m2[0].length];
    for (int i = 0; i < m1.length; i++) {
        for (int j = 0; j < m2[0].length; j++) {
            for (int k = 0; k < m2.length; k++) {
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    return res;
}

类似斐波那契数列的递归优化

如果某个递归，除了初始项之外，具有如下的形式

F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常数)

并且这个递归的表达式是严格的、不随条件转移的

那么都存在类似斐波那契数列的优化，时间复杂度都能优化成O(logN)
 

F(N) = F(N-1) + F(N-1) 是一个二阶系数问题
公式：|F(N),F(N- K + 1)| = |F(1),F(2)...F(K)| * 某个K阶矩阵的N-K次方

题目二：
第一年农场有1只成熟的母牛A，往后的每年：
1）每一只成熟的母牛都会生一只母牛
2）每一只新出生的母牛都在出生的第三年成熟
3）每一只母牛永远不会死
返回N年后牛的数量

public static int c3(int n) {
    if (n < 1) {
        return 0;
    }
    if (n == 1 || n == 2 || n == 3) {
        return n;
    }
    int[][] base = { 
        { 1, 1, 0 }, 
        { 0, 0, 1 }, 
        { 1, 0, 0 } };
    int[][] res = matrixPower(base, n - 3);
    //          {|x1,x2,x3|
    //|3,2,1| *  |y1,y2,y3|    =  3 * x1 + 2 * y1 + 1 * z1
    //           |z1,z2,z3|}
    return 3 * res[0][0] + 2 * res[1][0] + res[2][0];
}

题目三
一个人可以一次往上迈1个台阶，也可以迈2个台阶
返回这个人迈上N级台阶的方法数

思路：
最后一次迈台阶，分迈1个台阶和2个台阶，所以f(n) = f(n - 1) + f(n - 2)
和斐波那契数列唯一不同的，就是基数[1,1] 和 [1,2]的区别，其他矩阵计算均相同

给定一个数N，想象只由0和1两种字符，组成的所有长度为N的字符串
如果某个字符串,任何0字符的左边都有1紧挨着,认为这个字符串达标
返回有多少达标的字符串

思路：
如果f(n)第一个字符是0，[0.....]，那么不管后续怎么变化，都不满足结果
所以f(n) = [1 [n-1....]]
n - 1 位置 = 0 的话，第三个位置只能是1，也就是f(n - 2) 的结果
n - 1 位置 = 1 的话，第三个位置可以是0，可以是1，也就是f(n - 1)的结果
所以f(n) = f(n - 1) + f(n - 2)

给定一个黑盒函数f(),等概率返回1~7，请问怎么封装该函数返回等概率1~10？

思路：
把1~3的值当做0,4~6的值当做1，摇到7则重新摇，然后组装二进制[0000] 摇4次填入二进制值，大于10则重新摇

给定一个黑盒函数f()，P概率返回0,1-P的概率返回1，请问怎么封装成等概率返回0和1？

思路：
二进制[00]，把摇到的结果塞进二进制，若出现[00]或者[11]则重新摇，出现[01]或者[10]的概率都是p * (1 - p)

蓄水池算法

解决的问题：

假设有一个源源吐出不同球的机器，
只有装下10个球的袋子，每一个吐出的球，要么放入袋子，要么永远扔掉
如何做到机器吐出每一个球之后，所有吐出的球都等概率被放进袋子里

思想：
前十个球直接丢到袋子中，当11号球未吐出之前，入袋子的概率是100%，当第N个球吐出后，设定他入袋的概率是10/N
假设1号球被扔掉，那么它的概率被扔掉的概率是(10/N) * (1/10) = 1/N
那么11号球入袋后1号球还在袋子的概率就是 1 * (1 - 1/11) = 10/11
以此类推，当有N号球入袋后，1号球还在袋子中的概率是10/N

假设11号球以10/11的概率入袋了，当吐出12号球时，11号球还在袋的概率是：
10/11 * (1 - (10/12 * 1/10)) = 10/12
以此类推，当吐出N个球时，前面的球在袋子中的概率都是10/N，概率均等。

public static class RandomBox {
    private int[] bag;
    private int N;
    private int count;

    public RandomBox(int capacity) {
        bag = new int[capacity];
        N = capacity;
        count = 0;
    }

    private int rand(int max) {
        return (int) (Math.random() * max) + 1;
    }

    public void add(int num) {
        count++;
        if (count <= N) {
            bag[count - 1] = num;
        } else {
            if (rand(count) <= N) {
                bag[rand(N) - 1] = num;
            }
        }
    }

    public int[] choices() {
        int[] ans = new int[N];
        for (int i = 0; i < N; i++) {
            ans[i] = bag[i];
        }
        return ans;
    }

}

KMP算法

假设字符串str长度为N，字符串match长度为M，M <= N
想确定str中是否有某个子串是等于match的。
时间复杂度O(N)

暴力过程: 
i位置匹配match 0位置
str x位置, match y位置不同, 往回跳 str --> i+1, match 回 0位置
时间复杂度O(N^2)

KMP算法核心
1）如何理解next数组
2）如何利用next数组加速匹配过程，优化时的两个实质！

next[arr.length + 1]数组：
字符串以index = i结尾，[0..i-1]的区间上，前缀字符和后缀字符最长匹配长度，前缀和后缀不能囊括整个区间
如aabaac  arr[i] = c,那么next[i] = 2
next[0] = -1 ,人为规定
next[1] = 0 ,因为长度 1 的字符左边没有字符了

1.i位置不需要像暴力递归那样往回跳
2.j位置可以回跳到next[j] = k的位置接着比较

因为：str[0..i-1] = match[0..i-1]
     match[0..k] = match[0..j-k]
所以：match[0..k] = str[i-k..i-1]

所以接着判断 match[k+1] ?= str[i]

为什么 str[0..i-k]位置不需要再比较？
因为以[0..i-k]做起点，上若存在和match匹配的结果
那么next[j] = k 这个值必然会变得更长，但是next数组的含义就是最长匹配长度,怎么还能找到更长的呢?

// O(N)
public static int getIndexOf(String s, String m) {
    if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
        return -1;
    }
    char[] str = s.toCharArray();
    char[] match = m.toCharArray();
    int x = 0; // str中当前比对到的位置
    int y = 0; // match中当前比对到的位置
    // M  M <= N   O(M)
    int[] next = getNextArray(match); // next[i]  match中i之前的字符串match[0..i-1]
    // O(N)
    while (x < str.length && y < match.length) {
        if (str[x] == match[y]) {
            x++;
            y++;
        } else if (next[y] == -1) { // y == 0
            x++;
        } else {
            y = next[y];
        }
    }
    //当x 越界 若 y不越界，则表示当前y索引不等于match长度，返回-1
    //当x 越界 若 y也越界，表示y等于x的末尾串
    //当y 越界 则返回 y在x的中的index
    return y == match.length ? x - y : -1;
}

// M   O(M)
//获取match字符中，每i个字符的 [0 ~ i-1]位置，头部和尾部相等得到字符长度
public static int[] getNextArray(char[] match) {
    if (match.length == 1) {
        return new int[] { -1 };
    }
    int[] next = new int[match.length];
    next[0] = -1;  //默认第一个字符是-1
    next[1] = 0;   //默认第二个字符是0，因为前面只有一个字符
    int i = 2;
    // cn代表，cn位置的字符，是当前和i-1位置比较的字符 等价：cn = next[i - 1]
    int cn = 0;
    while (i < next.length) {
        if (match[i - 1] == match[cn]) { // 跳出来的时候
            next[i++] = ++cn;
            //等同于以下三句：
            //next[i] = cn + 1  当匹配到等长的字符时
            // i++; 移动指针
            // cn++; 由于cn = next[i - 1]，而cn也要向右移动一步
        } else if (cn > 0) {
            //如果不相等，则跳到next[i - 1]上继续对比
            cn = next[cn];
        } else {
            next[i++] = 0;
        }
    }
    return next;
}

有一个字符串X,判断另一个字符串V是否是该字符串的这种结构：
x = "123456" V = "234561"  结果：true
x = "123456" V = "345612"  结果：true
x = "123456" V = "456123"  结果：true
x = "123456" V = "234516"  结果: false

思路：把"123456"自身头尾拼接，变成 “123456123456”，只要该字符串包含V，则正确

给定两棵二叉树的头节点head1和head2

想知道head1中是否有某个子树的结构和head2完全一样

// 暴力递归
// big做头节点的树，其中是否有某棵子树的结构，是和small为头的树，完全一样的
// 时间复杂度：O(big.size * small.size)
public static boolean containsTree1(Node big, Node small) {
    if (small == null) {
        return true;
    }
    // small != null
    if (big == null) {
        return false;
    }
    // big！=null  small!=null
    if (isSameValueStructure(big, small)) {
        return true;
    }
    return containsTree1(big.left, small) || containsTree1(big.right, small);
}

// head1为头的树，是否在结构对应上，完全和head2一样
public static boolean isSameValueStructure(Node head1, Node head2) {
    if (head1 == null && head2 != null) {
        return false;
    }
    if (head1 != null && head2 == null) {
        return false;
    }
    if (head1 == null && head2 == null) {
        return true;
    }
    if (head1.value != head2.value) {
        return false;
    }
    // head1.value == head2.value
    return isSameValueStructure(head1.left, head2.left) 
        && isSameValueStructure(head1.right, head2.right);
}

//KMP算法
//思想：对big和small做先序遍历，用KMP比较生成的两个数组
public static boolean containsTree2(Node big, Node small) {
    if (small == null) {
        return true;
    }
    if (big == null) {
        return false;
    }
    ArrayList<String> b = preSerial(big);
    ArrayList<String> s = preSerial(small);
    String[] str = new String[b.size()];
    for (int i = 0; i < str.length; i++) {
        str[i] = b.get(i);
    }

    String[] match = new String[s.size()];
    for (int i = 0; i < match.length; i++) {
        match[i] = s.get(i);
    }
    return getIndexOf(str, match) != -1;
}

//先序遍历
public static ArrayList<String> preSerial(Node head) {
    ArrayList<String> ans = new ArrayList<>();
    pres(head, ans);
    return ans;
}

public static void pres(Node head, ArrayList<String> ans) {
    if (head == null) {
        ans.add(null);
    } else {
        ans.add(String.valueOf(head.value));
        pres(head.left, ans);
        pres(head.right, ans);
    }
}

//这里为什么用两个数组？如果拼接成两个字符串会有什么后果？
//原因：123_1_n_n_n 和 23_1_n_n_n 会造成子串匹配，但这不是我们想要的结果。
public static int getIndexOf(String[] str1, String[] str2) {
    if (str1 == null || str2 == null || str1.length < 1 || str1.length < str2.length) {
        return -1;
    }
    int x = 0;
    int y = 0;
    int[] next = getNextArray(str2);
    while (x < str1.length && y < str2.length) {
        if (isEqual(str1[x], str2[y])) {
            x++;
            y++;
        } else if (next[y] == -1) {
            x++;
        } else {
            y = next[y];
        }
    }
    return y == str2.length ? x - y : -1;
}

public static int[] getNextArray(String[] ms) {
    if (ms.length == 1) {
        return new int[] { -1 };
    }
    int[] next = new int[ms.length];
    next[0] = -1;
    next[1] = 0;
    int i = 2;
    int cn = 0;
    while (i < next.length) {
        if (isEqual(ms[i - 1], ms[cn])) {
            next[i++] = ++cn;
        } else if (cn > 0) {
            cn = next[cn];
        } else {
            next[i++] = 0;
        }
    }
    return next;
}

public static boolean isEqual(String a, String b) {
    if (a == null && b == null) {
        return true;
    } else {
        if (a == null || b == null) {
            return false;
        } else {
            return a.equals(b);
        }
    }
}

bfprt算法

题目：
在无序数组中求第K小的数
1）改写快排的方法
2）bfprt算法

// 改写快排，时间复杂度O(N)
public static int minKth2(int[] array, int k) {
    int[] arr = copyArray(array);
    return process2(arr, 0, arr.length - 1, k - 1);
}

public static int[] copyArray(int[] arr) {
    int[] ans = new int[arr.length];
    for (int i = 0; i != ans.length; i++) {
        ans[i] = arr[i];
    }
    return ans;
}

// arr 第k小的数
// process2(arr, 0, N-1, k-1)
// arr[L..R]  范围上，如果排序的话(不是真的去排序)，找位于index的数
// index [L..R]
public static int process2(int[] arr, int L, int R, int index) {
    if (L == R) { // L = =R ==INDEX
        return arr[L];
    }
    // 不止一个数  L +  [0, R -L]
    int pivot = arr[L + (int) (Math.random() * (R - L + 1))];

    // range[0] range[1]
    //  L   ..... R     pivot 
    //  0         1000     70...800
    int[] range = partition(arr, L, R, pivot);
    if (index >= range[0] && index <= range[1]) {
        return arr[index];
    } else if (index < range[0]) {
        return process2(arr, L, range[0] - 1, index);
    } else {
        return process2(arr, range[1] + 1, R, index);
    }
}

public static int[] partition(int[] arr, int L, int R, int pivot) {
    int less = L - 1;
    int more = R + 1;
    int cur = L;
    while (cur < more) {
        if (arr[cur] < pivot) {
            swap(arr, ++less, cur++);
        } else if (arr[cur] > pivot) {
            swap(arr, cur, --more);
        } else {
            cur++;
        }
    }
    return new int[] { less + 1, more - 1 };
}

public static void swap(int[] arr, int i1, int i2) {
    int tmp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = tmp;
}

思想：
bfprt算法的后续步骤和快排是相同的，唯一不同的是，它要精挑细选出第一次的pivot（快排是用随机生成）
数组长度为N，bfprt(arr, k)通过对数据进行分组，每5个一组，然后每个组内自行排序:O(1)，N/5个小组，则是O(N)
取每个小组的中位数组成新数组marr，再对marr取第marr.length/2小的值bfprt(marr, marr.length/2)
这样对挑出的值进行partition，能够保证左右分组最少有(3/10)N个数。

// 利用bfprt算法，时间复杂度O(N)
public static int minKth3(int[] array, int k) {
    int[] arr = copyArray(array);
    return bfprt(arr, 0, arr.length - 1, k - 1);
}

// arr[L..R]  如果排序的话，位于index位置的数，是什么，返回
public static int bfprt(int[] arr, int L, int R, int index) {
    if (L == R) {
        return arr[L];
    }
    //计算partition合适的值做划分
    int pivot = medianOfMedians(arr, L, R);
    int[] range = partition(arr, L, R, pivot);
    //如果k落在partition的区间上，则命中，否则继续bfprt左右其中一个分区
    if (index >= range[0] && index <= range[1]) {
        return arr[index];
    } else if (index < range[0]) {
        return bfprt(arr, L, range[0] - 1, index);
    } else {
        return bfprt(arr, range[1] + 1, R, index);
    }
}

// arr[L...R]  五个数一组
// 每个小组内部排序
// 每个小组中位数领出来，组成marr
// marr中的中位数，返回
public static int medianOfMedians(int[] arr, int L, int R) {
    int size = R - L + 1;
    int offset = size % 5 == 0 ? 0 : 1;
    int[] mArr = new int[size / 5 + offset];
    for (int team = 0; team < mArr.length; team++) {
        int teamFirst = L + team * 5;
        // L ... L + 4
        // L +5 ... L +9
        // L +10....L+14
        //取5个一组的数组的排序后的中位数
        mArr[team] = getMedian(arr, teamFirst, Math.min(R, teamFirst + 4));
    }
    // marr中，找到中位数
    // marr(0, marr.len - 1,  mArr.length / 2 )
    return bfprt(mArr, 0, mArr.length - 1, mArr.length / 2);
}

public static int getMedian(int[] arr, int L, int R) {
    insertionSort(arr, L, R);
    return arr[(L + R) / 2];
}

public static void insertionSort(int[] arr, int L, int R) {
    for (int i = L + 1; i <= R; i++) {
        for (int j = i - 1; j >= L && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
    int[] arr = new int[(int) (Math.random() * maxSize) + 1];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * (maxValue + 1));
    }
    return arr;
}

Manacher算法

Manacher算法核心

1）理解回文半径数组
2）理解所有中心的回文最右边界R，和取得R时的中心点C
3）理解   L…(i`)…C…(i)…R  的结构，以及根据i’回文长度进行的状况划分
4）每一种情况划分，都可以加速求解i回文半径的过程

假设字符串str长度为N，想返回最长回文子串的长度

时间复杂度O(N)

思想：

字符串中间穿插'#'字符，可以解决虚拟中心的问题，如【abba】->【#a#b#b#a#】，这时候能够定位到中心Index=4
回文半径数组：每个字符index = i当中心，中心到左/右回文边界的长度，生成一个数组
边界R：中心扩到最右边回文边界的距离index，当R被更新时，更新中心点C

情况一：当遍历的index落在区间[C,R]外，也就是index > R,只能暴力递归判断 index - 1 ?= index + 1 ...
当index落在区间[C,R]内，则index以C为中点，找到index`的之前计算的答案
情况二：当index`的答案区间落在[C,R]内，则index 答案 = index`答案 ，因为是基于C中点做的对称
情况三：当index`的答案区间落在[C,R]外，则以index为中心的回文边界 等于[C,R]中的R,因为若能再往外扩，那么[C,R]必定更大
情况四：当Index`回文区域左边界和[C,R]的左边界L相等，则接着暴力：R + 1 ?= 2(index) - R - 1...

public static int manacher(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    // "12132" -> "#1#2#1#3#2#"
    char[] str = manacherString(s);
    // 回文半径的大小
    int[] pArr = new int[str.length];
    int C = -1;
    // 思想中：R代表最右的扩成功的位置。coding：最右的扩成功位置的，再下一个位置
    int R = -1;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < str.length; i++) {
        // R第一个违规的位置，i>= R  pArr[i] = 1
        // i位置扩出来的答案，i位置扩的区域，至少是多大。 
        // 1）i对称点压线L -->i位置至少不用验证 R - i个区域
        // 2）i对称点在[L-R]内 --> i位置至少不用验证i对称点的区域（其实就是结果相等）
        // 3）i对称点在[L-R]外 --> i位置至少不用验证R - i个区域（其实结果就是R-i）
        //最终解释：把i位置不需要验证的区域设置到pArr[i]中
        pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
        
        //在不越界的情况下，接着往外扩，扩到了就pArr[i]++
        //在情况2发生的时候，while循环进去后就会马上break，因为它本来就扩不动
        while (i + pArr[i] < str.length && i - pArr[i] > -1) {
            if (str[i + pArr[i]] == str[i - pArr[i]])
                pArr[i]++;
            else {
                break;
            }
        }
        //判断是否刷新R，刷新则更新，并且更新中心点
        if (i + pArr[i] > R) {
            R = i + pArr[i];
            C = i;
        }
        max = Math.max(max, pArr[i]);
    }
    //#1#2#1# 回文半径=4, 4 - 1 = 3 = 原始字符串长度
    return max - 1;
}

public static char[] manacherString(String str) {
    char[] charArr = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for (int i = 0; i != res.length; i++) {
        res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    }
    return res;
}

题目：
给一个字符串，请问怎么拼接最短的情况下让这个字符串构成一个回文字符串？

思路：
找到C在最左侧，第一个R边界等于最后一个字符的位置，然后把左边不是回文的数据逆序拼接
如：abc12321 --> abc12321cba

Morris遍历

一种遍历二叉树的方式，并且时间复杂度O(N)，额外空间复杂度O(1)
 
通过利用原树中大量空闲指针的方式，达到节省空间的目的

什么时候能用Morris遍历？
当一个节点它需要收集左树的信息和右树的信息做整合，则无法使用
当一个节点它收集完左树的信息之后，使用完便丢弃，再收集右树的信息时，则可以使用

Morris遍历细节

假设来到当前节点cur，开始时cur来到头节点位置
1）如果cur没有左孩子，cur向右移动(cur = cur.right)
2）如果cur有左孩子，找到左子树上最右的节点mostRight：
  a.如果mostRight的右指针指向空，让其指向cur，
  然后cur向左移动(cur = cur.left)
  b.如果mostRight的右指针指向cur，让其指向null，
  然后cur向右移动(cur = cur.right)
3）cur为空时遍历停止

//      1
//   2     3
// 4   5 6   7     morris输出：1242513637
//规律：所有有左子树的节点，都会经过两次
public static void morris(Node head) {
    if (head == null) {
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while (cur != null) {
        // cur有没有左树
        mostRight = cur.left;
        if (mostRight != null) { // 有左树的情况下
            // 找到cur左树上，真实的最右
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            // 从while中出来，mostRight一定是cur左树上的最右节点
            // mostRight
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else { // mostRight.right != null  ->  mostRight.right == cur
                mostRight.right = null;
            }
        }
        cur = cur.right;
    }
}

morris遍历： 1242513637
先序：第二次经过节点时不打印第二次的节点  1245367
中序：第一次经过节点时不打印第一次的节点  4251637
后序：能经过两次，且第二次经过的节点，逆序打印他的左子树的右边界，之后单独打印整棵树的右边界  4256371

//morris先序输出
public static void morrisPre(Node head) {
    if (head == null) {
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            //第一次到达这个节点,打印
            if (mostRight.right == null) {
                mostRight.right = cur;
                System.out.print(cur.value + " ");
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
            }
        } else {
            //只到达一次的节点,打印
            System.out.print(cur.value + " ");
        }
        cur = cur.right;
    }
    System.out.println();
}

//morris中序遍历
//第一次到该节点，他是会cur = cur.left，第二次时cur = cur.right
//只会到达一次的节点也是cur = cur.right
//总结：当cur = cur.right时打印
public static void morrisIn(Node head) {
    if (head == null) {
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            //第一次到达该节点时，会continue
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
            }
        }
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    System.out.println();
}

//morris后序遍历 
public static void morrisPos(Node head) {
    if (head == null) {
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                //第二次经过该节点时逆序输出左子树的右边界
                mostRight.right = null;
                printEdge(cur.left);
            }
        }
        cur = cur.right;
    }
    //单独输出整棵树的右边界
    printEdge(head);
    System.out.println();
}
//反转链表，输出后再反转回来
public static void printEdge(Node head) {
    Node tail = reverseEdge(head);
    Node cur = tail;
    while (cur != null) {
        System.out.print(cur.value + " ");
        cur = cur.right;
    }
    reverseEdge(tail);
}

public static Node reverseEdge(Node from) {
    Node pre = null;
    Node next = null;
    while (from != null) {
        next = from.right;
        from.right = pre;
        pre = from;
        from = next;
    }
    return pre;
}

//判断是否是搜索二叉树
//中序遍历，值如果不是递增，则不是
public static boolean isBST(Node head) {
    if (head == null) {
        return true;
    }
    Node cur = head;
    Node mostRight = null;

    Integer pre = null; 
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) {
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else {
                mostRight.right = null;
            }
        }
        if(pre != null && pre >= cur.value) {
            return false;
        }
        pre = cur.value;
        cur = cur.right;
    }
    return true;
}

给定一棵二叉树的头节点head

求以head为头的树中，最小深度是多少？

//暴力递归
public static int minHeight1(Node head) {
    if (head == null) {
        return 0;
    }
    return p(head);
}

public static int p(Node x) {
    if (x.left == null && x.right == null) {
        return 1;
    }
    // 左右子树起码有一个不为空
    int leftH = Integer.MAX_VALUE;
    if (x.left != null) {
        leftH = p(x.left);
    }
    int rightH = Integer.MAX_VALUE;
    if (x.right != null) {
        rightH = p(x.right);
    }
    return 1 + Math.min(leftH, rightH);
}

// 根据morris遍历改写
public static int minHeight2(Node head) {
    if (head == null) {
        return 0;
    }
    Node cur = head;
    Node mostRight = null;
    //cur当前高度
    int curLevel = 0;
    //最小的层数
    int minHeight = Integer.MAX_VALUE;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) 
            //cur遍历的左子树(mostRight)的右边界节点的个数
            int rightBoardSize = 1;
            while (mostRight.right != null && mostRight.right != cur) {
                rightBoardSize++;
                mostRight = mostRight.right;
            }
            if (mostRight.right == null) { // 第一次到达，cur必定往下走，当前层数++，
                curLevel++;
                mostRight.right = cur;
                cur = cur.left;
                continue;
            } else { 
                // 第二次到达，重新捕获到了mostRight：cur左子树的右边界节点
                //当mostRight的左子树是否为空，若是，则为叶子节点，计算该叶子节点的高度
                if (mostRight.left == null) {
                    //curLevel是MostRight叶子节点的高度，在它串回去之前计算最小高度
                    minHeight = Math.min(minHeight, curLevel);
                }
                //往回串，curLevel需要回退，减去左子树的右边界节点个数
                curLevel -= rightBoardSize;
                mostRight.right = null;
            }
        } else { // 只有一次到达
            curLevel++;
        }
        cur = cur.right;
    }
  //最后要遍历一下根节点的右边界高度
    int finalRight = 1;
    cur = head;
    while (cur.right != null) {
        finalRight++;
        cur = cur.right;
    }
    if (cur.left == null && cur.right == null) {
        minHeight = Math.min(minHeight, finalRight);
    }
    return minHeight;
}

线段树

1，一种支持范围整体修改和范围整体查询的数据结构

2，解决的问题范畴：
大范围信息可以只由左、右两侧信息加工出，
而不必遍历左右两个子范围的具体状况

思路：
1.将整个数组[0,length - 1]，舍弃index=0，从1开始[1,length], 即新长度N = length + 1;
2.对数组进行二分[1,N/2] [newLength/2+1,N]...一直二分到[L,R]-->L==R
3.将之index看作一个完整二叉树，头节点headIndex = 1
4.它的左树index = 2 * headIndex, 右树index = 2 * headIndex + 1
5.舍弃index=0是为了进行位运算:快  左index = headIndex << 1; 右index = (headIndex << 1)|1
6.二分成index二叉树，数组长度N = 8时，节点数 = 2 * N - 1,当N = 9时，多一倍数量
7.所以新二分数组sum的长度时定义成4N， (N << 2)，为了完整的存储整个二分之后的二叉树
8.新数组中，index = 1存储原数组[1,length]的sum信息，index = 2存储 [1,length/2]，如下：
arr = {1,3,4,7};  sum = {15,4,11,1,3,4,7,0...}  sum.length = 4(N + 1)
    [1-4]
  [1-2]	[3-4]
   [1] [2] [3] [4]
9.创建lazy数组，length = 4(N + 1)，用以缓存操作值，如  区间[1,4]的值 + 1，则lazy[1] = 1
10.再操作[1,2] + 2,[1,2]无法完全覆盖[1,4],则lazy下发缓存，lazy[2]=1,lazy[3]=1,清空lazy[1]=0
11.清空完lazy[1]，然后接着处理[1,2] + 2的操作，区间[1-4]和[1-2]不匹配，把操作分散下发到子树上[1-2]
12.[1-2]区间对应lazy[2] = 1的值，处理[1,2] + 2操作,则lazy[2] += 2
13.最终lazy={0,2,3,0...}
14.而当lazy有懒住数据时，sum需要根据区间大小进行累加计算
15.如当区间[1,4] + 1 时lazy[1] = 1,[1,4]对应index=1,所以sum[1] += 1 * (4 - 1 + 1)
15.对应公式：sum[i] += C * (R - L + 1)，V时增加的值，R - L + 1是区间长度

线段树实例一：
给定一个数组arr，用户希望你实现如下三个方法
1）void add(int L, int R, int V) :  让数组arr[L…R]上每个数都加上V
2）void update(int L, int R, int V) :  让数组arr[L…R]上每个数都变成V
3）int sum(int L, int R) :让返回arr[L…R]这个范围整体的累加和
怎么让这三个方法，时间复杂度都是O(logN)

//暴力递归
public static class Right {
    public int[] arr;

    public Right(int[] origin) {
        arr = new int[origin.length + 1];
        for (int i = 0; i < origin.length; i++) {
            arr[i + 1] = origin[i];
        }
    }

    public void update(int L, int R, int C) {
        for (int i = L; i <= R; i++) {
            arr[i] = C;
        }
    }

    public void add(int L, int R, int C) {
        for (int i = L; i <= R; i++) {
            arr[i] += C;
        }
    }

    public long query(int L, int R) {
        long ans = 0;
        for (int i = L; i <= R; i++) {
            ans += arr[i];
        }
        return ans;
    }

}

public static class SegmentTree {
    // arr[]为原序列的信息从0开始，但在arr里是从1开始的
    // sum[]模拟线段树维护区间和
    // lazy[]为累加懒惰标记
    // change[]为更新的值
    // update[]为更新慵懒标记
    private int MAXN;
    private int[] arr;
    private int[] sum;
    private int[] lazy;
    private int[] change;
    private boolean[] update;

    public SegmentTree(int[] origin) {
        MAXN = origin.length + 1;
        arr = new int[MAXN]; // arr[0] 不用  从1开始使用
        for (int i = 1; i < MAXN; i++) {
            arr[i] = origin[i - 1];
        }
        sum = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围的累加和信息

        lazy = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围沒有往下傳遞的纍加任務
        change = new int[MAXN << 2]; // 用来支持脑补概念中，某一个范围有没有更新操作的任务
        update = new boolean[MAXN << 2]; // 用来支持脑补概念中，某一个范围更新任务，更新成了什么
    }
  
    //累加左右树的数据到节点中
    private void pushUp(int rt) {
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }

    // 之前的，所有懒增加，和懒更新，从父范围，发给左右两个子范围
    // 分发策略是什么
    // ln表示左子树元素结点个数，rn表示右子树结点个数
    private void pushDown(int rt, int ln, int rn) {
        //如果有update方法，先下发update懒住的内容，再下发lazy懒住的内容
        //因为update操作后，它的所有子树都是无效的，所以子树的update、lazy、sum全都清空
        if (update[rt]) {
            //设置左子树update懒住
            update[rt << 1] = true;
            //把左子树update懒住的值直接改成父节点之前懒住的值
            change[rt << 1] = change[rt];
            //清空左子树的Lazy缓存，因为没用了
            lazy[rt << 1] = 0;
            //左子树的sum = 底值 * 区间长度
            sum[rt << 1] = change[rt] * ln;
            
            //右子树也如此
            update[rt << 1 | 1] = true;
            change[rt << 1 | 1] = change[rt];
            lazy[rt << 1 | 1] = 0;
            sum[rt << 1 | 1] = change[rt] * rn;
            
            //清除父节点状态
            update[rt] = false;
        }
        //把自身的懒信息下发到左右子树上
        if (lazy[rt] != 0) {
            //左树加上父节点懒的信息
            lazy[rt << 1] += lazy[rt];
            //左树累加和值加上父节点懒住的值 * 区间长度
            sum[rt << 1] += lazy[rt] * ln;
            
            //右树也是
            lazy[rt << 1 | 1] += lazy[rt];
            sum[rt << 1 | 1] += lazy[rt] * rn;
            
            //清除父节点的
            lazy[rt] = 0;
        }
    }

    // 在初始化阶段，先把sum数组，填好
    // 在arr[l~r]范围上，去build，1~N，
    // rt :  这个范围在sum中的下标
    public void build(int l, int r, int rt) {
        if (l == r) {
            sum[rt] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        //先填左右树，然后收集答案
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 | 1);
        pushUp(rt);
    }
  
    // L..R -> 任务范围 ,所有的值累加上C
    // l,r -> 表达的范围
    // rt  去哪找l，r范围上的信息
    //假设：arr = {1,3,4,7}
    //[L..R] -> [1..3]  [l,r] -> [1..4] rt -> 1
    public void add(
        int L, int R, int C,
        int l, int r, 
        int rt) {
        // 任务的范围彻底覆盖了，当前表达的范围
        if (L <= l && r <= R) {
            sum[rt] += C * (r - l + 1);
            lazy[rt] += C;
            return;
        }
        // 任务并没有把l...r全包住
        // 要把当前任务往下发
        // 任务  L, R  没有把本身表达范围 l,r 彻底包住
        int mid = (l + r) >> 1; // l..mid  (rt << 1)   mid+1...r(rt << 1 | 1)
        // 下发之前所有攒的懒任务
        pushDown(rt, mid - l + 1, r - mid);
        // 左孩子是否需要接到任务
        if (L <= mid) {
            add(L, R, C, l, mid, rt << 1);
        }
        // 右孩子是否需要接到任务
        if (R > mid) {
            add(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        // 左右孩子做完任务后，我更新我的sum信息
        pushUp(rt);
    }
    
    public void update(int L, int R, int C, int l, int r, int rt) {
        if (L <= l && r <= R) {
            update[rt] = true;
            change[rt] = C;
            sum[rt] = C * (r - l + 1);
            lazy[rt] = 0;
            return;
        }
        // 当前任务躲不掉，无法懒更新，要往下发
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);
        if (L <= mid) {
            update(L, R, C, l, mid, rt << 1);
        }
        if (R > mid) {
            update(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        pushUp(rt);
    }

    //   1~6 累加和是多少？ 1~8   rt
    public long query(int L, int R, int l, int r, int rt) {
        //如果L-R包含l，r 返回返回内的值
        if (L <= l && r <= R) {
            return sum[rt];
        }
        int mid = (l + r) >> 1;
        //下发之前攒的任务
        pushDown(rt, mid - l + 1, r - mid);
        long ans = 0;
        //查询和累加子树结果，并返回
        if (L <= mid) {
            ans += query(L, R, l, mid, rt << 1);
        }
        if (R > mid) {
            ans += query(L, R, mid + 1, r, rt << 1 | 1);
        }
        return ans;
    }

}

线段树实例二：
想象一下标准的俄罗斯方块游戏，X轴是积木最终下落到底的轴线
下面是这个游戏的简化版：
1）只会下落正方形积木
2）[a,b] -> 代表一个边长为b的正方形积木，积木左边缘沿着X = a这条线从上方掉落
3）认为整个X轴都可能接住积木，也就是说简化版游戏是没有整体的左右边界的
4）没有整体的左右边界，所以简化版游戏不会消除积木，因为不会有哪一层被填满。

给定一个N*2的二维数组matrix，可以代表N个积木依次掉落，
返回每一次掉落之后的最大高度

public static class SegmentTree {
    private int[] max;
    private int[] change;
    private boolean[] update;

    public SegmentTree(int size) {
        int N = size + 1;
        max = new int[N << 2];

        change = new int[N << 2];
        update = new boolean[N << 2];
    }
  //左右树的最大高度就是父节点的最大高度
    private void pushUp(int rt) {
        max[rt] = Math.max(max[rt << 1], max[rt << 1 | 1]);
    }

    // ln表示左子树元素结点个数，rn表示右子树结点个数
    private void pushDown(int rt, int ln, int rn) {
        if (update[rt]) {
            update[rt << 1] = true;
            update[rt << 1 | 1] = true;
            change[rt << 1] = change[rt];
            change[rt << 1 | 1] = change[rt];
            max[rt << 1] = change[rt];
            max[rt << 1 | 1] = change[rt];
            update[rt] = false;
        }
    }

    public void update(int L, int R, int C, int l, int r, int rt) {
        if (L <= l && r <= R) {
            update[rt] = true;
            change[rt] = C;
            max[rt] = C;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);
        if (L <= mid) {
            update(L, R, C, l, mid, rt << 1);
        }
        if (R > mid) {
            update(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        pushUp(rt);
    }

    public int query(int L, int R, int l, int r, int rt) {
        if (L <= l && r <= R) {
            return max[rt];
        }
        int mid = (l + r) >> 1;
        pushDown(rt, mid - l + 1, r - mid);
        int left = 0;
        int right = 0;
        if (L <= mid) {
            left = query(L, R, l, mid, rt << 1);
        }
        if (R > mid) {
            right = query(L, R, mid + 1, r, rt << 1 | 1);
        }
        return Math.max(left, right);
    }

}
//正方形起始下标离线化 把大值映射到数组的index小值中，从1开始
// positions[起始index][方块长度]
// [2,7] -> [2 , 8） 左开右闭 -> [2,7]
// [3, 10] -> 3, 12
//
//
public HashMap<Integer, Integer> index(int[][] positions) {
    TreeSet<Integer> pos = new TreeSet<>();
    for (int[] arr : positions) {
        pos.add(arr[0]);
        //起始长度 + 正方形长度 -1 
        pos.add(arr[0] + arr[1] - 1);
    }
    //TreeSet排序之后存储下表映射
    HashMap<Integer, Integer> map = new HashMap<>();
    int count = 0;
    for (Integer index : pos) {
        map.put(index, ++count);
    }
    return map;
}

public List<Integer> fallingSquares(int[][] positions) {
    HashMap<Integer, Integer> map = index(positions);
    // 100   -> 1    306 ->   2   403 -> 3
    // [100,403]   1~3 
    int N = map.size(); // 1 ~ 	N
    SegmentTree segmentTree = new SegmentTree(N);
    int max = 0;
    List<Integer> res = new ArrayList<>();
    // 每落一个正方形，收集一下，所有东西组成的图像，最高高度是什么
    for (int[] arr : positions) {
        int L = map.get(arr[0]);
        int R = map.get(arr[0] + arr[1] - 1);
        //查询出原有高度 + 正方形高度
        int height = segmentTree.query(L, R, 1, N, 1) + arr[1];
        //比较最大高度
        max = Math.max(max, height);
        //收集截至到此时，图形的最大高度
        res.add(max);
        //更新该区间的高度【直接更新[1,N],index = 1】
        segmentTree.update(L, R, height, 1, N, 1);
    }
    return res;
}

线段覆盖问题：
假设现在有很多线段长度，如[1,2] [2,4] [1,4]，请问最多盖住的线段有几段?
如上问题：[1,4]盖住三段

//暴力递归
public static int maxCover1(int[][] lines) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < lines.length; i++) {
        min = Math.min(min, lines[i][0]);
        max = Math.max(max, lines[i][1]);
    }
    int cover = 0;
    for (double p = min + 0.5; p < max; p += 1) {
        int cur = 0;
        for (int i = 0; i < lines.length; i++) {
            if (lines[i][0] < p && lines[i][1] > p) {
                cur++;
            }
        }
        cover = Math.max(cover, cur);
    }
    return cover;
}

//小根堆解决
public static int maxCover2(int[][] m) {
    Line[] lines = new Line[m.length];
    for (int i = 0; i < m.length; i++) {
        lines[i] = new Line(m[i][0], m[i][1]);
    }
    //以线段的起始坐标排序，小的先画
    Arrays.sort(lines, new StartComparator());
    PriorityQueue<Line> heap = new PriorityQueue<>(new EndComparator());
    int max = 0;
   
    //遍历，当新的L > 小根堆中的R,弹出所有小于L的值，把L放进去
    for (int i = 0; i < lines.length; i++) {
        while (!heap.isEmpty() && heap.peek().end <= lines[i].start) {
            heap.poll();
        }
        heap.add(lines[i]);
        //这时候堆中的数量就是盖住的数量
        max = Math.max(max, heap.size());
    }
    return max;
}

public static class Line {
    public int start;
    public int end;

    public Line(int s, int e) {
        start = s;
        end = e;
    }
}

public static class StartComparator implements Comparator<Line> {
    @Override
    public int compare(Line o1, Line o2) {
        return o1.start - o2.start;
    }
}

public static class EndComparator implements Comparator<Line> {
    @Override
    public int compare(Line o1, Line o2) {
        return o1.end - o2.end;
    }
}

给个二维数组，里面包含了矩形的两个对角点，通过两个对角点(x1,y1)(x2,y2)能够画出用一个矩形，返回哪个区域盖住的矩形最多

public static class Rectangle {
    public int up;
    public int down;
    public int left;
    public int right;

    public Rectangle(int up, int down, int left, int right) {
        this.up = up;
        this.down = down;
        this.left = left;
        this.right = right;
    }

}

public static class DownComparator implements Comparator<Rectangle> {
    @Override
    public int compare(Rectangle o1, Rectangle o2) {
        return o1.down - o2.down;
    }
}

public static class LeftComparator implements Comparator<Rectangle> {
    @Override
    public int compare(Rectangle o1, Rectangle o2) {
        return o1.left - o2.left;
    }
}

public static class RightComparator implements Comparator<Rectangle> {
    @Override
    public int compare(Rectangle o1, Rectangle o2) {
        return o1.right - o2.right;
    }
}

// 矩形数量是N
// O(N*LogN)
// +
// O(N) * [ O(N) +   O(N *LogN)  ]
public static int maxCover(Rectangle[] recs) {
    if (recs == null || recs.length == 0) {
        return 0;
    }
    // 根据down（底）排序
    Arrays.sort(recs, new DownComparator());
    // 可能会对当前底边的公共局域，产生影响的矩形
    // list ->  treeSet(有序表表达)
    TreeSet<Rectangle> leftOrdered = new TreeSet<>(new LeftComparator());
    int ans = 0;
    // O(N)
    for (int i = 0; i < recs.length; i++) { // 依次考察每一个矩形的底边
        int curDown = recs[i].down; // 当前的底边值取出来
        int index = i;
        while (recs[index].down == curDown) {
            leftOrdered.add(recs[index]); // O(logN)
            index++;
        }
        i = index;
        // O(N) list是不是有一些顶<=底的矩形
        removeLowerOnCurDown(leftOrdered, curDown);
        // 维持了右边界排序的容器,演变成了线段覆盖问题
        TreeSet<Rectangle> rightOrdered = new TreeSet<>(new RightComparator());
        for (Rectangle rec : leftOrdered) { // O(N)
            removeLeftOnCurLeft(rightOrdered, rec.left);
            rightOrdered.add(rec);// O(logN)
            ans = Math.max(ans, rightOrdered.size());
        }
    }
    return ans;
}

public static void removeLowerOnCurDown(TreeSet<Rectangle> set, int curDown) {
    List<Rectangle> removes = new ArrayList<>();
    for (Rectangle rec : set) {
        if (rec.up <= curDown) {
            removes.add(rec);
        }
    }
    for (Rectangle rec : removes) {
        set.remove(rec);
    }
}

public static void removeLeftOnCurLeft(TreeSet<Rectangle> rightOrdered, int curLeft) {
    List<Rectangle> removes = new ArrayList<>();
    for (Rectangle rec : rightOrdered) {
        if (rec.right > curLeft) {
            break;
        }
        removes.add(rec);
    }
    for (Rectangle rec : removes) {
        rightOrdered.remove(rec);
    }
}

最后更新： 2020年12月29日 18:58

原始链接： https://midkuro.gitee.io/2020/10/30/algorithm-trainingcamp1/

Kuro

赏

× 请我吃糖~