整理了一下前几个月做过的一些大厂小厂的笔试题，一开始用C++写的，后来用JAVA写的。

华为模拟题

1.计算单词平均长度

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
#include <iostream>
#include <sstream>
#include <vector>
#include <iomanip>

using namespace std;
int main(){
    string str;
    getline(cin,str);
    //单纯cin的话遇到空格就停止了，需要geiline得到带空格的一整行
    istringstream ss(str);
    string temp;
    vector<string> words;
    while (getline(ss,temp,' ')){
        words.push_back(temp);
    }
    float n=words.size();
    float sum=0;
    for(int i=0;i<n;i++){
        int a=words[i].size();
        sum+=a;
    }
    cout << fixed<<setprecision(2)<<sum/n;
    return 0;
};

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
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <sstream>
#include <vector>
#include <set>

using namespace std;
int main(){
    string str;
    getline(cin,str);
    istringstream ss(str);
    string temp;
    vector<string> words;
    while (getline(ss,temp,' ')){
        words.push_back(temp);
    }
    set<char> myset1{'a','e','i','o','u'};
    set<char> myset2{'A','E','I','O','U'};
    int n=words.size();
    for(int i=0;i<n;i++){
        for(auto ch:words[i]){
            if(myset1.find(ch)!=myset1.end()){
                ch-=32;
                cout<<ch;
            }
            else if(myset2.find(ch)!=myset2.end()){
                cout<<ch;
            }
            else if(ch>='A'&&ch<='Z'){
                ch+=32;
                cout<<ch;
            }
            else{cout<<ch;}
        }
        if(i!=n-1){cout<<' ';}
        //注意最后一个单词后不要输出空格
    }
    return 0;
};

3.排列数

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
#include <iostream>
#include <unordered_map>

using namespace std;

int helper(int n){
    int d=1;
    while (n>1){
        d=d*n;
        n--;
    }
    return d;
}

int main(){
    string str;
    cin >> str;
    int n=str.size();
    int x=helper(n);
    unordered_map<char,int>mp;
    for(auto it:str){
        auto a=mp.find(it);
        if(a==mp.end()){
            mp[it]=1;
        }
        else{
            mp[it]+=1;
        }
    }
    int c=1;
    for(auto b:mp){
        c*= helper(b.second);
    }
    cout << x/c;
    return 0;
};

图论建图模板：

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
public class Main {
    static final int N = 100010;
    static ArrayList<Integer>[] g = new ArrayList[N];
    static int[] w = new int[N];

    static void dfs(int u, int fa) {
        // Do things
        for (int x : g[u]) {
            if (x == fa)//跳过父节点
                continue;
            dfs(x, u);
            // Do things
        }
    }

    public static void main(String[] args) {
        int n, m;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int a, b;
            a = scanner.nextInt();
            b = scanner.nextInt();
            g[a].add(b);  // a->b建立一条边
            //无向图则还需要添加g[b].add(a); 
        }

        for (int i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();
        }
    }
}

美团

1.外卖的定价

小美正在设计美团外卖的定价信息。已知外卖定价的规则如下： 1. 每道菜有折扣价和原价。折扣价不能超过原价。 2. 订单有满x元减y元的优惠。当购买的菜的价格总和不小于x元时，总价格可以减y元。“减”的价格不能超过“满”的价格。 3. 满减优惠和折扣价是互斥的，当且仅当每个菜都选择了原价才可以触发满减。 4. 系统会自动为客户计算最低价格的方案。 在设计定价时，原价、折扣价和满减的价格都必须是正实数。如果设计的定价发生问题，则会提示数据错误。 请使用等价划分法设计测试用例，来测试该系统的功能。

第一行输入一个正整数n，代表菜的总数。 接下来的n行，每行输入两个实数a_i和b_i，代表每道菜的原价是a_i，折扣价是b_i。 最后一行输入两个实数x和y，代表满x元可以减y元。 

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
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<double> a(n);
    vector<double> b(n);
    double sum1=0;
    double sum2=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        cin>>b[i];
        if(a[i]<=0||b[i]<=0||b[i]>a[i]){
            cout<<"error";
            return 0;
        }
        sum1+=a[i];
        sum2+=b[i];
    }
    double x,y;
    cin>>x;
    cin>>y;
    if(x<=0||y<=0||y>x){
        cout<<"error";
        return 0;
    }
    if(sum1>=x){
        sum1-=y;
    }
    if(sum1<=sum2){sum2=sum1;}
    cout<<fixed<<setprecision(2);
    cout<<sum2;
    return 0;

}

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
28
29
30
31
32
33
34
35
36
37
38
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();  // 字符串长度
        in.nextLine();
        String s = in.nextLine();
        String t = in.nextLine();
        char[] charS = s.toCharArray();
        char[] charT = t.toCharArray();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (charS[i] == charT[i]) {
                count++;
            }
        }

        // 交换之后 可能增加1 可能增加2  这一点比较难判断
        int flag = 0;

        for (int i = 0; i < n; i++) {
            if (charS[i] == charT[i]) { // s和t在i的位置相等的话 就不用交换了
                continue;
            }
            for (int j = i + 1; j < n; j++) { //交换的结果有三种: 0 1 2
                if(charS[j]==charT[j]){
                    continue;
                }
                if (charS[j] == charT[i] && charS[i] == charT[j]) {
                    System.out.println(count + 2); // 达到交换的最大值2了 直接输出即可
                    return;
                } else if (charS[j] == charT[i] || charS[i] == charT[j]) {  // 交换后只有一个相等 flag记录一下
                    flag = 1;
                }
            }
        }
        System.out.println(count + flag);
    }

