华为 OD 机试总结

  1. 核心数据
    编程语言：Java
    总分：300 分（满分400分）
    各题得分拆分：
    第一题：100 分 ×90% = 90 分
    第二题：100 分 ×100% = 100 分
    第三题：200 分 ×55% = 110 分
  2. 做题情况
    考试时有些紧张，部分API回忆耗时些许。
    第二题为纯DFS题，脑子抽风了，解题思路卡顿较久。
    第三题为抽象数据结构题，我做的时候题目图片无法显示QAQ，需自行绘制逻辑图。

字符串分割

题目描述

给定一个非空字符串S，其被N个‘-’分隔成N+1个子串，给定正整数K，要求除第一个子串外，其余的子串需先合并为一个整体，再按每K个字符组成新的子串，所有新子串之间用‘-’分隔。对于每个新组成的子串，需按以下规则转换大小写：

  1. 若子串中小写字母数量 > 大写字母数量：将所有大写字母转换为小写字母；
  2. 若子串中大写字母数量 > 小写字母数量：将所有小写字母转换为大写字母；
  3. 若大小写字母数量相等：不做转换。 最终将第一个子串与所有转换后的新子串用‘-’连接，输出结果。

输入格式

输入为两行，第一行为正整数K，第二行为非空字符串S。

输出格式

输出为转换后的字符串。

示例

示例1
输入

1
2
3
12abc-abCABc-4aB@

输出

1
12abc-abc-ABC-4aB-@

示例2
输入

1
2
12
12abc-abCABc-4aB@

输出

1
12abc-abCABc4aB@
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.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (sc.hasNextLine()) { // 注意 while 处理多个 case
            int k = Integer.parseInt(sc.nextLine());
            String[] strings = sc.nextLine().split("-");
            String s = "";
            for (int i = 1; i < strings.length; i++) {
                s += strings[i];
            }
            int index = 0;
            StringBuilder sb = new StringBuilder(strings[0]);
            while (s.length() - index > k) {
                sb.append("-" + check(s.substring(index, index + k)));
                index += k;
            }
            if (sb.length() - index > 0) {
                sb.append("-" + check(s.substring(index)));
            }
            System.out.println(sb.toString());
        }
    }
    private static String check(String str) {
        int upperNum = 0;
        int lowerNum = 0;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch >= 'a' && ch <= 'z') {
                lowerNum++;
            } else if (ch >= 'A' && ch <= 'Z') {
                upperNum++;
            }
        }
        if (lowerNum > upperNum) {
            return str.toLowerCase();
        } else if (lowerNum < upperNum) {
            return str.toUpperCase();
        } else {
            return str;
        }
    }
}

组成最大数

题目描述

小组中每位成员都有一张卡片，卡片上是 6 位内的正整数。将所有成员的卡片数字连起来可以组成多种不同的数字，要求计算能组成的最大数字。

输入描述

输入为用 “,” 号分割的多个正整数字符串，无需考虑非数字异常情况，小组人数最多 25 人。

输出描述

输出组成的最大数字字符串。

示例

示例 1

输入

1
22,221

输出

1
22221

示例 2

输入

1
4589,101,41425,9999

输出

1
9999458941425101
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String[] strings = sc.nextLine().split(",");
            Arrays.sort(strings, (a, b) -> (b + a).compareTo(a + b));
            StringBuilder sb = new StringBuilder();
            for (String str : strings) {
                sb.append(str);
            }
            System.out.println(sb.toString());
        }
    }
}

统计射击比赛成绩

题目描述

给定一个射击比赛成绩单，包含多个选手若干次射击的成绩分数，请对每个选手按其最高三个分数之和进行降序排名，输出降序排名后的选手 id 序列。

输入描述

输入第一行，一个整数 N，表示该场比赛总共进行了 N 次射击，产生 N 个成绩分数（2<=N<=100）

输入第二行，一个长度为 N 整数序列，表示参与每次射击的选手 id（0<=id<=99）

输入第三行，一个长度为 N 整数序列，表示参与每次射击选手对应的成绩（0<= 成绩 <=100）

输出描述

符合题设条件的降序排名后的选手 ID 序列

示例

输入

1
2
3
31
3,3,7,4,4,4,4,7,7,3,5,5,5
53,80,68,24,39,76,66,16,100,55,53,80,55

输出

1
5,3,7,4

说明

该场射击比赛进行了 13 次，参赛的选手为 {3,4,5,7}

3 号选手成绩 53,80,55 最高三个成绩的和为 188

4 号选手成绩 24,39,76,66 最高三个成绩的和为 205

5 号选手成绩 53,80,55 最高三个成绩的和为 188

7 号选手成绩 68,16,100 最高三个成绩的和为 184

比较各个选手最高 3 个成绩的和，有 4 号 > 3 号 = 5 号 > 7 号，由于 3 号和 5 号成绩相等，且 id 5>3，所以输出 5,3,7,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
42
43
44
45
46
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            List<Integer>ids = Arrays.stream(sc.nextLine().split(",")).map(
                                   Integer::parseInt).collect(Collectors.toList());
            List<Integer> scores = Arrays.stream(sc.nextLine().split(",")).map(
                                       Integer::parseInt).collect(Collectors.toList());
            Map<Integer, List<Integer>>id_scores = new HashMap<>();
            for (int i = 0; i < n; i++) {
                Integer id = ids.get(i);
                Integer score = scores.get(i);
                List<Integer> list = id_scores.getOrDefault(id, new ArrayList<>());
                list.add(score);
                id_scores.put(id, list);
            }
            StringBuilder sb = new StringBuilder();
            id_scores.entrySet()
            .stream()
            .filter(x->x.getValue().size() >= 3)
            .sorted((a, b)-> {
                int  asum = sum(a.getValue());
                int  bsum = sum(b.getValue());
                if (asum == bsum) {
                    return b.getKey() - a.getKey();
                } else {
                    return bsum - asum;
                }
            })
            .map(Map.Entry::getKey)
            .forEach(x->sb.append(x).append(","));
            System.out.println(sb.toString().substring(0, sb.length() - 1));
        }
    }
    private static int sum(List<Integer>list) {
        list.sort(Integer::compareTo);
        int ans = 0;
        for (int i = list.size() - 1; i >= list.size() - 3; i--) {
            ans += list.get(i);
        }
        return ans;
    }
}

字符串序列判定

题目描述

输入两个字符串 S 和 L，都只包含英文小写字母。S 长度 <=100，L 长度 <=500,000。判定 S 是否是 L 的有效子串，判定规则如下：

S 中的每个字符在 L 中都能找到（可以不连续），且 S 在Ｌ中字符的前后顺序与 S 中顺序要保持一致。

（例如，S=”ace” 是 L=”abcde” 的一个子序列且有效字符是 a、c、e，而”aec” 不是有效子序列，且有效字符只有 a、e）

输入描述

输入两个字符串 S 和 L，都只包含英文小写字母。S 长度 <=100，L 长度 <=500,000。先输入 S，再输入 L，每个字符串占一行。

输出描述

S 串最后一个有效字符在 L 中的位置。（首位从 0 开始计算，无有效字符返回 - 1）

示例

示例 1

输入

1
2
ace
abcde

输出

1
4

示例 2

输入

1
2
fgh
abcde

输出

1
-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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String S = sc.nextLine();
            String L = sc.nextLine();
            int j = 0;
            int ans = -1;
            for (int i = 0; i < L.length(); i++) {
                char lch = L.charAt(i);
                char sch = S.charAt(j);
                if (lch == sch) {
                    j++;
                }
                if (j == S.length()) {
                    ans = i;
                    break;
                }
            }
            System.out.println(ans);
        }
    }
}

数据分类

题目描述

对一个数据 a 进行分类，分类方法为：此数据 a（四个字节大小）的四个字节相加对一个给定的值 b 取模，如果得到的结果小于一个给定的值 c，则数据 a 为有效类型，其类型为取模的值；如果得到的结果大于或者等于 c，则数据 a 为无效类型。

例如：

  1. 一个数据 a=0x01010101，b=3，按照分类方法计算 (0x01+0x01+0x01+0x01)%3=1

    如果 c=2，则此 a 为有效类型，其类型为 1

    如果 c=1，则此 a 为无效类型

  2. 一个数据 a=0x01010103，b=3，按照分类方法计算 (0x01+0x01+0x01+0x03)%3=0

    如果 c=2，则此 a 为有效类型，其类型为 0

    如果 c=0，则此 a 为无效类型

输入描述

输入 12 个数据，用空格分隔：

  • 第一个数据为 c
  • 第二个数据为 b
  • 剩余 10 个数据为需要分类的数据

输出描述

输出最多数据的有效类型有多少个数据

示例

示例 1

输入

1
3 4 256 257 258 259 260 261 262 263 264 265

输出

1
3

说明

10 个数据 4 个字节相加后的结果分别为 1 2 3 4 5 6 7 8 9 10

故对 4 取模的结果为 1 2 3 0 1 2 3 0 1 2

c 为 3，所以 0、1、2 都是有效类型

类型为 1 和 2 的有 3 个数据，类型为 0 的只有 2 个数据，故输出 3

示例 2

输入

1
1 4 256 257 258 259 260 261 262 263 264 265

输出

1
2

说明

10 个数据 4 个字节相加后的结果分别为 1 2 3 4 5 6 7 8 9 10

故对 4 取模的结果为 1 2 3 0 1 2 3 0 1 2

c 为 1，所以只有 0 是有效类型，类型为 0 的有 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
28
29
30
31
32
33
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String []strings = sc.nextLine().split(" ");
            int c = Integer.parseInt(strings[0]);
            int b = Integer.parseInt(strings[1]);
            Map<Integer, Integer>count = new HashMap<>();
            for (int i = 2; i < strings.length; i++) {
                int x = Integer.parseInt(strings[i]);
                int sum = sum(x);
                sum %= b;
                if (sum < c) {
                    count.put(sum, count.getOrDefault(sum, 0) + 1);
                }
            }
            int ans = 0;
            for (int x : count.values()) {
                ans = Math.max(ans, x);
            }
            System.out.println(ans);
        }
    }
    private static int sum(int x) {
        int byte1 = (x >> 24) & 0xFF;
        int byte2 = (x >> 16) & 0xFF;
        int byte3 = (x >> 8) & 0xFF;
        int byte4 = x & 0xFF;
        return byte1 + byte2 + byte3 + byte4;
    }
}

5键键盘的输出

题目描述

有一个特殊的 5 键键盘，上面有 a，ctrl-c，ctrl-x，ctrl-v，ctrl-a 五个键，功能如下：

  • a 键：在屏幕上输出一个字母 a；
  • ctrl-c（对应数字 2）：将当前选择的字母复制到剪贴板；
  • ctrl-x（对应数字 3）：将当前选择的字母复制到剪贴板，并清空选择的字母；
  • ctrl-v（对应数字 4）：将当前剪贴板里的字母输出到屏幕；
  • ctrl-a（对应数字 5）：选择当前屏幕上的所有字母。

注意事项

  1. 剪贴板初始为空，新的内容被复制到剪贴板时会覆盖原来的内容；
  2. 当屏幕上没有字母时，ctrl-a 无效；
  3. 当没有选择字母时，ctrl-c 和 ctrl-x 无效；
  4. 当有字母被选择时，a 和 ctrl-v 这两个有输出功能的键会先清空选择的字母，再进行输出。

输入描述

输入为一行，为简化解析，用数字 1-5 代表五个键的输入，数字用空格分隔：

  • 1：a 键
  • 2：ctrl-c
  • 3：ctrl-x
  • 4：ctrl-v
  • 5：ctrl-a

输出描述

输出一个数字，为最终屏幕上字母的数量。

示例

示例 1

输入

1
1 1 1

输出

1
3

说明连续键入 3 个 a，故屏幕上字母的长度为 3。

