关键词：

图的遍历

题目描述

给定一张包含N个点、N-1条边的无向连通图，节点从1到N编号，每条边的长度均为1。假设你从1号节点出发并打算遍历所有节点，那么总路程至少是多少？

输入

第一行包含一个整数N，1≤N≤105。

接下来N-1行，每行包含两个整数X和Y，表示X号节点和Y号节点之间有一条边，1≤X，Y≤N。

输出

输出总路程的最小值。

样例输入

4
1 2
1 3
3 4

样例输出

4

Hint
按1->2->1->3->4的路线遍历所有节点，总路程为4。

思路

遍历所有节点类似于深度优先搜索，也就是说除了最后一条路径外，走了两遍，设最后一条路径为depth，总分支数为N-1，总路径=2 * (N-1-x)+x=2 * N - 2 - depth，当depth最大时总路径最小，所以转化为求二叉树的深度。

代码实现

package meituan;

import java.util.Scanner;

public class Main 
    public static void main(String[] args) 
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] t = new int[100005];
        int x, y;
        for (int i = 0; i < N - 1; i++) 
            x = sc.nextInt();
            y = sc.nextInt();
            t[y] = t[x] + 1;
        
        int depth = 0;
        for (int i = 1; i <= N; i++) 
            depth = t[i] > depth ? t[i] : depth;
        
        System.out.println(2 * N - 2 - depth);
    

区间统计

题目描述

小明拿到了一个数列a1 , a2 , ... an ，小明想知道存在多少个区间[l,r]同时满足下列两个条件：

1、r-l+1=k;

2、在a l , a l+1,...ar中，存在一个数至少出现了 t 次。

输出满足条件的区间个数。

输入

输入第一行三个整数n,k,t(1≤n,k,t≤10^5)。

第二行 n 个整数，a1 , a2 , ... an (1≤ai≤10^5)。

输出

输出一个数，问题的答案。

样例输入

5 3 2
3 1 1 1 2

样例输出

3

Hint

区间[1,3]中1出现了2次，区间[2,4]中1出现了3次，区间[3,5]中1出现了2次。所以一共有3个区间满足条件。

思路

滑动窗口维护区间中数字出现大于等于t次的个数

代码实现

package meituan;

import java.util.Scanner;

public class Main2 
    public static void main(String[] args) 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int t = sc.nextInt();
        if (k > n || t > n) 
            System.out.println(0);
        
        int[] num = new int[n];
        int[] ct = new int[n];
        int cnt = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) 
            num[i] = sc.nextInt();
        
        for (int i = 0; i < k - 1; i++) 
            ct[num[i]]++;
            if (ct[num[i]] >= t && ct[num[i]] - 1 < t) 
                cnt++;
            
        
        for (int i = k - 1; i < n; i++) 
            ct[num[i]]++;
            if (ct[num[i]] >= t && ct[num[i]] - 1 < t) 
                cnt++;
            
            if (cnt > 0) 
                ans++;
            
            ct[num[i - k + 1]]--;
            if (ct[num[i - k + 1]] < t && ct[num[i - k + 1]] + 1 >= t) 
                cnt--;
            
        
        System.out.println(ans);
    

字节秋季笔试四道编程题（2021-09-12）(代码片段)

...经全部整理好放在【TechGuide】了，私信公众号回复【美团】或者【百度】即可获得最实时的笔试题解啦！通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复... 查看详情

美团点评2017秋招笔试编程题

美团点评2017秋招笔试编程题  1， 大富翁游戏，玩家根据骰子的点数决定走的步数，即骰子点数为1时可以走一步，点数为2时可以走两步，点数为n时可以走n步。求玩家走到第n步（n<=骰子最大点数且是方法的唯一入... 查看详情

1.虎牙直播2019秋招编程题(代码片段)

第一题： #include<iostream>#include<string>usingnamespacestd;boolIsVoChar(charc)return(c==‘a‘)||(c==‘e‘)||(c==‘o‘)||(c==‘i‘)||(c==‘u‘)||(c==‘A‘)||(c==‘E‘)||(c==‘O‘)||(c==‘I‘)||(c==‘U‘); 查看详情

美团点评2017秋招笔试编程题——大富翁游戏

大富翁游戏，玩家根据骰子的点数决定走的步数，即骰子点数为1时可以走一步，点数为2时可以走两步，点数为n时可以走n步。求玩家走到第n步（n<=骰子最大点数且是方法的唯一入参）时，总共有多少种投骰子的方法。 输... 查看详情

2018秋招小红书算法方向在线编程题(代码片段)

