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

训练营四期

给定一个数组arr，再给定一个k值
返回累加和小于等于k，但是离k最近的子数组累加和

//思路如同数组累加和三连的第三题
// 请返回arr中，求各个子数组的累加和，是<=K的，并且是最大的。
// 返回这个最大的累加和
public static int getMaxLessOrEqualK(int[] arr, int K) {
    // 记录i之前的，前缀和，按照有序表组织
    TreeSet<Integer> set = new TreeSet<Integer>();
    // 一个数也没有的时候，就已经有一个前缀和是0了
    set.add(0);

    int max = Integer.MIN_VALUE;
    int sum = 0;
    // 每一步的i，都求子数组必须以i结尾的情况下，求个子数组的累加和，是<=K的，并且是最大的
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i]; // sum -> arr[0..i];
        if (set.ceiling(sum - K) != null) {
            max = Math.max(max, sum - set.ceiling(sum - K));
        }
        set.add(sum); // 当前的前缀和加入到set中去
    }
    return max;
}

给定一个二维数组matrix，再给定一个k值
返回累加和小于等于k，但是离k最近的子矩阵累加和

思路：
把第一行求出答案，把第二行的列数据累加到第一行中，压缩成一维数组，得出来的答案就是[0,1]行的答案
以此类推，能够求得以第0行开始，一直到[0..N-1]行的答案
要求[1..N-1]行的答案，只需要用[0..N-1]行的答案减去[0,1]行的答案即可

一行长度为M，计算一行的时间复杂度O(M * logM)，整体时间复杂度O(N^2 * M * logM)

给定一个二维数组matrix，可以从任何位置出发，每一步可以走向上、下、左、右，四个方向。返回最大递增链的长度。
例子：
matrix = 
5  4  3
3  1  2
2  1  3
从最中心的1出发，是可以走出1 2 3 4 5的链的，而且这是最长的递增链。所以返回长度5

思路：
暴力递归任何一个点，上下左右四个分支的递增链，取Max
优化：
建立计算过的每个点的dp[i][j]值，记忆化搜索复用，时间复杂度O(M * N)

public static int maxPath2(int[][] matrix) {
    int ans = Integer.MIN_VALUE;

    int[][] dp = new int[matrix.length][matrix[0].length];

    for (int row = 0; row < matrix.length; row++) {
        for (int col = 0; col < matrix[0].length; col++) {
            ans = Math.max(ans, process(matrix, row, col, dp));
        }
    }
    return ans;
}

// 假设在matrix中，从i行，j列出发，能走出的最长递增路径，返回
// dp[i][j] == 0 process(i,j) 之前没遇到过
// dp[i][j] != 0 process(i,j) 之前已经算过了
public static int process(int[][] matrix, int i, int j, int[][] dp) {
    if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
        return -1;
    }
    if (dp[i][j] != 0) {
        return dp[i][j];
    }
    int next1 = 0;
    int next2 = 0;
    int next3 = 0;
    int next4 = 0;
    if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
        next1 = process(matrix, i - 1, j);
    }
    if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
        next2 = process(matrix, i + 1, j);
    }
    if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
        next3 = process(matrix, i, j - 1);
    }
    if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
        next4 = process(matrix, i, j + 1);
    }
    int ans = 1 + Math.max(Math.max(next1, next2), Math.max(next3, next4));
    dp[i][j] = ans;
    return ans;
}

给定一个字符类型的二维数组board，和一个字符串组成的列表words。
可以从board任何位置出发，每一步可以走向上、下、左、右，四个方向，
但是一条路径已经走过的位置，不能重复走。
返回words哪些单词可以被走出来。
例子 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

思路：
words生成前缀树，加速查找过程，递归上下左右位置
通过修改原数组中的值来验证不能重复走的问题，深度优先遍历后还原数组中的值
通过一个List缓存每次走过的字符，匹配上前缀树的end，则记录答案
通过一个List记录每次合法的答案，一次深度优先遍历求多个合法答案
通过递归方法返回值记录匹配到多少个合法答案，前缀树的pass--，同样答案的不会再走
用来避免求得答案的不同位置重新计算

public static List<String> findWords(char[][] board, String[] words) {
    TrieNode head = new TrieNode(); // 前缀树最顶端的头
    HashSet<String> set = new HashSet<>();
    for (String word : words) {
        if (!set.contains(word)) {
            fillWord(head, word);
            set.add(word);
        }
    }
    // 答案
    List<String> ans = new ArrayList<>();
    // 沿途走过的字符，收集起来，存在path里
    LinkedList<Character> path = new LinkedList<>();
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board[0].length; col++) {
            // 枚举在board中的所有位置
            // 每一个位置出发的情况下，答案都收集
            process(board, row, col, path, head, ans);
        }
    }
    return ans;
}

// 从board[row][col]位置的字符出发，
// 之前的路径上，走过的字符，记录在path里
// cur还没有登上，有待检查能不能登上去的前缀树的节点
// 如果找到words中的某个str，就记录在 res里
// 返回值，从row,col 出发，一共找到了多少个str
public static int process(
    char[][] board, 
    int row, int col,
    LinkedList<Character> path,
    TrieNode cur, 
    List<String> res) {
    char cha = board[row][col];
    if (cha == 0) { // 这个row col位置是之前走过的位置
        return 0;
    }
    // (row,col) 不是回头路   cha 有效

    int index = cha - 'a';
    // 如果没路，或者这条路上最终的字符串之前加入过结果里
    if (cur.nexts[index] == null || cur.nexts[index].pass == 0) {
        return 0;
    }
    // 没有走回头路且能登上去
    cur = cur.nexts[index];
    path.addLast(cha);// 当前位置的字符加到路径里去
    int fix = 0; // 从row和col位置出发，后续一共搞定了多少答案
    // 当我来到row col位置，如果决定不往后走了。是不是已经搞定了某个字符串了
    if (cur.end > 0) { 
        res.add(generatePath(path));
        cur.end--;
        fix++;
    }
    // 往上、下、左、右，四个方向尝试
    board[row][col] = 0;
    if (row > 0) {
        fix += process(board, row - 1, col, path, cur, res);
    }
    if (row < board.length - 1) {
        fix += process(board, row + 1, col, path, cur, res);
    }
    if (col > 0) {
        fix += process(board, row, col - 1, path, cur, res);
    }
    if (col < board[0].length - 1) {
        fix += process(board, row, col + 1, path, cur, res);
    }
    board[row][col] = cha;
    path.pollLast();
    cur.pass -= fix;
    return fix;
}

public static class TrieNode {
    public TrieNode[] nexts;
    public int pass;
    public int end;

    public TrieNode() {
        nexts = new TrieNode[26];
        pass = 0;
        end = 0;
    }
}

public static void fillWord(TrieNode head, String word) {
    head.pass++;
    char[] chs = word.toCharArray();
    int index = 0;
    TrieNode node = head;
    for (int i = 0; i < chs.length; i++) {
        index = chs[i] - 'a';
        if (node.nexts[index] == null) {
            node.nexts[index] = new TrieNode();
        }
        node = node.nexts[index];
        node.pass++;
    }
    node.end++;
}

给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个? 如果得到子序列A删除的位置与得到子序列B删除的位置不同，那么认为A和B就是不同的。
【例子】
S = "rabbbit", T = "rabbit"
返回: 3

