校招后端面试算法题 —— Java 实现
Aidan Engineer
 2021-09-11 21:09:25      9.3k 字  43 分钟

自己参加秋招时做过的算法题（包括面试、笔试），这里贴出来做一个记录，代码够清晰了，所以也就没写注释，以后也尽量改掉一行注释一行代码的习惯，毕竟能够靠代码自己表达的东西就没必要啰嗦了

度小满金融

秋招开始第一次做笔试题，因为不能在自己的 IDE 上写，可给我难受坏了，第一次做的时候发挥的一塌糊涂，后来应该是邮件重复了又给我发了一次笔试邀请，想着闲着也是闲着就又参加了一次，第二次感觉还不错，第一次笔试之后有事耽误了总结，这里只贴第二次笔试的代码

变形的约瑟夫环

题目：
1, ···, n 这 n 个人按编号排成一个圆圈，从数字 1 开始报数，报出的数字为 a 的人出局，下一个人继续从 1 开始报数，报出 b 的人出局，也就是奇数次出局的为报 a 的人，偶数次出局的人报的是 b
输入格式为 n a b 求出这个圆圈里剩下的最后一个人的编号

样例输入：

6 3 5

样例输出：

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
/**
 * Created by Aidan on 2021/9/26 16:29
 * GitHub: github.com/huaxin0304
 * Blog: aidanblog.top
 */

public class JosephRing {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        scanner.close();
        // 使用集合维护元素，方便淘汰的处理 
        List<Integer> person = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            person.add(i);
        }

        int k = 0, now = a;
        while (person.size() != 1) {
            k += now;
            // 根据淘汰值找出被淘汰的具体人 
            k = k % person.size() - 1;
            if (k < 0) {
                person.remove(person.size() - 1);
                k = 0;
            } else {
                person.remove(k);
            }
            // 每次更换淘汰值 
            now = now == a ? b : a;
        }

        System.out.println(person.get(0));
    }
}

奥运会

题目：
两个电视频道同时转播奥运会的竞赛项目，两个频道播出的项目中没有重复的，如果看一个项目就全部看完的话，根据节目单判断最多能完整看多少个项目（忽略换台的时间）
第一行输入 m, n 作为两个频道转播的项目数量，然后以 HH:mm 的格式输入 m+n 行时间，返回能观看项目的最大值

样例输入：

3 4
07:00-08:00
08:00-09:00
08:00-11:00
09:30-11:00
13:00-15:00
12:00-13:30
13:00-15:30

样例输出：

4

思路：
这道题算法不多，考察的更像是字符串、时间类和集合的应用（我没想到更好的解决方式），首先将 String 转换成 LocalTime 然后使用 TreeMap 存储时间的结束和开始，因为判断的是最多，所以用结束时间为 key 来排序，判断下一场的开始时间是不是晚于当前的结束时间，符合条件的累加

代码：

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
/**
 * Created by Aidan on 2021/9/26 16:31
 * GitHub: github.com/huaxin0304
 * Blog: aidanblog.top
 */

public class TimeLag {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int total = m + n;
        scanner.nextLine();
        Map<LocalTime, LocalTime> map = new TreeMap<>();
        // 定义字符串转时间的格式（直接用字符串也行）
        DateTimeFormatter dtf = DateTimeFormatter.ofPattern("HH:mm");
        // 依次转换格式放入 map 中 
        while (total > 0) {
            String time = scanner.nextLine();
            LocalTime start = LocalTime.parse(time.substring(0, 5), dtf);
            LocalTime end = LocalTime.parse(time.substring(6), dtf);
            if (map.get(end) == null) {
                map.put(end, start);
            } else if (start.isAfter(map.get(end))) {// 结束时间相同只保留开始时间晚的 
                map.put(end, start);
            }
            total--;
        }
        scanner.close();
        int count = 0;
        LocalTime perEnd = LocalTime.parse("00:00", dtf);
        for (Map.Entry<LocalTime, LocalTime> entry : map.entrySet()) {
            if (count == 0) {// 第一场永远是最优解 
                perEnd = entry.getKey();
                count++;
                continue;
            }
            // 开始时间不早于上一场的结束时间即有效 
            if (!entry.getValue().isBefore(perEnd)) {
                count++;
            }
            perEnd = entry.getKey();
        }

        System.out.println(count);
    }
}

涂鸦移动

路径深度

题目：
首先看这么一段文件路径 

1
2
3
4
5
6
7
Preface 1
  Java SE5 and SE6
      Java SE6
  The 4th edition
      Changes
  Note on the cover design
  Acknowledgements

如果用代码表示，上面的文件系统可以写为： Preface 1\n\tJava SE5 and SE6\n\t\tJava SE6\n\tThe 4th edition\n\t\tChanges\n\tNote on the cover design\n\tAcknowledgements" ，其中 ‘\n’ 和 ‘\t’ 分别是换行符和制表符。那么指向目录中任何一个条目，都会有一条路径，路径都有深度

上面的例子中：
Note on the cover design 的路径是 Preface 1/Note on the cover design ，深度是 2，路径都由字母、数字或空格组成，给定一个以上述代码格式表示目录的字符串 input，返回深度最深的条目中，最长路径的长度