示例 2

输入

1
1 1 5 1 5 2 4 4

输出

1
2

说明

输入两个 a 后 ctrl-a 选择这两个 a，再输入 a 时选择的两个 a 先被清空，所以此时屏幕只有一个 a，后续的 ctrl-a，ctrl-c 选择并复制了这一个 a，最后两个 ctrl-v 在屏幕上输出两个 a，故屏幕上字母的长度为 2（第一个 ctrl-v 清空了屏幕上的那个 a）。

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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String [] strings = sc.nextLine().split(" ");
            String screen = ""; //屏幕
            String temp = ""; //剪切板
            boolean selected = false; //是否被选择
            for (int i = 0; i < strings.length; i++) {
                int x = Integer.parseInt(strings[i]);
                if (x == 1) {
                    if (selected) {
                        screen = "a";
                        selected = false;
                    } else {
                        screen += "a";
                    }
                } else if (x == 2) {
                    if (selected) {
                        temp = screen;
                    }
                } else if (x == 3) {
                    if (selected) {
                        temp = screen;
                        screen = "";
                        selected = false;
                    }
                } else if (x == 4) {
                    if (selected) {
                        screen = temp;
                        selected = false;
                    } else {
                        screen += temp;
                    }
                } else if (x == 5) {
                    if (!screen.equals("")) {
                        selected = true;
                    }
                }
                // System.out.println("screen=" + screen + ",temp=" + temp + ",selected=" +
                //                    selected);
            }
            System.out.println(screen.length());
        }
    }
}

检查是否存在满足条件的数字组合

题目描述

给定一个正整数数组，检查数组中是否存在满足规则的数组组合。规则：A = B + 2×C。要求数组中的每个成员只能在结果算式中使用一次（如数组成员为 [0,0,1,5]，算式 0=0+2×0 不允许，因为使用了 3 个 0）。

输入描述

第一行输入数组的元素个数；

第二行输出所有数组元素，用空格隔开。

输出描述

如果存在满足要求的数，在同一行里依次输出规则里 A、B、C 的取值，用空格隔开；

如果不存在，输出 0。

示例

示例 1

输入

1
2
4
2 7 3 0

输出

1
7 3 2

说明

7 = 3 + 2×2，数组中每个元素仅使用一次。

备注

  1. 数组长度在 3~100 之间；
  2. 数组成员为 0~65535；
  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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String []strings = sc.nextLine().split(" ");
            int n = Integer.parseInt(strings[0]);
            int []arr = new int[n];
            for (int i = 1; i <= n; i++) {
                arr[i - 1] = Integer.parseInt(strings[i]);
            }
            boolean ans = false;
            Arrays.sort(arr);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        if (arr[k] == arr[j] + arr[i] * 2 && i != j && j != k && i != k) {
                            ans = true;
                            System.out.println(arr[k] + " " + arr[j] + " " + arr[i]);
                        }
                    }
                }
            }
            if (!ans) {
                System.out.println(0);
            }
        }
    }
}

数组拼接

题目描述

现在有多组整数数组，需要将它们合并成一个新的数组。合并规则：从每个数组里按顺序取出固定长度的内容合并到新的数组中，取完的内容会删除掉；如果该行不足固定长度或者已经为空，则直接取出剩余部分的内容放到新的数组中，继续下一行。

输入描述

第一行是每次读取的固定长度，0 < 长度 < 10；

第二行是整数数组的数目，0 < 数目 < 1000；

第 3-n 行是需要合并的数组，不同的数组用回车换行分隔，数组内部用逗号分隔，最大不超过 100 个元素。

输出描述

输出一个新的数组，用逗号分隔。

示例

示例 1

输入

1
2
3
4
3
2
2,5,6,7,9,5,7
1,7,4,3,4

输出

1
2,5,6,1,7,4,7,9,5,3,4,7

说明

  1. 获得长度 3 和数组数目 2；
  2. 先遍历第一行，获得 2,5,6；
  3. 再遍历第二行，获得 1,7,4；
  4. 再循环回到第一行，获得 7,9,5；
  5. 再遍历第二行，获得 3,4；
  6. 再回到第一行，获得 7，按顺序拼接成最终结果。

示例 2

输入

1
2
3
4
5
4
3
1,2,3,4,5,6
1,2,3
1,2,3,4

输出

1
1,2,3,4,1,2,3,1,2,3,4,5,6
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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int len = Integer.parseInt(sc.nextLine());
            int cnt = Integer.parseInt(sc.nextLine());
            List<String> list = new ArrayList<>();
            for (int i = 1; i <= cnt; i++) {
                list.add(sc.nextLine());
            }
            Map<Integer, Queue<Integer>>map = new HashMap<>();
            for (int i = 0; i < list.size(); i++) {
                String []strings = list.get(i).split(",");
                Queue<Integer> queue = new ArrayDeque<>();
                for (String str : strings) {
                    queue.offer(Integer.parseInt(str));
                }
                map.put(i, queue);
            }
            int num = 0;
            List<Integer>ans = new ArrayList<>();
            while (!map.isEmpty()) {
                if (map.containsKey(num)) {
                    for (int i = 0; i < len; i++) {
                        if (map.get(num).isEmpty()) {
                            map.remove(num);
                            break;
                        }
                        ans.add(map.get(num).poll());
                    }
                }
                num++;
                num %= list.size();
            }
            System.out.println(ans.toString().substring(1, ans.toString().length() - 1));
        }
    }
}

数列描述

题目描述

有一个数列 A [n]，从 A [0] 开始每一项都是一个数字字符串，数列中 A [n+1] 是对 A [n] 的描述，生成规则如下：

  • A [0] = 1（初始项）
  • A [1] = 11：含义是 A [0] 由 “1 个 1” 组成，即从左到右连续出现 1 次 1
  • A [2] = 21：含义是 A [1] 由 “2 个 1” 组成，即从左到右连续出现 2 次 1
  • A [3] = 1211：含义是 A [2] 由 “1 个 2、1 个 1” 组成，即从左到右先连续出现 1 次 2，再连续出现 1 次 1
  • A [4] = 111221：含义是 A [3] 由 “1 个 1、1 个 2、2 个 1” 组成，即从左到右先连续出现 1 次 1，再连续出现 1 次 2，最后连续出现 2 次 1

给定整数 n（0<=n<=59），输出数列的第 n 项结果。

输入描述

输入一个整数 n，表示数列的第 n 项（0<=n<=59）。

输出描述

输出数列第 n 项的字符串内容。

示例

示例 1

输入

1
4

输出

1
111221
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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<String>list = new ArrayList<>();
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            list.add("1");
            for (int i = 1; i <= n; i++) {
                String str = list.get(i - 1);
                String str1 = process(str);
                // System.out.println(str1);
                list.add(str1);
            }
            System.out.println(list.get(n));
        }
    }
    private static String process(String str) {
        int len = str.length();
        int i = 0;
        int cnt = 0;
        char ch;
        StringBuilder sb = new StringBuilder();
        while (i < len) {
            ch = str.charAt(i);
            while (str.charAt(i) == ch && i < len) {
                cnt++;
                i++;
                if (i >= len) {
                    break;
                }
            }
            sb.append(cnt).append(ch);
            cnt = 0;
        }
        return sb.toString();
    }
}

考勤信息

题目描述

公司用一个字符串来表示员工的出勤信息：

  • absent：缺勤
  • late：迟到
  • leaveearly：早退
  • present：正常上班

现需根据员工出勤信息，判断本次是否能获得出勤奖，能获得出勤奖的条件如下：

  1. 缺勤不超过一次；
  2. 没有连续的迟到 / 早退；
  3. 任意连续 7 次考勤，缺勤 / 迟到 / 早退不超过 3 次。

输入描述

第一行输入一个整数 n，表示有多少个员工；后面 n 行，每一行输入若干个字符串（用空格分隔），表示第 i 名员工的出勤信息。

输出描述

输出 n 行，每一行表示这名员工能否获得出勤奖，如果可以，则输出 “true”，否则输出 “false”。

示例

示例 1

输入

1
2
3
2
present
present absent present present leaveearly present absent

输出

1
true false

示例 2

输入

1
2
3
2
present
present present

输出

1
true true
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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    static Map<String, Integer>map = new HashMap<>();
    static {
        map.put("absent", 0);
        map.put("late", 1);
        map.put("leaveearly", 1);
        map.put("present", 2);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            StringBuilder ans = new StringBuilder();
            for (int i = 1; i <= n; i++) {
                String str = sc.nextLine();
                ans.append(judge(str) + " ");
            }
            System.out.println(ans.toString());
        }
    }
    private static boolean judge(String str) {
        String []strings = str.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String str1 : strings) {
            sb.append(map.get(str1));
        }
        String s = sb.toString();
        int absentCnt = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            if (ch == '0') {
                absentCnt++;
                if (absentCnt > 1) {
                    return false;
                }
            } else if (ch == '1') {
                if (s.charAt(i + 1) == '1' && i + 1 < len) {
                    return false;
                }
            }
            if (i >= 6) {
                int badCnt = 0;
                for (int j = i; j >= i - 6; j--) {
                    if (s.charAt(j) != '2') {
                        badCnt++;
                    }
                }
                if (badCnt > 3) {
                    return false;
                }
            }
        }
        return true;
    }
}

按单词下标区间翻转文章内容

题目描述

输入一个英文文章片段，翻转指定区间的单词顺序，标点符号和普通字母一样处理。

例如输入字符串 “I am a developer.”，区间 [0,3] 则输出 “developer. a am I”。

输入描述

使用换行隔开三个参数：

第一个参数为英文文章内容即英文字符串；

第二个参数为反转起始单词下标，下标从 0 开始；

第三个参数为结束单词下标。

输出描述

反转后的英文文章片段，所有单词之间以一个半角空格分割进行输出。

示例

示例 1

输入

1
2
3
I am a developer.
1
2

输出

1
I a am developer.

示例 2

输入

1
2
3
Hello world!
0
1

输出

1
world! Hello

说明

输入字符串可以在前面或者后面包含多余的空格，但是反转后的不能包含多余空格。

示例 3

输入

1
2
3
I am a developer.
0
3

输出

1
developer. a am I

说明

如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

示例 4

输入

1
2
3
Hello!
0
3

输出

1
Hello!

说明

指定反转区间只有一个单词，或无有效单词则统一输出原字符串。

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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String []strings = sc.nextLine().split(" ");
            int start = Integer.parseInt(sc.nextLine());
            int end = Integer.parseInt(sc.nextLine());
            System.out.println(solve(strings, start, end));
        }
    }
    private static String solve(String [] strings, int start, int end) {
        StringBuilder sb = new StringBuilder();
        int n = strings.length;
        end = Math.min(end, n - 1);
        if (start > n - 1 || (end - start + 1) == 1) {
            for (int i = 0; i < n - 1; i++) {
                sb.append(strings[i]).append(" ");
            }
            sb.append(strings[n - 1]);
            return sb.toString();
        }
        int i = start, j = end;
        while (i < j) {
            String temp = strings[i];
            strings[i] = strings[j];
            strings[j] = temp;
            i++;
            j--;
        }
        for (int k = 0; k < n - 1; k++) {
            sb.append(strings[k]).append(" ");
        }
        sb.append(strings[n - 1]);
        return sb.toString();
    }
}

最大括号深度

题目描述

现有一字符串仅由 ‘(‘，’)’，‘{‘，’}’，’[‘，’]’六种括号组成。若字符串满足以下条件之一，则为无效字符串：

①任一类型的左右括号数量不相等；

②存在未按正确顺序（先左后右）闭合的括号。

输出括号的最大嵌套深度，若字符串无效则输出 0。

备注：0≤字符串长度≤100000

输入描述

一个只包括 ‘(‘，’)’，‘{‘，’}’，’[‘，’]’的字符串