思路：
dp问题，一个样本做行，一个样本做列的对应模型
dp[i][j]：
可能性一：与i无关 dp[i][j] = dp[i-1][j]
可能性二：与i有关 s[i] == t[j]的前提下，dp[i][j] = dp[i-1][j-1] + 1
两种可能性相加

给定一个二维数组 map，含义是一张地图，例如，如下矩阵: 
-2 -3   3
-5 -10  1
 0  30 -5
游戏的规则如下: 
骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
地图中每个位置的值代表骑士要遭遇的事情。
如果是负数，说明此处有怪兽，要让骑士损失血量。
如果是非负数，代表此处有血瓶，能让骑士回血。
骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。
为了保证骑士能见到公主，初始血量至少是多少?根据map，返回至少的初始血量。

思路：
dp问题，baseCase：到达最后公右下角格子的时候，最少需要多少血量
假设到了最后一行，一直往右走，最少需要多少血量 dp[N-1][j]，取决于它右边的格子
假设到了最后一列，一直往下走，最少需要多少血量 dp[i][N-1]，取决于它下面的格子
在中间，取决于下面和右边的血量最小值

public static int needMin(int[][] matrix) {
    return process(matrix, matrix.length, matrix[0].length, 0, 0);
}

// 来到了matrix[row][col]，还没登上去，到达右下角，返回至少的初始血量
public static int process(int[][] matrix, int N, int M, int row, int col) {
    if(row == N - 1 && col == M - 1) { // 已经达到右下角了
        return matrix[N-1][M-1] < 0 ? (-matrix[N-1][M-1] + 1) : 1;
    }
    if(row == N - 1) {
        int rightNeed = process(matrix, N, M, row, col+1);
        if(matrix[row][col] < 0) { // 3    -7    10
            return -matrix[row][col] + rightNeed;
        }else if(matrix[row][col] >= rightNeed) {  // 3    3    1
            return 1;
        }else { //  3   1    2
            return rightNeed - matrix[row][col];
        }
    }
    if(col == M - 1) {
        int downNeed = process(matrix, N, M, row+1, col);
        if(matrix[row][col] < 0) { // 3    -7    10
            return -matrix[row][col] + downNeed;
        }else if(matrix[row][col] >= downNeed) {  // 3    3    1
            return 1;
        }else { //  3   1    2
            return downNeed - matrix[row][col];
        }
    }
    int minNextNeed = Math.min(process(matrix, N, M, row, col+1), process(matrix, N, M, row+1, col));
    if(matrix[row][col] < 0) { // 3    -7    10
        return -matrix[row][col] + minNextNeed;
    }else if(matrix[row][col] >= minNextNeed) {  // 3    3    1
        return 1;
    }else { //  3   1    2
        return minNextNeed - matrix[row][col];
    }
}

给定一个矩阵matrix，先从左上角开始，每一步只能往右或者往下走，走到右下角。然后从右下角出发，每一步只能往上或者往左走，再回到左上角。任何一个位置的数字，只能获得一遍。返回最大路径和。

思路：
BaseCase：两个点同时出发，到达相同点和最后一个点时只累加一次值，不同点累加两个点的值
第二个点的一个坐标可以通过另一个点计算坐标出来

// 从matrix左上角，走到右下角，过程中只能向右或者向下
// 到达后，回来，过程中只能向左或者向上，沿途数字只能获得一遍
// 返回，最大路径和
public static int comeGoMaxPathSum(int[][] matrix) {
    return process(matrix, 0, 0, 0);
}

// matrix中，没有负数
// A来到的位置是 Ar,Ac
// B来到的位置是 Br, Ar + Ac - Br
// A和B，一定迈出的步数，一样多，同步走的
// 两人会共同到达右下角，返回两个人路径的最大累加和
// 重要限制：来到同一个位置时，只获得一份
//   3  7     5     ?
public static int process(int[][] matrix, int Ar, int Ac, int Br) {
    int N = matrix.length;
    int M = matrix[0].length;
    if(Ar == N - 1 && Ac == M - 1) {
        return matrix[Ar][Ac];
    }
    // 还没到右下角
    // A 下   B 右
    // A 下   B 下
    // A 右   B 右
    // A 右   B 下
    int Bc = Ar + Ac - Br;
    int ADownBRight = -1;
    if(Ar + 1 < N && Bc + 1 < M) {
        ADownBRight = process(matrix, Ar + 1, Ac, Br);
    }
    int ADownBDown = -1;
    if(Ar + 1 < N && Br + 1 < N) {
        ADownBDown = process(matrix, Ar + 1, Ac, Br + 1);
    }

    int ARightBRight = -1;
    if(Ac + 1 < M && Bc + 1 < M) {
        ARightBRight = process(matrix, Ar, Ac+1, Br);
    }
    int ARightBDown = -1;
    if(Ac + 1 < M && Br + 1 < N) {
        ARightBDown = process(matrix, Ar, Ac + 1, Br + 1);
    }
    int nextBest = Math.max(Math.max(ADownBRight, ADownBDown), Math.max(ARightBRight, ARightBDown));
    // A B 相同位置，只能累加一次
    if(Ar == Br) {
        return matrix[Ar][Ac] + nextBest;
    }
    // A 和 B，一定是不同位置
    //A + B + 递归最好的结果
    return matrix[Ar][Ac] + matrix[Br][Bc] + nextBest;
}

给定一个无序数组arr，返回如果排序之后，相邻数之间的最大差值
{3,1,7,9}，如果排序后{1,3,7,9}，相邻数之间的最大差值来自3和7，返回4
要求：不能真的进行排序，并且要求在时间复杂度O(N)内解决

思路：
先遍历一遍数组，求最大值和最小值，根据数组长度分成N + 1份个桶
将N个数字放进N+1个桶中，桶的左右两侧是数组的最大值和最小值，那么必然会存在空桶
空桶的定义是为了忽略桶内部的差值结果，因为空桶左侧桶内最大值和右侧桶内最小值势必大于一个桶的结果
这样做的目的是忽略掉最平凡的解
每个桶记录桶中的最大值和最小值，结果必然在两个不同的桶的最大值最小值之差

public static int maxGap(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    int len = nums.length;
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < len; i++) {
        min = Math.min(min, nums[i]);
        max = Math.max(max, nums[i]);
    }
    if (min == max) {
        return 0;
    }
    // 不止一种数，min~max一定有range,  len个数据，准备len+1个桶
    boolean[] hasNum = new boolean[len + 1]; // hasNum[i] i号桶是否进来过数字
    int[] maxs = new int[len + 1];  // maxs[i] i号桶收集的所有数字的最大值
    int[] mins = new int[len + 1];  // mins[i] i号桶收集的所有数字的最小值

    int bid = 0; // 桶号
    for (int i = 0; i < len; i++) {
        bid = bucket(nums[i], len, min, max);
        mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
        maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
        hasNum[bid] = true;
    }
    int res = 0;
    int lastMax = maxs[0]; // 上一个非空桶的最大值
    int i = 1;
    for (; i <= len; i++) {
        if (hasNum[i]) {
            res = Math.max(res, mins[i] - lastMax);
            lastMax = maxs[i];
        }
    }
    return res;
}

public static int bucket(long num, long len, long min, long max) {
    return (int) ((num - min) * len / (max - min));
}