类似题 LeetCode 地址

样例输入：

Title\n\tSubtitle1\n\tSubtitle2\n\t\taaaa

样例输出：

20
解释：aaaa 路径为 “Title/Subtitle2/aaaa”，深度是 3，路径长度 20

思路：
首先将输入的路径根据 \n 进行切割，遍历每一段根据 \t 的个数判断处于第几层，将每层的目录长度放到数组中，根据最后求出的最大深度计算最大长度

代码：

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
/**
 * Created by Aidan on 2021/9/3 16:22
 * GitHub: github.com/huaxin0304
 * Blog: aidanblog.top
 */

public class FilePathLength {
    public static void main(String[] args) {
        String input = "Title\n\tSubtitle1\n\t\taaa\n\t\tSubsubtitle1\n\t\t\tbbbb\n\tSubtitle2\n\t\tSubsubtitle2\n\t\t\tcccccc";
        System.out.println(LongestPath(input));

    }

    public static int LongestPath(String input) {
        if (input.length() == 0) {
            return 0;
        }
        int[] sum = new int[input.length() + 1];    // 从 1 开始，第 0 层就是 0
        int Deepest = 0;
        int deepestLen = 0;

        for (String s : input.split("\n")) {
            int level = s.lastIndexOf('\t') + 2;    // 计算当前在第几层（从第一层开始，没有、t 为第一层）
            Deepest = Math.max(Deepest, level);
            deepestLen = s.length() - (Deepest - 1);    // 即便层数深度相同，最深长度也会更新 
            int len = s.length() - (level - 1);     // 计算当前这一行的长度 
            sum[level] = sum[level - 1] + len + 1;  // 是目录，要 +1，目录有个 / 的 
        }
        return sum[Deepest - 1] + deepestLen;
    }
}

Temmie 的 X 运算

题目：
有一种特殊的运算 X，它的运算方式如下：对于一个整数 n，对它的每一位 d，用 d+1 替换 d
例如，对于 193，它的每一位 +1 后的结果为 2，10，4。所以，193 的 X 运算结果为 2104
计算 n 进行 m 次运算后结果的位数，因为结果可能超过整形范围，所以你只需要告诉他结果模 10^9+7 的余数即可

样例输入：
输入多行，每行用 m n 的格式表示数字和遍历次数

5
1912 1
5 6
999 1
88 2
12 100

样例输出：

5
2
6
4
2115

思路：
直接模拟即可，注意当一位数字等于 10 之后会占两位

代码：

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
/**
 * Created by Aidan on 2021/9/3 17:43
 * GitHub: github.com/huaxin0304
 * Blog: aidanblog.top
 */

public class ArithmeticNum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int fre = scanner.nextInt();
        for (int i = 0; i < fre; i++) {

            long n = scanner.nextInt();
            long m = scanner.nextInt();

            long product = 0;
            while (n < 10) {
                n++;
                m--;
            }
            while (m-- != 0) {
                long temp = 0;
                long power = 1;
                while (n > 0) {
                    temp = n % 10;
                    temp++;
                    // 处理 10 占两位的情况 
                    if (temp == 10) {
                        temp *= power;
                        power *= 10;
                    } else {
                        temp *= power;
                    }
                    product += temp;
                    power *= 10;
                    n /= 10;
                }
                temp = 0;
                power = 1;
                n = product;
            }
            long count = 0;
            while (product > 0) {
                product = product / 10;
                count++;
                count %= Math.pow(10, 9) + 7;
            }
            System.out.println(count);
        }
    }
}

58 同城

58 同城的笔试题（9-11 20:00），牛客上进行的，当初度小满的第一次笔试题可给我自闭坏了（一道样例怎么改都是 81.7%，还有一道忘了加 scanner.nextLine() 一直报空指针，因为读到的换行符是作为空字符串存储的），这次倒好，三道编程题没半小时全部 AC，调试都不用调，安逸的很

数组唯一数

题目：
给出一个整型数组，找出其中只出现过一次的数字，这里确定至少会有一个出现一次的数，返回一个数组，其中按原数组顺序返回

样例输入：

[1, 1, 4, 6, 7, 7, 3]

样例输出：

[4, 6, 3]

思路：
这里规定按原数组属性返回，如果使用 HashMap 需要增加遍历一次原数组的代码，所以直接使用 LinkedHashSet 就完了
不存在添加进 Set 集合，如若已经存在则移除，最后根据 Set.size() 取出数据即可
存在的问题是如果数字出现奇数次也会存在 Set 中，但 AC 了，看来测试数据没有出现过超过两次的情况，后续添加了一个 deletedSet 保存删除的数字解决问题

代码：

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
/**
 * Created by Aidan on 2021/9/11 20:50
 * GitHub: github.com/huaxin0304
 * Blog: aidanblog.top
 */

public class UniqueNumber {
    public static void main(String[] args) {
        int[] test = {1, 1, 4, 6, 7, 7, 3};
        int[] result = find(test);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }

