题目1:LCR 152. 验证二叉搜索树的后序遍历序列

请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。

定义一个指针p,从左到右遍历数组,找到第一个大于等于根节点的节点,记录index为m

p继续右移,右移条件变为大于根节点

最后判断p是否移到了最右侧,若是,说明这一层子树没问题,然后用&&继续递归判断左右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        return recur(postorder, 0, postorder.length - 1);
    }
    boolean recur(int[] postorder, int i, int j) {
        if(i >= j) return true; //分化为左右子树
        int p = i;
        while(postorder[p] < postorder[j]) p++; 
        int m = p;//寻找 第一个大于根节点 的节点，索引记为 m
        while(postorder[p] > postorder[j]) p++;//让p继续向右,如果走不到最右侧(根节点),说明右子树不是搜索树(左侧已经验证过是绝对ok的)
        return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
    }
}

题目2: 1817. 查找用户活跃分钟数

给你用户在 LeetCode 的操作日志，和一个整数 k 。日志用一个二维整数数组 logs 表示，其中每个 logs[i] = [IDi, timei] 表示 ID 为 IDi 的用户在 timei 分钟时执行了某个操作。

多个用户 可以同时执行操作，单个用户可以在同一分钟内执行 多个操作 。

指定用户的 用户活跃分钟数（user active minutes，UAM） 定义为用户对 LeetCode 执行操作的 唯一分钟数 。 即使一分钟内执行多个操作，也只能按一分钟计数。

请你统计用户活跃分钟数的分布情况，统计结果是一个长度为 k 且 下标从 1 开始计数 的数组 answer ，对于每个 j（1 <= j <= k），answer[j] 表示 用户活跃分钟数 等于 j 的用户数。

返回上面描述的答案数组 answer 。

建立一个map,记录每个id下的活跃分钟,最后遍历每个id,数一下分钟总数,让该分钟对应的ans++即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    class Solution {
    public int[] findingUsersActiveMinutes(int[][] logs, int k) {
        int[] ans = new int[k];
        Map<Integer,Set<Integer>> map = new HashMap<>();//账户id,该id下的活跃时间

        for(int[] log: logs){
            int id = log[0],time=log[1];
            map.putIfAbsent(id,new HashSet<Integer>());
            map.get(id).add(time);
        }

        for(Set<Integer> set : map.values()){
            ans[set.size()-1]++;
        }

        return ans;
    }
}