假设所有字符都是小写字母.   长字符串是str
arr是去重的单词表, 每个单词都不是空字符串且可以使用任意次
使用arr中的单词有多少种拼接str的方式，返回方法数.

思路：
解法一：
枚举从[0...i]上，在数组中的单词，匹配上则进入递归
截取子串并且Set的Contains操作时间复杂度O(N)，所以总体时间复杂度O（N^3）
解法二：
前缀树，先生成数组的前缀，通过O(1)优化了Set的O(N)过程，并且前缀树不满足的字符串直接跳出
建前缀树O(K)，总体时间复杂度O(K) + O(N^2)

根据数据量选择不同的解法

//解法一：
public static int ways(String str, String[] arr) {
    HashSet<String> set = new HashSet<>();
    for (String candidate : arr) {
        set.add(candidate);
    }
    return process(str, 0, set);
}

// 所有的贴纸，都已经放在了set中
// str[i....] 能够被set中的贴纸分解的话，返回分解的方法数
public static int process(String str, int i, HashSet<String> set) {
    if (i == str.length()) {
        return 1;
    }
    int ways = 0;
    // [i ... end] 前缀串 每一个前缀串
    for (int end = i; end < str.length(); end++) {
        String pre = str.substring(i, end + 1);// [)
        if (set.contains(pre)) {
            ways += process(str, end + 1, set);
        }
    }
    return ways;
}

//解法二
public static class Node {
    public boolean end;
    public Node[] nexts;

    public Node() {
        end = false;
        nexts = new Node[26];
    }
}

public static int ways3(String str, String[] arr) {
    if (str == null || str.length() == 0 || arr == null || arr.length == 0) {
        return 0;
    }
    Node root = new Node();
    for (String s : arr) {
        char[] chs = s.toCharArray();
        Node node = root;
        int index = 0;
        for (int i = 0; i < chs.length; i++) {
            index = chs[i] - 'a';
            if (node.nexts[index] == null) {
                node.nexts[index] = new Node();
            }
            node = node.nexts[index];
        }
        node.end = true;
    }
    return g(str.toCharArray(), root, 0);
}

// str[i...] 被分解的方法数，返回

public static int g(char[] str, Node root, int i) {
    if (i == str.length) {
        return 1;
    }
    int ways = 0;
    Node cur = root;
    // i...end
    for (int end = i; end < str.length; end++) {
        int path = str[end] - 'a';
        //如果没有前缀树匹配了，直接break加速
        if (cur.nexts[path] == null) {
            break;
        }
        cur = cur.nexts[path];
        if (cur.end) { // i...end
            ways += g(str, root, end + 1);
        }
    }
    return ways;
}

给定一棵二叉树的头节点head，和一个数K
路径的定义: 
可以从任何一个点开始，但是只能往下走，往下可以走到任何节点停止
返回路径累加和为K的所有路径中，最长的路径最多有几个节点？

思路：
树每一条分支都是一个一维数组，求每个一维数组中累加和为K的最长子数组问题，数组三连

public static int ans = 0; // 收集累加和为K的，最长路径有多少个节点

public static int longest(Node head, int K) {
    ans = 0;
    // key ： 前缀和
    // value : 该前缀和，最早出现在哪一层
    // sumMap：只维持，从头节点出发到当前节点，这条路径上的前缀和
    HashMap<Integer, Integer> sumMap = new HashMap<>();
    sumMap.put(0, -1);
    process(head, 0, 0, K, sumMap);
    return ans;
}

// 节点X在level层，从头节点到X的父节点形成的累加和是preSum，
// 从头节点到X的路径上，每一个前缀和都存在sumMap里(key)，记录的是该前缀和最早出现的层数(value)
// 求出必须以X节点结尾的、累加和是K的所有路径中，含有最多的节点是多少？
// 并看看能不能更新全局的ans
public static void process(Node X, int level, int preSum, int K, HashMap<Integer, Integer> sumMap) {
    if (X != null) {
        // 从头节点出发，到当前X节点，总的前缀和是多少，allSum
        int allSum = preSum + X.value;
        if (sumMap.containsKey(allSum - K)) {
            ans = Math.max(ans, level - sumMap.get(allSum - K));
        }
        if (!sumMap.containsKey(allSum)) {
            sumMap.put(allSum, level);
        }
        process(X.left, level + 1, allSum, K, sumMap);
        process(X.right, level + 1, allSum, K, sumMap);
        if (sumMap.get(allSum) == level) {
            sumMap.remove(allSum);
        }
    }
}

给定一个int类型的数组arr，已知除了一种数只出现1次之外，
剩下所有的数都出现了k次，如何使用O(1)的额外空间，找到这个数。
int[] arr,  int K,   K > 1

思路：
出现K次的数，把他理解成一个无进位相加的K进制数，累加计算他们的位数然后模K，出现K次的数一定能被整除
剩下的就是出现1次的数

public static int onceNum(int[] arr, int k) {
    int[] eO = new int[32];
    for (int i = 0; i != arr.length; i++) {
        // 当前数是arr[i], 请把arr[i]变成K进制的形式，每一位累加到eO
        setExclusiveOr(eO, arr[i], k);
    }
    int res = getNumFromKSysNum(eO, k);
    return res;
}

public static void setExclusiveOr(int[] eO, int value, int k) {
    int[] curKSysNum = getKSysNumFromNum(value, k);
    for (int i = 0; i != eO.length; i++) {
        eO[i] = (eO[i] + curKSysNum[i]) % k;
    }
}

public static int[] getKSysNumFromNum(int value, int k) {
    int[] res = new int[32];
    int index = 0;
    while (value != 0) {
        res[index++] = value % k;
        value = value / k;
    }
    return res;
}

public static int getNumFromKSysNum(int[] eO, int k) {
    int res = 0;
    for (int i = eO.length - 1; i != -1; i--) {
        res = res * k + eO[i];
    }
    return res;
}

给定一个数组arr，如果有某个数出现次数超过了数组长度的一半，打印这个数，如果没有不打印
额外空间O(1)

思路：
每次同时删掉两个不同的数，最后那个留下来的一定是超过数组长度的一半的数
代码实现的思想很重要！！！！

public static void printHalfMajor(int[] arr) {
    int cand = 0;
    //通过一个值自增自减来达到同时删除两个数的目的O(1)，很重要的思想！！！！
    int HP = 0;
    for (int i = 0; i < arr.length; i++) {
        if (HP == 0) {
            cand = arr[i];
            HP = 1;
        } else if (arr[i] == cand) {
            HP++;
        } else {
            HP--;
        }
    }
    if(HP == 0) {
        System.out.println("no such number.");
        return;
    }
    HP = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == cand) {
            HP++;
        }
    }
    if (HP > arr.length / 2) {
        System.out.println(cand);
    } else {
        System.out.println("no such number.");
    }
}

给定一个数组arr和整数k，arr长度为N，如果有某些数出现次数超过了N/K，打印这些数，如果没有不打印

思想：
用一个长度为K的Map来存储，Key是数字，Value是HP的值，和上题相同思路解答

