美团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

样例输出

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); } }