图的遍历

题目描述

给定一张包含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);
    }
}