3.好矩阵个数

判断有多少3*3的好矩阵,要求只包含ABC且ABC都出现过，相邻的字符都不相等

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
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine();
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++) {
            matrix[i] = scanner.nextLine().toCharArray();
        }

        int result = 0; // 好矩阵的数量

        // 遍历每个3x3子矩阵
        for (int i = 0; i <= n - 3; i++) {
            for (int j = 0; j <= m - 3; j++) {
                if (isGood(matrix, i, j)) {
                    // 符合条件的使result++
                    result++;
                }
            }
        }
        System.out.println(result);
    }

    // 判断子矩阵是否满足2个条件
    private static boolean isGood(char[][] matrix, int row, int col) {
        Set<Character> set = new HashSet<>();

        for (int x = row; x < row + 3; x++) {
            for (int y = col; y < col + 3; y++) {
                char ch = matrix[x][y];
                set.add(ch);
                // 相邻相等的话，跟右边和跟下面的字符相比较就OK
                if (ch >= 'D' || (y + 1 < col + 3 && ch == matrix[x][y + 1]) || (x + 1 < row + 3 && ch == matrix[x + 1][y])) {
                    return false;
                }
            }
        }
        // 到了这一步表明相邻的字符没有相等的，只剩下判断ABC是否都出现过即可
        return set.size() == 3;
    }
}

4.矩阵切割

输出切割后两部分权值之后的差值最小值

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
package com.company;

import java.util.Scanner;
//第一行输出两个正整数 n 和 m ，代表蛋糕区域的行数和列数。
//        接下来的 n 行，每行输入 m 个正整数 a_{ij} ，用来表示每个区域的美味度

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n=in.nextInt();
        long[]row=new long[n];
        int m=in.nextInt();
        long[]col=new long[m];
        int[][]matrix=new int[n][m];
        for (int i = 0; i < n; i++) {
            if (i>0) row[i]=row[i-1];
            for (int j = 0; j < m; j++) {
                matrix[i][j]=in.nextInt();
                row[i]+=matrix[i][j];
            }
        }
        long sum=row[n-1];
        for (int i = 0; i < m; i++) {
            if (i>0) col[i]=col[i-1];
            for (int j = 0; j < n; j++) {
                col[i]+=matrix[j][i];
            }
        }
        long ans=Long.MAX_VALUE;
        for (long a:row){
            ans=Math.min(ans,Math.abs(sum-a*2));
        }
        for (long a:col){
            ans=Math.min(ans,Math.abs(sum-a*2));
        }
        System.out.println(ans);
    }
}

5.字符串平铺为矩阵
小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证x∗y=n，即每y个字符换行，共x行）。该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？

注：我们定义，上下左右四个方向相邻的相同字符是连通的。

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
import java.util.*;

public class Main {
    public static int minWeight(int n, String s) {
        int minW = Integer.MAX_VALUE;
        // 遍历所有可能的矩阵大小，找到所有满足x*y=n的x和y
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                int x = i;
                int y = n / i;
                // 构建矩阵
                char[][] matrix = new char[x][y];
                for (int j = 0; j < x; j++) {
                    for (int k = 0; k < y; k++) {
                        matrix[j][k] = s.charAt(j * y + k);
                    }
                }
                // 计算矩阵的权值并更新最小权值
                minW = Math.min(minW, countConnected(matrix));

                //这里面x*y=n 其中一个作为长 一个作为宽 两个情况都要考虑
                x = n / i;
                y = i;
                // 构建矩阵
                matrix = new char[x][y];
                for (int j = 0; j < x; j++) {
                    for (int k = 0; k < y; k++) {
                        matrix[j][k] = s.charAt(j * y + k);
                    }
                }
                // 计算矩阵的权值并更新最小权值
                minW = Math.min(minW, countConnected(matrix));
            }
        }
        return minW;
    }

    // 计算矩阵的连通块数量
    public static int countConnected(char[][] matrix) {
        int count = 0;
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (!visited[i][j]) {
                    count++;
                    dfs(matrix, visited, directions, i, j);
                }
            }
        }
        return count;
    }

    // 深度优先搜索连通块
    public static void dfs(char[][] matrix, boolean[][] visited, int[][] directions,
                           int x, int y) {
        visited[x][y] = true;//标记为true 避免重复计算
        for (int[] direction : directions) {
            int nx = x + direction[0];
            int ny = y + direction[1];
            if (nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length &&
                    !visited[nx][ny] && matrix[nx][ny] == matrix[x][y]) {
                dfs(matrix, visited, directions, nx, ny);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        String s = scanner.nextLine();
        System.out.println(minWeight(n, s));
    }
}

5.树形dp

小美拿到了一棵树，每个节点有一个权值。初始每个节点都是白色。

小美有若干次操作，每次操作可以选择两个相邻的节点，如果它们都是白色且权值的乘积是完全平方数，小美就可以把这两个节点同时染红。

小美想知道，自己最多可以染红多少个节点？

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
package com.company;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    //题目给出n个点和n-1条边的一棵树 可以当成有向无环图来存
    //建树完之后从叶子节点一直往上贪心
    //从树的叶子开始涂色，才是可以涂最多的方法。
    static final int N = (int) (1e5 + 10);
    static int n;
    static long w[] = new long[N]; //结点权重数组

    static ArrayList<Integer> g[] = new ArrayList[N]; //邻接表

    static boolean st[] = new boolean[N]; //标记是否染色
    static int ans;//结果

    private static boolean fun(long x) {
        long d = (long) Math.sqrt(x);
        return d * d == x;
    }

    private static void dfs(int u, int fa) {
        for (Integer x : g[u]) {
            if (x == fa) continue; //确保不访问父节点
            dfs(x, u);
            if (fun(w[u] * w[x]) && (!st[x] && !st[u])) {
                ans += 2;
                st[x] = true;
                st[u] = true;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < N; i++) {
            g[i]=new ArrayList<>();
        }
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            g[u].add(v);
            g[v].add(u);
        }
        dfs(1, -1); //从第一个结点开始dfs,其没有父结点设为-1
        System.out.println(ans);
    }

    //ps:由于只在乎相邻节点权值乘积为完全平方数的，所以不必使用所有的边建立树，而是使用乘积为平方数的边构造一棵树，然后对这棵树进行深度优先搜索

}

