腾讯2024实习生在线笔试-0331

Q1 小红的图上染色

小红拿到了一个无向图，其中一些边被染成了红色。

小红定义一个点是“好点”，当且仅当这个点的所有邻边都是红边。

现在请你求出这个无向图“好点”的数量。

注：如果一个节点没有任何邻边，那么它也是好点。

输入描述

第一行输入两个正整数n,m ，代表节点的数量和边的数量。

接下来的m行，每行输入两个正整数u, v和一个字符chr，代表节点 u 和节点v 有一条边连接。如果 chr 为’R’，代表这条边被染红；’W’代表未被染色。

1 <= n, m <= 10^5 1 <= u, v <= n

输出描述

一个整数，代表“好点”的数量。

示例 1

输入

4 4
1 2 R
2 3 W
3 4 W
1 4 R

输出

1

说明

只有 1 号节点是好点

我的代码

package oj1;

import java.util.Scanner;

/**
 * @Description
 * @Author chenyi0008
 * @Date 2024/3/31
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 节点
        int m = sc.nextInt(); // 边
        boolean[] arr = new boolean[100010];
        int a, b;
        String c;
        for (int i = 0; i < m; i++) {
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.next();
            if(c.equals("W")){
                arr[a] = true;
                arr[b] = true;
            }
        }
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if(arr[i] == false)sum ++;
        }
        System.out.println(sum);
    }
}

通过100%

这题没啥难 会分析就行

Q2 小红的链表断裂

小红拿到了一个链表。她准备将这个链表断裂成两个链表，再拼接到一起，使得链表从头节点到尾部升序。你能帮小红判断能否达成目的吗？

给定的为一个链表数组，你需要对于数组中每个链表进行一次“是”或者“否”的答案回答，并返回布尔数组。

每个链表的长度不小于 2，且每个链表中不包含两个相等的元素。所有链表的长度之和保证不超过10^5

示例 1

输入

[{1,2,3},{2,3,1},{3,2,1}]

输出

[true,true,false]

说明

第三个链表无论怎么操作都不满足条件。

我的代码

package oj2;

/**
 * @Description
 * @Author chenyi0008
 * @Date 2024/3/31
 */
public class Solution {
    public static void main(String[] args) {
        ListNode l11 = new ListNode(1);
        ListNode l12 = new ListNode(2);
        ListNode l13 = new ListNode(3);
        ListNode[] listNodes = new ListNode[1];
        l11.next =l12;
        l12.next = l13;
        listNodes[0] = l11;

        Solution solution = new Solution();
        boolean[] booleans = solution.canSorted(listNodes);
        for (boolean aBoolean : booleans) {
            System.out.println(aBoolean);
        }
    }

    public boolean[] canSorted (ListNode[] lists) {
        int len = lists.length;
        boolean[] ans = new boolean[len];

        for (int i = 0; i < lists.length; i++) {
            ListNode node = lists[i];
            boolean flag = false;
            boolean ji = false;
            int first = node.val;
            int tmp = node.val;
            while (node.next != null){
                node = node.next;
                if(tmp > node.val && flag == false){
                    flag = true;
                }else if(tmp > node.val && flag == true){
                    ji = true;
                    break;
                }
                tmp = node.val;
            }

            if(!ji && first > tmp || flag == false) ans[i] = true;
//            if(ji) ans[i] = false;
        }

        return ans;
    }
}

通过100%

没啥难的，主要是花在debug的时间有点长

Q3 小红的连通图

小红拿到了一个有n个节点的无向图，这个图初始并不是连通图。

现在小红想知道，添加恰好一条边使得这个图连通，有多少种不同的加边方案？

输入描述

第一行输入两个正整数n, m，用空格隔开。

接下来的m行，每行输入两个正整数u,v，代表节点u和节点v之间有一条边连接。

1 <= n, m <= 10^5

1 <= u, v <= n

保证给出的图是不连通的。

输出描述

一个整数，代表加边的方案数。

示例 1

输入

4 2
1 2
3 4

输出

4

说明

添加边 (1,3) 或者 (1,4) 或者 (2,3) 或者 (2,4) 都是可以的。

示例 2

输入

4 1
1 3

输出

0

说明

无法变成连通图

我的代码

package oj3;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

/**
 * @Description
 * @Author chenyi0008
 * @Date 2024/3/31
 */
public class Main {

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

        arr = new int[n + 1];
        for (int i = 1; i < arr.length; i++) {
            arr[i] = i;
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            if(find(a) != find(b)){
                if(arr[a] == a)arr[a] = find(b);
                else if(arr[b] == b)arr[b] = find(a);
            }
        }
        for (int i = 1; i <= n; i++) {
            arr[i] = find(i);
        }

        HashSet<Integer> set = new HashSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] tmp = new int[100];
        int sum = 0;


        for (int i = 1; i < arr.length; i++) {
            int father = find(arr[i]);
            if(!set.contains(father)){
                sum ++;
                tmp[sum] = father;
                set.add(father);
                map.put(father, 1);
            }else {
                Integer value = map.get(father);
                map.put(father, value + 1);
            }
            if(sum > 2){
//                System.out.println("超出");
                System.out.println(0);
                return;
            }
        }

        System.out.println(map.get(tmp[1]) * map.get(tmp[2]));

//        System.out.println(sum);



    }

    public static int find(int i){
//        while (arr[i] != i){
//            arr[i] = find(arr[i]);
//            if(arr[i] == find(arr[i]))return arr[i];
//        }
        if(arr[i] != i)arr[i] = find(arr[i]);
        return arr[i];
    }



}

通过率100%

做题的时候想不起来并查集的模板，自己在那研究了好久才发现写的代码有问题

Q4 小红的数组分割

小红拿到了一个数组，她准备将数组分割成k段，使得每段内部做按位异或后，再全部求和。小红希望最终这个和尽可能大，你能帮帮她吗？

输入描述

输出描述

输出一个正整数，表示最终的最大和。

示例 1

输入

6 2
1 1 1 2 3 4

输出

10

说明

示例 2

输入

5 3
1 0 1 1 0

输出

3

示例 3

输入

3 3
1 1 2

输出

4

我的代码

一眼看出dp，这是笔试结束后写的 不知道通过率多少 有问题请评论提出

package oj4;

import java.util.Scanner;

/**
 * @Description
 * @Author chenyi0008
 * @Date 2024/3/31
 */
public class Main {

    static int[][] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = arr[i];
        }

        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = dp[i][i] ^ dp[i + 1][i + 1];
        }

        for (int p = 1; p < n; p++) {
            for (int i = 0; i < n - p; i++) {
                dp[i][i + p] = dp[i][i] ^ dp[i + p][i + p];
            }
        }

        // k为分割段数量 start表示从哪开始分割
        int res = dfs(k, 0, n - 1);
        System.out.println(res);

    }

    public static int dfs(int n ,int start, int end){

        if(n == 2){
            int max = 0;
            for (int idx = start; idx < end; idx++){
                int sum = dp[start][idx] + dp[idx + 1][end];
                max = sum > max ? sum : max;
            }
            return max;
        }
        int max = 0;
        for(int idx = start; idx < end; idx ++){
            int sum = dfs(n - 1, start, idx) + dfs(n - 1, idx + 1, end);
            max = sum > max ? sum : max;
        }
        return max;
    }
}