代码如下：classTreeNode:def__init__(self,x):self.left=Noneself.right=Noneself.value=xdefBuildTree(ceng,zhong):iflen(ceng)==0:returnNoneiflen(ceng)==1:returnTreeNode(ceng[0])else:flag=TreeNode(ceng[0])root= 查看详情

百度2018春招开发测试工程师编程题题解(代码片段)

题目描述在一个家庭中,每位成员都有手机。这家户主维护一棵家族树,树的每个节点代表一位家庭成员,每个节点的值代表他她所拥有的手机数量,户主作为这棵树的根。户主想要找到同一代家庭成员所拥有手机的最大数量。属于... 查看详情

网易秋招校招编程题(代码片段)

　　网易内推面试凉了，再战正式批笔试，选择和简答略难，编程题很良心，基本就是模拟、找规律，略加思考就能解出来的题目，本弱鸡只有在良心网易笔试才能AK。1、翻转翻转　　　　这题一开始没思路，ac了后两题后再回... 查看详情

codem美团点评编程竞赛资格赛题

最近看到牛课网美团一个编程竞赛，想着做做看，结果一写就是两天。。真是写不动了啊。话不多说，下面开始我的题解。题目大致还是比较考察思维和代码能力（因为自己代码能力较弱，才会觉得比较考察代码能力吧==！），... 查看详情

搜狗2019秋招的一道算法题：龟兔赛跑(代码片段)

时间限制：3秒空间限制：92160K定义如下图所示的比赛地图： S表示比赛起点，E表示比赛终点。实线表示陆路，虚线表示水路。兔子只能走陆路，乌龟既可以走陆路也可以走水路。每条路径的长度在图中给出。假定兔子和乌龟... 查看详情

2019vivo秋招提前批笔试题第3题(代码片段)

笔试的时候没做出来，就顺手截图了。虽然知道要用动态规划做，但我一直就不太懂动态规划。笔试完又花了2小时把它做出来了。也不知道性能怎么样，但还好做出来了。defsolution(n,toltal_money,until_price,until_hot):#二维数组，每一... 查看详情

备战秋招冲击大厂java面试题系列—并发编程(代码片段)

1.进程和线程的区别进程是资源分配的最小单位，线程是CPU调度的最小单位，一个程序至少一个进程，一个进程至少一个线程。进程：是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概... 查看详情

2017年腾讯秋招软件开发笔试编程题回忆版

2017年腾讯秋招软件开发笔试编程题回忆版（所有题目大致描述如下，并非完整的题目回忆，但意思大致一样）1、又一个魔法城市，城市里面有n个魔法城堡，序号为0，1，2。。。n-1；魔法城堡之间都有路径相连；魔法城堡两两之... 查看详情

字节跳动2019春招研发部分编程题汇总题解(代码片段)

差不多2个小时才AK,题目难度还行吧。自己好菜。题目地址：https://www.nowcoder.com/test/16516564/summary目录万万没想到之聪明的编辑【模拟】万万没想到之抓捕孔连顺【思维/二分】雀魂启动！【枚举/二进制枚举】特征提取【模... 查看详情

2019acm首尔j题题解(代码片段)

...离中，最大距离的最小。求该最小值（数据范围n为3-1e6）题解这个距离其实就是两个三角形之间隔离几条线(包括自身三角形的)这题首先应该确定划分方案由于分割出三角形的数量是一定的 查看详情

2021大厂秋招必备—linux网络编程面试题「好文收藏」

推荐视频：基于linuxepoll原理剖析以及三握四挥的细节处理tcpip，accept，11个状态，细枝末节的秘密，还有哪些你不知道c/c++linux服务器开发学习地址：c/c++linux后台服务器高级架构师1、什么是IO多... 查看详情

携程2019校招编程题(代码片段)

携程今年的机试题为20道选择+3编程由于今天最后提交时第三题编程未通过，交卷之后想出来的解法这里记录一下。importjava.util.ArrayList;importjava.util.List;importjava.util.Scanner;//携程3publicclassLRUpublicstaticvoidmain(String[]args)Scannersc=newScanner( 查看详情

秋招上岸！双非本科，从外包实习到秋招收获阿里美团b站意向书！(代码片段)

大家好，我是路飞，今天这篇文章是来还愿的！秋招顺利结束，感谢大家一直以来的支持和陪伴！1、秋招果实秋招正式批第一个意向书，阿里巴巴——Java研发岗：9月初，终于收到了自己梦寐以求... 查看详情

2022年java秋招面试，程序员求职必看的dubbo面试题(代码片段)

...，企业工作过的，都可参考学习!小编分享的这份2022年Java秋招备战面试题总计有1000多道面试题，包含了MyBatis、ZooKeeper、 查看详情