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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏韦弦的偶尔分享

Swift 旋转数组 - LeetCode

例如,如果 n = 7 , k = 3,给定数组 [1,2,3,4,5,6,7] ,向右旋转后的结果为 [5,6,7,1,2,3,4]。

1685
来自专栏蓝天

彻底理解C/C++指针

彻底理解C++指针.pdf 推荐阅读pdf版本,原因是从WPS复制粘贴到ChinaUnix后格式有些丢了。

981
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

782
来自专栏蓝天

进一步理解指针2:双指针、指针数组和数组指针

1) 如果int* p,则“1”实际是sizeof(int),也就是p指向的类型大小;

1441
来自专栏Java 源码分析

排序算法

选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

4046
来自专栏mukekeheart的iOS之旅

No.008 String to Integer (atoi)

8. String to Integer (atoi) Total Accepted: 112863 Total Submissions: 825433 Dif...

2487
来自专栏简书专栏

Numpy入门2

标题中的英文首字母大写比较规范,但在python实际使用中均为小写。 2018年7月26日笔记

1353
来自专栏AI派

Numpy 修炼之道 (2)—— N维数组 ndarray

ndarray中的每个元素在内存中使用相同大小的块。 ndarray中的每个元素是数据类型对象的对象(称为 dtype)。

3616
来自专栏Java开发者杂谈

算法之数组和问题

算法题之数组和求解 数组和问题 ​ 加上给定一个数组和值x。设计一个算法使得如果数组中存在两个元素的和为x,则输出两个元素的值组成的数组(不区分先后),否则输出...

3958
来自专栏静默虚空的博客

排序五 简单选择排序

要点 简单选择排序是一种选择排序。 选择排序:每趟从待排序的记录中选出关键字最小的记录,顺序放在已排序的记录序列末尾,直到全部排序结束为止。 简单排序处理流程 ...

2059

扫码关注云+社区

领取腾讯云代金券