题目一 绳子覆盖最多点的数量

给定一个有序数组arr,代表数轴上从左到右有n个点arr[0]、arr[1]... arr[n-1],给定一个正数T，代表一根长度为T的绳子，求绳子最多能覆盖其中的几个点。

解法一-二分查找

以每个点开始，向左延伸T的长度，看有多个点被覆盖。时间复杂度：遍历一遍n,找点二分logn，O(nlogn)。

利用二分找小于等于arr[L]+k的最右侧的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 二分法
public static int maxCoverPoint(int[] arr,int K){
    if (arr == null || arr.length == 0 || K <= 0) {
        return 0;
    }
    int max=1;
    for(int L=0;L<arr.length;L++){
        int R=binarySearch(arr,L,K);
        max=Math.max(max,R-L+1);
    }
    return max;
}
public static int binarySearch(int[] arr,int i,int K){
    int L=i;
    int R=arr.length-1;
    int target=arr[i]+K;
    int ans=-1;
    while(L<=R){
        //1:找中点
        int mid=L+((R-L)>>1);
        if(arr[mid]<=target){
            ans=mid;
            L=mid+1;
        }
        else{
            R=mid-1;
        }
    }
    return ans;
}

解法二-滑动窗口

维持一个窗口，L和R位置都是不回退的，在一个点L不动，让R一直向右走不能大于绳子长度，然后让L向右走一格，看R能向右走多少。时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int maxCoverPoint2(int[] arr, int K) {
    //双指针 时间复杂度为O(N)
    if (arr == null || arr.length == 0 || K <= 0) {
        return 0;
    }
    int max=1;
    int L=0;
    int R=0;
    for(;L<arr.length;L++){
        while(R<arr.length&&arr[R]-arr[L]<=K){
            R++;
        }
        //R指向的是匹配失败的位置
        max=Math.max(max,R-L);
    }
    return max;
}

这题是窗口问题中的经典题目，窗口模型的关键之处在于双指针不回退，每次尝试下一个开头的时候，都只需要从上一个失败的位置继续尝试即可，而不需要回退R指针。

题目二 买苹果的最小袋子数

小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装包装不可拆分。可是小虎现在只想购买恰好n个苹果，小虎想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小虎将不会购买。输入一个整数n，表示小虎想购买的个苹果，返回最小使用多少袋子。如果无论如何都不能正好装下，返回-1。

暴力解法

先用暴力方法解决这个问题：用苹果数量除以8就知道了至多要用多少个8号袋，然后依次减少8号袋的数量，看剩下的苹果需要多少个6号袋…

1
2
3
4
5
6
7
8
9
10
public static int minBags(int n) {
    int y = n / 8;
    for (int i = y; i >= 0; i--) {
        int rest = n - i * 8;
        if (rest % 6 == 0) {
            return rest / 6 + i;
        }
    }
    return -1;
}

6和8的最小公倍数是24，剩下的袋子大于24时就可以停止了，因为24这部分可以被8处理为什么要用6来处理。

6和8的最大公约数是2，所以如果数量不能被2整除就可以停止了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 有可以装8个和6个袋子，给n个苹果，最小使用的袋子数
// 解
// 先用暴力方法解决这个问题：用苹果数量除以8就知道了至多要用多少个8号袋，
// 然后依次减少8号袋的数量，看剩下的苹果需要多少个6号袋…
public static int minBags(int n) {
    if (n < 0) {
        return -1;
    }
    int bag6 = -1;
    int bag8 = n / 8;
    int rest = n - 8 * bag8;
    while (bag8 >= 0 && rest < 24) {
        int restUse6 = minBagsBase6(rest);
        if (restUse6 != -1){
            bag6 = restUse6;
            break;
        }
        rest = n - 8 * (--bag8);
    }
    return bag6 == -1 ? -1 : bag6 + bag8;
}

//如果剩余苹果rest可以被装6个苹果的袋子搞定，返回袋子数量
//不能搞定返回-1
private static int minBagsBase6(int rest) {
    return rest % 6 == 0 ? (rest / 6) : -1;
}

根据结果反推，找规律

N一定是2的倍数，否则两种袋子始终装不满，原因是6和8的最小公倍数是2。
N大于等于18时，从18开始，8个数字一组。
N小于18时，直接给出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int minBag2(int apple)  {
    if ((apple & 1) != 0 ){ // 如果是奇数，返回-1
        return -1;
    }
    if (apple < 18) {
        if (apple == 0){
            return 0;
        }else if (apple == 6 || apple == 8){
            return 1;
        }else if (apple == 12 || apple == 14 || apple== 16){
            return 2;
        }
        return -1;
    }
    return (apple-18)/8 + 3;
}