6.众数出现次数最多

（1）数组的和能够整除数组元素的个数，众数就是数组的平均数avg，众数的数量是n。此时计算操作数，那就是每个元素到平均数avg的距离之和除以2，除以二是因为，每一次操作，一个数加一，另一个数减一。
（2）数组的和不能整除数组元素的个数。这时，众数的数量是n-1，把数组中的一个数当做垃圾桶（称之为垃圾数），可以把多余的操作都用在垃圾数上，从而让另外n-1个数相同，达到n-1个众数。运用贪心的思想，这个垃圾数一定是数组的最大值或者最小值。

我们以最大值作为垃圾数为例，众数就是剩下n-1个数的平均值（avg），但是有可能不能整除，所以，众数有可能是avg，也有可能是avg+1，（C++、JAVA默认向下取整）。所以分众数分别是avg和avg+1两种情况讨论，假定众数就是avg，我们现在去计算操作数，定义了两个变量a，b，a用来统计减操作的次数，b用来统计加操作的次数，整体的操作数是max(a,b)，a和b的差值就是用在垃圾数上的操作次数。同理，定义c，d去计算众数是avg+1情况下的操作数。最终取min(max(a,b),max(c,d))为最终的操作数。所以，comp函数可以计算数组l到r元素的操作数。

同理，最小值作为垃圾数的操作数也通过comp函数计算。最终的结果就是最大值作为垃圾数，和最小值作为垃圾数两种情况下的操作数的最小值

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
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static long target = -1;
    private static List<Integer> remove = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];
        long sum  = 0L;
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            sum += arr[i];
        }

        // 众数要么是n个，要么是n-1个，
        // 能整除就是n个，不能整除就是n-1个，其中的一个数用来接收多余的操作
        long ans = 0L;
        if (sum % n == 0) {
            long target = sum / n;
            ans = calOps(arr,target,-1);//-1表示不需要排除任何数
        } else {
            // 基于贪心的思想，排除的数要么是最大，要么是最小，两者取操作数最小的作为结果
            Arrays.sort(arr);
            ans = Math.min( cal(arr, sum, 0), cal(arr, sum, arr.length - 1));
        }

        System.out.println(ans);
    }

    private static long cal(int[] arr, long sum, int excludeIndex) {
        long ans = 0L;
        sum = sum - arr[excludeIndex];
        long target = sum / (arr.length - 1);
        // avg = sum(n-1个数) / n-1， avg有可能整除，有可能不整除，因此不整除时还要计算众数为avg+1的操作数，取最小
        if( sum % (arr.length -1) == 0){
            return calOps(arr,target,excludeIndex);
        }else{
            return Math.min(calOps(arr,target,excludeIndex),calOps(arr,target+1,excludeIndex));
        }
    }

    /**
     * 计算排除了excludeIndex后，其他数变为target所需要的操作数
     */
    private static long calOps(int[] arr, long target, int excludeIndex) {
        long add = 0L;
        long minus = 0L;
        for (int i = 0; i < arr.length; i++) {
            if (i == excludeIndex) continue;
            if (target - arr[i] > 0) {
                // 加的操作数
                add += target - arr[i];
            } else {
                // 减的操作数
                minus += arr[i] - target;
            }
        }
        // 如果不用排除，则add==minus，
        // 否则|add-minus|多余的操作则作用在excludeIndex的数上
        return Math.max(add, minus);
    }

}