    public static int[] find(int[] arg) {
        Set<Integer> set = new LinkedHashSet<>();
        for (int i = 0; i < arg.length; i++) {
            if (!set.contains(arg[i])) {
                set.add(arg[i]);
            } else {
                set.remove(arg[i]);
            }
        }
        int[] arr = new int[set.size()];
        int index = 0;
        for (Integer i : set) {
            arr[index] = i;
            index++;
        }
        return arr;
    }

    /**
    public static int[] find(int[] arg) {
        Set<Integer> set = new LinkedHashSet<>();
        Set<Integer> delSet = new HashSet<>();
        for (int i = 0; i < arg.length; i++) {
            if (!set.contains(arg[i]) && !delSet.contains(arg[i])) {
                set.add(arg[i]);
            } else {
                set.remove(arg[i]);
                delSet.add(arg[i]);
            }
        }
        int[] arr = new int[set.size()];
        int index = 0;
        for (Integer i : set) {
            arr[index] = i;
            index++;
        }
        return arr;
    }
    **/
}

最大子数组和

题目：
给定一个数组和子数组的长度，找出子数组和的最大值，返回值一个数组包含其子数组的起始下标与子数组和，格式为：[index, sum]

样例输入：

[1, 2, 30, 4, 5, 6, 7, 8, 9, 10], 10, 3

样例输出：

[2, 39]

思路：
模拟一下就好，注意不要超过数组边界

代码：

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
/**
 * Created by Aidan on 2021/9/11 20:50
 * GitHub: github.com/huaxin0304
 * Blog: aidanblog.top
 */

public class SumBySub {
    public static void main(String[] args) {
        int[] result = subArraySum(new int[]{1, 2, 30, 4, 5, 6, 7, 8, 9, 10}, 10, 3);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }

    public static int[] subArraySum(int[] Array, int arrayLen, int subArrayLen) {
        // write code here
        int max = 0;
        int index = 0;
        int i = 0;
        while (i + subArrayLen < arrayLen) {
            int tempMax = 0;
            for (int j = i; j < i + subArrayLen; j++) {
                tempMax += Array[j];
            }
            if (max < tempMax) {
                max = tempMax;
                index = i;
            }
            i++;
        }
        return new int[]{index, max};
    }
}

不能坑队友

题目：
王者荣耀中英雄大致可以分为五类：上中下、打野、辅助，给定整型数组代表英雄，返回有几种组合，如果阵容不合理则不能开团（返回 0）

样例输入：

{0, 1, 2, 3, 4}

样例输出：

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
/**
 * Created by Aidan on 2021/9/11 20:58
 * GitHub: github.com/huaxin0304
 * Blog: aidanblog.top
 */

public class HeroPool {
    public static void main(String[] args) {
        int result = getTeams(new int[]{0, 1, 2, 3, 4});
        System.out.println(result);
    }

    public static int getTeams(int[] heros) {
        // write code here
        int countZero = 0, countOne = 0, countTwo = 0, countThree = 0, countFour = 0;
        for (int i = 0; i < heros.length; i++) {
            switch (heros[i]) {
                case 0: {
                    countZero++;
                    break;
                }
                case 1: {
                    countOne++;
                    break;
                }
                case 2: {
                    countTwo++;
                    break;
                }
                case 3: {
                    countThree++;
                    break;
                }
                case 4: {
                    countFour++;
                    break;
                }
            }
        }
        return countZero * countOne * countTwo * countThree * countFour;
    }
}

字节跳动

为面试准备的算法题，面试的部门是非中商业化技术，刷了一些面经中出现频率比较高的，结果很遗憾面试的时候没能撑到算法那一关

二叉树的右视图

LeetCode 地址

思路：
同时维护两个栈：节点栈和深度栈，节点站按照先左后右的顺序存放结点，深度栈存放每个结点对应的深度，这样在同一层深度第一个弹出的必定是最右边的结点，然后将当前深度和结点放入 Map 中，如果后续已经存在当前的深度的 Key，那就直接进入下一层