输出描述

一个整数，最大的括号深度

示例

示例 1

输入

1
[]

输出

1
1

说明

有效字符串，最大嵌套深度为 1

示例 2

输入

1
([]{()})

输出

1
3

说明

有效字符串，最大嵌套深度为 3

示例 3

输入

1
(]

输出

1
0

说明

无效字符串，有两种类型的左右括号数量不相等

示例 4

输入

1
([)]

输出

1
0

说明

无效字符串，存在未按正确顺序闭合的括号

示例 5

输入

1
)(

输出

1
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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String str = sc.nextLine();
            System.out.println(solve(str));
        }
    }
    private static int  solve(String str) {
        int ans = 0;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (stack.isEmpty()) {
                if (!(ch == '(' || ch == '[' || ch == '{')) {
                    ans = 0;
                    break;
                }
                stack.push(ch);
                ans = Math.max(ans, stack.size());
            } else if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
                ans = Math.max(ans, stack.size());
            } else {
                char ch1 = stack.peek();
                if ((ch1 == '(' && ch != ')') || (ch1 == '[' && ch != ']') || (ch1 == '{' &&
                        ch != '}')) {
                    ans = 0;
                    break;
                }
                stack.pop();
            }
        }
        return ans;
    }
}

字符串加密

题目描述

给你一串未加密的字符串 str，通过对字符串的每一个字母进行改变来实现加密，加密规则如下：

  1. 对字符串的每一个字母 str [i] 偏移特定数组元素 a [i] 的量；
  2. 偏移数组 a 的初始值：a [0]=1，a [1]=2，a [2]=4；
  3. 当 i>=3 时，数组元素 a [i] = a [i-1] + a [i-2] + a [i-3]。

例如：原文 abcde 加密后 bdgkr，其中偏移量分别是 1,2,4,7,13。

输入描述

第一行为一个整数 n（1<=n<=1000），表示有 n 组测试数据；

每组数据包含一行，为原文 str（只含有小写字母，0 < 长度 <=50）。

输出描述

每组测试数据输出一行，表示字符串的密文。

示例

示例 1

输入

1
2
1
xy

输出

1
ya

说明

第一个字符 x 偏移量是 1，即为 y，第二个字符 y 偏移量是 2，即为 a。

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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int []a = new int[100];
            a[0] = 1;
            a[1] = 2;
            a[2] = 4;
            for (int i = 3; i < 50; i++) {
                a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 26;
            }
            int n = Integer.parseInt(sc.nextLine());
            for (int i = 0; i < n; i++) {
                String str = sc.nextLine();
                System.out.println(solve(str, a));
            }
        }
    }
    private static String solve(String str, int []a) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            for (int j = 0; j < a[i]; j++) {
                ch += 1;
                if (ch > 'z') {
                    ch = 'a';
                }
            }
            sb.append((char)ch);
        }
        return sb.toString();
    }
}

整数对最小和

题目描述

给定两个整数数组 array1、array2，数组元素按升序排列。假设从 array1、array2 中分别取出一个元素可构成一对元素，现在需要取出 k 对元素，并对取出的所有元素求和，计算和的最小值。

注意：两对元素如果对应于 array1、array2 中的两个下标均相同，则视为同一对元素。

输入描述

输入两行数组 array1、array2，每行首个数字为数组大小 size (0 < size <= 100)；

0 < array1 [i] <= 1000；

0 < array2 [i] <= 1000；

接下来一行为正整数 k（0 < k <= array1.size () * array2.size ()）。

输出描述

满足要求的最小和

示例

示例 1

输入

1
2
3
3 1 1 2
3 1 2 3
2

输出

1
4

说明

用例中，需要取 2 对元素

取第一个数组第 0 个元素与第二个数组第 0 个元素组成 1 对元素 [1,1];

取第一个数组第 1 个元素与第二个数组第 0 个元素组成 1 对元素 [1,1];

求和为 1+1+1+1=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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int []arr1 = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                             Integer::parseInt).toArray();
            int []arr2 = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                             Integer::parseInt).toArray();
            int k = Integer.parseInt(sc.nextLine());
            List<Integer>list = new ArrayList<>();
            for (int i = 0; i < arr1.length; i++) {
                for (int j = 0; j < arr2.length; j++) {
                    list.add(arr1[i] + arr2[j]);
                }
            }
            list.sort(null);
            int ans = 0;
            for (int i = 0; i < k; i++) {
                ans += list.get(i);
            }
            System.out.println(ans);
        }
    }
}

求字符串中所有整数的最小和

题目描述

输入字符串 s，输出 s 中包含所有整数的最小和，规则如下：

  1. 字符串 s 只包含 a~z、A~Z、+、-；
  2. 合法的整数包括正整数（一个或者多个 0-9 组成，如：0、2、3、002、102）；
  3. 负整数（负号开头，数字部分由一个或者多个 0-9 组成，如 - 2、-012、-23、-00023）。

输入描述

包含数字的字符串

输出描述

所有整数的最小和

示例

示例 1

输入

1
bb1234aa

输出

1
10

说明

1+2+3+4=10

示例 2

输入

1
bb12-34aa

输出

1
-31

说明

1+2-34=-31

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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String str = sc.nextLine();
            int i = 0;
            int n = str.length();
            int ans = 0;
            while (i < n) {
                char ch = str.charAt(i);
                if (ch == '-') {
                    i++;
                    int x = 0;
                    while (str.charAt(i) >= '0' && str.charAt(i) <= '9' && i < n) {
                        x = x * 10 + (str.charAt(i) - '0');
                        i++;
                        if (i >= n) {
                            break;
                        }
                    }
                    ans -= x;
                    continue;
                } else if (ch >= '0' && ch <= '9') {
                    ans += ch - '0';
                }
                i++;
            }
            System.out.println(ans);
        }
    }
}

两数之和绝对值最小

题目描述

给定一个从小到大的有序整数序列（存在正整数和负整数）数组 nums，请你在该数组中找出两个数，其和的绝对值 (|nums [x]+nums [y]|) 为最小值，并返回这个绝对值。每种输入只会对应一个答案，且数组中同一个元素不能使用两遍。

输入描述

一个通过空格分割的有序整数序列字符串，最多 1000 个整数，且整数数值范围是 - 65535~65535。

输出描述

两数之和绝对值最小值

示例

示例 1

输入

1
-3 -1 5 7 11 15

输出

1
2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int [] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                             Integer::parseInt).toArray();
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    ans = Math.min(ans, Math.abs(arr[i] + arr[j]));
                }
            }
            System.out.println(ans);
        }
    }
}

非严格递增连续数字序列

题目描述

输入一个字符串仅包含大小写字母和数字，求字符串中包含的最长的非严格递增连续数字序列的长度（比如 12234 属于非严格递增连续数字序列）。

输入描述

输入一个字符串仅包含大小写字母和数字，输入的字符串最大不超过 255 个字符。

输出描述

最长的非严格递增连续数字序列的长度

示例

示例 1

输入

1
abc2234019A334bc

输出

1
4

说明

2234 为最长的非严格递增连续数字序列，所以长度为 4

测试用例 1

输入

1
aaaaaa44ko543j123j7345677781

输出

1
8

说明

34567778 为最长的非严格递增连续数字序列，长度为 8

测试用例 2

输入

1
aaaaa34567778a44ko543j123j71

输出

1
8

说明

34567778 为最长的非严格递增连续数字序列，长度为 8

测试用例 3

输入

1
345678a44ko543j123j7134567778aa

输出

1
9

说明

134567778 为最长的非严格递增连续数字序列，长度为 9

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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String str = sc.nextLine();
            int ans = 0;
            int len = 0;
            char pre = '0';
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                if (ch >= pre && ch <= '9') {
                    len++;
                    pre = ch;
                    ans = Math.max(ans, len);
                } else if (ch >= '0' && ch <= '9') {
                    len = 1;
                    pre = ch;
                } else {
                    len = 0;
                    pre = '0';
                }
            }
            System.out.println(ans);
        }
    }
}

分积木

题目描述

Solo 和 koko 是两兄弟，妈妈给了他们一大堆积木，每块积木上都有自己的重量。现在他们想要将这些积木分成两堆：

  1. 哥哥 Solo 负责分配，弟弟 koko 要求两个人获得的积木总重量 “相等”（根据 Koko 的逻辑），个数可以不同，不然就会哭；
  2. Koko 的加法逻辑：先将两个数转成二进制再进行加法，且总会忘记进位（每个进位都忘记）。例如 25（11001）加 11（01011）时，koko 得到的计算结果是 18（10010）。

Solo 想要尽可能使自己得到的积木总重量最大，且不让 koko 哭。

输入描述

第一行是一个整数 N (2≤ N ≤100)，表示有多少块积木；

第二行为空格分开的 N 个整数 Ci (1 ≤ Ci ≤ 1000)，表示第 i 块积木的重量。

输出描述

如果能让 koko 不哭，输出 Solo 所能获得积木的最大总重量；否则输出 “-1”。

示例

示例 1

输入

1
2
3
3 5 6

输出

1
11

说明

Solo 能获得重量为 5 和 6 的两块积木，5 转换成二进制是 101，6 的二进制是 110，按照 koko 的计算方法（忘记进位），结果为 3（二进制 011）。koko 获得重量为 3 的积木，而 solo 获得重量为 11（十进制，5 + 6）的积木。

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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                            Integer::parseInt).toArray();
            System.out.println(solve(arr));
        }
    }
    private static int solve(int []arr) {
        int sum = 0;
        int x = 0;
        int minValue = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            x ^= arr[i];
            sum += arr[i];
            minValue = Math.min(minValue, arr[i]);
        }
        if (x != 0) {
            return -1;
        } else {
            return sum - minValue;
        }
    }
}

连续字母长度

题目描述

给定一个字符串，只包含大写字母，求在包含同一字母的子串中，长度第 k 长的子串的长度，相同字母只取最长的那个子串。

输入描述

第一行有一个子串 (1 < 长度 <=100)，只包含大写字母。

第二行为 k 的值。

输出描述

输出连续出现次数第 k 多的字母的次数。

示例

用例 1

输入

1
2
AAAAHHHBBCDHHHH
3

输出

1
2

说明

同一字母连续出现的最多的是 A 和 H，四次；

第二多的是 H，3 次，但是 H 已经存在 4 个连续的，故不考虑；

下个最长子串是 BB，所以最终答案应该输出 2。

用例 2

输入

1
2
AABAAA
2

输出

1
1

说明

同一字母连续出现的最多的是 A，三次；

第二多的还是 A，两次，但 A 已经存在最大连续次数三次，故不考虑；

下个最长子串是 B，所以输出 1。

用例 3

输入

1
2
ABC
4

输出

1
-1

说明

只含有 3 个包含同一字母的子串，小于 k，输出 - 1。

用例 4

输入

1
2
ABC
2

输出

1
1

说明

三个子串长度均为 1，所以此时 k = 1，k=2，k=3 这三种情况均输出 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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            int k = Integer.parseInt(sc.nextLine());
            System.out.println(solve(s, k));
        }
    }
    private static int solve(String s, int k) {
        if (s.length() < k) {
            return -1;
        }
        int []cnt = new int [26];
        int n = s.length();
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j + 1 < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            int index = s.charAt(i) - 'A';
            cnt[index] = Math.max(cnt[index], j - i);
            i = j;
        }
        List<Integer>list = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) {
                list.add(cnt[i]);
            }
        }
        if (list.size() < k) {
            return -1;
        }
        Arrays.sort(cnt);
        return cnt[26 - k];
    }
}

滑动窗口最大和

题目描述

有一个 N 个整数的数组，和一个长度为 M 的窗口，窗口从数组内的第一个数开始滑动直到窗口不能滑动为止，每次窗口滑动产生一个窗口和（窗口内所有数的和），求窗口滑动产生的所有窗口和的最大值。