题目三 吃草的获胜者

2只动物先后进行吃草，每个人只能吃4的某次方的草，比如1,4,16…,给你草的数量N，问谁最先把艹吃完。

暴力解法

先手从1份草开始尝试吃，一直到base*4 >n，看能不能赢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// n份青草放一堆，先手后手
public static String winner1(int n){
    // 0  1  2  3   4
    // 后 先 后  先  先
    if (n < 5){
        return (n == 0) || (n == 2) ? "后手" :"先手";
    }
    // n>=5时
    int base = 1; // 先手要吃的草
    while (base <= n){

        // 当前一共n份草，先手吃掉的是base份，n-base是留给后手的草
        // 当前过程是先手，之后的过程就是后手
        if (winner1(n - base).equals("后手")){
            return "先手";
        }
        // 防止溢出
        if (base > n/4){
            break;
        }
        base *= 4;
    }
    return "后手";
}

根据结果，找规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
后手,后手
先手,先手
后手,后手
先手,先手
先手,先手
后手,后手
先手,先手
后手,后手
先手,先手
先手,先手
后手,后手
先手,先手
后手,后手
先手,先手
先手,先手
后手,后手
先手,先手
后手,后手
先手,先手
先手,先手

从结果看，5次一循环，后手，先手，后手，先手，先手

1
2
3
4
5
6
7
public static String winner2(int n) {
    if (n % 5 == 0 || n % 5 == 2) {
        return "后手";
    } else {
        return "先手";
    }
}

题目四 最大正方形

给定一个N*N的矩阵matrix，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
例如:

1
2
3
4
5
01111
01001
01001
01111
01011

其中边框全是1的最大正方形的大小为4*4，所以返回4。

解法一

一个n*n的矩阵，子矩阵的数量：以任意一点n*n为左上角，任意一点n*n 为右下角，做成的长方形（两个点重合，交换的可能性少），数量为 n*n*n*n

一个n*n的矩阵，子正方形的数量：以任意一点n*n为左上角，另外一个点构成的边长会枚举1,2,3…n的数量，数量为 n*n*n

遍历正方形的每个点，然后开始枚举边长从1…边界(右边先到边界还是左边先到边界)，然后判断这个正方形的边长都为一（这时又需要遍历每条边），找到最大的正方形即可。时间复杂度为O(n*n*n*n)

解法二-预处理

此时需要2个矩阵记录连续1的信息

right矩阵信息记录每个点包括自己的右侧有多个连续的1;

down矩阵信息记录每个点包括自己的下侧有多个连续的1;