public static void printKMajor(int[] arr, int K) {
    if (K < 2) {
        System.out.println("the value of K is invalid.");
        return;
    }
    HashMap<Integer, Integer> cands = new HashMap<Integer, Integer>();
    for (int i = 0; i != arr.length; i++) {
        if (cands.containsKey(arr[i])) {
            cands.put(arr[i], cands.get(arr[i]) + 1);
        } else {
            if (cands.size() == K - 1) {
                allCandsMinusOne(cands);
            } else {
                cands.put(arr[i], 1);
            }
        }
    }
    HashMap<Integer, Integer> reals = getReals(arr, cands);
    boolean hasPrint = false;
    for (Entry<Integer, Integer> set : cands.entrySet()) {
        Integer key = set.getKey();
        if (reals.get(key) > arr.length / K) {
            hasPrint = true;
            System.out.print(key + " ");
        }
    }
    System.out.println(hasPrint ? "" : "no such number.");
}

public static void allCandsMinusOne(HashMap<Integer, Integer> map) {
    List<Integer> removeList = new LinkedList<Integer>();
    for (Entry<Integer, Integer> set : map.entrySet()) {
        Integer key = set.getKey();
        Integer value = set.getValue();
        if (value == 1) {
            removeList.add(key);
        }
        map.put(key, value - 1);
    }
    for (Integer removeKey : removeList) {
        map.remove(removeKey);
    }
}

public static HashMap<Integer, Integer> getReals(int[] arr,
                                                 HashMap<Integer, Integer> cands) {
    HashMap<Integer, Integer> reals = new HashMap<Integer, Integer>();
    for (int i = 0; i != arr.length; i++) {
        int curNum = arr[i];
        if (cands.containsKey(curNum)) {
            if (reals.containsKey(curNum)) {
                reals.put(curNum, reals.get(curNum) + 1);
            } else {
                reals.put(curNum, 1);
            }
        }
    }
    return reals;
}

数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。
认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。
每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。
洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
四个参数：arr, n, a, b
假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。

思路：
小根堆，把每个咖啡的（时间总和，单次时长））放小根堆里，依次弹出使用增加

public static class CoffeeMachine{
    public int start;
    public int work;

    public CoffeeMachine(int s, int w) {
        start = s;
        work = w;
    }
}

public static class CoffeeMachineComparator implements Comparator<CoffeeMachine>{

    @Override
    public int compare(CoffeeMachine o1, CoffeeMachine o2) {
        return o1.start + o1.work - o2.start - o2.work;
    }

}

public static int[] bestChoices(int[] arr, int M) {
    int[] ans = new int[M];
    PriorityQueue<CoffeeMachine> heap = new PriorityQueue<>(new CoffeeMachineComparator());
    for(int coffeWork : arr) {
        heap.add(new CoffeeMachine(0, coffeWork));
    }
    for(int i = 0; i< M; i++) {
        CoffeeMachine cur = heap.poll();
        ans[i] = cur.start + cur.work;
        cur.start = ans[i];
        heap.add(cur);
    }
    return ans;
}

给定两个整数数组A和B
A是长度为m、元素从小到大排好序了
B是长度为n、元素从小到大排好序了
希望从A和B数组中，找出最大的k个数字

思路：
解法一：卡两个指针一直移动，时间复杂度O(K)

解法二：二分A数组，然后二分的那个值去B里面二分，判断A左边的数量+B左边的数量和K有什么关系
大于则表示这个二分的值拿大了，小于则拿小了
若这个值不在A数组中，则重复操作数组B
时间复杂度O(logN * logM)

解法三：
假设把两个数组看做等长的偶数数组N，求第N小，可以先求出这两个数组的上中位数
若他们上中位数相等，则这个值是两个数组中第N小的值
若数组A的中位数X大于数组B的中位数Y，则有X左边部分（包括X）和Y右边部分（不包括Y）都可能是第N小的值
把这两段数组当做一个新数组递归下去，新数组长度是N/2，等于求第N/2小的值

若数组的长度是奇数，求第N小，则分类：
若数组A的中位数X大于数组B的中位数Y，则有X左边部分（不包括X）和Y右边部分（包括Y）都可能是第N小的值
在这种情况下，Y部分的长度会比X部分的长度大一，可以通过程序匹配过滤掉一个，使得他们长度等长，接着计算

所以通过这种方式求得了数组长度都是N的情况下，第N小的值
上面的题目若K < Min(M,N),则可以直接按照K长数组来算，其他情况看代码...
时间复杂度O(log Min(M,N))

public static int findKthNum(int[] arr1, int[] arr2, int kth) {
    if (arr1 == null || arr2 == null) {
        return -1;
    }
    if (kth < 1 || kth > arr1.length + arr2.length) {
        return -1;
    }
    int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
    int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
    int l = longs.length;
    int s = shorts.length;
    if (kth <= s) {
        return getUpMedian(shorts, 0, kth - 1, longs, 0, kth - 1);
    }
    if (kth > l) {
        if (shorts[kth - l - 1] >= longs[l - 1]) {
            return shorts[kth - l - 1];
        }
        if (longs[kth - s - 1] >= shorts[s - 1]) {
            return longs[kth - s - 1];
        }
        return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
    }
    // 短数组长度 < k <= 长数组长度
    if (longs[kth - s - 1] >= shorts[s - 1]) {
        return longs[kth - s - 1];
    }
    return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
}

// A[s1...e1]
// B[s2...e2]
// 这两段一定等长且都有序
// 求这两段整体的上中位数，上中位数值返回
public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
    int mid1 = 0;
    int mid2 = 0;
    while (s1 < e1) {
        mid1 = (s1 + e1) / 2;
        mid2 = (s2 + e2) / 2;
        if (A[mid1] == B[mid2]) {
            return A[mid1];
        }
        if (((e1 - s1 + 1) & 1) == 1) { // 奇数长度
            if (A[mid1] > B[mid2]) {
                if (B[mid2] >= A[mid1 - 1]) {
                    return B[mid2];
                }
                e1 = mid1 - 1;
                s2 = mid2 + 1;
            } else { // A[mid1] < B[mid2]
                if (A[mid1] >= B[mid2 - 1]) {
                    return A[mid1];
                }
                e2 = mid2 - 1;
                s1 = mid1 + 1;
            }
        } else { // 偶数长度
            if (A[mid1] > B[mid2]) {
                e1 = mid1;
                s2 = mid2 + 1;
            } else {
                e2 = mid2;
                s1 = mid1 + 1;
            }
        }
    }
    return Math.min(A[s1], B[s2]);
}

约瑟夫环问题
给定一圈人，报数从1开始，报到m位置，就杀死他，然后下一个重新报数，求最后活下来的人在最开始的编号

思路：
函数一：y = x%i （剃刀函数）通过它来推导
假设在不杀人的情况下，编号是从x=1,y=1的，所以是函数一右移1，上移1
得到函数二：报数y和编号x的关系 y = (x - 1)%i + 1  

旧：1 2 3 4 5 6 7
新：5 6   1 2 3 4
假设报S = 3被杀，新编号做x轴，旧编号做y轴，画图
然后延伸线段，能够发现第一条线段最后会落在 -2 位置上
所以第一个线段当 y = 1时，x = -S + 1
这个函数的图像等于函数二左移(-S + 1)
得到函数三：旧编号 y = (x + S - 1)%i + 1
S是老链表中被杀掉时的报数（函数二中的y，带入函数二到函数三）
i是老链表的杀掉之前的长度
x是新的编号

得到函数四 旧编号 y = (x + (m-1)%i)%i + 1
m是被杀的报数

最后简化成 y = (x + m - 1)%i + 1