输入描述

第一行输入一个正整数 N，表示整数个数。（0<N<100000）

第二行输入 N 个整数，整数的取值范围为 [-100,100]。

第三行输入一个正整数 M，M 代表窗口大小，M<=100000，且 M<=N。

输出描述

窗口滑动产生的所有窗口和的最大值。

示例

输入

1
2
3
6
10 20 30 15 23 12
3

输出

1
68

说明

窗口长度为 3，窗口滑动产生的窗口和分别为 10+20+30=60，20+30+15=65，30+15+23=68，15+23+12=50，所以窗口滑动产生的所有窗口和的最大值为 68。

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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            int [] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                             Integer::parseInt).toArray();
            int m = Integer.parseInt(sc.nextLine());
            System.out.println(solve(n, m, arr));
        }
    }
    private static int solve(int n, int m, int []arr) {
        int ans = 0;
        int sum = 0;
        for (int i = 0; i < m; i++) {
            sum += arr[i];
        }
        int top = 0;
        ans = Math.max(ans, sum);
        for (int i = m; i < n; i++) {
            sum -= arr[top];
            sum += arr[i];
            top++;
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

素数之积

题目描述

RSA 加密算法在网络安全世界中无处不在，它利用了极大整数因数分解的困难度，数据越大，安全系数越高，给定一个 32 位正整数，请对其进行因数分解，找出是哪两个素数的乘积。

输入描述

一个正整数 num（0<num<=2147483647）。

输出描述

如果成功找到，以单个空格分割，从小到大输出两个素数；分解失败，请输出 - 1 -1。

示例

示例 1

输入

1
15

输出

1
3 5

说明

因数分解后，找到两个素数 3 和 5，使得 3*5=15，按从小到大排列后，输出 3 5。

示例 2

输入

1
27

输出

1
-1 -1

说明

通过因数分解，找不到任何素数，使得他们的乘积为 27，输出 - 1 -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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            System.out.println(solve(n));
        }
    }
    private  static boolean isPrime(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return  true;
    }
    private static String solve(int n) {
        for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
            if (isPrime(i) == true && isPrime(n / i) == true && n % i == 0) {
                return new String(i + " " + n / i);
            }
        }
        return new String("-1 -1");
    }
}

仿 LISP 运算

题目描述

小基设计了一种简化版的 LISP 语言，其唯一的语法就是括号要配对。

形如 (OP P1 P2 …)，括号内元素由单个空格分割。

其中第一个元素 OP 为操作符，后续元素均为其参数，参数个数取决于操作符类型。

注意

  1. 参数 P1, P2 也有可能是另外一个嵌套的 (OP P1 P2 …)；
  2. 当前 OP 类型为 add /sub/mul /div（全小写），分别代表整数的加减乘除法，简单起见，所有 OP 参数个数均为 2；
  3. 题目涉及数字均为整数，可能为负；
  4. 不考虑 32 位溢出翻转，计算过程中也不会发生 32 位溢出翻转；
  5. 除零错误时，输出 “error”；
  6. 除法遇除不尽，向下取整，即 3/2 = 1。

输入格式

输入为长度不超过 512512512 的字符串，用例保证了无语法错误。

输出格式

输出计算结果或者 “error”。

样例

样例 1

输入

1
(div 12 (sub 45 45))

输出

1
error

解释说明

45 减 45 得 0，12 除以 0 为除零错误，输出 error。

样例 2

输入

1
(add 1 (div -7 3))

输出

1
-2

解释说明

-7 除以 3 向下取整得 - 3，1 加 - 3 得 - 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
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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    static Stack<Integer>numStack = new Stack<>();
    static Stack<String>opStack = new Stack<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            int n = s.length();
            int pos = 0;
            for (int i = 0; i < n; i++) {
                char ch = s.charAt(i);
                if (ch == '(') {
                    opStack.push(s.substring(i + 1, i + 4));
                    i += 4;
                    pos = i + 1;
                } else if (ch == ')') {
                    if (pos < i) {
                        numStack.push(Integer.parseInt(s.substring(pos, i)));
                        i += 1;
                        pos = i + 1;
                    }
                    int num2 = numStack.pop();
                    int num1 = numStack.pop();
                    calculate(num1, num2);
                } else if (ch == ' ') {
                    if (pos < i) {
                        numStack.push(Integer.parseInt(s.substring(pos, i)));
                        pos = i + 1;
                    }
                }
            }
            while (opStack.size() != 0) {
                int num2 = numStack.pop();
                int num1 = numStack.pop();
                calculate(num1, num2);
            }
            System.out.println(numStack.get(0));
        }
    }
    private static void calculate(int num1, int num2) {
        String op = opStack.pop();
        if (op.equals("add")) {
            numStack.push(num1 + num2);
        } else if (op.equals("sub")) {
            numStack.push(num1 - num2);
        } else if (op.equals("mul")) {
            numStack.push(num1 * num2);
        } else if (op.equals("div")) {
            if (num2 == 0) {
                System.out.println("error");
                System.exit(0);
            }
            int x = num1 / num2; //考虑负数的情况
            if (num1 % num2 != 0) {
                if (x < 0) {
                    x -= 1;
                }
            }
            numStack.push(x);
        }
    }
}

贪吃蛇

题目描述

贪吃蛇是一个经典游戏，蛇的身体由若干方格连接而成，身体随蛇头移动。蛇头触碰到食物时，蛇的长度会增加一格。蛇头和身体的任一方格或者游戏版图边界碰撞时，游戏结束。

下面让我们来完成贪吃蛇游戏的模拟：

26bdc5c3c52a4e559f519d5282eab151(1).png

给定一个 NM 的数组 arr，代表 NM 个方格组成的版图，贪吃蛇每次移动一个方格。

  • 若 arr [i][j] == ‘H’，表示该方格为贪吃蛇的起始位置；
  • 若 arr [i][j] == ‘F’，表示该方格为食物；
  • 若 arr [i][j] == ‘E’，表示该方格为空格。

贪吃蛇初始长度为 1，初始移动方向为向左。

为给定一系列贪吃蛇的移动操作，返回操作后蛇的长度，如果在操作执行完之前已经游戏结束，返回游戏结束时蛇的长度。

输入描述

  1. 第一行为空格分隔的字母，代表贪吃蛇的移动操作。字母取值为 U、D、L、R 和 G：

    • U、D、L、R 分别表示贪吃蛇往上、下、左、右转向，转向时贪吃蛇不移动；

    • G 表示贪吃蛇按当前的方向移动一格。

      用例保证输入的操作正确。

  2. 第二行为空格分隔的两个数，指定 N 和 M，为数组的行和列数。

  3. 余下 N 行每行是空格分隔的 M 个字母。字母取值为 H、F 和 E：

    • H 表示贪吃蛇的起始位置（用例保证有且只有一个 H）；
    • F 表示食物；
    • E 表示该方格为空。

输出描述

输出一个数字，为蛇的长度。

用例 1

输入

1
2
3
4
5
D G G
3 3
F F F
F F H
E F E

输出

1
1

说明

地图表示为：

  • 蛇头 H (Head)
  • 食物 F (Food)
  • E 表示该方格为空

四个方向分别表示为：

  • 向上 U (up)
  • 向下 D (down)
  • 向左 L (Left)
  • 向右 R (Right)
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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String []ops = sc.nextLine().split(" ");
            int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                            Integer::parseInt).toArray();
            int n = arr[0];
            int m = arr[1];
            String [][]board = new String[n + 1][m + 1];
            for (int i = 0; i < n; i++) {
                board[i] = sc.nextLine().split(" ");
            }
            int []startPos = null;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if ("H".equals(board[i][j])) {
                        board[i][j] = "E";
                        startPos = new int[] {i, j};
                        break;
                    }
                }
                if (startPos != null) {
                    break;
                }
            }
            List<int[]>snakeBody = new ArrayList<>();
            snakeBody.add(startPos);
            String direction = "L";
            for (String op : ops) {
                switch (op) {
                    case "U":
                    case "D":
                    case "L":
                    case "R":
                        direction = op;
                        break;
                    case "G":
                        int []head = snakeBody.get(0);
                        int []nextPos = new int[2];
                        switch (direction) {
                            case "U":
                                nextPos[0] = head[0] - 1; // 行减1（向上）
                                nextPos[1] = head[1];
                                break;
                            case "D":
                                nextPos[0] = head[0] + 1; // 行加1（向下）
                                nextPos[1] = head[1];
                                break;
                            case "L":
                                nextPos[0] = head[0];
                                nextPos[1] = head[1] - 1; // 列减1（向左）
                                break;
                            case "R":
                                nextPos[0] = head[0];
                                nextPos[1] = head[1] + 1; // 列加1（向右）
                                break;
                        }
                        if (nextPos[0] < 0 || nextPos[0] >= n || nextPos[1] < 0 || nextPos[1] >= m) {
                            System.out.println(snakeBody.size());
                            System.exit(0);
                        }
                        boolean flag = false;
                        for (int i = 0; i < snakeBody.size() - 1; i++) {
                            int [] bodyPart = snakeBody.get(i);
                            if (bodyPart[0] == nextPos[0] && bodyPart[1] == nextPos[1]) {
                                flag = true;
                                break;
                            }
                        }
                        if (flag) {
                            System.out.println(snakeBody.size());
                            System.exit(0);
                        }
                        if ("E".equals(board[nextPos[0]][nextPos[1]])) {
                            List<int[]>newBody = new ArrayList<>();
                            newBody.add(nextPos);
                            newBody.addAll(snakeBody.subList(0, snakeBody.size() - 1));
                            snakeBody = newBody;
                        } else if ("F".equals(board[nextPos[0]][nextPos[1]])) {
                            List<int[]>newBody = new ArrayList<>();
                            newBody.add(nextPos);
                            newBody.addAll(snakeBody);
                            snakeBody = newBody;
                            board[nextPos[0]][nextPos[1]] = "E";
                        }
                        break;
                }
            }
            System.out.println(snakeBody.size());
        }
    }
}

解密犯罪时间

题目描述

警察在侦破一个案件时，得到了线人给出的可能犯罪时间，形如 “HH:MM” 表示的时刻。根据警察和线人的约定，为了隐蔽，该时间是修改过的，解密规则为：利用当前出现过的数字，构造下一个距离当前时间最近的时刻，则该时间为可能的犯罪时间。每个出现数字都可以被无限次使用。

输入描述

形如HH:MM的字符串，表示原始输入。

输出描述

形如HH:MM的字符串，表示推理处理的犯罪时间。

备注

  1. 可以保证线人给定的字符串一定是合法的。例如，“01:35” 和 “11:08” 是合法的，“1:35” 和 “11:8” 是不合法的。
  2. 最近的时刻可能在第二天。

示例

输入 输出
20:12 20:20
23:59 22:22
12:58 15:11
18:52 18:55
23:52 23:53
09:17 09:19
07:08 08:00 
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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            int index = s.indexOf(":");
            boolean []vis = new boolean[10];
            for (char ch : s.toCharArray()) {
                if (ch != ':') {
                    vis[ch - '0'] = true;
                }
            }
            int hour = Integer.parseInt(s.substring(0, index)),
                minute = Integer.parseInt(s.substring(index + 1)), x = Integer.MAX_VALUE;
            int cur = hour * 60 + minute;
            int ansHour = 0, ansMinute = 0;
            for (int i = 0; i < 24; i++) {
                if (!(vis[i / 10] && vis[i % 10])) {
                    continue;
                }
                for (int j = 0; j < 60; j++) {
                    if (!(vis[j / 10] && vis[j % 10])) {
                        continue;
                    }
                    int times = i * 60 + j;
                    int sub = times > cur ? times - cur : 24 * 60 - (cur - times);
                    if (sub < x && sub > 0) {
                        x = sub;
                        ansHour = i;
                        ansMinute = j;
                    }
                }
            }
            System.out.printf("%02d:%02d%n", ansHour, ansMinute);
        }
    }
}

