算法
2024真题

2024真题

仅记录值得注意的题目

小米0312春招实习笔试真题

链接 (opens in a new tab)

小明打砖块

题目描述：

小明在玩一个消除游戏。这个消除游戏有点特别。 游戏中，你会得到n个一维排列的有各自颜色的砖块。

消除的时候，你有三种消除方案。你可以单消一个砖块， 这样你可以得到a的得分；如果两个颜色一样的砖块在一起， 你可以将这两个砖块一起消除获得b的得分； 如果三个颜色一样的砖块在一期，你可以将这三个砖块一起消除获得c的得分。

消除后，被消除的砖块自动消失， 被消除砖块的左右两端的砖块将在消除之后挨在一起。

小明想知道在最优策略下他能得到多少得分。

输入描述:

第一行4个整数n，a，b，c，表示砖块数量，和一消/二消/三消的得分。

接下来一行n个整数，第i个整数si表示第i个砖块的颜色。

输出描述:

输出最高得分

样例输入:

8 1 3 7
3 1 3 1 3 2 2 3

样例输出:

14

解题思路：

动态规划

private void xiaomi0321_2() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int a = in.nextInt();
    int b = in.nextInt();
    int c = in.nextInt();
    int[] nums = new int[n];
    for (int i = 0; i < n; i++) {
        nums[i] = in.nextInt();
    }
 
    // dp[i, j] 表示i，j区间内最大的收益（闭区间）
 
    int[][] dp = new int[n][n];
 
    // 初始化：对角线
    for (int i = 0; i < n; i++) {
        dp[i][i] = a;
    }
 
    // 从下往上，从左往右
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            int left = dp[i + 1][j] + a; // 单消左边
            int right = dp[i][j - 1] + a; // 单消右边
            int both = 0; // 两边都消
            int trip = 0; // 三个都消
            if (nums[i] == nums[j]) {
                both = dp[i + 1][j - 1] + b; // 两边都消
                for (int k = i + 1; k < j; k++) {
                    if (nums[k] == nums[i]) { // 三个都消
                        trip = Math.max(trip, dp[i + 1][k - 1] + dp[k + 1][j - 1] + c);
                    }
                }
            }
            dp[i][j] = Math.max(Math.max(left, right), Math.max(both, trip));            
        }
    }
    System.out.println(dp[0][n - 1]);
}

携程0313春招实习笔试真题

链接 (opens in a new tab)

游游的数组推平

题目描述：

游游拿到了一个数组，她每次操作可以任选一个元素加 1 或者减 1。 游游想知道，将所有元素都变成和ai相等需要操作最少多少次？ 你需要回答i∈[1,n]的结果。

输入描述:

第一行输入一个正整数n，代表数组的大小。第二行输入n个正整数ai， 代表数组的元素。

1<=n<=10^5

1<=ai<=10^9

输出描述:

输出n行，分别代表i∈[1,n]的结果。

示例 1:

输入：

3
2 1 4

输出：

3
4
5

解题思路：

排序后前缀和。 因为要求按原数组顺序输出，所以还需二分查找原数组元素排序后的位置

public static void xiancheng0313_2() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
    }
 
    // 原数组排序
    int[] sortedArr = arr.clone();
    Arrays.sort(sortedArr);
    int[] pres = new int[n];
    pres[0] = sortedArr[0];
 
    // 计算前缀和
    for (int i = 1; i < n; i++) {
        pres[i] = pres[i - 1] + sortedArr[i];
    }
 
    long[] sortedResult = new long[n];
    // 计算结果集
    for (int i = 0; i < n; i++) {
        long cur = (long) sortedArr[i] * (i + 1) - pres[i] + (pres[n - 1] - pres[i]) - (sortedArr[i] * (n - 1 - i));
        sortedResult[i] = cur;
    }
 
    // 通过二分查找找到原数组对应的结果
    for (int i = 0; i < n; i++) {
        int index = Arrays.binarySearch(sortedArr, arr[i]);
        System.out.println(sortedResult[index]);
    }
 
    in.close();
}