代码：

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
/** TreeNode 结构 
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // 以 <Depth, Node> 的形式存储每层深度的结点 
        Map<Integer, Integer> rightSideNode = new HashMap<>();
        int maxDepth = -1;  // 最大深度，负责从 Map 中取出对应深度的 Node

        Stack<TreeNode> nodeStack = new Stack<>();
        Stack<Integer> depthStack = new Stack<>();

        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int depth = depthStack.pop();
            if (node != null) {
                maxDepth = Math.max(maxDepth, depth);
                // 如果当前深度在 Map 中没有对应的 Key
                if (!rightSideNode.containsKey(depth)) {
                    rightSideNode.put(depth, node.val);
                }
                // 从左向右依次放入结点 
                nodeStack.push(node.left);
                nodeStack.push(node.right);
                depthStack.push(depth + 1);
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i <= maxDepth; i++) {
            list.add(rightSideNode.get(i));
        }
        return list;
    }
}

删除排序链表中的重复元素

LeetCode 地址

思路：
因为是排序链表，所以重复元素一定是连续出现的，可以维护一对快慢指针，当 slow.next==fast.next 时，取出当前重复值，快指针不断前移判断，直到不再重复时停下继续判断，中间重复值取消连接即可

代码：
这里优化后的代码仅使用一个指针，用 cursor.next 和 cursor.next.next 表示快慢 

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        // 用哑结点表示头结点的前置结点，因为头节点也可能重复被删除 
        ListNode dummy = new ListNode(0, head);
        ListNode cursor = dummy;

        // 只要快慢指针还能前移就持续判断 
        while (cursor.next != null && cursor.next.next != null) {
            // 当快慢指针的 next 结点值重复 
            if (cursor.next.val == cursor.next.next.val) {
                int x = cursor.next.val;
                do {
                    // 越过第一个重复值之后判断后续是否继续重复 
                    cursor.next = cursor.next.next;
                } while (cursor.next != null && cursor.next.val == x);
            } else {
                cursor = cursor.next;
            }
        }
        return dummy.next;
    }
}

子集

LeetCode 地址

思路：
回溯寻找，首先找长度 k=1k=1 的子集，到达数组末尾就表示寻找完毕，保存结果集
然后寻找长度为 k=2k=2 的子集，到达数组末尾可能存在存在 K 不为 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
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    int len = 0;

    public List<List<Integer>> subsets(int[] nums) {
        len = nums.length;
        for (int k = 0; k <= len; k++) {    // 寻找所有长度的子集 
            backTrack(0, k, new ArrayList<>(), nums);
        }
        return ans;
    }

    public void backTrack(int start, int k, List<Integer> tempSet, int[] nums) {
        if (k == 0) {   // 当前长度已经找完保存结果 
            ans.add(new ArrayList<>(tempSet));
            return;
        }
        for (int i = start; i < len; i++) {
            tempSet.add(nums[i]);
            // 防止重复，每次从下一个开始寻找，同时缩小子集要求个数 
            backTrack(i + 1, k - 1, tempSet, nums);
            tempSet.remove(tempSet.size() - 1);
        }
    }
    /* dfs 版本 
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
    */
}

删除链表的倒数第 N 个结点

LeetCode 地址

思路：

  1. 可以先遍历长度，第二次遍历到 length-n+1 时进行删除
  2. 将链表全部压入栈中，弹出的第 n 个数据就是要删除的链表
  3. 使用间隔为 n 的快慢指针，当 fast 为空时，删除 slow 结点

代码：
这里使用第三种方法实现，复杂度最低 

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head); // 创建哑结点，因为头结点也有可能被删除 
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next; // 快结点先走 n 步 
        }
        while (first != null) { // 快结点到达末尾删除满结点所在位置 
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

合并 K 个升序链表

LeetCode 地址

思路：
这里先把问题规模缩小，不考虑 K 个链表怎么合并，看作是两个链表，每次合并后作为一个链表继续和后续链表合并即可

至于两个链表的合并就是每次判断值赋予新链表上，当一个链表为空后，将另一链表直接置于新链表末尾即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {// 遍历每一条链表让其与上一条链表合并 
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);    // 哑结点的 next 表示，防止错乱 
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {  // 比较值之后保留小的 
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;   // 指针后移 
        }
        tail.next = (aPtr != null ? aPtr : bPtr);   // 当有链表为空时，另一链表放到结果链表的后边 
        return head.next;
    }
}

花旗

纯英文的题目，但好在描述的简洁直接，读题还是没障碍的，一道 SQL 实现题，放到了这篇 实现贴上面 ，还有一道合并有序数组的没必要放上来了，说说这道动规吧

规定时间内到达终点的最小花费

LeetCode 地址

思路：
这道题第一时间想的是最短路径实现，但后来还是换成了动态规划，结束之后推算了一下确实也是动态规划的复杂度比较小，要花费 n∗maxTimesn*maxTimes 的规模初始化 dp 数组，然后遍历 maxTimesmaxTimes 来对每一个 edges 数组来操作，最后的复杂度为 O((n+m)⋅maxTimes)O((n+m)⋅maxTimes)