求满足条件的最长子串的长度

题目描述

给定一个字符串，只包含字母和数字，按要求找出字符串中的最长（连续）子串的长度，字符串本身是其最长的子串，子串要求：

  1. 只包含 1 个字母 (a~z, A~Z)，其余必须是数字；
  2. 字母可以在子串中的任意位置。

如果找不到满足要求的子串（如全是字母或全是数字），则返回 - 1。

输入描述

输入为只包含字母和数字的字符串。

输出描述

输出满足条件的子串的长度。

示例

示例 1

输入

1
abC124ACb

输出

1
4

说明

满足条件的最长子串是 C124 或者 124A，长度都是 4。

示例 2

输入

1
a5

输出

1
2

说明

字符串自身就是满足条件的子串，长度为 2。

示例 3

输入

1
aBB9

输出

1
2

说明

满足条件的子串为 B9，长度为 2。

示例 4

输入

1
abcdef

输出

1
-1

说明

没有满足要求的子串，返回 - 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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            int l = 0, r = 0, charCount = 0, numCount = 0, ans = -1;
            int n = s.length();
            while (r < n) {
                if (s.charAt(r) >= '0' && s.charAt(r) <= '9') {
                    numCount++;
                } else {
                    charCount++;
                }
                if (charCount == 1 && numCount >= 1) {
                    ans = Math.max(ans, r - l + 1);
                }
                while (charCount > 1) {
                    if (s.charAt(l) >= '0' && s.charAt(l) <= '9') {
                        numCount--;
                    } else {
                        charCount--;
                    }
                    l++;
                }
                r++;
            }
            System.out.println(ans);
        }
    }
}

机器人走迷宫

题目描述

img

机器人走一个X*Y的迷宫，迷宫中有障碍物（用 0 表示），可通行方格用 #表示。机器人从(0,0)的位置走到(X,Y)的位置，且只能向 X、Y 坐标增加的方向走（向下或向前），不能回退。

迷宫中存在两类特殊方格：

  • 不可达方格：机器人在行走路径上不可能走到的方格；
  • 陷阱方格：走进之后无法抵达终点的方格。

要求输出陷阱方格和不可达方格的数量。

输入描述

  1. 第一行为房间的 X 和 Y（0<=X/Y <=1000）；
  2. 第二行为房间中的墙壁障碍物个数 N（0<= N <=X*Y）；
  3. 接下来会有 N 行墙壁的坐标，同一行中若有多个障碍物，以空格隔开，所有数据输入均合法。

输出描述

输出陷阱方格与不可达方格数量，以空格隔开。

示例

示例 1

输入

1
2
3
4
5
6
7
6 4
5
0 2
1 2
2 2
4 1
5 1

输出

1
2 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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                            Integer::parseInt).toArray();
            int n = arr[0], m = arr[1];
            int k = Integer.parseInt(sc.nextLine());
            int [][]map = new int[n + 1][m + 1];
            for (int i = 0; i < k; i++) {
                arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                          Integer::parseInt).toArray();
                map[arr[0]][arr[1]] = 1;
            }
            map[n - 1][m - 1] = 2;
            dfs(0, 0, n, m, map);
            int ans1 = 0, ans2 = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (map[i][j] == -1) {
                        ans1++;
                    } else if (map[i][j] == 0) {
                        ans2++;
                    }
                }
            }
            System.out.println(ans1 + " " + ans2);
        }
    }
    private static boolean dfs(int x, int y, int n, int m, int [][]map) {
        if (map[x][y] == -1 || map[x][y] == 1 || x >= n || y >= m) {
            return false;
        }
        if (map[x][y] == 2) {
            return true;
        }
        if (map[x][y] == 0) {
            boolean right = dfs(x + 1, y, n, m, map);
            boolean up = dfs(x, y + 1, n, m, map);
            if (right || up) {
                map[x][y] = 2;
            } else {
                map[x][y] = -1;
            }
        }
        return map[x][y] == 2;
    }
}

高效的任务规划

题目描述

你有 n 台机器编号为 1~n，每台都需要完成一项工作，机器经过配置后都能独立完成一项工作。假设第 i 台机器需要花 B 分钟进行设置，然后开始运行，J 分钟后完成任务。现在需要选择布置工作的顺序，使得用最短的时间完成所有工作。

注意：不能同时对两台机器进行配置，但配置完成的机器们可以同时执行各自的工作。

输入描述

  1. 第一行输入代表总共有 M 组任务数据（1<M<=10）。
  2. 每组数据第一行为一个整数指定机器的数量 N（0<N<=1000）。
  3. 随后的 N 行每行两个整数，第一个表示 B（0<=B<=10000），第二个表示 J（0<=J<=10000）。
  4. 每组数据连续输入，不会用空行分隔。各组任务单独计时。

输出描述

对于每组任务，输出最短完成时间，且每组的结果独占一行。

示例

示例 1

输入

1
2
3
1
1
2 2

输出

1
4

解释

第一行 1 为一组任务，第二行 1 代表只有一台机器，第三行表示该机器配置需 2 分钟，执行需 2 分钟，总耗时 2+2=4 分钟。

示例 2

输入

1
2
3
4
5
6
7
8
2
2
1 1
2 2
3
1 1
2 2
3 3

输出

1
2
4
7

解释

  • 第一行 2 代表两组任务；
  • 第二行 2 代表第一组任务有 2 个机器；
  • 第三行 1 1 代表机器 1 配置需要 1 分、运行需要 1 分；
  • 第四行 2 2 代表机器 2 配置需要 2 分、运行需要 2 分；
  • 第五行 3 代表第二组任务需要 3 个机器；
  • 第 6-8 行分别表示 3 个机器的配置与运行时间；
  • 第一组最优顺序为机器 2→机器 1：配置总耗时 2+1=3 分钟，机器 2 运行结束时间 3+2=5 分钟，机器 1 运行结束时间 3+1=4 分钟，总耗时 4 分钟；
  • 第二组最优顺序为机器 3→机器 2→机器 1：配置总耗时 3+2+1=6 分钟，机器 3 运行结束时间 6+3=9 分钟，机器 2 运行结束时间 6+2=8 分钟，机器 1 运行结束时间 6+1=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
24
25
26
27
28
29
30
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int m = Integer.parseInt(sc.nextLine());
            for (int i = 0; i < m; i++) {
                int n = Integer.parseInt(sc.nextLine());
                int []dp = new int[n + 1];
                int ans = 0;
                int sum = 0;
                int [][]a = new int[n][2];
                for (int j = 0; j < n; j++) {
                    int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                                    Integer::parseInt).toArray();
                    a[j][0] = arr[0];
                    a[j][1] = arr[1];
                }
                Arrays.sort(a, (arr1, arr2)->(arr2[1] - arr1[1]));
                for (int j = 0; j < n; j++) {
                    dp[j] = sum + a[j][0] + a[j][1];
                    sum += a[j][0];
                    ans = Math.max(ans, dp[j]);
                }
                System.out.println(ans);
            }
        }
    }
}

二叉树遍历

题目描述

根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。中序遍历顺序为：左子树 → 根结点 → 右子树。

输入描述

输入为由大小写字母、左右大括号、逗号组成的字符串：

  • 字母代表一个节点值；
  • 左右括号内包含该节点的子节点；
  • 左右子节点使用逗号分隔，逗号前为空则表示左子节点为空，没有逗号则表示右子节点为空。

备注：二叉树节点数最大不超过 100；输入字符串格式是正确的，无需考虑格式错误的情况。

输出描述

输出一个字符串，为二叉树中序遍历各节点值的拼接结果。

示例

示例 1

输入

1
a{b{d,e{g,h{,I}}},c{f}}

输出

1
dbgehIafc
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.*;

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode(char x) { val = x; }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine().trim();
        TreeNode root = parse(input);
        String result = inorder(root);
        System.out.println(result);
    }

    // 解析字符串为二叉树
    private static TreeNode parse(String s) {
        if (s.isEmpty()) return null;
        int i = 0;
        // 提取当前节点值（第一个字母）
        char val = s.charAt(i++);
        TreeNode node = new TreeNode(val);
        // 检查是否有子节点（是否有 '{'）
        if (i < s.length() && s.charAt(i) == '{') {
            int start = i;
            int count = 1; // 括号层数计数器
            i++; // 跳过 '{'
            // 找到匹配的 '}'
            while (i < s.length() && count > 0) {
                if (s.charAt(i) == '{') count++;
                else if (s.charAt(i) == '}') count--;
                i++;
            }
            // 子节点部分（去掉外层括号）
            String children = s.substring(start + 1, i - 1);
            // 分割左右子节点
            List<String> parts = splitChildren(children);
            node.left = parse(parts.get(0));
            node.right = parse(parts.get(1));
        }
        return node;
    }

    // 分割左右子节点字符串
    private static List<String> splitChildren(String s) {
        List<String> parts = new ArrayList<>();
        int count = 0; // 括号层数
        int splitIndex = -1;
        // 遍历找到第一个外层逗号
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{') count++;
            else if (c == '}') count--;
            else if (c == ',' && count == 0) {
                splitIndex = i;
                break;
            }
        }
        if (splitIndex != -1) { // 存在分割点
            parts.add(s.substring(0, splitIndex));
            parts.add(s.substring(splitIndex + 1));
        } else { // 无分割点，整个字符串是左子节点
            parts.add(s);
            parts.add("");
        }
        return parts;
    }

    // 中序遍历二叉树
    private static String inorder(TreeNode root) {
        if (root == null) return "";
        return inorder(root.left) + root.val + inorder(root.right);
    }
}

书籍叠放

题目描述

给定一组书的长宽，并且只有当一本书的长宽同时小于另一本书的长宽时，两书才能叠放在一起，求该组书中最多能有多少本书叠放在一起。

输入描述

输入为二维列表形式的书的长宽数据（如[[20,16],[15,11],[10,10],[9,10]]）。

输出描述

输出最多可叠放的书籍数量。

示例

示例 1

输入

1
[[20,16],[15,11],[10,10],[9,10]]

输出

1
3

解释

前三本可叠放在一起（20,16）→（15,11）→（10,10），第四本宽 10 不小于第三本的宽 10，无法叠放，故最多 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
import java.util.*;
import java.util.stream.Collectors;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine().replaceAll("\\[", "").replaceAll("\\]", "");
            String[] str = s.split(",");
            int[][] nums = new int[str.length / 2][2];
            for (int i = 0; i < nums.length; i++) {
                nums[i][0] = Integer.parseInt(str[i * 2]);
                nums[i][1] = Integer.parseInt(str[i * 2 + 1]);
            }
            Arrays.sort(nums, (a, b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]));
            int[] dp = new int[nums.length];
            Arrays.fill(dp, 1);
            int res = 0;
            for (int[] num : nums) {
                int left = 0, right = res;
                while (left < right) {
                    int mid = (right - left ) / 2 + left;
                    if (dp[mid] < num[1]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                dp[left] = num[1];
                if (left == res) {
                    res++;
                }
            }
            System.out.println(res);
        }
    }
}

区间交集

题目描述

给定一组闭区间，其中部分区间存在交集。任意两个给定区间的交集称为公共区间（如[1,2]和[2,3]的公共区间为[2,2]，[3,5]和[3,6]的公共区间为[3,5]）。公共区间之间若存在交集，则需要合并（如[1,3]和[3,5]区间存在交集[3,3]，需合并为[1,5]）。按升序排列输出合并后的区间列表。

输入描述

  1. 输入为一组区间列表的简化形式（去掉逗号和括号），区间数 N 满足 0<=N<=1000；
  2. 区间元素 X 满足 -10000<=X<=10000。