游游的数组压缩

题目描述：

游游拿到了一个数组，她希望你将数组相同的相邻元素压缩在一起。你能帮帮她吗？

给定的数组是已经被压缩了一部分的形式，请你继续将其压缩到不能再压缩为止。 举个例子，数组[2,3,5,5,5,3]会被压缩成[2(1),3(1),5(3),3(1)]。

输入示例：

[1(2),1(1),-1(3)]

输出示例：

[1(3),-1(3)]

解题思路：

重点如何读入字符串，如何解析字符串。这里用正则表达式

另外输出时注意最后一个元素的处理

public static void xiancheng0313_3() {
    Scanner in = new Scanner(System.in);
    String input = in.nextLine();
    in.close();
 
    Pattern pattern = Pattern.compile("-?\\d+");
    Matcher matcher = pattern.matcher(input);
 
    List<List<Integer>> result = new ArrayList<>();
    while (matcher.find()) {
        List<Integer> pair = new ArrayList<>();
        pair.add(Integer.parseInt(matcher.group()));
        if (matcher.find()) {
            pair.add(Integer.parseInt(matcher.group()));
        }
        result.add(pair);
    }
 
    int preNum = result.get(0).get(0);
    int preCnt = result.get(0).get(1);
 
    System.out.print("[");
    for (int i = 1; i < result.size(); i++) {
        int num = result.get(i).get(0);
        int cnt = result.get(i).get(1);
        if (i != result.size() - 1) {
            if (num == preNum) {
                preCnt += cnt;
            } else {
                System.out.print("" + preNum + "(" + preCnt + "),");
                preNum = num;
                preCnt = cnt;
            }
        }
        else {
            if (num == preNum) {
                preCnt += cnt;
                System.out.print("" + preNum + "(" + preCnt + ")");
            } else {
                System.out.print("" + preNum + "(" + preCnt + "),");
                System.out.print("" + num + "(" + cnt + ")");
            }
        }
    }
    System.out.print("]");
}

米哈游0310春招实习笔试真题

链接 (opens in a new tab)

米小游和建木

题目描述：

仙舟罗浮上有一棵建木，据说服下建木生成的神实就可以得到“无尽形寿”的身体，蜕变为长生种。米小游是短生种，因此她很想找到神实。

建木是一棵有 n 个节点的有根树，节点编号为1-n ，根节点为x 。

对于编号为i 的节点f[i] 表示以i 为根的子树中，节点编号是i 的因子的节点个数。

建木上神实的总数就是 Σf[i] ，米小游想知道建木上神实的总数是多少。

输入描述：

第一行包含两个整数 n,x(1<=x<=n<=5*10^5)，表示树的节点个数，根节点编号。

接下来n-1 行，每行两个整数 u, v(1<=u,v<=n) ，表示一条u 到v 的树边。

数据保证一定是一棵树。

输出描述：

输出一个整数，表示建木上神实的总数。

示例：

输入：

4 4
1 2
4 3
2 4

输出：

7

解题思路：

DFS+回溯

逆转思路，计算每一个节点的贡献值即可。每个节点贡献值取决于上层所有的父节点的因子数量

public static void main(String[] args){
    new AcmTest().mhy0310_3();
}
 
public Map<Integer, Integer> map = new HashMap<>();
public int ans = 0;
 
public void mhy0310_3() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int x = in.nextInt();
 
    // 建图（树）
    List<Integer>[] graph = new ArrayList[n + 1];
    for (int i = 0; i < n + 1; i++) {
        graph[i] = new ArrayList<>();
    }
    for (int i = 0; i < n - 1; i++) {
        int u = in.nextInt();
        int v = in.nextInt();
        graph[u].add(v);
        graph[v].add(u);
    }
 
    // dfs
    dfs(x, 0, graph);
 
    System.out.println(ans);
 
    in.close();
}
 
// 求一个数的因子（复杂度O(sqrt(n))）
public Set<Integer> getDivisor(int n) {
    Set<Integer> res = new HashSet<>();
    for (int i = 1; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            res.add(i);
            if (i != n / i) {
                res.add(n / i);
            }
        }
    }
    return res;
}
 