7.01串翻转

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
package com.company;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        String s = in.next();

        int sum = getNum(s);

        System.out.println(sum);

    }

    public static int getNum(String s) {

        int n = s.length();

        StringBuffer sb1 = new StringBuffer();

        StringBuffer sb2 = new StringBuffer();

        //sb1表示101010101...即以1开头的标准01串

        //sb2表示010101010...即以0开头的标准01串

        for (int i = 0; i < n; i++) {

            sb1.append((i+1)%2);

            sb2.append(i%2);

        }

        int sum = 0;

        //dp1[i][j]表示s.substring(i,j+1)这个子串根据sb1.substring(i,j+1)得到的权重值

        //dp2[i][j]表示s.substring(i,j+1)这个子串根据sb2.substring(i,j+1)得到的权重值

        //s.substring(i,j+1)这个子串的权重值取dp1[i][j]和dp2[i][j]的最小值

        int dp1[][] = new int[n][n];

        int dp2[][] = new int[n][n];

        for (int i = 0; i < n ; i++) {

            for (int j = i ; j < n; j++) {

                if (j == i ) {

                    dp1[i][j] = s.charAt(i) == sb1.charAt(i) ? dp1[i][j] : 1;

                    dp2[i][j] = s.charAt(i) == sb2.charAt(i) ? dp2[i][j] : 1;

                    sum = sum + Math.min(dp1[i][j], dp2[i][j]);

                    continue;

                }

                dp1[i][j] = dp1[i][j - 1];

                dp2[i][j] = dp2[i][j - 1];

                if (s.charAt(j) != sb1.charAt(j)) {

                    dp1[i][j] ++;

                }

                if (s.charAt(j) != sb2.charAt(j)) {

                    dp2[i][j] ++;

                }

                sum = sum + Math.min(dp1[i][j], dp2[i][j]);

            }

        }

        return sum;

    }

}


8.商家注册

请你开发一个美团商家测试系统，并用等价划分法确认商家注册信息是否成功。
商家信息必须满足以下条件：

  1. 系统中第一次注册的商家名字，被视为主店。
  2. 系统中若出现重名商家，需要判断地址是否已存在该商家。若存在，则注册失败。否则注册成功，该商家被视为分店。
  3. 商家的名字和地址必须由小写的英文字母组成，否则注册失败。
    请你输出每个商家的信息，按商家名字的字典序升序输出。需要输出商家名字，商家主店地址，商家分店数量。
    第一行输入一个正整数n，代表注册信息数量。
    接下来的n行，每行输入两个字符串，用空格隔开。分别代表商家名字和商家地址。给定的商家名字和商家地址字符串长度不超过 20，且不包含空格。
    按商家名字字典序输出全部商家信息。每行输出一个，分别输出商家名字，商家主店地址，商家分店数量，用空格隔开。
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
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        Map<String,List<String>>adMap=new TreeMap<>();
        //TreeMap默认排序方式是按照其键（key）的自然顺序进行排序，也就是升序排序。——整数从小到大，字符串按照字典顺序排列。
        for (int i = 0; i < n; i++) {
            String name=in.next();
            String address=in.next();
            if (isValid(name)&&isValid(address)){
                if (!adMap.containsKey(name)){
                    List<String>temp=new ArrayList<>();
                    temp.add(address);
                    adMap.put(name,temp);
                }
                else {
                    List<String>addressList=adMap.get(name);
                    if (!addressList.contains(address)){
                        addressList.add(address);
                        adMap.put(name,addressList);
                    }
                }
            }
        }
        for (Map.Entry<String,List<String>>a:adMap.entrySet()){
            System.out.println(a.getKey()+" "+a.getValue().iterator().next()+" "+(a.getValue().size()-1));
            //分店数量不包括主店，所以减一
        }

    }
    public static boolean isValid(String str){
        char[]s=str.toCharArray();
        int len=s.length;
        for (int i = 0; i < len; i++) {
            if (s[i]<'a'||s[i]>'z'){
                return false;
            }
        }
        return true;
    }
}

9.数组构造-经典dp

小美拿到了一个数组a，她准备构造一个数组b满足：

  1. b的每一位都和a对应位置不同
  2. b的所有元素之和都和a相同。
  3. b的数组均为正整数。
    请你告诉小美有多少种构造方式。由于答案过大，请对10的9次方+7取模。
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
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[]arr=new int[n];
        int sum=0;
        for (int i = 0; i < n; i++) {
            arr[i]=in.nextInt();
            sum+=arr[i];
        }
        long[][]dp=new long[305][505];
        dp[0][0]=1;//dp i j表示前i个数总和为j的方案数
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                for (int k = 1; k <= j; k++) {//k表示最后一个数
                    if (k==arr[i-1]) continue;
                    dp[i][j]=(dp[i-1][j-k]+dp[i][j])%(long)(1e9+7);
                }
            }
        }
        System.out.println(dp[n][sum]);
    }
}

10. 平均数为k的最长连续子数组

给定n个正整数组成的数组，求平均数正好等于 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
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k=in.nextInt();
        int[]arr=new int[n];
        long[]sum=new long[n+1];
        sum[0]=0;
        for (int i = 0; i < n; i++) {
            arr[i]=in.nextInt()-k;
            sum[i+1]=sum[i]+arr[i];
        }
        long ans=-1;
        Map<Long,Integer>map=new HashMap<>();
        map.put(0L,0);//非常重要的一步，第一次出现前缀和为0时已经满足条件
        for (int i = 1; i <= n; i++) {
            if (!map.containsKey(sum[i])){
                map.put(sum[i],i);
            }
            else {
                long temp=i-map.get(sum[i])+1;
                ans=Math.max(ans,temp);
            }
        }
        System.out.println(ans);
    }
}