输出描述

  1. 按升序排列输出合并后的区间列表（简化形式，无括号和逗号）；
  2. 若无公共区间，输出None；
  3. 单个区间认定为无公共区间。

示例

示例 1

输入

1
0 3 1 3 3 5 3 6

输出

1
1 5

说明

  • [0,3]和[1,3]的公共区间为[1,3]；
  • [0,3]和[3,5]的公共区间为[3,3]；
  • [0,3]和[3,6]的公共区间为[3,3]；
  • [1,3]和[3,5]的公共区间为[3,3]；
  • [1,3]和[3,6]的公共区间为[3,3]；
  • [3,5]和[3,6]的公共区间为[3,5]；
  • 公共区间列表为[[1,3],[3,3],[3,5]]，合并后为[1,5]。

示例 2

输入

1
1 6 2 5 5 7

输出

1
2 6

说明

  • [1,6]和[2,5]的交集为[2,5]；
  • [1,6]和[5,7]的交集为[5,6]；
  • [2,5]和[5,7]的交集为[5,5]；
  • 公共区间合并后为[2,6]。

示例 3

输入

1
1 2 3 4

输出

1
None

说明

[1,2]和[3,4]无公共区间，故输出None。

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

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] str = in.nextLine().split(" ");
        int[] arr = new int[str.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
        // 先计算交集
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < arr.length; i += 2) {
            for (int j = i + 2; j < arr.length; j += 2) {
                int left = Math.max(arr[i], arr[j]);
                int right = Math.min(arr[i + 1], arr[j + 1]);
                if (left <= right) {
                    res.add(new int[] {left, right});
                }
            }
        }
        // 计算完交集，按从小到大排序，左边界升序，相同，有边界升序
        int[][] ans = res.toArray(new int[res.size()][]);
        Arrays.sort(ans, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
        // 求交集的并集
        int[][] result = new int[ans.length][2];
        int index = -1;
        for (int[] an : ans) {
            if (index == -1 || an[0] > result[index][1]) {
                result[++index] = an;
            } else {
                result[index][1] = Math.max(result[index][1], an[1]);
            }
        }
        int[][] last = Arrays.copyOf(result, index + 1);
        for (int i = 0; i < last.length; i++) {
            System.out.print(last[i][0]);
            System.out.print(" ");
            System.out.print(last[i][1]);
            if (i != last.length - 1) {
                System.out.print(" ");
            }
        }
    }
}

分月饼

题目描述

公司分月饼，有m个员工，买了n个月饼（m <= n），每个员工至少分一个月饼，也可以分到多个。设单人分到最多月饼的个数为Max1，第二多的为Max2，需满足Max1-Max2 <= 3；以此类推，任意相邻排名的月饼数差值都需<=3。问有多少种分月饼的方法？

注意：不同顺序但数值组合相同的分法算同一种（如 1+3 和 3+1 算一种）。

输入描述

每一行输入m和n，表示m个员工、n个月饼（m <= n）。

输出描述

输出满足条件的分法数量。

示例

示例 1

输入

1
2 4

输出

1
2

说明

合法分法：4=1+3、4=2+2（1+3 和 3+1 算同一种）。

示例 2

输入

1
3 5

输出

1
2

说明

合法分法：5=1+1+3、5=1+2+3。

示例 3

输入

1
3 12

输出

1
6

说明

满足要求的 6 种分法：

  1. 12 = 1 + 4 + 7
  2. 12 = 2 + 4 + 6
  3. 12 = 2 + 5 + 5
  4. 12 = 3 + 3 + 6
  5. 12 = 3 + 4 + 5
  6. 12 = 4 + 4 + 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
42
43
44
45
46
47
import java.util.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                            Integer::parseInt).toArray();
            int m = arr[0], n = arr[1];
            int []a = new int [m];
            Arrays.fill(a, 1);
            if (n == m) {
                System.out.println("1");
                System.exit(0);
            }
            System.out.println(dfs(m, n - m, a, 0));
        }
    }
    private static int dfs(int m, int remaining, int []arr, int index) {
        if (index == m) {
            if (remaining == 0) {
                return 1;
            } else {
                return 0;
            }
        }
        if (remaining == 0) {
            if (arr[index - 1] - arr[index] <= 3) {
                return 1;
            } else {
                return 0;
            }
        }
        int result = 0;
        for (int i = 0; i <= remaining; i++) {
            int x = arr[index] + i;
            if (index == 0 || (index > 0 && arr[index - 1] >= x &&
                               arr[index - 1] - x <= 3)) {
                arr[index] += i;
                result += dfs(m, remaining - i, arr, index + 1);
                arr[index] -= i;
            }
        }
        return result;
    }
}

找最小数

题目描述

给一个正整数NUM1（以字符串形式表示），移除N位数字后得到新正整数NUM2，要求NUM2的值最小。

输入描述

  1. 第一行为字符串形式的正整数NUM1，长度小于 32；
  2. 第二行为需要移除的数字个数（小于NUM1长度）。

输出描述

输出最小值NUM2的数字字符串。

示例

示例 1

输入

1
2
2615371
4

输出

1
131

说明

移除 2、6、5、7 这四个数字，剩下 1、3、1 按原有顺序排列组成 131，为最小值。

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            int n = Integer.parseInt(sc.nextLine());
            Stack<Character>stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                while (!stack.isEmpty() && stack.peek() > ch && n > 0) {
                    stack.pop();
                    n--;
                }
                stack.push(ch);
            }
            while (n > 0) {
                stack.pop();
                n--;
            }
            StringBuilder ans = new StringBuilder();
            for (char ch : stack) {
                if (!(ans.length() == 0 && ch == '0')) {
                    ans.append(ch);
                }
            }
            System.out.println(ans.length() == 0 ? "0" : ans.toString());
        }
    }
}

简易内存池

题目描述

实现一个简易内存池，支持REQUEST（分配内存）和RELEASE（释放内存）两种操作，规则如下：

  1. 内存池总大小为 100 字节；
  2. 内存分配必须是连续内存，优先从低地址分配；
  3. 释放的内存可被再次分配，已释放的空闲内存不能二次释放；
  4. 不会释放已申请内存块的中间地址，释放仅针对首地址对应的单个内存块。

输入描述

  1. 首行为整数N（0 < N <= 100），表示操作命令的个数；
  2. 接下来N行，每行是操作命令，格式为REQUEST=大小或RELEASE=首地址。

输出描述

  • REQUEST：分配成功返回首地址，内存不足 / 大小为 0 输出error；
  • RELEASE：释放成功无输出，释放不存在的首地址输出error。

示例

样例 1

输入

1
2
3
2
REQUEST=10
REQUEST=20

输出

1
2
0
10

样例 2

输入

1
2
3
4
5
6
5
REQUEST=10
REQUEST=20
RELEASE=0
REQUEST=20
REQUEST=10

输出

1
2
3
4
0
10
30
0

提示说明

  • 第一条指令：申请 0~9 字节，返回首地址 0；
  • 第二条指令：申请 10~29 字节，返回首地址 10；
  • 第三条指令：释放 0~9 字节，无输出；
  • 第四条指令：0~9 字节不足 20 字节，申请 30~49 字节，返回 30；
  • 第五条指令：申请 0~9 字节，返回 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
import java.util.*;
import java.util.Scanner;

public class Main {
    static final int  MAX_VALUE = 100;
    static Map<Integer, Integer>map = new TreeMap<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            String [][]strings = new String[n][2];
            for (int i = 0; i < n; i++) {
                strings[i] = sc.nextLine().split("=");
            }
            for (int i = 0; i < n; i++) {
                int value = Integer.parseInt(strings[i][1]);
                String op = strings[i][0];
                if (op.equals("REQUEST")) {
                    request(value);
                } else if (op.equals("RELEASE")) {
                    release(value);
                } else {
                    System.out.println("error");
                }
            }
        }
    }
    private static void request(int value) {
        if (value > MAX_VALUE || value <= 0) {
            System.out.println("error");
            return ;
        }
        int pre = 0;
        if (map.isEmpty()) {
            map.put(0, value);
            System.out.println("0");
        } else {
            for (Integer requestHead : map.keySet()) {
                if (requestHead - pre >= value) {
                    map.put(pre, pre + value);
                    System.out.println(pre);
                    return ;
                } else {
                    pre = map.get(requestHead);
                }
            }
            if (MAX_VALUE - pre >= value) {
                map.put(pre, pre + value);
                System.out.println(pre);
            } else {
                System.out.println("error");
            }
        }
    }
    private static void release(int value) {
        if (map.containsKey(value)) {
            map.remove(value);
        } else {
            System.out.println("error");
        }
    }

}

服务失效判断

题目描述

某系统中有多个唯一标识的服务（字符串，长度 <=10），服务间存在依赖关系（如 A 依赖 B，则 B 故障会导致 A 故障），依赖具有传递性（A 依赖 B、B 依赖 C，C 故障则 A、B 均故障）。给定依赖关系和故障服务列表，输出所有正常服务。

输入描述

  1. 第一行：半角逗号分隔的依赖关系列表（格式：服务 1 - 服务 2，表示服务 1 依赖服务 2）；
  2. 第二行：半角逗号分隔的故障服务列表。

输出描述

  1. 输出依赖关系中提及的所有正常服务，按依赖关系列表中出现的次序排序，半角逗号分隔；
  2. 无正常服务时输出单个半角逗号。

示例

示例 1

输入

1
2
a1-a2,a5-a6,a2-a3
a5,a2

输出

1
a6,a3

说明

  • a1 依赖 a2，a2 故障→a1 故障；a2 依赖 a3，a2 故障不影响 a3；
  • a5 故障不影响 a6；
  • 正常服务为 a6、a3，按依赖列表出现次序输出。

示例 2

输入

1
2
a1-a2
a2

输出

1
,

说明

a1 依赖 a2，a2 故障→a1 故障，无正常服务，输出单个逗号。

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.*;
public class Main {
    static Map<String, List<String>>map = new HashMap<>();
    static Set<String>set = new LinkedHashSet<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String []strings = sc.nextLine().split(",");
            for (String str : strings) {
                String[]s = str.split("-");
                set.add(s[0]);
                set.add(s[1]);
                map.computeIfAbsent(s[1], k->new ArrayList<String>()).add(s[0]);
            }
            Set<String> badSet = new HashSet<>();
            Queue<String>queue = new ArrayDeque<>();
            strings = sc.nextLine().split(",");
            for (String str : strings) {
                queue.offer(str);
                badSet.add(str);
            }
            while (!queue.isEmpty()) {
                String cur = queue.poll();
                List<String>list = map.getOrDefault(cur, new ArrayList<>());
                for (String str : list) {
                    if (!badSet.contains(str)) {
                        badSet.add(str);
                        queue.offer(str);
                    }
                }
            }
            List<String>ans = new ArrayList<>();
            for (String str : set) {
                if (!badSet.contains(str)) {
                    ans.add(str);
                }
            }
            if (ans.isEmpty()) {
                System.out.println(",");
            } else {
                System.out.println(String.join(",", ans));
            }

        }
    }
}

图像物体的边界

题目描述

给定M行N列的二维数组（仅包含像素 1 和 5），像素 1 代表的物体的边界定义为：与像素 5 相邻（8 个方向：上、下、左、右、左上、左下、右上、右下）的像素 1 格子；相邻的边界格子属于同一个边界。求像素 1 代表的物体的边界个数。

输入描述

  1. 第一行：行数M、列数N（0<M<100，0<N<100）；
  2. 第二行开始：M行N列的像素数组（仅包含 1 和 5）。

输出描述

输出像素 1 代表的物体的边界个数，无边界输出 0。

示例

示例 1

输入

img

1
2
3
4
5
6
7
6 6
1 1 1 1 1 1
1 5 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 5

输出

1
2

