美团2019秋招后台开发编程题题解
图的遍历
题目描述
给定一张包含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样例输出
4Hint 按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样例输出
3Hint
区间[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);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-09-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录