public void dfs(int u, int parent, List<Integer>[] graph) {
    Set<Integer> divisors = getDivisor(u);
    // 此节点的所有因子贡献度+1，如果在后续dfs中出现了这个因子，
    // 那么处理此因子时就可以得知此因子在向上直到根节点的贡献度
    for (int i : divisors) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }
    // 遍历所有子节点，但是避免回头
    for (int v : graph[u]) {
        if (v == parent) continue;
        dfs(v, u, graph);
    }
    // 本节点下面已经遍历完了，那么就可以计算本节点的贡献度
    ans += map.getOrDefault(u, 0);
    // 恢复进入此节点前的贡献度map
    for (int i : divisors) {
        map.put(i, map.get(i) - 1);
    }
}

滴滴0317春招实习笔试真题

链接 (opens in a new tab)

模拟陨石对地质的危害

题目描述：

小明正在模拟陨石对地质的危害。在小明的模型下， 将地面从0,1,2…直到N依次从左到右进行标号。每次陨石i坠落，会使得标号在[L,R]这个区间范围内的地面受到一次陨石打击。

在 M 次陨石坠落后，小明想知道某些指定地面在刚才 M 次 陨石坠落中受到了多少次陨石打击。

输入描述：

第一行两个正整数 N,M，含义如题面,

接下来一行 M 个数，分别为L1,L2,...,Ln表示这M次陨石打击的左边界。

接下来一行 M 个数，分别为R1,R2,...,Rn，表示这M次陨石打击的右边界。

接下来一个数 Q，表示小明询同次数。

接下来一行Q个数x，表示小明想知道标号为x的地面在刚才M次阳石坠落中受到了多少次打击。

输出描述：

输出一行 Q 个数，用空格隔开(无行未空格)，分别表示每次询问的答案。

示例：

输入：
    4 3
    1 2 2
    2 3 4
    5
    0 1 2 3 4
输出：
    0 1 2 3 4

解题思路：

差分数组

public void didi0317_1() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
    int[] left = new int[m];
    int[] right = new int[m];
    for (int i = 0; i < m; i++) {
        left[i] = in.nextInt();
    }
    for (int i = 0; i < m; i++) {
        right[i] = in.nextInt();
    }
    int q = in.nextInt();
    int[] x = new int[q];
    for (int i = 0; i < q; i++) {
        x[i] = in.nextInt();
    }
 
    int[] diff = new int[n + 1];
    Arrays.fill(diff, 0);
 
    for (int i = 0; i < m; i++) {
        diff[left[i]]++;
        if (right[i] + 1 < n + 1) diff[right[i] + 1]--;
    }
 
    int[] ans = new int[n + 1];
    ans[0] = diff[0];
    for (int i = 1; i < n + 1; i++) {
        ans[i] = ans[i - 1] + diff[i];
    }
 
    System.out.printf("%d",ans[x[0]]);
    for (int i = 1; i < q; i++) {
        System.out.printf(" %d",ans[x[i]]);
    }
}

技术能力最近的领导

题目描述：

小A所在的企业中，每个员工在请求授权的时候都需要向他上面的某一级领导提出申请。

为了避免混乱，一个员工只会向他的上级领导中技术能力与他最相近的那位领导提出申请。现在小A想知道每个人的申请对象是谁。

小A所在企业的组织架构可以用一棵有根树来描述。即除了树根对应的最高领导以外，每个人都有唯一的一个直屋领导。

同时，每个员工的技术能力均可以用一个正整数表示，称为技术等级。两个人之间的技术能力越近则他们的技术等级之差的绝对值越小。

输入描述：

第一行有一个正整数 n(2≤n≤1000 00)。n 代表小 A所在企业中的员工数量。

第二行有 n-1个正整数，第i个数 fi(i<fi≤n)代表编号为i的员工的直属领导是fi，编号为n的员工是没有直属领导的最高级领导。

第三行有n个正整数，第i个数ai代表编号为i的员工的技术等级。技术等级的范围在1到n之间。

