秋招面/笔试题目集合——08

第一题

思路：递归——》记忆化搜索

public class 第一题09 {
    public static void main(String[] args) {
        int[] arr = {1,0,2,0,0,0,1,3,0,0,0,1,0,0,0,0};
        int res1 = combines1(arr);
        System.out.println(res1);
        int res2 = combines2(arr);
        System.out.println(res2);

        int res = combines(arr);
        System.out.println(res);
    }
    public static int combines1(int[] arr) {
        return process1(arr,0,0);
    }
    private static int process1(int[] arr, int i, int j) {
        if (i == arr.length){
            return j == 0 ? 1 : 0;
        }
        if (j < 0){
            return 0;
        }
        if (arr.length - i < j){
            return 0;
        }
        int ans = 0;
        if (arr[i] > 0){
            ans = process1(arr,i + 1,j + 1);
        }else {
            ans = process1(arr,i + 1,j - 1) + process1(arr,i + 1,j + 1);
        }
        return ans;
    }

    public static int combines2(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0;i < n;i++){
            for (int j = 0;j < n;j++){
                dp[i][j] = -1;
            }
        }
        return process2(arr,0,0,dp);
    }
    private static int process2(int[] arr, int i, int j, int[][] dp) {
        if (i == arr.length){
            return j == 0 ? 1 : 0;
        }
        if (j < 0){
            return 0;
        }
        if (arr.length - i < j){
            return 0;
        }
        if (dp[i][j] != -1){
            return dp[i][j];
        }
        int ans = 0;
        if (arr[i] > 0){
            ans = process2(arr,i + 1,j + 1, dp);
        }else {
            ans = process2(arr,i + 1,j - 1, dp) + process2(arr,i + 1,j + 1, dp);
        }
        dp[i][j] = ans;
        return dp[i][j];
    }

    // 忽略染色这件事，求合法的括号结合数量
    public static int combines(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1;
            }
        }
        return f(arr, 0, 0, dp);
    }

    // 在arr[i...]范围上做决定
    // 之前在arr[0...i-1]上的决定，使得左括号比右括号多了j个
    // 最终合法的括号结合是多少
    public static int f(int[] arr, int i, int j, int[][] dp) {
        int n = arr.length;
        if (i == n) {
            return j == 0 ? 1 : 0;
        }
        if (j < 0) {
            return 0;
        }
        // i....   n-i(10个) ...(11个)
        if (n - i < j) {
            return 0;
        }
        // 如果缓存命中，直接返回答案
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int ans = 0;
        if (arr[i] > 0) {
            ans = f(arr, i + 1, j + 1, dp);
        } else {
            ans = f(arr, i + 1, j + 1, dp) + f(arr, i + 1, j - 1, dp);
        }
        dp[i][j] = ans;
        return ans;
    }
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

第二题

思路：滑动窗口

public class 第二题09 {
    public static void main(String[] args) {
        int[] arr = {1,0,1,1,1,0,1,1,1};
        int res = maxLen("abazbzzcb", arr, 2);
        System.out.println(res);
    }
    public static int maxLen(String str, int[] arr, int m) {
        int n = str.length();
        int ans = 0;
        char[] chars = str.toCharArray();
        for (char c = 'a';c <= 'z';c++){
            int r = 0;
            int change = 0;
            for (int l = 0;l < n;l++){
                while (r < n){
                    if (chars[r] == c){
                        r++;
                        continue;
                    }
                    if (arr[r] == 0 || change == m){
                        break;
                    }
                    change++;
                    r++;
                }
                ans = Math.max(ans,r - l);
                if (chars[l] != c && arr[l] == 1){
                    change--;
                }
                r = Math.max(r,l + 1);
            }
        }
        return ans;
    }
}
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