创建一个 maxTimesmaxTimes 的 dp 数组，然后我们在时间限定内进行动规，dp[t][i] 表示第 t 分钟到达城市 i 时的最少费用，然后假设跟其有边的点 j 就是到达 i 的最后一步，进行状态转移，最后找出时间范围中到达 n-1 花费最小的即可

  • 当前时间为 1，只能从 0 走到 3 号点，这样的花费就是 25 dp[1][3]=dp[0][0]+cost[3]
  • 时间在 2-9 之间时只能在 0-3 点横跳
  • …
  • 此时时间为 10，横跳结束，可以走到 1 号点，花费 15 dp[10][1]=dp[0][0]+cost[1]
  • 时间来到 11，可以到达 4 号点，花费 45 dp[11][34]=dp[1][3]+cost[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
48
49
50
51
52
53
public class MinCostWithTimeLimited {
    public static void main(String[] args) {
        System.out.println(minCostWithTimeLimited(30,
                new int[][]{
                        {0, 1, 10},
                        {1, 2, 10},
                        {2, 5, 10},
                        {0, 3, 1},
                        {3, 4, 10},
                        {4, 5, 15}
                },
                new int[]{5, 1, 2, 20, 20, 3}));
    }

    public static int minCostWithTimeLimited(int maxTime, int[][] edges, int[] passingFees) {

        int n = passingFees.length; // 根据城市成本数组保留城市个数 
        /*
        最大费用，这里根据数据规模计算 
        可以使用 `Integer.MAX_VALUE - Arrays.stream(passingFees).max().getAsInt();`
        */
        int maxFee = (int) 1E6 + 1;
        // 创建时间限制同样规模的数组，保留从 0 到 i 需要的时间 
        int[][] dp = new int[maxTime + 1][n];

        // 使用最大成本填充 
        for (int i = 0; i <= maxTime; i++) {
            Arrays.fill(dp[i], maxFee);
        }

        // 起点花费 
        dp[0][0] = passingFees[0];
        // 在时间限定中尝试 
        for (int i = 1; i <= maxTime; i++) {
            for (int[] edge : edges) {
                // 耗时超过当前时间限定直接下一次循环 
                if (edge[2] > i) {
                    continue;
                }
                int x = edge[0], y = edge[1], time = edge[2];
                // 根据边关系求出走这条路时的花费 
                dp[i][x] = Math.min(dp[i][x], dp[i - time][y] + passingFees[x]);
                dp[i][y] = Math.min(dp[i][y], dp[i - time][x] + passingFees[y]);
            }
        }

        int ans = maxFee;
        for (int i = 0; i <= maxTime; i++) {
            ans = Math.min(ans, dp[i][n - 1]);
        }
        return (ans == maxFee) ? -1 : ans;
    }
}

阿里巴巴

两道题，第二道没做明白，只 AC 了第一道

补码的加法运算

题目：
第一行给出组数 N，紧接输入 N 行数据，每行一对以补码形式的的 32 位字符，输出相加后的十进制结果

样例输入：

2
00000000000000000000000000000101 11111111111111111111111111111111
00000000000000000000000000011111 00000000000000000000000000000111

样例输出：

4
38

思路：
可以根据补码直接定义运算规则，也可以转换为原码后进行计算，我这里选择的是第二种，根据原码对补码的转换思路反向操作即可，转换补码的思路：

  1. 正数：保持不变
  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
import java.util.Scanner;

/**
 * @author Aidan
 * @createTime 2021/10/8 20:06
 * @GitHub github.com/huaxin0304
 * @Blog aidanblog.top
 */

public class ComplementArithmetic {

    /**
     * 尽量不要在代码中出现 magic number
     * 可以使用 int 型定义为 48,49
     */
    static final char ZERO = '0';
    static final char ONE = '1';

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            scanner.nextLine();
            String a = scanner.next();
            String b = scanner.next();
            // 数据读取后进行处理，转换为 10 进制 
            int x = hand(a), y = hand(b);
            System.out.println(x + y);
        }
    }

    public static int hand(String str) {
        char[] chars = str.toCharArray();
        int m;

        // 符号位为 0 是一个正数，直接进行进制转换 
        if (chars[0] == ZERO) {
            m = Integer.parseInt(str, 2);
        } else {
            // 将数值位按位取反 
            for (int i = 1; i < chars.length; i++) {
                if (chars[i] == ONE) {
                    chars[i] = ZERO;
                } else {
                    chars[i] = ONE;
                }
            }
            String newA = String.copyValueOf(chars, 1, 31);
            // 处理末尾与符号 
            m = Integer.parseInt(newA, 2) + 1;
            if (m > 0) {
                m *= -1;
            }
        }
        return m;
    }
}

倍业科技

字符串压缩与解压

LeetCode 地址

代码：

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

/**
 * @author Aidan
 * @createTime 2021/10/26 14:13
 * @GitHub github.com/huaxin0304
 * @Blog aidanblog.top
 */

public class TarString {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        System.out.println(compress(str));
        System.out.println(decompress(str));
    }

    static String compress(String str) {
        StringBuilder builder = new StringBuilder();
        char start = str.charAt(0);
        int count = 1;
        for (int i = 1; i < str.length(); i++) {
            char next = str.charAt(i);
            // 重复字符累加 
            if (start == next) {
                count++;
                continue;
            }
            // 根据重复次数压缩 
            if (count == 1) {
                builder.append(start);
            } else {
                builder.append(count).append(start);
            }
            // 开始下一轮重复 
            start = next;
            count = 1;
        }
        // 处理末尾数据 
        if (count == 1) {
            builder.append(start);
        } else {
            builder.append(count).append(start);
        }
        return builder.toString();
    }

    static String decompress(String str) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < str.length();) {
            char c = str.charAt(i);
            // 如果当前遍历到的字符是数字，考虑位数超过一的情况 
            if (Character.isDigit(c)) {
                int j = i + 1;
                for (; j < str.length(); j++) {
                    if (!Character.isDigit(str.charAt(j))) {
                        break;
                    }
                }
                // 根据数字进行重复 
                int num = Integer.parseInt(str.substring(i, j));
                builder.append(String.valueOf(str.charAt(j)).repeat(Math.max(0, num)));
                i = j + 1;
                // 遇到单个字符的情况 
            } else {
                builder.append(str.charAt(i));
                i++;
            }
        }
        return builder.toString();
    }
}

便利蜂

测量次数