更优雅的代码，sum数组并不需要：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long pre = 0, cur;
        Map<Long, Integer> map = new HashMap<>();
        map.put(0L, 0);
        int ans = -1;
        for (int i = 1; i <= n; i++) {
            cur = pre + sc.nextInt() - k;
            if (map.containsKey(cur)) ans = Math.max(ans, i - map.get(cur));
            else map.put(cur, i);
            pre = cur;
        }
        System.out.println(ans);
    }
}

11.IP地址是否合法

某网络系统需要对输入的IP地址进行合法性判断。IP地址由四个十进制数字组成，每个数字的取值范围是0到255（包含0和255）。
IP地址的格式为X.X.X.X，其中X表示一个十进制数字。系统要求判断输入的IP地址是否合法，即满足以下条件：

​ 1.IP地址由四个数字组成，用点号分隔。

​ 2.每个数字的取值范围是0到255。

​ 3.数字之间没有多余的前导零，例如01是非法的。

​ 4.IP地址不能以点号开始或结束，例如.192.168.0.1和192.168.0.1.是非法的。

​ 不合法的情况下输出”invalid”，合法的情况下，你还需要判断是哪一类地址：

​ A类地址：地址范围从1.0.0.0到126.0.0.0

​ B类地址：地址范围从128.0.0.0到191.255.255.255

​ C类地址：范围从192.0.0.0到223.255.255.255
​ 其它地址：合法输入，但是不是A、B、C类

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
import java.util.*;

public class Main {
    public static List<Integer>adList=new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String ad=in.next();
        if (!isValid(ad)){
            System.out.println("invalid");
        }
        else {
            int ad1= adList.get(0);
            if (ad1>=1&&ad1<=125||(ad.equals("126.0.0.0"))){
                System.out.println("A_address");
            }
            else if (ad1>=128&&ad1<=191){
                System.out.println("B_address");
            }
            else if (ad1>=192&&ad1<=223){
                System.out.println("C_address");
            }
            else System.out.println("other");
        }
    }
    public static boolean isValid(String ad){
        char[]str=ad.toCharArray();
        int n=ad.length();
        if (str[0]=='.'||str[n-1]=='.'){
            return false;
        }
        int begin=0,end=0;
        for (int i = 0; i < 4; i++) {
            if (!Character.isDigit(str[end])) return false;
            while (end<n&&Character.isDigit(str[end])){
                end++;
            }
            if (end<n&&str[end]!='.') return false;
            String num=ad.substring(begin,end);
            if (num.charAt(0)=='0'&&num.length()!=1) return false;
            int number=Integer.parseInt(num);
            if (number<0||number>255) return false;
            adList.add(number);
            begin=end+1;
            end++;
            if (end>=n&&i<3)return false;
        }
        return end==n+1;
    }
}

12.小美有一个长为 n 的字符串 s，她希望删除尽可能少的字符，使得字符串不含长度为偶数的回文子串。她想知道她最少要删除几个字符，请你帮帮她吧。

13.小美拿到了一个排列，其中初始所有元素都是红色，但有一些元素被染成了白色。 小美每次操作可以选择交换任意两个红色元素的位置。她希望操作尽可能少的次数使得数组变成非降序，你能帮帮她吗？ 排列是指：一个长度为n的数组，其中 1 到n每个元素恰好出现了一次。 输入描述 第一行输入一个正整数n，代表数组的长度。 第二行输入n个正整数a_i，代表数组的元素。 第三行输入一个长度为n的字符串，代表数组元素的染色情况。第i个字符为’R’代表第i个元素被染成红色，为’W’代表初始的白色。 输出描述 如果无法完成排序，请输出 -1。 否则输出一个整数，代表操作的最小次数。

14.小美定义一个字符串的权值为：字符串长度乘以字符的种类数。例如，”arcaea”的权值为 6*4=24

​ 现在小美拿到了一个字符串，她希望你将该字符串切割成若干个连续子串，使得每个子串的权值不小于k。请你求出最终最多可以切割出的子串数量。

​ 请注意，由于字符串过长，给出的字符串将是以连续段长度形式给出，例如：aabbaaa 将描述为 a(2)b(2)a(3)，aaaaaaaaaaaab 将描述为 a(12)b(1)。

​ 输入描述
​ 第一行输入一个两个正整数n,k，代表原字符串长度和每个子串至少应取的权值。
​ 第二行一个仅包含小写字母、数字和括号的字符串。长度不超过10^6。
​ 保证所有括号内的数字之和恰好等于n。给定的每个字母后面必然包含一个括号加数字。
​ 1\leq k,n \leq 10^{18}

​ 输出描述
​ 如果整个字符串的权值小于k，请直接输出 -1。
​ 否则输出一个正整数，代表可以切割的最多子串数量。

15.有一棵有 n 个节点的树，小美在 s 节点，要去 t 节点。

​ 但小美是经常迷路的孩子，她不知道该怎么走，因此她每次都会随机选择一条之前没有走过的边走，小美想知道她能到达 t 节点的概率是多少。

​ 有多次询问，每次询问需要求出小美能到达 t 节点的概率对 10^9+7 取模后的结果。

​ 如果最后答案为分数，则最简分式后的形式为 ，其中 a 和 b 互质，那么输出整数 x 使得b \times x≡a(mod \ 10^9+7)且。可以证明这样的整数 x 是唯一的。

​ 输入描述
​ 第一行输入一个整数 n(1 \leq n \leq 2 \times 10^5) 表示树节点个数。