说明

  • 左上角与 5 相邻的 1 组成 1 个边界；
  • 右下角与 5 相邻的 1 组成 1 个边界；
  • 总边界数为 2。

示例 2

输入

img

1
2
3
4
5
6
7
6 6
1 1 1 1 1 1
1 5 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 5 1
1 1 1 1 1 1

输出

1
1

说明

所有与 5 相邻的 1 格子相互相邻，仅构成 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.*;
public class Main {
    static int m, n;
    static int [][]grid;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String [] strings = sc.nextLine().split(" ");
            m = Integer.parseInt(strings[0]);
            n = Integer.parseInt(strings[1]);
            grid = new int[m][n];
            for (int i = 0; i < m; i++) {
                grid[i] = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                              Integer::parseInt).toArray();
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 5) {
                        for (int dx = -1; dx < 2; dx++) {
                            for (int dy = -1; dy < 2; dy++) {
                                int x = dx + i;
                                int y = dy + j;
                                if (check(x, y) && grid[x][y] == 1) {
                                    grid[x][y] = 2;
                                }
                            }
                        }
                    }
                }
            }
            int ans = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 2) {
                        dfs(i, j);
                        ans++;
                    }
                }
            }
            System.out.println(ans);
        }
    }
    private static boolean check(int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return false;
        }
        return true;
    }
    private static void dfs(int x, int y) {
        if (!check(x, y) || grid[x][y] != 2) {
            return ;
        }
        grid[x][y] = 1;
        for (int dx = -1; dx < 2; dx++) {
            for (int dy = -1; dy < 2; dy++) {
                int xx = dx + x;
                int yy = dy + y;
                dfs(xx, yy);
            }
        }
    }
}

跳格子游戏

题目描述

小明和朋友们玩跳格子游戏，每个格子有特定分数score（如[1, -1, -6, 7, -17, 7]）。从起点score[0]开始，每次最大步长为k，返回跳到终点score[n-1]时能得到的最大得分。

输入描述

  1. 第一行输入格子总数n；
  2. 第二行输入每个格子的分数score[i]；
  3. 第三行输入最大跳步长k。

输出描述

输出能得到的最大得分。

备注

  • 格子总数n和步长k的范围：[1, 100000]；
  • 每个格子分数score[i]范围：[-10000, 10000]。

示例

输入

1
2
3
6
1 -1 -6 7 -17 7
2

输出

1
14

说明

小明从score[0]开始，依次跳到score[1]、score[3]、score[5]，总得分1 + (-1) + 7 + 7 = 14，为最大得分。

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
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                            Integer::parseInt).toArray();
            int k = Integer.parseInt(sc.nextLine());
            if (arr.length == 1) {
                System.out.println(arr[0]);
                continue;
            }
            int []dp = new int [n];
            PriorityQueue<Integer> queue = new PriorityQueue<>((a, b)->(b - a));
            for (int i = 0; i < n; i++) {
                if (i == 0) {
                    dp[i] = arr[0];
                } else {
                    dp[i] = queue.peek() + arr[i];
                }
                queue.add(dp[i]);
                if (i - k >= 0) {
                    queue.remove(dp[i - k]);
                }
            }
            System.out.println(dp[n - 1]);
        }
    }
}

数组二叉树

题目描述

二叉树用数组存储：根节点值存于下标 1，下标N的节点，其左子节点存于2N、右子节点存于2N+1；值-1表示节点为空。给定存储二叉树的数组，求从根节点到最小叶子节点的路径（路径由节点值组成）。

输入描述

输入一行为数组内容，元素为正整数（-1表示空节点），元素间用空格分隔；数组第N个元素对应下标N（下标 0 省略）；树最多 7 层。

输出描述

输出从根节点到最小叶子节点的路径上的节点值，空格分隔（保证最小叶子节点唯一）。

示例

示例 1

输入

1
3 5 7 -1 -1 2 4

输出

1
3 7 2

说明

最小叶子节点为 2，路径是 3→7→2。

示例 2

输入

1
5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6

输出

1
5 8 7 6

说明

最小叶子节点为 6，路径是 5→8→7→6；数组仅存储至最后一个非空节点，不含 “7” 右子节点的 - 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
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            //获取存放二叉树信息的数组
            int[] array = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                              Integer::parseInt).toArray();
            int n = array.length;
            //初始化最小叶子结点的值
            int min = Integer.MAX_VALUE;
            //初始化最小叶子结点的下标
            int min_index = -1;
            for (int i = 0; i < n; i++) {
                if (array[i] != -1) {
                    //跳过非叶子结点
                    if ((i + 1) * 2 - 1 < n && array[(i + 1) * 2 - 1] != -1) continue;
                    if ((i + 1) * 2 < n && array[(i + 1) * 2] != -1) continue;
                    //通过比较获取最小叶子结点
                    if (min > array[i]) {
                        min_index = i;
                        min = array[i];
                    }
                }
            }
            //存放最小叶子结点到根路径的所有节点
            List<Integer> list = new ArrayList<>();
            list.add(min);
            //通过当前节点下标计算上一个父节点的下标
            int temp = min_index;
            while (temp > 0) {
                temp = (temp - 1) / 2;
                list.add(array[temp]);
            }
            //倒序输出根节点到最小叶子结点的路径
            for (int i = list.size() - 1; i >= 0 ; i--) {
                System.out.print(list.get(i) + " ");
            }
        }
    }
}

考古学家

题目描述

考古石碑被打碎成n块，每块有一个 / 若干字符。请输出石碑文字所有可能的组合，并按升序排列。

输入描述

  1. 第一行输入n（石碑碎片个数）；
  2. 第二行依次输入n个碎片的文字内容s。

输出描述

输出所有组合（升序排列），行末无多余空格。

示例

示例 1

输入

1
2
3
a b c

输出

1
2
3
4
5
6
abc
acb
bac
bca
cab
cba

示例 2

输入

1
2
3
a b a

输出

1
2
3
aab
aba
baa
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
import java.util.*;
public class Main {
    static boolean []used;
    static Set<String>ans = new TreeSet<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int n = Integer.parseInt(sc.nextLine());
            String []strings = sc.nextLine().split(" ");
            used = new boolean[n + 1];
            dfs(n, new StringBuilder(), strings);
            for (String str : ans) {
                System.out.println(str);
            }
        }
    }
    private static void dfs(int n, StringBuilder sb, String[]strings) {
        if (sb.length() == n) {
            ans.add(sb.toString());
            return ;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = true;
                sb.append(strings[i]);
                dfs(n, sb, strings);
                sb.deleteCharAt(sb.length() - 1);
                used[i] = false;
            }
        }
    }
}

解压报文

题目描述

为提升传输效率，报文会按规则压缩：n[str]表示方括号内的str重复n次（0 < n <= 100，str仅含小写字母）。给定压缩后的报文，返回解压后的原始报文。

输入描述

输入压缩后的报文：

  1. 无额外空格，方括号格式合法；
  2. 原始报文无数字，数字仅表示重复次数（无5b/3[8]类输入）。

输出描述

输出解压后的原始报文（长度≤1000）。

示例

示例 1

输入

1
3[k]2[mn]

输出

1
kkkmnmn

说明

k重复 3 次，mn重复 2 次，拼接得kkkmnmn。

示例 2

输入

1
3[m2[c]]

输出

1
mccmccmcc

说明

m2[c]解压为mcc，重复 3 次得mccmccmcc。

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
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            Stack<Character> strStack = new Stack<>();
            StringBuilder numSb = new StringBuilder();
            for (char ch : s.toCharArray()) {
                if (ch == ']') {
                    StringBuilder temp = new StringBuilder();
                    while (!strStack.isEmpty() && strStack.peek() != '[') {
                        temp.append(strStack.pop());
                    }
                    strStack.pop();
                    while (!strStack.isEmpty() && Character.isDigit(strStack.peek())) {
                        numSb.append(strStack.pop());
                    }
                    int num = Integer.parseInt(numSb.reverse().toString());
                    numSb.setLength(0);
                    String str = temp.reverse().toString();
                    for (int i = 0; i < num; i++) {
                        for (char ch1 : str.toCharArray()) {
                            strStack.push(ch1);
                        }
                    }
                } else {
                    strStack.push(ch);
                }
            }
            StringBuilder ans = new StringBuilder();
            while (!strStack.isEmpty()) {
                ans.append(strStack.pop());
            }
            System.out.println(ans.reverse().toString());
        }
    }
}

最长的指定瑕疵度的元音子串

题目描述

定义

  1. 元音字符串：开头和结尾均为元音字母（aeiouAEIOU）的字符串；
  2. 瑕疵度：元音字符串中混杂的非元音字母数量（如abira瑕疵度为 2）；
  3. 子串：字符串中任意连续字符组成的子序列。

给定字符串，找出指定瑕疵度的最长元音子串，输出其长度；无满足条件的子串则输出 0。

输入描述

  1. 首行输入整数flaw（预期瑕疵度，[0, 65535]）；
  2. 第二行输入仅含a-z/A-Z的字符串（长度(0, 65535]）。

输出描述

输出满足条件的元音子串长度。

示例

示例 1

输入

1
2
0
asdbuiodevauufgh

输出

1
3

示例 2

输入

1
2
2
aeueo

输出

1
0

示例 3

输入

1
2
1
aabeebuu

输出

1
5

说明

满足条件的最长元音子串为aabee和eebuu，长度均为 5。

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 sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int flaw = Integer.parseInt(sc.nextLine());
            String s = sc.nextLine();
            Set<Character> set = new HashSet<>();
            for (char ch : "aeiouAEIOU".toCharArray()) {
                set.add(ch);
            }
            int n = s.length();
            int cnt = 0;
            List<Integer> pos = new ArrayList<>();
            int []num = new int[n + 1];
            for (int i = 0; i < n; i++) {
                char ch = s.charAt(i);
                if (set.contains(ch)) {
                    pos.add(i);
                } else {
                    cnt++;
                }
                num[i + 1] = cnt;
            }
            int l = 0, ans = 0;
            for (int r = 0; r < pos.size(); r++) {
                int right = pos.get(r);
                while (l <= r) {
                    int left = pos.get(l);
                    int curFlaw = num[right + 1] - num[left + 1];
                    if (curFlaw > flaw) {
                        l++;
                        continue;
                    }
                    if (curFlaw == flaw) {
                        ans = Math.max(ans, right - left + 1);
                    }
                    break;
                }
            }
            System.out.println(ans);
        }
    }
}

目录删除

题目描述

某文件系统的目录结构为树状：根目录 ID 为 0，每个目录有唯一 ID，且仅有一个父目录（根目录无父目录）。给定[子目录ID，父目录ID]的父子关系表，以及待删除的目录 ID，删除该目录及其所有子目录后，返回剩余目录 ID 的递增序列。

输入描述

  1. 第一行：父子关系表的长度m；
  2. 接下来m行：每行一个父子关系对（子目录 ID 父目录 ID）；
  3. 最后一行：待删除的目录 ID。

输出描述

输出剩余目录 ID 的递增序列，空格分隔。

示例

示例 1

输入

1
2
3
4
5
6
7
5
8 6
10 8
6 0
20 8
2 6
8

输出

1
2 6

说明

删除 8 及其子目录（10、20），剩余目录为 2、6。

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
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int m = Integer.parseInt(sc.nextLine());
            Set<Integer>set = new TreeSet<>();
            Map<Integer, List<Integer>>map = new HashMap<>();
            for (int i = 0; i < m; i++) {
                int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                                Integer::parseInt).toArray();
                set.add(arr[1]);
                set.add(arr[0]);
                map.computeIfAbsent(arr[1], k->new ArrayList<Integer>()).add(arr[0]);
            }
            Set<Integer>badNum = new HashSet<>();
            Queue<Integer>queue = new ArrayDeque<>();
            int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                            Integer::parseInt).toArray();
            for (int i = 0; i < arr.length; i++) {
                queue.offer(arr[i]);
                badNum.add(arr[i]);
            }
            while (!queue.isEmpty()) {
                int x = queue.poll();
                List<Integer>list = map.getOrDefault(x, Collections.emptyList());
                for (Integer num : list) {
                    if (!badNum.contains(num)) {
                        queue.offer(num);
                        badNum.add(num);
                    }
                }
            }
            Set<Integer>ans = new TreeSet<>();
            for (Integer x : set) {
                if (!badNum.contains(x)) {
                    ans.add(x);
                }
            }
            for (Integer x : ans) {
                if (x != 0) {
                    System.out.print(x + " ");
                }
            }
            System.out.println();
        }
    }
}