题目：
小明和他的伙伴发现了一堆木头排成了一排，一共 n 个，假设排列在 x 轴上，最左端的木头的坐标是 -1，最右端木头的坐标是 n。他们想拿走里面最重和最轻的木头各一个，但是他们并不知道是这一堆里的哪一个，因此他们需要挨个测量。现在他们在这排木头的两端，一个人在坐标 0，一个人在坐标 n，他们只能按顺序测量，即在 0 位置的人只能依次测量 0, 1, 2, 3 然后到 n，在 n 位置的人则相反。现在你已经知道每个木头的重量，你可以指挥他们是否继续测量，问两个人一共最少需要多少次测量就可以找到最重和最轻的木头

输入描述：
第一行一个整数 n，0<=n<=1000

第二行 n 个空格隔开的整数，表示木头的重量，其中任意一个数大小范围是 [-1, 10000]。

输出描述：
一个整数，表示最少需要测量的次数。

样例输入：

4
0 5 4 3 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
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author Aidan
 * @createTime 2021/10/30 19:24
 * @GitHub github.com/huaxin0304
 * @Blog aidanblog.top
 */

public class MeasureNum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int maxInd = 0, max = Integer.MIN_VALUE, minInd = 0, min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
            if (arr[i] > max) {
                max = arr[i];
                maxInd = i;
            }
            if (arr[i] < min) {
                min = arr[i];
                minInd = i;
            }
        }

        List<Integer> maxIndList = new ArrayList<>();
        List<Integer> minIndList = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == arr[minInd]) {
                minIndList.add(i);
            }
            if (arr[i] == arr[maxInd]) {
                maxIndList.add(i);
            }
        }
        int result = 0;
        for (Integer maxTemp : maxIndList) {
            maxInd = maxTemp;
            for (Integer minTemp : minIndList) {
                minInd = minTemp;
                if (maxInd < minInd) {
                    int temp = maxInd;
                    maxInd = minInd;
                    minInd = temp;
                }
                result = Math.min(Math.min(n - minInd, maxInd + 1), (minInd + 1) + (n - maxInd));
            }
        }

        System.out.println(result);
    }
}

滴滴

删除游戏的最大得分

题目：
首先随机写下 N 个正整数，然后任选一个数字作为起始点，从起始点开始从左往右每次可以删除一个数字，但是必须满足下一个删除的数字要小于上一个删除的数字。每成功删除一个数字计 1 分。请问对于给定的 N 个正整数，一局游戏过后可以得到的最大计分是多少？

思路：
第一时间考虑的 dfs 方式，也能跑完但这种问题还是动态规划比较好，所以结束后又写了一遍动规的写法

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.Scanner;

/**
 * @author Aidan
 * @createTime 2021/10/23 16:33
 * @GitHub github.com/huaxin0304
 * @Blog aidanblog.top
 */

public class MaxScore {

    private static int result = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        /* dfs 调用 
        for (int i = 0; i < arr.length; i++) {
            dfs(arr[i], i, arr, 1);
        }
        */
        dp(arr);
        System.out.println(result);

    }

    private static void dp(int[] arr) {
        int[] dp = new int[arr.length];
        dp[0] = 1;
        int maxIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (arr[j] > arr[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
            if (dp[maxIndex] < dp[i]) {
                maxIndex = i;
            }
        }
        result = dp[maxIndex];
    }

    /* dfs 解法 
    private static void dfs(int flag, int i, int[] arr, int count) {
        if (i + 1 == arr.length) {
            result = Math.max(result, count);
        }
        int j = i + 1;
        for (; j < arr.length; j++) {
            if (arr[j] < flag) {
                count++;
                dfs(arr[j], j, arr, count);
                count--;
            }
        }
        if (j == arr.length) {
            result = Math.max(result, count);
        }
    }
    */
}

最小生成树

题目：
X 星大学新校区终于建成啦！ 新校区一共有 N 栋教学楼和办公楼。现在需要用光纤把这 N 栋连接起来，保证任意两栋楼之间都有一条有线网络通讯链路。
已知任意两栋楼之间的直线距离（单位：千米）。为了降低成本，要求两栋楼之间都用直线光纤连接。
光纤的单位成本 C 已知（单位：X 星币 / 千米），请问最少需要多少 X 星币才能保证任意两栋楼之间都有光纤直接或者间接相连？
注意：如果 1 号楼和 2 号楼相连，2 号楼和 3 号楼相连，则 1 号楼和 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
import java.util.Scanner;

/**
 * @author Aidan
 * @createTime 2021/10/23 16:59
 * @GitHub github.com/huaxin0304
 * @Blog aidanblog.top
 */

