腾讯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;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505283.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Web】NSSCTF Round#20 Basic 个人wp

目录 前言 真亦假&#xff0c;假亦真 CSDN_To_PDF V1.2 前言 感谢17&#x1f474;没让我爆零 真亦假&#xff0c;假亦真 直接getshell不行&#xff0c;那就一波信息搜集呗&#xff0c;先开dirsearch扫一下 扫的过程中先试试常规的robots.txt,www.zip,shell.phps,.git,.sv…

类的新功能

类的新功能 默认成员函数 在C11之前&#xff0c;一个类中有如下六个默认成员函数&#xff1a; 构造函数。拷贝构造函数赋值重载析构函数取地址重载函数const取地址函数 其中前四个默认成员函数最重要&#xff0c;后面两个默认成员函数一般不会用到&#xff0c;这里默认成员…

[MSSQL]理解SQL Server AlwaysOn AG的备份

AG提供了以下几种备份策略 下面来看看各项的解释 Prefer Secondary(首选辅助副本) 应在辅助副本上执行此可用性组的自动备份。如果没有可用的辅助副本,将在主副本上执行备份。 这个选项只是概念上的选项。基本上,用户可以从任何复制节点上执行备份命令。 我们可以在主副本…

《计时器》是谁演唱的?

是李亚云演唱的。李亚云&#xff0c;湖南省中峰富盛控股集团有限责任公司旗下全签艺人 &#xff0c;就读于南昌航空大学本科表演专业&#xff0c;&#xff0c;一个拥有“模特、练习生、爱豆和演员”多重身份的艺人&#xff0c;2003年3月10日出生于湖南长沙&#xff0c;7岁童星出…

设计模式深度解析:AI如何影响装饰器模式与组合模式的选择与应用

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》《MYSQL应用》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 AI如何影响装饰器模式与组合模式的选择与应用 在今天这个快速发展的技术时代&#…

C++11新特性(二):更好用的 lambda 表达式和 function 包装器

目录 lambda 表达式 基本格式及参数列表 对于 lambda 捕捉列表的说明 function 包装器 bind 包装器 lambda 表达式 C11引入了lambda表达式&#xff0c;它是一种用于创建匿名函数的语法。lambda表达式可以被视为一个匿名函数对象&#xff0c;它可以在需要函数对象的地方使用…

并查集----格子游戏

并查集中最重要的是要搞懂&#xff1a; 不明白的可以拿纸自己先演示一番&#xff0c;find函数不仅能找到他们的祖先数&#xff0c;而且同时也能更新路径的子结点都等于祖先&#xff0c;然后以后寻找时会更加的方便&#xff01;

【Linux】详解软硬链接

一、软硬链接的建立方法 1.1软链接的建立 假设在当前目录下有一个test.txt文件&#xff0c;要对其建立软链接&#xff0c;做法如下&#xff1a; ln就是link的意思&#xff0c;-s表示软链接&#xff0c;test.txt要建立软链接的文件名&#xff0c;后面跟上要建立的软链接文件名…

C语言-文件操作

&#x1f308;很高兴可以来阅读我的博客&#xff01;&#x1f31f;我热衷于分享&#x1f58a;学习经验&#xff0c;&#x1f3eb;多彩生活&#xff0c;精彩足球赛事⚽&#x1f517;我的CSDN&#xff1a; Kevin ’ s blog&#x1f4c2;专栏收录&#xff1a;C预言 1. 文件的作用 …

TransmittableThreadLocal 问题杂记

0、前言 TransmittableThreadLocal&#xff0c;简称 TTL&#xff0c;是阿里巴巴开源的一个Java库&#xff0c;它能够实现ThreadLocal在多线程间的值传递&#xff0c;适用于使用线程池、异步调用等需要线程切换的场景&#xff0c;解决了ThreadLocal在使用父子线程、线程池时不能…

Inter开发板实验汇总

背景 产品型号&#xff1a;AIxBoard-N5105 开发公司&#xff1a;蓝蛙智能 蓝蛙智能成立于2018年&#xff0c;2021年成为英特尔OpenVINO官方技术伙伴&#xff0c;2023年推出英特尔数字化开发套件爱克斯板AIxBoard-N5105。 资源 类型 网站 备注 产品介绍 ​​产品介绍 - …

华为云免费云服务器-低价云虚拟主机VPS-个人免费云服务器

华为云80款云服务产品0元试用活动&#xff0c;免费试用云服务器&#xff0c;云数据库、云速建站、云安全、CDN、OBS、Redis等云计算产品。为用户提供免费的云服务试用机会&#xff0c;帮助企业和个人轻松享受云服务。 原文&#xff1a;https://www.vpspick.com/vps/442.html …

js垃圾回收新生代和老生代以及堆栈内存详细

js 堆栈内存、新生代和老生代、垃圾回收详聊 要想了解JS内存管理就必须明白存这些js数据的内存又分为&#xff1a;栈内存和堆内存 一、 栈|堆内存(Stack|Heap) 栈(Stack)内存 原始值&#xff1a;Number、String、Boolean、Null、Undefined、Symbol和BigInt 栈内存主要存储原始…

UE5启用SteamOSS流程

一、安装OnlineSubsystemSteam插件 1、在UE里安装OnlineSubsystemSteam 2、设置默认开始地图 3、设置DefaultEngine.ini文件&#xff1a; 打开项目根目录/Config/DefaultEngine.ini文件 打开官网的配置说明 复制并粘贴到该文件中 4、设置运行模式 5、测试 确保Steam平台已…

玩转ChatGPT:Suno制作音乐

AI开始进军音乐领域了。 一款音乐AI神器——Suno V3发布&#xff0c;它能够处理从间奏到主歌、副歌、桥段直至尾奏的完整结构&#xff0c;零门槛创作音乐。 需要科学上网&#xff0c;官方网站&#xff1a;https://app.suno.ai/ 使用GPT写个歌词&#xff0c;然后丢进Suno生成…

EMD关于信号的重建,心率提取

关于EMD的俩个假设&#xff1a; IMF 有两个假设条件&#xff1a; 在整个数据段内&#xff0c;极值点的个数和过零点的个数必须相等或相差最多不能超过一 个&#xff1b;在任意时刻&#xff0c;由局部极大值点形成的上包络线和由局部极小值点形成的下包络线 的平均值为零&#x…

聚观早报 | 小米SU7正式发布;xAI推出Grok-1.5

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 3月30日消息 小米SU7正式发布 xAI推出Grok-1.5 红魔9 Pro新品亮相 长城汽车2023年营收 快狗打车2023年度业绩 小…

C++心决之命名空间、重载函数和引用

目录 1. C关键字(C98) 2. 命名空间 2.1 命名空间定义 2.2 命名空间使用 3. C输入&输出 4. 缺省参数 4.1 缺省参数概念 4.2 缺省参数分类 5. 函数重载 5.1 函数重载概念 5.2 C支持函数重载的原理--名字修饰(name Mangling) 6. 引用 6.1 引用概念 6.2 引用特性…

二维码门楼牌管理应用平台:构建社区信息新生态

文章目录 前言一、二维码门楼牌管理应用平台的功能优势二、信息展示与居民互动三、提升社区治理效能四、展望未来的发展方向 前言 随着信息技术的迅猛发展&#xff0c;二维码门楼牌管理应用平台逐渐崭露头角&#xff0c;成为社区管理的新宠。通过这一平台&#xff0c;居民可以…

Spring Boot 使用 Redis

1&#xff0c;Spring 是如何集成Redis的&#xff1f; 首先我们要使用jar包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency><dependency><gro…