public static Node josephusKill2(Node head, int m) {
    if (head == null || head.next == head || m < 1) {
        return head;
    }
    Node cur = head.next;
    int size = 1; // tmp -> list size
    while (cur != head) {
        size++;
        cur = cur.next;
    }
    int live = getLive(size, m); // tmp -> service node position
    while (--live != 0) {
        head = head.next;
    }
    head.next = head;
    return head;
}

// 现在一共有i个节点，数到m就杀死节点，最终会活下来的节点，请返回它在有i个节点时候的编号
// 旧 
// getLive(N, m)
public static int getLive(int i, int m) {
    if (i == 1) {
        return 1;
    }
    // getLive(i - 1, m)   长度为i-1时候，活下来的编号
    return (getLive(i - 1, m) + m - 1) % i + 1;
}

给定一个 N×3 的矩阵 matrix，对于每一个长度为 3 的小数组 arr，都表示一个大楼的三个数 据。
arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定大于 0)。 
每座大楼的地基都在 X 轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。

【举例】 matrix ={{2,5,6}, {1,7,4}, {4,6,7}, {3,6,5}, {10,13,2}, {9,11,3}, {12,14,4},{10,12,5} }

返回: {{1,2,4},{2,4,6}, {4,6,7}, {6,7,4}, {9,10,3}, {10,12,5}, {12,14,4}}

思路：
思考如何计算出每个坐标当前高度即可
{2,5,6}-> 坐标2高度+6，坐标5高度-6，这样就计算出每个坐标的高度
如果有多个坐标点相同，先计算+，再计算-
如果有多个高度相同，要统计累加次数，当高度减掉时减掉次数
用两个Map实现

// 描述高度变化的对象
public static class Op {
    public int x; // x轴上的值
    public boolean isAdd;// true为加入，false为删除
    public int h; // 高度

    public Op(int x, boolean isAdd, int h) {
        this.x = x;
        this.isAdd = isAdd;
        this.h = h;
    }
}

// 排序的比较策略
// 1，第一个维度的x值从小到大。
// 2，如果第一个维度的值相等，看第二个维度的值，“加入”排在前，“删除”排在后
// 3，如果两个对象第一维度和第二个维度的值都相等，则认为两个对象相等，谁在前都行。
public static class OpComparator implements Comparator<Op> {
    @Override
    public int compare(Op o1, Op o2) {
        if (o1.x != o2.x) {
            return o1.x - o2.x;
        }
        if (o1.isAdd != o2.isAdd) {
            return o1.isAdd ? -1 : 1;
        }
        return 0;
    }
}

// 全部流程的主方法
// [s,e,h]
// [s,e,h]
// { {1,5,3} , {6,8,4}  .. ...  ...    }
public static List<List<Integer>> buildingOutline(int[][] matrix) {
    int N = matrix.length;
    Op[] ops = new Op[N << 1];
    for (int i = 0; i < matrix.length; i++) {
        ops[i * 2] = new Op(matrix[i][0], true, matrix[i][2]);
        ops[i * 2 + 1] = new Op(matrix[i][1], false, matrix[i][2]);
    }
    // 把描述高度变化的对象数组，按照规定的排序策略排序
    Arrays.sort(ops, new OpComparator());


    // TreeMap就是java中的红黑树结构，直接当作有序表来使用
    // key  某个高度  value  次数
    TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>();
    // key   x点，   value 最大高度
    TreeMap<Integer, Integer> mapXHeight = new TreeMap<>();


    for (int i = 0; i < ops.length; i++) {
        // ops[i]
        if (ops[i].isAdd) { // 如果当前是加入操作
            if (!mapHeightTimes.containsKey(ops[i].h)) { // 没有出现的高度直接新加记录
                mapHeightTimes.put(ops[i].h, 1);
            } else { // 之前出现的高度，次数加1即可
                mapHeightTimes.put(ops[i].h, mapHeightTimes.get(ops[i].h) + 1);
            }
        } else { // 如果当前是删除操作
            if (mapHeightTimes.get(ops[i].h) == 1) { // 如果当前的高度出现次数为1，直接删除记录
                mapHeightTimes.remove(ops[i].h);
            } else { // 如果当前的高度出现次数大于1，次数减1即可
                mapHeightTimes.put(ops[i].h, mapHeightTimes.get(ops[i].h) - 1);
            }
        }
        // 根据mapHeightTimes中的最大高度，设置mapXvalueHeight表
        if (mapHeightTimes.isEmpty()) { // 如果mapHeightTimes为空，说明最大高度为0
            mapXHeight.put(ops[i].x, 0);
        } else { // 如果mapHeightTimes不为空，通过mapHeightTimes.lastKey()取得最大高度
            mapXHeight.put(ops[i].x, mapHeightTimes.lastKey());
        }
    }
    // res为结果数组，每一个List<Integer>代表一个轮廓线，有开始位置，结束位置，高度，一共三个信息
    List<List<Integer>> res = new ArrayList<>();
    // 一个新轮廓线的开始位置
    int start = 0;
    // 之前的最大高度
    int preHeight = 0;
    // 根据mapXvalueHeight生成res数组
    for (Entry<Integer, Integer> entry : mapXHeight.entrySet()) {
        // 当前位置
        int curX = entry.getKey();
        // 当前最大高度
        int curMaxHeight = entry.getValue();
        if (preHeight != curMaxHeight) { // 之前最大高度和当前最大高度不一样时
            if (preHeight != 0) {
                res.add(new ArrayList<>(Arrays.asList(start, curX, preHeight)));
            }
            start = curX;
            preHeight = curMaxHeight;
        }
    }
    return res;
}

Nim博弈问题
给定一个非负数组，每一个值代表该位置上有几个铜板。
a和b玩游戏，a先手，b后手， 轮到某个人的时候，只能在一个位置上拿任意数量的铜板，但是不能不拿。谁最先把铜 板拿完谁赢。
假设a和b都极度聪明，请返回获胜者的名字

思路：
先手让自己每次拿的时候，异或和都不等于0，并且让后手拿的时候，异或和等于0，就能保证自己先手赢

结论：数组的eor != 0，先手win，eor == 0,后手win

给定一个数组arr，长度为N且每个值都是正数，代表N个人的体重。再给定一个正数 limit，代表一艘船的载重。
以下是坐船规则 :
1)每艘船最多只能坐两人;
2)乘客 的体重和不能超过limit
返回如果同时让这N个人过河最少需要几条船。

思路：
排序，在limit/2的位置上，L往左移动，R往右移动，L+R<limit，则R++