public class MinLen {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), c = scanner.nextInt();
        int[][] map = new int[n + 1][n + 1];
        int[] visited = new int[n + 1];
        for (int i = 1; i <= n * (n - 1) / 2; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int len = scanner.nextInt();
            map[x][y] = len;
            map[y][x] = len;
        }
        // 所有楼都会间接可达，不用考虑入口，直接选择 1 号楼 
        visited[1] = 1;
        int result = 0, step = 1, now = 0, min;
        while (step < n) {
            min = Integer.MAX_VALUE;
            for (int i = 1; i <= n; i++) {
                if (visited[i] == 1) {
                    // 选择没被连接的可达最小值 
                    for (int j = 1; j <= n; j++) {
                        if (visited[j] == 0 && min > map[i][j]) {
                            min = map[i][j];
                            now = j;
                        }
                    }
                }
            }
            if (min != Integer.MAX_VALUE) {
                // 被连接后标识 
                visited[now] = 1;
                result += min;
                step++;
            }
        }
        System.out.println(result * c);
    }
}

去哪儿

题目：
对字符串按照字符出现频率重新排序，频率相同按大小写排序，同为大写或小写按字母序排列

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class StringReordering {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String str = scanner.nextLine();
        char[] chars = str.toCharArray();
        Map<Character, Integer> map = new HashMap<>();

        for (char c : chars) {
            int count;
            if (map.containsKey(c)) {
                count = map.get(c);
                map.put(c, ++count);
            } else {
                map.put(c, 1);
            }
        }

        List<Map.Entry<Character, Integer>> entryList = new ArrayList<>(map.entrySet());

        entryList.sort((o1, o2) -> {
            if (!Objects.equals(o2.getValue(), o1.getValue())) {
                return o2.getValue() - o1.getValue();
            } else if ((o1.getKey() > 94 && o2.getKey() > 94) || (o1.getKey() < 95 && o2.getKey() < 95)) {
                return o1.getKey() - o2.getKey();
            }
            return o1.getKey() > 94 ? 1 : -1;
        });
        StringBuilder stringBuilder = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : entryList) {
            stringBuilder.append(String.valueOf(entry.getKey()).repeat(Math.max(0, entry.getValue())));
        }
        System.out.println(stringBuilder);

    }
}

360

题目：
小 A 的英语考了个不及格，老师很生气，并且发现他英语的语法几乎全错！于是老师决定好好教教他英语语法

老师想先从句子结构开始教他。一个句子至少需要包含主谓结构，即主语和谓语，并且主语在前，谓语在后。有些句子会在谓语后面加上宾语。避免复杂，本题中句子的顺序严格按照主语 - 谓语 - 宾语的顺序（即无宾语前置和倒装等情况）。

老师给了小 A 三张单词表，分别是主语单词表、谓语单词表和宾语单词表。老师要让小 A 用这些单词表中的单词来造句，并且规定：谓语有且仅有一个单词，主语和宾语可以包含任意个单词（主语不可为空）。老师暂时不想让小 A 造出能保证意思通顺的句子，他只想让小 A 能够学会基本的句子结构就行。

现在，小 A 根据这些单词造了 m 条句子，现在假设你是老师，你需要判断每条句子是否符合上述句子结构。

输入描述

  1. 第一行三个正整数 n1, n2, n3，分别表示主语、谓语、宾语单词表的单词数；
  2. 第二行包含 n1 个单词，单词仅由小写英文字母组成，每两个单词之间有一个空格，单词长度不超过 10；
  3. 第三行包含 n2 个单词，其他格式同上；
  4. 第四行包含 n3 个单词，其他格式同上；
  5. 第五行一个正整数 m；
  6. 接下来 m 行，每行一个句子。句子由若干单词（至少一个）组成，并且保证出现的单词都在上面的单词表内。每两个单词之间一个空格隔开

数据保证一个单词最多只可做一种句子成分。即每个单词仅会出现在一个单词表上。
1≤n1, n2, n3≤1000, 1≤m≤20, 1≤句子单词数≤10

输出描述
对于每条句子，如果其符合句子结构，输出一行“YES”（不含引号），否则输出一行“NO”（不含引号）

样例输入

3 3 3
i you he
am is are
yours his hers
5
i am yours
you is his
he are hers yours
i am am yours
is his

样例输出

YES
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
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;

/**
 * Created by Aidan on 2021/10/24 15:42
 * GitHub: github.com/huaxin0304
 * Blog: aidanblog.top
 */

public class AmIsAre {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int zCount = scanner.nextInt(), wCount = scanner.nextInt(), bCount = scanner.nextInt();
        Map<String, Integer> map = new HashMap<>();
        for (int j = 0; j < zCount; j++) {
            String temp = scanner.next();
            map.put(temp, 0);
        }
        scanner.nextLine();
        for (int j = 0; j < wCount; j++) {
            String temp = scanner.next();
            map.put(temp, 1);
        }
        scanner.nextLine();
        for (int j = 0; j < bCount; j++) {
            String temp = scanner.next();
            map.put(temp, 2);
        }
        scanner.nextLine();

        int count = scanner.nextInt();
        scanner.nextLine();
        for (int i = 0; i < count; i++) {
            String str = scanner.nextLine();
            String[] strings = str.split(" ");
            List<Integer> list = new ArrayList<>();
            for (String string : strings) {
                list.add(map.get(string));
            }
            String flag = "YES";
            if (!list.contains(0)) {
                flag = "NO";
            } else {
                int W_Count = 0;
                for (int i1 = 1; i1 < list.size(); i1++) {
                    if (list.get(i1 - 1) > list.get(i1) || W_Count > 1
                            || (list.get(i1) == 2) && W_Count == 0) {
                        flag = "NO";
                        break;
                    } else if (list.get(i1) == 1) {
                        W_Count++;
                    }
                }
            }
            System.out.println(flag);
        }
    }
}