输出描述：

在一行中输出 n-1 个以空格分隔的正整教，行未不能有空格。第i个代表编号为i的员工请求授权时的申请对象。

如果某个员工有个技术能力与他最相近的上级领导，则他会选择在组织架构上离他最近的那一位。

示例：

输入：
    6
    3 3 5 5 6
    2 5 4 1 3 6
输出：
    5 3 5 5 6

解题思路：

DFS

private List<Integer> path = new ArrayList<>();
private int[] ans;
public void didi0317_2() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    ans = new int[n];
    List<Integer>[] graph = new List[n];
    for (int i = 0; i < n; i++) {
        graph[i] = new ArrayList<>();
    }
    for (int i = 0; i < n - 1; i++) {
        int u = in.nextInt();
        graph[u - 1].add(i);
    }
    int[] level = new int[n];
    for (int i = 0; i < n; i++) {
        level[i] = in.nextInt();
    }
 
    // System.out.printf("aaa");
 
    dfs(n, n - 1, graph, level);
    System.out.printf("%d", ans[0] + 1);
    for (int i = 1; i < n - 1; i++) {
        System.out.printf(" %d", ans[i] + 1);
    }
}
private void dfs (int n, int root, List<Integer>[] graph, int[] level) {
    if (root != n - 1) findLeader(root, level);
    path.add(root);
    for (int i = 0; i < graph[root].size(); i++) {
        dfs(n, graph[root].get(i), graph, level);
    }
    path.remove(path.size() - 1);
}
 
private void findLeader(int root, int[] level) {
    int leader = path.get(path.size() - 1);
    int diff = Math.abs(level[leader] - level[root]);
    for (int i = path.size() - 2; i >= 0; i--) {
        if (diff > Math.abs(level[path.get(i)] - level[root])) {
            leader = path.get(i);
            diff = Math.abs(level[path.get(i)] - level[root]);
        }
    }
    ans[root] = leader;
}

阿里云0318面试（来源舍友）

// 阿里云 2021.03.18 一面第二题
// 给定数组a和整数h，求a[i]+a[j]+a[k]的最大值，其中i,j,k满足i<j<K且j-i>h且k-j>h
// 我的解法是O(n)，声明两个数组，一个维护每个位置左边的最大值，
// 另一个维护每个位置右边的最大值，然后遍历中间的j即可
 
public void maxByIJK() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int h = in.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = in.nextInt();
    }
    
    System.out.println(maxTripleSum1(a, h));
    System.out.println(maxTripleSum2(a, h));
}
 
public int maxTripleSum1(int[] a, int h) {
    int n = a.length;
    int[] maxRight = new int[n];
    int[] maxLeft = new int[n];
    maxRight[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        maxRight[i] = Math.max(maxRight[i + 1], a[i]);
    }
    maxLeft[0] = a[0];
    for (int i = 1; i < n; i++) {
        maxLeft[i] = Math.max(maxLeft[i - 1], a[i]);
    }
    int ans = Integer.MIN_VALUE;
    for (int j = h + 1; j < n - h - 1; j++) {
        ans = Math.max(ans, maxLeft[j - h - 1] + a[j] + maxRight[j + h + 1]);
    }
    return ans;
}
 
public int maxTripleSum2(int[] a, int h) {
    int n = a.length;
    int ans = Integer.MIN_VALUE;
    for (int i = 0; i < n - h - h - 2; i++) {
        for (int j = i + h + 1; j < n - h - 1; j++) {
            for (int k = j + h + 1; k < n; k++) {
                ans = Math.max(ans, a[i] + a[j] + a[k]);
            }
        }
    }
    return ans;
}
 