这样在我们遍历矩阵计算连续正方形时就不必在遍历矩阵了。时间复杂度优化为O(n*n*n*n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 获取预处理数组
public static void setBorderMap(int[][] m, int[][] right, int[][] down) {
    int r = m.length;
    int c = m[0].length;
    if (m[r - 1][c - 1] == 1) {
        right[r - 1][c - 1] = 1;
        down[r - 1][c - 1] = 1;
    }
    for (int i = r - 2; i != -1; i--) {
        if (m[i][c - 1] == 1) {
            right[i][c - 1] = 1; 
            down[i][c - 1] = down[i + 1][c - 1] + 1;
        }
    }
    for (int i = c - 2; i != -1; i--) {
        if (m[r - 1][i] == 1) {
            right[r - 1][i] = right[r - 1][i + 1] + 1;
            down[r - 1][i] = 1;
        }
    }
    for (int i = r - 2; i != -1; i--) {
        for (int j = c - 2; j != -1; j--) {
            if (m[i][j] == 1) {
                right[i][j] = right[i][j + 1] + 1;
                down[i][j] = down[i + 1][j] + 1;
            }
        }
    }
}

public static int getMaxSize(int[][] m) {
    int[][] right = new int[m.length][m[0].length];
    int[][] down = new int[m.length][m[0].length];
    setBorderMap(m, right, down); // O(N^2); + 

    //开始遍历每个边长
    for (int size = Math.min(m.length, m[0].length); size != 0; size--) {
        if (hasSizeOfBorder(size, right, down)) {
            return size;
        }
    }
    return 0;
}

public static boolean hasSizeOfBorder(int size, int[][] right, int[][] down) {
    // 遍历每个位置，看是否有满足的情况
    for (int i = 0; i != right.length - size + 1; i++) {
        for (int j = 0; j != right[0].length - size + 1; j++) {
            if (right[i][j] >= size && down[i][j] >= size
                    && right[i + size - 1][j] >= size
                    && down[i][j + size - 1] >= size) {
                return true;
            }
        }
    }
    return false;
}

题目五 等概率返回函数

给定一个函数f，可以1~5的数字等概率返回一个。 请加工出1~7的数字等概率返回一个的函数g。
给定一个函数f，可以a~b的数字等概率返回一个。 请加工出c~d的数字等概率返回一个的函数g。
给定一个函数f，以p概率返回0，以1-p概率返回1。 请加工出等概率返回0和1的函数g.

1解法

等概率返回1-5的函数，先把它变成等概率返回0-1的函数，如果返回是1-2,返回0，如果是得到4-5返回1，如果是得到3重新获取值。

等概率获取1-7等于等概率获取0-6,0-6在二进制上是3位，那么我们可以把等概率返回0-1的函数调用3次，获取3位数，这3位数分别组成二进制位，这样就获取到了0-7的等概率数；如果是获取到7，就重新进行计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 等概率返回 1-5
public static int f1() {
    return (int) (Math.random() * 5) + 1;
}

// 等概率返回0和1
public static int r01() {
    int res = 0;
    do {
        res = f1();
    } while (res == 3);
    return res < 3 ? 0 : 1;
}

// 等概率返回1-7
public static int g() {
    int res = 0;
    do {
        // 3个二进制位
        res = (r01() << 2) + (r01() << 1) + r01();
    } while (res == 7);
    return res + 1;
}

2解法

函数f，可以a~b的数字等概率返回一个，把该函数转换为等概率返回0~1的函数，对a~b二分，低位部分返回0，高位部分返回1，多余的数字重新计算；然后将c~d转换为0~d-c，并判断其是几位二进制，然后获取0~1的函数几次，对于多余的部分重新计算，最后的结果加+c就是等概率返回c~d的函数。

3解法

以p概率返回0，以1-p概率返回1。那么用该函数计算2次，获取到00、11就重新获取，直到获取的10和01，这2个概率为1*(1-p),获取到01返回0，获取到01返回1。

题目六 节点为n的二叉树数量

给定一个非负整数n，代表二叉树的节点个数。返回能形成多少种不同的二叉树结构(同leetcode 96)

暴力递归

N个节点，计算n个节点的函数为F(N)

  1. 左树没有节点，右树N-1个节点，F(N-1)

  2. 左树1个节点，右树N-2个节点，F(N-2)

  3. 左树2个节点，右树N-3的节点，F(2) * F(N-3)

  4. …

得出结论左树i个节点，右树N-i-1个节点,F(i) * F(N-i-1) ，将所有结果相加就是最后的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int process(int n) {
    if (n < 0) {
        return 0;
    }
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    int res = 0;
    for (int leftNum = 0; leftNum <= n - 1; leftNum++) {
        int leftWays = process(leftNum);
        int rightWays = process(n - 1 - leftNum);
        res += leftWays * rightWays;
    }
    return res;
}

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int numTrees(int n) {
    if (n < 2) {
        return 1;
    }

    int dp[] = new int[n + 1];
    dp[0] = 1;
    for (int i = 1; i < n + 1; i++) { // 节点数为i
        // 节点个数为i时 左侧节点 j-1,右侧节点 i-j
        for (int j = 1; j < i + 1; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    return dp[n];
}

题目七 完整的括号字符串

一个完整的括号字符串定义规则如下:
①空字符串是完整的。
②如果s是完整的字符串，那么(s)也是完整的。
③如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。
例如，"(() ())"，""和"(()) () "是完整的括号字符串，"())("，"()("和")"是不完整的括号字符串。
牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。

(同leetcode921)

题解

一个完整字符串的判断方法：从左向右遍历字符串，定义变量count,遇到左括号++，遇到右括号–，满足以下条件就是一个完整字符串

  1. 遍历中间没有count<0;

  2. 结束后count=0；

那么如何添加括号使其满足完整的括号字符串。定义一个新的变量ans=0,

  1. 当出现count<0时，说明缺少了左括号，ans++,并把count重新置为0；
  2. 遍历完的时候如果count>0,就添加count个右括号

参考

[绳子最大覆盖点数【窗口】][https://blog.csdn.net/ai15013602354/article/details/124161141]

[小虎去买苹果][https://bbs.huaweicloud.com/blogs/250330]