​ 接下来 n-1 行，每行输入两个整数 u,v(1 \leq u,v \leq n) 表示树上的边。

​ 接下来一行，输入一个整数 q(1 \leq q \leq 2 \times 10^5) 表示询问次数。

​ 接下来 q 行，每行输入两个整数 s,t(1 \leq s,t \leq n) 表示询问。

​ 输出描述
​ 输出 q 行，每行输出一个整数表示概率。

小米

1.替换喜欢的字符

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
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        Set<Character> love=new HashSet<>();
        for (int i = 0; i < m; i++) {
            String temp=in.next();
            love.add(temp.charAt(0));
        }
        String st=in.next();
        char[] str=st.toCharArray();
        boolean[] loved=new boolean[n];
        Set<Integer> loved2=new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (love.contains(str[i])){
                loved[i]=true;
            }
            else {
                loved2.add(i);
            }
        }
        for (int it:loved2){
            int len=1;
            while (true){
                if ((it-len)>=0&&loved[it-len]==true){
                    str[it]=str[it-len];
                    break;
                }
                else if ((it+len)<n&&loved[it+len]==true){
                    str[it]=str[it+len];
                    break;
                }
                else{
                    len++;
                }
            }
        }
        System.out.println(str);
    }
}

超时（91%）

优化：维护两个数组分别表示左边离它最近的偏爱字符的位置，右边离它最近的偏爱字符的位置，我们可以使用哈希表，或者一个长度为26的数组来快速判断当前字符是否为偏爱字符

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
import java.util.*;

public class Main {
    static final int N = (int)1e5 + 10;
    static int n, m;
    static int[] r = new int[N], l = new int[N];
    static String s;
    static boolean[] st = new boolean[26];  //判断偏爱字符

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0; i < m; i++){
            char ch = sc.next().charAt(0);
            st[ch - 'A'] = true;
        }
        s = sc.next();
        char[] res = new char[n];
        Arrays.fill(r, n, r.length, (int)1e9);
        Arrays.fill(l, 0, 1, (int)-1e9);
        for(int i = n - 1; i >= 0; i--){
            int x = s.charAt(i) - 'A';
            if(st[x]){  //如果当前字符为偏爱字符
                r[i] = i;
            }
            else{
                r[i] = r[i + 1];
            }
        }
        for(int i = 0; i < n; i++){
            int x = s.charAt(i) - 'A';
            if(st[x]){
                l[i] = i;
            }
            else if(i > 0){
                l[i] = l[i - 1];
            }
        }
        for(int i = 0; i < n; i++){
            int left = i - l[i], right = r[i] - i;
            if(left <= right){
                res[i] = s.charAt(l[i]);
            }
            else{
                res[i] = s.charAt(r[i]);
            }
        }
        System.out.println(new String(res));
    }
}

再优化：

在Java中，state |= (1 << (ch - 'A')); 这行代码是进行按位或操作和左移操作的组合，常用于更新一个标志变量（比如 state）以表示一组选项中的某一项是否被设置。

这里逐个解释：

  1. 1 << (ch - 'A') 是一个左移操作。它将数值 1 向左移动 (ch - 'A') 位。这里的 ch 应该是一个字符变量，通常假设它代表的是一个大写字母（ASCII码从’A’到’Z’）。通过 ch - 'A' 计算出字符 'A' 到当前字符 ch 之间的差值，这个差值作为移动的位数。例如，如果 ch 是 'B'，则差值为 1，结果就是 1 << 1 = 2；如果是 'C'，则结果是 1 << 2 = 4，以此类推。这种编码方式可以用来紧凑地用一个整数位来代表字母表中的每个字母是否存在（或者某种状态是否开启）。

  2. |= ( 是按位或赋值操作符。它会将 state 变量与表达式右侧的结果进行按位或运算，并将结果重新赋值给 state。这意味着如果 state 的某个位置上的比特位已经为1，则该位置保持不变；如果为0而右侧对应的位是1，则该位置会被置为1。

综合起来，这行代码的作用是根据字符 ch 更新 state 变量，使得 state 中对应于 ch 在字母表中位置的那个比特位被置为1，从而实现对一系列选项或状态的标记。例如，在一些算法中，可能需要跟踪输入文本中出现的大写字母的情况，这样的操作就可以简洁高效地完成这一任务。

(state >> x) & 1 == 1 的含义是检查 state 变量二进制表示的第 x 位（从右向左数，最右边为第0位）是否为1。

2.消消乐

四个整数nabc，代表砖块个数和一消二消三消的得分，消除后其余砖块会自动连在一起，给出可能的最高得分

区间DP套路：
先枚举区间长度len
在枚举左端点i 右端点j通过i+len-1计算得出
在枚举方案(有时候只有一种方案则不需要枚举)
在枚举分界点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
31
32
33
34
35
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int MAXN = 1000 + 10;
        int[][] dp = new int[MAXN][MAXN];
        int[] s = new int[MAXN];
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int c = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            s[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            dp[i][i] = a;
        }
        for (int len = 2; len <= n; len++) {
            for (int l = 0; l <= n - len; l++) {
                int r = l + len - 1;
                if (s[l] == s[r]) {
                    dp[l][r] = Math.max(dp[l][r], dp[l + 1][r - 1] + Math.max(b, a * 2));
                    for (int k = l + 1; k < r; k++) {
                        if (s[k] == s[l]) {
                            dp[l][r] = Math.max(dp[l][r], dp[l + 1][k - 1] + dp[k + 1][r - 1]+Math.max(a*3,Math.max(a+b,c)));
                        }
                    }
                }
                for (int k = l; k < r; k++) {
                    dp[l][r] = Math.max(dp[l][r], dp[l][k] + dp[k + 1][r]);
                }
            }
        }
        System.out.println(dp[0][n - 1]);
    }
}