火锅

题目描述

火锅中不同时间下菜，每道菜x秒下锅，需煮y秒才刚好合适。你的手速为m（捞菜后至少隔m秒才能再捞，每次捞 1 个），求最多能吃到的刚好合适的菜的数量。

输入描述

  1. 第一行：整数n（菜的个数）、m（手速，1 < n, m < 1000）；
  2. 接下来n行：每行两个数x、y（1 < x, y < 1000），表示x秒下的菜需煮y秒。

输出描述

输出最多能吃到的刚好合适的菜的数量。

示例

示例 1

输入

1
2
3
2 1
1 2
2 1

输出

1
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
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int []arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                            Integer::parseInt).toArray();
            int n = arr[0], m = arr[1];
            int []a = new int[n];
            for (int i = 0; i < n; i++) {
                arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(
                          Integer::parseInt).toArray();
                int x = arr[0], y = arr[1];
                a[i] = x + y;
            }
            Arrays.sort(a);
            int cnt = 1;
            int pre = 0;
            for (int i = 1; i < a.length; i++) {
                if (a[i] >= a[pre] + m) {
                    cnt++;
                    pre = i;
                }
            }
            System.out.println(cnt);
        }
    }
}

服务器广播

题目描述

给定N×N的服务器连接矩阵（matrix[i][j]=1表示服务器i和j直接连接，连接对称且自连），广播可通过直接 / 间接连接传播。求最少需要向几台服务器发送广播，才能让所有服务器接收。

输入描述

输入N行，每行N个 0/1（空格分隔），1<=N<=50。

输出描述

输出最少广播的服务器数量。

示例

示例 1

输入

1
2
3
4
3
1 1 0
1 1 1
0 1 1

输出

1
1

说明

服务器 0、1、2 互通，只需广播 1 台。

示例 2

输入

1
2
3
4
3
1 0 0
0 1 0
0 0 1

输出

1
3

说明

3 台服务器互不连接，需分别广播。

示例 3

输入

1
2
3
2
1 1
1 1

输出

1
1

说明

2 台服务器互通，只需广播 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
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<String>list = new ArrayList<>();
        while (sc.hasNextLine()) {
            String str = sc.nextLine();
            if (str.isEmpty()) {
                break;
            }
            list.add(str);
        }
        sc.close();
        int n = list.size();
        int [][]matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            matrix[i] = Arrays.stream(list.get(i).split(" ")).mapToInt(
                            Integer::parseInt).toArray();
        }
        Map<Integer, Integer>map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1 && i != j) {
                    int tagI = map.get(i);
                    int tagJ = map.get(j);
                    if (tagI != tagJ) {
                        int max = Math.max(tagI, tagJ);
                        int min = Math.min(tagI, tagJ);
                        for (int k = 0; k < n; k++) {
                            if (map.get(k) == max) {
                                map.put(k, min);
                            }
                        }
                    }
                }
            }
        }
        Set<Integer>ans = new HashSet<>(map.values());
        System.out.println(ans.size());
    }
}

二叉树的广度优先遍历

题目描述

给定二叉树的后序遍历（左→右→父）和中序遍历（左→父→右）结果（节点为大写字母，最多 26 个），输出层次遍历（广度优先）结果。

输入描述

输入一行，为后序遍历和中序遍历结果（空格分隔）。

输出描述

输出层次遍历结果（无空格）。

示例

示例 1

输入

1
CBEFDA CBAEDF

输出

1
ABDCEF
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
import java.util.*;
public class Main {
    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode (char val) {
            this.val = val;
        }

    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String []strings = sc.nextLine().split(" ");
            String postOrder = strings[0];
            String inOrder = strings[1];
            TreeNode root = build(postOrder, inOrder);
            bfs(root);
        }
    }
    private static TreeNode build(String postOrder, String inOrder) {
        if (postOrder.isEmpty() || inOrder.isEmpty()) {
            return null;
        }
        char rootVal = postOrder.charAt(postOrder.length() - 1);
        TreeNode root = new TreeNode(rootVal);
        int index = inOrder.indexOf(rootVal);
        String leftInOrder = inOrder.substring(0, index);
        String rightInOrder = inOrder.substring(index + 1);
        int lSize = leftInOrder.length();
        String leftPostOrder = postOrder.substring(0, lSize);
        String rightPostOrder = postOrder.substring(lSize, postOrder.length() - 1);
        root.left = build(leftPostOrder, leftInOrder);
        root.right = build(rightPostOrder, rightInOrder);
        return root;
    }
    //注意：层次遍历!=前序遍历
    private static void bfs(TreeNode root) {
        if (root == null) {
            return ;
        }
        Queue<TreeNode>queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            System.out.print(curNode.val);
            if (curNode.left != null) {
                queue.offer(curNode.left);
            }
            if (curNode.right != null) {
                queue.offer(curNode.right);
            }
        }
    }
}

找单词

题目描述

给定N×N的大写字符数组和一个目标字符串，若字符串按顺序出现在数组中（相邻单元格，单元格不重复使用），输出每个字符的下标序列；否则输出N。

输入描述

  1. 第 1 行：数字N（二维数组行数，0<N<=100）；
  2. 第 2~N+1 行：二维字符数组（每行字符用,分隔）；
  3. 第 N+2 行：待查找字符串（大写，长度 0<K<1000）。

输出描述

输出下标字符串（格式：行，列，行，列…），无匹配则输出N。

示例

示例 1

输入

1
2
3
4
5
6
4
A,C,C,F
C,D,E,D
B,E,S,S
F,E,C,A
ACCESS

输出

1
0,0,0,1,0,2,1,2,2,2,2,3

说明

ACCESS 对应下标依次为 [0,0]、[0,1]、[0,2]、[1,2]、[2,2]、[2,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
import java.util.*;
public class Main {
    static int n;
    static char [][]grid;
    static boolean [][]used;
    static int []dx = {-1, 0, 0, 1};
    static int []dy = {0, -1, 1, 0};
    static String word;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            n = Integer.parseInt(sc.nextLine());
            grid = new char[n][n];
            used = new boolean[n][n];
            for (int i = 0; i < n; i++) {
                String []strings = sc.nextLine().split(",");
                for (int j = 0; j < n; j++) {
                    grid[i][j] = strings[j].charAt(0);
                }
            }
            word = sc.nextLine();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == word.charAt(0)) {
                        List<int[]>path = new ArrayList<>();
                        path.add(new int[] {i, j});
                        if (dfs(0, i, j, path )) {
                            return;
                        }
                    }
                }
            }
            System.out.println("N");
        }
    }
    private static boolean dfs(int cnt, int x, int y, List<int[]>path) {
        if (x < 0 || x >= n || y < 0 || y >= n || used[x][y] ||
                grid[x][y] != word.charAt(cnt)) {
            return false;
        }
        if (cnt == word.length() - 1) {
            for (int i = 0; i < path.size(); i++) {
                System.out.print(path.get(i)[0] + "," + path.get(i)[1]);
                if (i < path.size() - 1) {
                    System.out.print(",");
                }
            }
            return true;
        }
        used[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            path.add(new int[] {xx, yy});
            if (dfs(cnt + 1, xx, yy, path)) {
                return true;
            }
            path.remove(path.size() - 1);
        }
        used[x][y] = false;
        return false;
    }
}

招聘

题目描述

给定n场面试的起止时间（Si < Ei），每名面试官每次只能面试 1 人，完成后可立即开始下一场，且每人最多面试m人次。求至少需要的面试官数量。

输入描述

  1. 第一行：面试官最多面试人次m（1<=m<=500）；
  2. 第二行：面试场次n（1<=n<=500）；
  3. 接下来n行：每场面试的起始、结束时间（空格分隔）。

输出描述

输出至少需要的面试官数量。

示例

示例 1

输入

1
2
3
4
5
6
7
2
5
1 2
2 3
3 4
4 5
5 6

输出

1
3

说明

5 场无重叠面试，每人最多 2 场，需 3 人。

示例 2

输入

1
2
3
4
5
3
3
1 2
2 3
3 4

输出

1
1

说明

3 场无重叠，每人最多 3 场，需 1 人。

示例 3

输入

1
2
3
4
5
3
3
8 35
5 10
1 3

输出

1
2

说明

[5,10] 和 [8,35] 重叠，需 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
39
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            int m = Integer.parseInt(sc.nextLine());
            int n = Integer.parseInt(sc.nextLine());
            int [][]arr = new int[n][2];
            for (int i = 0; i < n; i++) {
                String []strings = sc.nextLine().split(" ");
                arr[i][0] = Integer.parseInt(strings[0]);
                arr[i][1] = Integer.parseInt(strings[1]);
            }
            Arrays.sort(arr, (a, b)->a[1] - b[1]);
            List<List<Integer>> lists = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                lists.add(new ArrayList<>());
            }
            for (int []range : arr) {
                int start = range[0];
                int end = range[1];
                for (List<Integer>list : lists) {
                    if (list.size() < m && (list.isEmpty() || list.get(list.size() - 1) <= start)) {
                        list.add(end);
                        break;
                    }
                }
            }
            int cnt = 0;
            for (List<Integer> list : lists) {
                // System.out.println( list.toString());
                if (!list.isEmpty()) {
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}

斗地主之顺子

题目描述

斗地主中顺子规则：由至少 5 张连续递增的牌组成（顺序：3,4,5,6,7,8,9,10,J,Q,K,A,2），且不含 2。给定 13 张牌，输出所有合法顺子（按首张牌升序，无则输出 No）。

输入描述

输入 13 张牌（空格分隔，无大小王）。

输出描述

每行输出一个顺子（空格分隔）；无则输出 No。

示例

示例 1

输入

1
2 9 J 2 3 4 K A 7 9 A 5 6

输出

1
3 4 5 6 7

示例 2

输入

1
2 9 J 10 3 4 K A 7 Q A 5 6

输出

1
2
3 4 5 6 7
9 10 J Q K A

示例 3

输入

1
2 9 9 9 3 4 K A 10 Q A 5 6

输出

1
No
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 {
    //拿下
    static String[] order = {"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A"};
    static Map<String, Integer>map = new HashMap<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            for (int i = 0; i < order.length; i++) {
                map.put(order[i], i);
            }
            String []strings = sc.nextLine().split(" ");
            Set<String>uniqueCard = new HashSet<>();
            for (String card : strings) {
                if (!card.equals("2")) {
                    uniqueCard.add(card);
                }
            }
            List<String>list = new ArrayList<>(uniqueCard);
            list.sort(Comparator.comparingInt(map::get));
            List<List<String>>result = new ArrayList<>();
            int n = list.size();
            int i = 0;
            while (i < n) {
                int start = i;
                while (i + 1 < n && map.get(list.get(i + 1)) == map.get(list.get(i)) + 1) {
                    i++;
                }
                List<String>curList = list.subList(start, i + 1);
                if (curList.size() >= 5) {
                    result.add(new ArrayList<>(curList));
                }
                i++;
            }
            if (result.isEmpty()) {
                System.out.println("No");
            } else {
                for (List<String>strList : result) {
                    System.out.println(String.join(" ", strList));
                }
            }
        }
    }
}