// 阿里云 2021.03.18 一面第一题
// 原地排序链表，奇数位节点在前，偶数位节点在后
// 我的解法是O(n)，维护奇头和偶头，然后遍历链表，
// 将奇数位节点和偶数位节点分别串起来，最后将偶头接到奇尾
 
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 
public void swap() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    ListNode head = new ListNode(in.nextInt());
    ListNode cur = head;
    for (int i = 1; i < n; i++) {
        ListNode node = new ListNode(in.nextInt());
        cur.next = node;
        cur = node;
    }
 
    ListNode evenHead = head; // 0 偶
    ListNode oddHead = head.next; // 1 奇
    evenHead.next = null;
    cur = oddHead.next;
    oddHead.next = null;
    ListNode evenCur = evenHead;
    ListNode oddCur = oddHead;
    while (cur != null) {
        evenCur.next = cur;
        evenCur = cur;
        cur = cur.next;
        if (cur != null) {
            oddCur.next = cur;
            oddCur = cur;
            cur = cur.next;
        }
    }
    oddCur.next = evenHead;
 
    cur = oddHead;
 
    while (cur != null) {
        System.out.printf("%d ", cur.val);
        cur = cur.next;
    }
}

顺丰0318春招实习笔试真题

链接 (opens in a new tab)

钓鱼比赛

题目描述：

小明参加了一个钓鱼比赛，比赛时间一共T秒，看参赛者谁钓上来的鱼最多。

一共有n个池子，不同的池子里鱼的类型不同，同一个池子里鱼的类型相同。 参赛者只有一条鱼竿，同一时刻只能在一个池子里钓一条鱼，一个池子的鱼最多可以钓一条。 第i个池子里的鱼需要花t[i]的时间才可以钓上来，同时每个池子都有一个特定参数a[i]， 它的意思是这个池子里的鱼被钓上来后算有效得分需要满足一个条件， 就是整场比赛该参赛人员钓上的鱼的总数不能超过a[i]。你能帮助小明合理安排， 使得钓上可以算有效得分的鱼最多么？

输入描述：

第一行两个整数n和T，1<=n<=200000, 1<=T<=1000000000;

接下来n行，每行两个整数a[i],t[i], 1<=a[i]<=n, 1<=t[i]<=10000

输出描述：

一个整数，表示小明最多可以钓上来的鱼的数量。

示例：

输入：
2 10
2 4
2 5
输出：
2

输入：
5 300
3 100
4 150
4 80
2 90
2 300
输出：
2

解题思路：

贪心算法+优先队列

先用时间排序（升序，即贪最短时间的鱼）， 然后用优先队列（小根堆，此池子可算有效得分的鱼数，堆头是最小）维护当前钓上来的鱼。

若发现当前池子的鱼数超过了a[i]，则将堆头弹出，同时更新当前池子的鱼数。

细节：如果一开始判断不能钓鱼（超时了），但后面又弹出了鱼（因为超过有效数量了），那么就再次判断是否能钓鱼。

public void shunfeng0318_2() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int T = in.nextInt();
    List<List<Integer>> at = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        List<Integer> cur = new ArrayList<>();
        cur.add(in.nextInt());
        cur.add(in.nextInt());
        at.add(cur);
    }
    
    Collections.sort(at, new Comparator<List<Integer>>() {
        @Override
        public int compare(List<Integer> o1, List<Integer> o2) {
            return o1.get(1) - o2.get(1);
        }
    });
 
    PriorityQueue<List<Integer>> pq = new PriorityQueue<>(new Comparator<List<Integer>>() {
        @Override
        public int compare(List<Integer> o1, List<Integer> o2) {
            return (o1.get(0) - o2.get(0));
        }
    });
 
    int ans = 0;
    int cost = 0;
 
    for (int i = 0; i < n; i++) {
        boolean flag = false;
        if (cost + at.get(i).get(1) <= T) {
            flag = true;
            pq.offer(at.get(i));
            cost += at.get(i).get(1);
            ans++;
        }
        if (pq.peek().get(0) < ans) {
            cost -= pq.poll().get(1);
            ans--;
            if (!flag) {
                pq.offer(at.get(i));
                cost += at.get(i).get(1);
                ans++;
            }
            if (pq.peek().get(0) < ans) {
                cost -= pq.poll().get(0);
                ans--;
            }
        }
        
    }
 
    System.out.println(ans);
}
Hot100Day00 模板