携程

1.游游的排列统计

游游想知道，有多少个长度为n的排列满足任意两个相邻元素之和都不是素数。我们定义，长度为n的排列值一个长度为n的数组，其中1到n每个元素恰好出现了一次。

n属于2到10

2.将所有元素都变为ai（待更新）

游游拿到了一个数组，她每次操作可以任选一个元素加 1 或者减 1。游游想知道，将所有元素都变成和a_i相等需要操作最少多少次？你需要回答i∈[1,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
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> arr = new ArrayList<>();
        List<Integer> sortArr = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            int num = scanner.nextInt();
            arr.add(num);
            sortArr.add(num);
        }
        Collections.sort(sortArr);
        List<Integer> prefixSum = new ArrayList<>(Collections.nCopies(n + 1, 0));
        for (int i = 1; i <= n; ++i) {
            prefixSum.set(i, prefixSum.get(i - 1) + sortArr.get(i - 1));
        }
        for (int a : arr) {
            int index = Collections.binarySearch(sortArr, a);
            index = index >= 0 ? index : -index - 1;
            int result = index * a - prefixSum.get(index) + prefixSum.get(n) - prefixSum.get(index) - (n - index) * a;
            System.out.println(result);
        }
    }
}

3.压缩字符串

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
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
//一个字符串，代表待压缩的数组。
//字符串长度不超过 10^5，且括号内的一定是不超过10^9的正整数。数组中每个元素的值域范围是[-10^9,10^9]
//测试用例：
// [1(1),2(2),3(31),3(42),2(12)]
////[1(1),2(2),3(31),3(42),2(12),2(2)]

public class Main {
    public static int begin=1;
    public static void main(String[] args) {
        Map<Character,Integer>map=new HashMap<>();
        map.put('1',1);
        map.put('2',2);
        map.put('3',3);
        map.put('4',4);
        map.put('5',5);
        map.put('6',6);
        map.put('7',7);
        map.put('8',8);
        map.put('9',9);
        map.put('0',0);
        StringBuilder ans=new StringBuilder();
        Scanner in=new Scanner(System.in);
        String s=in.next();
        int n=s.length();
        ans.append('[');
        char[] str=s.toCharArray();
        String pre=getString(str);
        ++begin;
        int count=getDigits(str,map);
        while (begin<n){
            String temp=getString(str);
            if (temp.equals(pre)){
                ++begin;
                count+=getDigits(str,map);
            }
            else {
                ans.append(pre);
                ans.append('(');
                ans.append(count);
                ans.append(')');
                ans.append(',');
                pre=temp;
                begin++;
                count=getDigits(str,map);
            }
        }
        ans.append(pre);//最后一个pre由于没有temp比较是否相等了，需要手动添加
        ans.append('(');
        ans.append(count);
        ans.append(')');
        ans.append(']');
        System.out.println(ans.toString());



    }
    public static String getString(char[] str){
        StringBuilder ans=new StringBuilder();
        while (str[begin]!=')'&&str[begin]!='('){
            ans.append(str[begin++]);
        }
        return ans.toString();
    }
    public static int getDigits(char[] str,Map<Character,Integer>map){
        int ans=0;
        while (str[begin]!=')'){
            int a=map.get(str[begin++]);
            ans=ans*10+a;
        }
        begin+=2;//跳过）和，
        return ans;
    }
}

优化：单个字符转数字，直接减去’0’

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
package com.company;
import java.util.Scanner;
//一个字符串，代表待压缩的数组。
//字符串长度不超过 10^5，且括号内的一定是不超过10^9的正整数。数组中每个元素的值域范围是[-10^9,10^9]
//测试用例：
// [1(1),2(2),3(31),3(42),2(12)]
////[1(1),2(2),3(31),3(42),2(12),2(2)]

public class Main {
    public static int begin=1;
    public static void main(String[] args) {
        StringBuilder ans=new StringBuilder();
        Scanner in=new Scanner(System.in);
        String s=in.next();
        int n=s.length();
        ans.append('[');
        char[] str=s.toCharArray();
        String pre=getString(str);
        ++begin;
        int count=getDigits(str);
        while (begin<n){
            String temp=getString(str);
            if (temp.equals(pre)){
                ++begin;
                count+=getDigits(str);
            }
            else {
                ans.append(pre);
                ans.append('(');
                ans.append(count);
                ans.append(')');
                ans.append(',');
                pre=temp;
                begin++;
                count=getDigits(str);
            }
        }
        ans.append(pre);//最后一个pre由于没有temp比较是否相等了，需要手动添加
        ans.append('(');
        ans.append(count);
        ans.append(')');
        ans.append(']');
        System.out.println(ans.toString());



    }
    public static String getString(char[] str){
        StringBuilder ans=new StringBuilder();
        while (str[begin]!=')'&&str[begin]!='('){
            ans.append(str[begin++]);
        }
        return ans.toString();
    }
    public static int getDigits(char[] str){
        int ans=0;
        while (str[begin]!=')'){
            int a=str[begin++]-'0';
            ans=ans*10+a;
        }
        begin+=2;//跳过）和，
        return ans;
    }
}

