yubのAlgorithm.0xf

前K个高频元素

link:347. 前 K 个高频元素 - 力扣（LeetCode）

思路分析

对于统计元素出现的频率，这一类问题可以用map来进行统计（key和value无敌）key存放元素，value存放出现的频率.
其实最开始想到的是暴力的遍历循环，逐个判断计数排列，剔除出现频率最小的元素.想用set但是不匹配统计频率的要求.就需要Set和Lsit结合.最后发现还是离不开心爱的map啊（大顶堆秒了）

大顶堆实现

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //创建Map
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums) {
            //确保更新元素
            map.put(num,map.getOrDefault(num,0)+1);
        } 
        //优先级队列存储(num，count)按从大到小排
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair,pair1)->pair1[1]-pair[1]);
        for(Map.Entry<Integer,Integer>entry:map.entrySet()){
            pq.add(new int[]{entry.getKey(),entry.getValue()});
        }
        int[] result = new int[k];
        for(int i = 0; i < k; i++) {
            result[i] = pq.poll()[0];
        }
        return result;
    }
}

小顶堆实现

注意 小顶堆由于出现频率少的在前面 所以要先剔除频率最小的元素以及不足k个的情况单独优先考虑

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        //出现次数最低的在队头
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            //小顶堆只需要维持k个元素有序
            if(pq.size()<k){
                //小顶堆元素个数小于k个时直接加
                pq.add(new int[]{entry.getKey(),entry.getValue()});
            }else{
                if(entry.getValue()>pq.peek()[1]){
                    //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll();
                    //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for(int i=k-1;i>=0;i--){
            //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

接下来二叉树基础遍历 递归秒了
递归注意三要素（来自代码随想录）
1.确定递归函数的参数和返回值
2.确定终止条件
3.确定单层递归的逻辑

二叉树的前序遍历

link：144. 二叉树的前序遍历 - 力扣（LeetCode）

思路分析

递归

使用ArrayList

动态大小：ArrayList 可以根据需要动态调整大小，适合在不知道最终节点数目的情况下使用。

快速随机访问：ArrayList 提供 O(1) 的时间复杂度来访问元素，这在需要频繁读取结果时非常高效。

简单易用：ArrayList 的 API 设计简单，提供了方便的方法（如 add）来添加元素。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        preOrder(root,list);
        return list;
    }
    //前序遍历递归 中左右 无返回值
    public void preOrder(TreeNode cur,List<Integer> result) {
        if(cur == null) {
            return ;
        }
        result.add(cur.val);
        preOrder(cur.left,result);
        preOrder(cur.right,result);
    }
}

二叉树的中序遍历

link：94. 二叉树的中序遍历 - 力扣（LeetCode）

思路分析

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        return list;
    }
    public void inOrder(TreeNode cur,List<Integer> list) {
        if(cur == null) {
            return ;
        }
        inOrder(cur.left,list);
        list.add(cur.val);
        inOrder(cur.right,list);
    }
}

二叉树的后序遍历

link：145. 二叉树的后序遍历 - 力扣（LeetCode）

思路分析

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        postOrder(root,list);
        return list;
    }
    public void postOrder(TreeNode cur,List<Integer> list) {
        if(cur == null) {
            return ;
        }
        postOrder(cur.left,list);
        postOrder(cur.right,list);
        list.add(cur.val);  
    }
}