// 请保证arr有序
public static int minBoat(int[] arr, int limit) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    // Arrays.sort(arr);
    if(arr[N - 1] > limit) {
        return -1;
    }
    int lessR = -1;
    // 所有的人体重都不超过limit，继续讨论,  <= limit / 2  最右的位置
    for (int i = N  - 1; i >= 0; i--) {
        if (arr[i] <= (limit / 2)) {
            lessR = i;
            break;
        }
    }
    if (lessR == -1) {
        return N;
    }
    //  <= limit / 2
    int L = lessR;
    int R = lessR + 1;
    int noUsed = 0; // 画X的数量统计，画对号的量(加工出来的)
    while (L >= 0) {
        int solved = 0; // 此时的[L]，让R画过了几个数
        while (R < N && arr[L] + arr[R] <= limit) {
            R++;
            solved++;
        }
        // R来到又不达标的位置
        if (solved == 0) {
            noUsed++;
            L--;
        } else { // 此时的[L]，让R画过了solved（>0）个数
            L = Math.max(-1, L - solved);
        }
    }
    int all = lessR + 1;// 左半区总个数  <= limit /2 的区域
    int used = all - noUsed; // 画对号的量
    int moreUnsolved = (N - all) - used; // > limit/2 区中，没搞定的数量
    return used + ((noUsed + 1) >> 1) + moreUnsolved;
}// 请保证arr有序
public static int minBoat(int[] arr, int limit) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    // Arrays.sort(arr);
    if(arr[N - 1] > limit) {
        return -1;
    }
    int lessR = -1;
    // 所有的人体重都不超过limit，继续讨论,  <= limit / 2  最右的位置
    for (int i = N  - 1; i >= 0; i--) {
        if (arr[i] <= (limit / 2)) {
            lessR = i;
            break;
        }
    }
    if (lessR == -1) {
        return N;
    }
    //  <= limit / 2
    int L = lessR;
    int R = lessR + 1;
    int noUsed = 0; // 画X的数量统计，画对号的量(加工出来的)
    while (L >= 0) {
        int solved = 0; // 此时的[L]，让R画过了几个数
        while (R < N && arr[L] + arr[R] <= limit) {
            R++;
            solved++;
        }
        // R来到又不达标的位置
        if (solved == 0) {
            noUsed++;
            L--;
        } else { // 此时的[L]，让R画过了solved（>0）个数
            L = Math.max(-1, L - solved);
        }
    }
    int all = lessR + 1;// 左半区总个数  <= limit /2 的区域
    int used = all - noUsed; // 画对号的量
    int moreUnsolved = (N - all) - used; // > limit/2 区中，没搞定的数量
    return used + ((noUsed + 1) >> 1) + moreUnsolved;
}

给定一个字符串str，求最长回文子序列长度

思路：
解法一：把str逆序，一个样本做行，一个样本做列，求最长公共子序列
解法二：范围上尝试模型，L..R，填一半的dp表，右下角无效
四种可能：
和L有关，和R有关，和L/R无关，和L/R有关

给定一个二维数组matrix，每个单元都是一个整数，有正有负。
最开始一条长度为0的蛇，从矩阵最左侧任选一个单元格进入地图，蛇每次只能够到达当前位置的右上相邻，右侧相邻和右下相邻的单元格。
蛇蛇到达一个单元格后，自身的长度会 瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。
小Q是个天才，他拥有一 个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数(注:最多 只能改变一个节点)。
问在小Q游戏过程中，他的蛇蛇最长长度可以到多少?
比如:
1 -4  10
3 -2 -1
2 -1  0
0  5 -2
最优路径为从最左侧的3开始，3 -> -4(利用能力变成4) -> 10。所以返回17。

思路：
业务上尝试模型
每次都递归统计使用能力和非使用能力的解
baseCase：
当前使用/不使用能力，以及当前第0行的答案

// 从假想的最优左侧到达(i,j)的旅程中
// 0) 在没有使用过能力的情况下，返回路径最大和，没有可能到达的话，返回负
// 1) 在使用过能力的情况下，返回路径最大和，没有可能到达的话，返回负
public static int[] process(int[][] m, int i, int j) {
    if (j == 0) { // (i,j)就是最左侧的位置
        return new int[] { m[i][j], -m[i][j] };
    }
    int[] preAns = process(m, i, j - 1);
    // 所有的路中，完全不使用能力的情况下，能够到达的最好长度是多大
    int preUnuse = preAns[0];
    // 所有的路中，使用过一次能力的情况下，能够到达的最好长度是多大
    int preUse = preAns[1];
    if (i - 1 >= 0) {
        preAns = process(m, i - 1, j - 1);
        preUnuse = Math.max(preUnuse, preAns[0]);
        preUse = Math.max(preUse, preAns[1]);
    }
    if (i + 1 < m.length) {
        preAns = process(m, i + 1, j - 1);
        preUnuse = Math.max(preUnuse, preAns[0]);
        preUse = Math.max(preUse, preAns[1]);
    }
    // preUnuse 之前旅程，没用过能力
    // preUse 之前旅程，已经使用过能力了
    int no = -1; // 之前没使用过能力，当前位置也不使用能力，的最优解
    int yes = -1; // 不管是之前使用能力，还是当前使用了能力，请保证能力只使用一次，最优解
    if (preUnuse >= 0) {
        no = m[i][j] + preUnuse;
        yes = -m[i][j] + preUnuse;
    }
    if (preUse >= 0) {
        yes = Math.max(yes, m[i][j] + preUse);
    }
    return new int[] { no, yes };
}

给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右 括号，返回公式的计算结果。
【举例】
str="48*((70-65)-43)+8*1"，返回-1816。
str="3+1*4"，返回7。
str="3+(1*4)"，返回7。
【说明】 
1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。 
2.如果是负数，就需要用括号括起来，比如"4*(-3)"。
但如果负数作为公式的开头 或括号部分的开头，则可以没有括号，比如"-3*4"和"(-3*4)"都是合法的。 
3.不用考虑计算过程中会发生溢出的情况。

思路：
通过递归f(0)，当遇到')'则终止计算，遇到'('则迭代计算,返回值返回递归结果和当前计算到的index
将每个符号压入队列中，遇到符号'+-*/'时，把前面的符号合成一个数字
每次压入队列中判断的队列的头部是否是'*/'，若是，则弹出前两个字符进行计算合并后再压入队列中

public static int getValue(String str) {
    return value(str.toCharArray(), 0)[0];
}

// 请从str[i...]往下算，遇到字符串终止位置或者右括号，就停止
// 返回两个值，长度为2的数组
// 0) 负责的这一段的结果是多少
// 1) 负责的这一段计算到了哪个位置
public static int[] value(char[] str, int i) {
    LinkedList<String> que = new LinkedList<String>();
    int cur = 0;
    int[] bra = null;
    // 从i出发，开始撸串
    while (i < str.length && str[i] != ')') {
        //如果是数字，就一直累加字符
        if (str[i] >= '0' && str[i] <= '9') {
            cur = cur * 10 + str[i++] - '0';
        } else if (str[i] != '(') { // 遇到的是运算符号，添加累加的字符数字
            addNum(que, cur);
            que.addLast(String.valueOf(str[i++]));
            cur = 0;
        } else { // 遇到左括号了
            bra = value(str, i + 1);
            cur = bra[0];
            i = bra[1] + 1;
        }
    }
    addNum(que, cur);
    return new int[] { getNum(que), i };
}

//把当前数字添加进队列，队列顶部是 '* /'时，拿出来计算，再放回去
public static void addNum(LinkedList<String> que, int num) {
    if (!que.isEmpty()) {
        int cur = 0;
        String top = que.pollLast();
        if (top.equals("+") || top.equals("-")) {
            que.addLast(top);
        } else {
            cur = Integer.valueOf(que.pollLast());
            num = top.equals("*") ? (cur * num) : (cur / num);
        }
    }
    que.addLast(String.valueOf(num));
}

//把队列的数据都拿出来计算，里面只有加号和减号了
public static int getNum(LinkedList<String> que) {
    int res = 0;
    boolean add = true;
    String cur = null;
    int num = 0;
    while (!que.isEmpty()) {
        cur = que.pollFirst();
        if (cur.equals("+")) {
            add = true;
        } else if (cur.equals("-")) {
            add = false;
        } else {
            num = Integer.valueOf(cur);
            res += add ? num : (-num);
        }
    }
    return res;
}