再优化：直接调用parseInt方法，注意这个方法在Interger类中！！！

1
2
3
4
5
6
public static int getDigits(char[] str){
    String temp=getString(str);
    int ans=Integer.parseInt(temp);
    begin+=2;//跳过）和，
    return ans;
}

神州信息

涉及的知识：

public String substring(int beginIndex)
//该子字符串从指定索引处的字符开始，直到此字符串末尾。

public String substring(int beginIndex, int endIndex)
//从指定的 beginIndex 处开始，直到索引 endIndex - 1 处的字符。因此，该子字符串的长度为 endIndex-beginIndex。

split()+正则表达式来进行截取
将字符串按照分割符截取，以数组形式返回

String str = “hello, name, 12345, 6789”;
String[] strs=str.split(“,”);
for(int i=0,len=strs.length;i<len;i++){
System.out.println(strs[i].toString());
}

柠檬微趣

1.数组中有多少种组合综合为给定的数，数组中相同的数视为两个不同的数

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
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SumCombinationFinder {

    public List<List<Integer>> findCombinations(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, 0, target, new HashSet<>());
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> currentCombination, int[] nums, int start, int remainingTarget, Set<Integer> usedIndexes) {
        if (remainingTarget == 0) {
            // 找到一组符合条件的组合
            result.add(new ArrayList<>(currentCombination));
            return;
        }

        for (int i = start; i < nums.length && remainingTarget >= nums[i]; i++) {
            // 避免添加已使用的数字
            if (!usedIndexes.add(i)) {
                continue;
            }

            currentCombination.add(nums[i]);
            backtrack(result, currentCombination, nums, i, remainingTarget - nums[i], usedIndexes); // 继续搜索剩余目标
            currentCombination.remove(currentCombination.size() - 1);
            usedIndexes.remove(i); // 回溯，移除上一步添加的数字的索引
        }
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 2, 1, 1};
        int target = 4;
        SumCombinationFinder finder = new SumCombinationFinder();
        List<List<Integer>> combinations = finder.findCombinations(nums, target);

        System.out.println("和为 " + target + " 的组合有：");
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }
}

2.实现正则匹配

3.野猪骑士（超时）

新思路：滑动窗口，一次遍历

优化java写算法题的时间：快速输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // 读取一行整数
        int n = Integer.parseInt(reader.readLine());

        // 或者读取多个整数，以空格分隔
        String[] numbersStr = reader.readLine().split(" ");
        int[] numbers = new int[numbersStr.length];
        for (int i = 0; i < numbersStr.length; i++) {
            numbers[i] = Integer.parseInt(numbersStr[i]);
        }

        // 处理输入并计算结果...

        // 关闭BufferedReader
        reader.close();
    }
}

4.实现排行榜的业务逻辑：插入、删除、查询、更新，要求最坏时间复杂度为O（n），参数包括指令、名字、权值（待更新）

滴滴

1.过了

2.每个人向技术水平最接近的领导请示，给出所有员工请示的对象（待更新）

小红书

1.四舍五入保留10位小数

用到的知识：BigDecimal类

例如：

1
2
3
4
String numberStr = "123456789.1234567890123456789";
BigDecimal bd = new BigDecimal(numberStr);
bd = bd.setScale(10, RoundingMode.HALF_UP);
System.out.println(bd);

2.过了

3.每隔一段时间，随机一篇博客点赞量+1，求第一次出现点赞量全是偶数的时候总点赞量的期望（待更新）

途游

1.字符串能否通过插入’ab‘构造 过了

2.比赛怎么安排 过了

3.给定一个n个节点的有根树，根节点为1号节点。i号节点的点权为a_i。现在小红站在根节点，她每次可以选择当前节点的任意一个儿子前进（可以随时停止）。 小红需要在满足路径点权和不小于m的前提下，使得路径上的点权最大值尽可能小。请你帮小红求出这个最小的最大值（待更新）

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
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int[]power=new int[n];
        for (int i = 0; i < n; i++) {
            power[i]=in.nextInt();
        }
        int c[]=new int[n];
        List<List<Integer>>son=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer>temp=new ArrayList<>();
            c[i]=in.nextInt();
            for (int j = 0; j < c[i]; j++) {
                temp.add(in.nextInt());
            }
            son.add(temp);
        }
        int ans=power[0], sum=power[0], location=0;
        while (true){
            backdrop(location,son,0,sum,power,c);

        }
    }
    public static void backdrop(int location, List<List<Integer>> son, int begin,int sum,int[]power,int[]c){
        for (int i=begin; i < c[location]; i++) {
            location=son.get(location).get(i);
            sum+=power[location];
        }

    }
}

建信金科

1.删除字符串（待更新）

给定一个字符串，最少删除多少个字符使得每个字符的出现次数各不相同

2.删除链表（待更新）

每次随机删除一个节点和此节点的上一个节点和下一个节点，注意头节点无上一个节点，尾节点无下一个节点，求将长度为n的链表删除为空链表的删除次数期望