途家民宿

生成城市树

题目：

按照固定的格式进行输入，每行的格式为：IdpIdlevelnameId pId level name，最后按照级别生成目录形式的文本输出，若级别相同，则按姓名进行升序排列

思路：

将每个城市封装成一个 class，对级别为 0 的城市进行遍历，然后递归输出后续的城市并进行格式的调整

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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
import java.util.*; 

/**
 * @author Aidan
 * @createTime 2021/11/13 15:28
 * @GitHub github.com/huaxin0304
 * @Blog aidanblog.top
 */

public class GenerateCityTree {

    static class City {
        int ID, PID, level;
        String name;

        public City(int ID, int PID, int level, String name) {
            this. ID = ID; 
            this. PID = PID; 
            this.level = level; 
            this.name = name; 

        }

    }

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

        List<City> cityList = new ArrayList<>();

        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            Scanner scannerStr = new Scanner(str);
            String[] strings = new String[4];
            for (int i = 0; i < 4; i++) {
                strings[i] = scannerStr.next();
            }
            City tempCity = new City(Integer.parseInt(strings[0]),
                    Integer.parseInt(strings[1]), Integer.parseInt(strings[2]), strings[3]);
            cityList.add(tempCity);

        }

        cityList.sort((o1, o2) -> {
            if (o1.level != o2.level) {
                return o1.level - o2.level;
            }
            return o1.ID - o2.ID;
        });

        /*for (City city : cityList) {
            System.out.println(city.getName());
        }*/

        for (City city : cityList) {
            if (city.level == 1) {
                System.out.println(city.name);
                dfs(cityList, city.level + 1, city.ID);
            }

        }

    }

    static void dfs(List<City> list, int level, int ID) {
        for (City city : list) {
            if (city. PID == ID && city.level == level) {
                outSpace(level); 
                System.out.print(city.name); 
                System.out.println(); 
                dfs(list, level + 1, city. ID); 
            }

        }

        return; 

    }

    static void outSpace(int level) {
        for (int i = 0; i < (level - 1) * 4; i++) {
            System.out.print(" ");

        }

    }

}

逆序输出文章

题目：

输入一篇英文文章，将每个词颠倒顺序进行输出，每个词仍保证有序

思路：

将每个词放入 List 集合中，对特定格式的词进行处理（包含 ‘, ‘，’.’），然后逆序遍历输出即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

/**
 * @author Aidan
 * @createTime 2021/11/13 14:55
 * @GitHub github.com/huaxin0304
 * @Blog aidanblog.top
 */

public class ReviseArticle {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] s1 = s.split(" ");
        ArrayList<String> strings = new ArrayList<>(Arrays.asList(s1));

        Collections.reverse(strings);

        int i = 0;
        for (String string : strings) {
            i++;
            if (string.contains(",")) {
                String[] split = string.split(",");
                System.out.print(split[1]);
                System.out.print(",");
                System.out.print(split[0]);
            } else if (string.contains(".")) {
                String[] split = string.split("\\.");
                if (split.length == 1) {
                    System.out.print(".");
                    System.out.print(string.replace('.', ' '));
                    continue;
                } else {
                    System.out.print(split[1]);
                    System.out.print(".");
                    System.out.print(split[0]);
                }
            } else {
                System.out.print(string);
            }
            if (i < strings.size()) {
                System.out.print(" ");
            }
        }
    }
}

数美科技

题目：

如果有相邻字符是连续状态则可以看作是连续子串，输入一串字符，求其中连续子串的个数

代码：

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

/**
 * @author Aidan
 * @createTime 2021/11/18 20:10
 * @GitHub github.com/huaxin0304
 * @Blog aidanblog.top
 */

public class SubStr {

    // 将连续子串放入 set 中防止重复 
    private static Set<String> set = new HashSet<String>();

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

        // 截取字符串的不中断连续子串 
        for (int i = 0; i < str.length(); i++) {
            int j = i;
            while (j + 1 < str.length() && str.charAt(j + 1) == str.charAt(j) + 1) {
                j++;
            }
            numSub(str.substring(i, j + 1));
            // i 会自增，使用 j 即可 
            i = j;

        }

        // 结果去掉空串 
        System.out.println(set.size() - 1);
    }

    /**
     * 每个连续子串又可以分成 n(n+1)/2 个（不包括空串）
     *
     * @param string 截取的不中断连续子串 
     */
    private static void numSub(String string) {

        // 子串可以分隔成 i~n 中长度 
        for (int i = 1; i <= string.length(); i++) {
            int j = 0;
            for (; j + i <= string.length(); j++) {
                set.add(string.substring(j, j + i));
            }
            set.add(string.substring(j));
        }
    }
}
  • 本文标题：校招后端面试算法题 —— Java 实现
  • 本文作者：Aidan
  • 创建时间：2021-09-11 21:09:25
  • 本文链接：https://aidanblog.top/school_interview-exam/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论