对于一个字符串, 从前开始读和从后开始读是一样的, 我们就称这个字符串是回文串。
例如"ABCBA","AA", "A" 是回文串, 而"ABCD", "AAB"不是回文串。
牛牛特别喜欢回文串, 他手中有一个字符串s, 牛牛在思考能否从字 符串中移除部分(0个或多个)字符使其变为回文串，并且牛牛认为空串不是回文串。
牛牛发现移除的方案可能有 很多种, 希望你来帮他计算一下一共有多少种移除方案可以使s变为回文串。
对于两种移除方案, 如果移除的字 符依次构成的序列不一样就是不同的方案。
例如，XXY 4种 ABA 5种
【说明】 这是今年的原题，提供的说明和例子都很让人费解。现在根据当时题目的所有测试用例，重新解释当时的题目
含义:

 1) "1AB23CD21"，你可以选择删除A、B、C、D，然后剩下子序列{1,2,3,2,1}，只要剩下的子序列是同一个，
那么就只算1种方法，和A、B、C、D选择什么样的删除顺序没有关系。 

2)"121A1"，其中有两个{1,2,1}的子序列，第一个{1,2,1}是由{位置0，位置1，位置2}构成，第二个{1,2,1} 是由{位置0，位置1，位置4}构成。
这两个子序列被认为是不同的子序列。也就是说在本题中，认为字面值一样 但是位置不同的字符就是不同的。 

3)其实这道题是想求，str中有多少个不同的子序列，每一种子序列只对应一种删除方法，那就是把多余的东 西去掉，而和去掉的顺序无关。

4)也许你觉得我的解释很荒谬，但真的是这样，不然解释不了为什么，XXY 4种 ABA 5种，而且其他的测试用例都印证了这一点。

思路：
范围上尝试模型，dp表，右下角没用，中间对角线L==R，第二条判断L和L+1的是否相等
dp[L][R]的可能性：
一：L无关，R无关 = a
二：L有关，R无关 = b
三：L无关，R有关 = c
四：L有关，R有关 = d(str[L]==str[R]时成立)

所以最后dp[L][R] = a+ b + c + d
而dp[L+1][R-1] = a   dp[L+1][R] = a + c     dp[L][R-1] = a + b
所以 a + b + c = dp[L+1][R] + dp[L][R-1] - dp[L+1][R-1]
str[L]==str[R]时，d = dp[L+1][R-1] + 1 (因为中间可以是空串)

public static int way1(String str) {
    char[] s = str.toCharArray();
    int len = s.length;
    int[][] dp = new int[len + 1][len + 1];
    for (int i = 0; i <= len; i++) {
        dp[i][i] = 1;
    }
    // dp[i][j]，在空串不算回文串的情况下，求str[i..j]有多少不同的回文子序列
    // index -> dp
    // str[index-1]
    // dp 1 str 0
    // dp 2 str 1
    for (int subLen = 2; subLen <= len; subLen++) {
        for (int l = 1; l <= len - subLen + 1; l++) {
            int r = l + subLen - 1;
            dp[l][r] += dp[l + 1][r];
            dp[l][r] += dp[l][r - 1];
            if (s[l - 1] == s[r - 1])
                dp[l][r] += 1;
            else
                dp[l][r] -= dp[l + 1][r - 1];
        }
    }
    return dp[1][len];
}

给定一个正数1，裂开的方法有一种，(1) 给定一个正数2，裂开的方法有两种，(1和1)、(2) 给定一个正数3，裂开的方法有三种，(1、1、1)、(1、2)、
(3) 给定一个正数4，裂开的方法有五种，
(1、1、1、1)、(1、1、2)、(1、3)、(2、2)、 (4)
给定一个正数n，求裂开的方法数。 动态规划优化状态依赖的技巧

思路：
定义一个函数f(1,N)，限制裂开的值不能比1小，递归调用f(X,N-X)，若调用到f(N,0)，则认为是一种方法

//暴力递归
public static int ways1(int n) {
    if (n < 1) {
        return 0;
    }
    return process(1, n);
}

// pre  要裂开rest的，前一个约束(rest裂开的第一个部分不能<pre)
// rest 还剩多少值，需要去裂开
// 返回裂开的方法数
public static int process(int pre, int rest) {
    if (rest == 0) {
        return 1; // 之前裂开的方案，构成了1种有效方法
    }
    // 如果rest还剩下东西
    if (pre > rest) {
        return 0;
    }
    int ways = 0;
    for (int i = pre; i <= rest; i++) { // i : rest第一个裂开的部分，值是多少
        ways += process(i, rest - i);
    }
    return ways;
}

//改动态规划
//枚举行为可以优化
public static int ways1dp(int n) {
    if (n < 1) {
        return 0;
    }
    // pre -> 0  ~ n  (0不用)
    // rest -> 0 ~ n
    int[][] dp = new int[n+1][n+1];
    // dp[0][...]不需要填
    for(int pre = 1; pre <= n; pre++) {
        dp[pre][0] = 1;
    }
    for(int pre = n; pre >= 1; pre--) {
        for(int rest = pre; rest <= n; rest++) {
            // dp[pre][rest]
            int ways = 0;
            for (int i = pre; i <= rest; i++) { // i : rest第一个裂开的部分，值是多少
                ways += dp[i] [rest - i];
            }
            dp[pre][rest] = ways;
        }
    }
    return dp[1][n];
}

//优化动态规划的枚举行为
//dp[i][j] = dp[i+1][j] + dp[i][j-i]

public static int ways3(int n) {
    if (n < 1) {
        return 0;
    }
    int[][] dp = new int[n + 1][n + 1];
    for (int pre = 1; pre < dp.length; pre++) {
        dp[pre][0] = 1;
    }
    for (int pre = 1; pre < dp.length; pre++) {
        dp[pre][pre] = 1;
    }
    for (int pre = n - 1; pre > 0; pre--) {
        for (int rest = pre + 1; rest <= n; rest++) {
            dp[pre][rest] = dp[pre + 1][rest] + dp[pre][rest - pre];
        }
    }
    return dp[1][n];
}

给定一个正数N，代表你有1～N这些数字。在给定一个整数K。
你可以随意排列这些数字，但是每一种排列都有若干个逆序对。返回有多少种排列，正好有K个逆序对

例子1:
Input: n = 3, k = 0
Output: 1
解释：
只有[1,2,3]这一个排列有0个逆序对。 

例子2:
Input: n = 3, k = 1
Output: 2
解释
[3,2,1]有(3,2)、(3,1)、(2,1)三个逆序对，所以不达标。
达标的只有：
[1,3,2]只有(3,2)这一个逆序对，所以达标。
[2,1,3]只有(2,1)这一个逆序对，所以达标。

思路：
一个样本做行，一个样本做列的尝试模型
dp[i][j]表示在i行，j列中，长度是i的数中，有j个逆序对的排列数量
dp[i][j]的可能性：
一：i<j时，i放在任意一个位置S，产生的新的排列，依赖dp[i-1][j...0]
二：j>=j时，i依赖dp[i-1][j...j-i+1]

public static int dp1(int N, int K) {
    if (N < 1 || K < 0) {
        return 0;
    }
    if (K == 0) {
        return 1;
    }
    int[][] dp = new int[N + 1][K + 1];
    // dp[0][...] 不要
    dp[1][0] = 1;// dp[1][1...] 0
    for (int i = 2; i <= N; i++) {
        dp[i][0] = 1;
    }
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            // dp[i][j] i > j dp[i-1][j...0]
            // dp[i][j] i >= j dp[i-1][j....j-i+1]
            for (int s = j; s >= Math.max(0, j - i + 1); s--) {
                dp[i][j] += dp[i - 1][s];
            }
        }
    }
    return dp[N][K];
}

//优化枚举行为
public static int dp2(int N, int K) {
    if (N < 1 || K < 0) {
        return 0;
    }
    if (K == 0) {
        return 1;
    }
    int[][] dp = new int[N + 1][K + 1];
    // dp[0][...] 不要
    dp[1][0] = 1;// dp[1][1...] 0
    for (int i = 2; i <= N; i++) {
        dp[i][0] = 1;
    }
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            // dp[i][j] -> dp[i][j-1]
            // j == 1 dp[i][1] dp[i][0]
            //				if (i > j) {
            //					dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            //				}
            //				if (i <= j) {
            //					dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - i];
            //				}
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - (i <= j ? dp[i - 1][j - i] : 0);
        }
    }
    return dp[N][K];
}

给定一棵二叉树的头节点head，已知所有节点的值都不一样，返回其中最大的且符 合搜索二叉树条件的最大拓扑结构的大小。 
拓扑结构：不是子树，只要能连起来的结构都算。

public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

public static int bstTopoSize1(Node head) {
    if (head == null) {
        return 0;
    }
    int max = maxTopo(head, head);
    max = Math.max(bstTopoSize1(head.left), max);
    max = Math.max(bstTopoSize1(head.right), max);
    return max;
}

public static int maxTopo(Node h, Node n) {
    if (h != null && n != null && isBSTNode(h, n, n.value)) {
        return maxTopo(h, n.left) + maxTopo(h, n.right) + 1;
    }
    return 0;
}

public static boolean isBSTNode(Node h, Node n, int value) {
    if (h == null) {
        return false;
    }
    if (h == n) {
        return true;
    }
    return isBSTNode(h.value > value ? h.left : h.right, n, value);
}

给定一个长度为偶数的数组arr，长度记为2*N。前N个为左部分，后N个为右部分。 arr就可以表示为{L1,L2,..,Ln,R1,R2,..,Rn}， 请将数组调整成{R1,L1,R2,L2,..,Rn,Ln}的样子。
时间复杂度O(N),空间复杂度O(1)

思路：
一个f函数，i<N时，他对应的坐标是 2 * i , i > N时，对应的(i - N) * 2 - 1
循环替换数字，一直踢到环结束，但是环结束不一定表示数组的数据都替换完了

结论一（背）：当S = 3^K - 1(偶数)时，它环的出发点是1,3,9...3^(K-1)

结论二：如何把 abcde fgh   变成 fgh abcde?
解：abcde逆序，fgh逆序 -》 edcbahgf ->再逆序  fgh abcde

那么当S = 14时，他不是3^K - 1 这种数时，找到和他最接近小于他的值 8，
L1L2L3L4[L5L6L7 R1R2R3R4]R5R6R7    把括号中的按照 结论二操作
得到 L1L2L3L4 R1R2R3R4 L5L6L7 R5R6R7 ,那么，前8个就可以调用f函数找下一个环搞定
后面6个值，接着重复操作分解即可。

// 数组的长度为len，调整前的位置是i，返回调整之后的位置
// 下标不从0开始，从1开始
public static int modifyIndex2(int i, int len) {
    if (i <= len / 2) {
        return 2 * i;
    } else {
        return 2 * (i - (len / 2)) - 1;
    }
}

// 主函数
// 数组必须不为空，且长度为偶数
public static void shuffle(int[] arr) {
    if (arr != null && arr.length != 0 && (arr.length & 1) == 0) {
        shuffle(arr, 0, arr.length - 1);
    }
}

// 在arr[L..R]上做完美洗牌的调整（arr[L..R]范围上一定要是偶数个数字）
public static void shuffle(int[] arr, int L, int R) {
    while (R - L + 1 > 0) { // 切成一块一块的解决，每一块的长度满足(3^k)-1
        int len = R - L + 1;
        int base = 3;
        int k = 1;
        // 计算小于等于len并且是离len最近的，满足(3^k)-1的数
        // 也就是找到最大的k，满足3^k <= len+1
        while (base <= (len + 1) / 3) { // base > (N+1)/3
            base *= 3;
            k++;
        }
        // 3^k -1
        // 当前要解决长度为base-1的块，一半就是再除2
        int half = (base - 1) / 2;
        // [L..R]的中点位置
        int mid = (L + R) / 2;
        // 要旋转的左部分为[L+half...mid], 右部分为arr[mid+1..mid+half]
        // 注意在这里，arr下标是从0开始的
        rotate(arr, L + half, mid, mid + half);
        // 旋转完成后，从L开始算起，长度为base-1的部分进行下标连续推
        cycles(arr, L, base - 1, k);
        // 解决了前base-1的部分，剩下的部分继续处理
        L = L + base - 1; // L ->     [] [+1...R]
    }
}

// 从start位置开始，往右len的长度这一段，做下标连续推
// 出发位置依次为1,3,9...
public static void cycles(int[] arr, int start, int len, int k) {
    // 找到每一个出发位置trigger，一共k个
    // 每一个trigger都进行下标连续推
    // 出发位置是从1开始算的，而数组下标是从0开始算的。
    for (int i = 0, trigger = 1; i < k; i++, trigger *= 3) {
        int preValue = arr[trigger + start - 1];
        int cur = modifyIndex2(trigger, len);
        while (cur != trigger) {
            int tmp = arr[cur + start - 1];
            arr[cur + start - 1] = preValue;
            preValue = tmp;
            cur = modifyIndex2(cur, len);
        }
        arr[cur + start - 1] = preValue;
    }
}

// [L..M]为左部分，[M+1..R]为右部分，左右两部分互换
public static void rotate(int[] arr, int L, int M, int R) {
    reverse(arr, L, M);
    reverse(arr, M + 1, R);
    reverse(arr, L, R);
}

// [L..R]做逆序调整
public static void reverse(int[] arr, int L, int R) {
    while (L < R) {
        int tmp = arr[L];
        arr[L++] = arr[R];
        arr[R--] = tmp;
    }
}

一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。
比如， {3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。 
山峰A和山峰B能够相互看见的条件为: 
1.如果A和B是同一座山，认为不能相互看见。 
2.如果A和B是不同的山，并且在环中相邻，认为可以相互看见。 
3.如果A和B是不同的山，并且在环中不相邻，假设两座山高度的最小值为min。
1)如果A通过顺时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互 看见
2)如果A通过逆时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互 看见
3)两个方向只要有一个能看见，就算A和B可以相互看见 给定一个不含有负数且没有重复值的数组 arr，请返回有多少对山峰能够相互看见。
进阶: 给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见。

思路：
不重复：2N - 3 O(1)
进阶：
单调栈解决

最后更新： 2021年02月21日 23:44

原始链接： https://midkuro.gitee.io/2020/11/01/algorithm-trainingcamp4/

Kuro

赏

× 请我吃糖~