招舟子 普通 2023年9月29日 下午4:32

    本打卡对应问题:【回溯专题】剑指 Offer 34. 二叉树中和为某一值的路径
    具体打卡内容:

    /**
    * 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 {
    List<List> res;
    List
    tmp;
    public List<List
    > pathTarget(TreeNode root, int target) {
    res = new ArrayList<>();
    tmp = new ArrayList<>();
    dfs(root,target);
    return res;
    }
    void dfs(TreeNode root, int target){
    if(rootnull){
    return;
    }
    tmp.add(root.val);
    target = target-root.val;
    if(root.right
    null&&root.leftnull&&target0){
    res.add(new ArrayList<>(tmp));
    }
    dfs(root.left,target);
    dfs(root.right,target);
    tmp.remove(tmp.size()-1);
    }
    }
    时间复杂度O(n)
    空间复杂度O(n)

    泡芙 永久会员 2023年9月27日 下午1:58

    本打卡对应问题:二叉树的右视图 🌟🌟🌟中等
    具体打卡内容:

    层序遍历,记录每层最后一个节点

    • Time:O(n)
    • Space:O(n)
    class Solution {
        public List<Integer> rightSideView(TreeNode root) {
            if (root == null) {
                return new ArrayList<>();
            }
            Queue<TreeNode> queue = new LinkedList<>();
            List<Integer> res = new ArrayList<>();
    
            queue.add(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i ++) {
                    TreeNode temp = queue.poll();
                    if (temp.left != null) {
                        queue.add(temp.left);
                    }
                    if (temp.right != null) {
                        queue.add(temp.right);
                    }
                    if (i == size - 1) { //将当前层的最后一个节点放入结果列表
                        res.add(temp.val);
                    }
                }
            }
            return res;
        }
    }
    
    DataSpace 普通 2023年9月26日 下午3:01

    本打卡对应问题:第四章:理解链表🌟🌟🌟🌟🌟
    具体打卡内容:

    打卡

    smiler 永久会员 2023年9月26日 上午11:55

    本打卡对应问题:【作业2】求 x 平方根的上界
    具体打卡内容:

    以下是代码

    public int mySqrt(int x) {
            int l = 0, r = x;
            while (l <= r) {
                int m = l + (r - l) / 2;
                long t = (long) m * m;
                if ((long) m * m == x) {
                    return m;
                }
                if (t < x) {
                    l = m + 1;
                }
                if (t > x) {
                    r = m - 1;
                }
            }
            return l;
        }
    
    DataSpace 普通 2023年9月25日 下午5:41

    本打卡对应问题:【作业3】剑指 Offer 57 – II. 和为s的连续正数序列
    具体打卡内容:

    “`python代码
    class Solution:
    def fileCombination(self, target: int) -> List[List[int]]:
    if target<=0: return -1

        i,j,s,r = 1,2,3,[]
        while i<j:
            if s == target:
                r.append(list(range(i, j + 1)))
            if s>=target:
                s = s - i
                i = i + 1
            else:
                j = j + 1
                s = s + j
        return r
    

    “`

    DataSpace 普通 2023年9月25日 下午4:15

    本打卡对应问题:LeetCode11.盛最多水的容器🌟🌟🌟中等
    具体打卡内容:

    打卡

    DataSpace 普通 2023年9月25日 下午2:50

    本打卡对应问题:【作业1】LeetCode 26. 删除有序数组中的重复项
    具体打卡内容:
    class Solution:
        def removeDuplicates(self, nums: List[int]) -> int:
            if nums is None or len(nums)<1:
                return 0
            i,j = 0,1
            while j<=len(nums)-1:
                if nums[i] == nums[j]: #不做操作j后移
                    j = j + 1
                else:#i增加 同时把nums[j] 换到nums[i]处 这样i之前是处理好的
                    i = i + 1
                    nums[i] = nums[j]                
                    j = j + 1
            return i+1
    
    DataSpace 普通 2023年9月25日 上午11:45

    本打卡对应问题:LeetCode69.x的平方根.🌟🌟🌟🌟🌟简单
    具体打卡内容:

    打卡

    DataSpace 普通 2023年9月25日 上午11:21

    本打卡对应问题:LeetCode704.二分查找🌟🌟🌟🌟🌟简单
    具体打卡内容:

    打卡

    DataSpace 普通 2023年9月25日 上午11:12

    本打卡对应问题:第三章:二分查找基础
    具体打卡内容:

    打卡

    DataSpace 普通 2023年9月25日 上午11:11

    本打卡对应问题:第二章:时间复杂度分析
    具体打卡内容:

    打卡

    DataSpace 普通 2023年9月25日 上午11:11

    本打卡对应问题:第一章:如何准备一场算法面试?
    具体打卡内容:

    打卡

    黎明之前 普通 2023年9月25日 上午9:34

    本打卡对应问题:【二分查找专题】给出四种二分查找的模板
    具体打卡内容:

    //给出四种变形二分查找的模板代码
    //有序数组 arr = [1,2,3,3,3,4,5,5,7]
    //target = 3

    //给出四种变形二分查找的模板代码
    //有序数组 arr = [1,2,3,3,3,4,5,5,7]
    //target = 3

    //寻找第一个大于target 的元素的下标,本案例中 4就是第一个大于target 的元素,下标 = 5
    int upper(int[] arr, int target) {
    //如果都不存在,则返回-1
    if(arr[arr.length-1] <= target) return -1;

    int l = 0;
    int r = arr.length - 1;
    int mid = -1;
    while(l < r) {
        mid = (l + r) / 2;
        if(arr[mid] > target) {
            r = mid;//这里不能减一,否则mid是第一个大于target 的元素,的场景就缺失了
        }
        else if(arr[mid] < target) {
            l = mid + 1;
        }
        else {//arr[mid] = target
            l = mid + 1;
        }
    }
    //l就是第一个大于target 的元素的下标
    return l;
    

    }

    //如果数组中存在元素等于target,则返回最后一个等于target的元素的下标,
    //如果不存在,则返回第一个大于target的元素的下标。本案例中最后一个等于target的下标 = 4
    int floor_upper(int[] arr, int target) {
    //如果都不存在,则返回-1
    if(arr[arr.length-1] < target) return -1;
    if(arr[arr.length-1] target) return arr.length-1;

    int l = 0;
    int r = arr.length - 1;
    int mid = -1;
    while(l < r) {
        mid = (l + r) / 2;
        if(arr[mid] > target) {
            r = mid;//这里不能减一,否则mid是第一个大于target 的元素,的场景就缺失了
        }
        else if(arr[mid] < target) {
            l= mid + 1;
        }
        else {//arr[mid] = target
            l = mid + 1;
        }
    }
    //l就是第一个大于target 的元素的下标,如果存在等于target的元素,一定是l-1
    if(l - 1 >= 0 && arr[l - 1] == target) {
        return l - 1; 
    }
    return l;
    

    }

    //寻找最后一个小于target的元素的下标,本案例中2则是最后一个小于target的,下标1
    int lower(int[] arr, int target) {
    //如果都不存在,则返回-1
    if(arr[0] >= target) return -1;

    int l = 0;
    int r = arr.length - 1;
    int mid = -1;
    while(l < r) {
        mid = (l + r + 1) / 2;//虽然明白有一个场景需要做向上取整,但是说不清楚其中的原理
        if(arr[mid] > target) {
            r = mid -1;
        }
        else if(arr[mid] < target) {
            l = mid;
        }
        else {//arr[mid] = target
            r = mid - 1;
        }
    }
    //l就是第一个小于target 的元素的下标
    return l;
    

    }

    //如果数组中存在元素等于target,则返回第一个等于target的下标,
    //如果不存在,则返回最后一个小于target的元素的下标
    int floor_lower(int[] arr, int target) {
    //如果都不存在,则返回-1
    if(arr[0] > target) return -1;
    if(arr[0] target) return 0;

    int l = 0;
    int r = arr.length - 1;
    int mid = -1;
    while(l < r) {
        mid = (l + r + 1) / 2;//虽然明白有一个场景需要做向上取整,但是说不清楚其中的原理
        if(arr[mid] > target) {
            r = mid -1;
        }
        else if(arr[mid] < target) {
            l = mid;
        }
        else {//arr[mid] = target
            r = mid - 1;
        }
    }
    if(l + 1 < arr.length && arr[l + 1] == target) {
        return l + 1;//l就是第一个小于target 的元素的下标,如果存在等于target的元素,一定是l+1
    }
    //l就是第一个小于target 的元素的下标
    return l;
    

    }

    //简单记录一下寻找
    //第一个大于target的元素的下标为什么向下取整(除法默认的)
    //最后一个小于target的元素的下标为什么向上取整?mid = (l + r + 1) / 2;

    第一个大于target的元素,第一次使用二分查找时,如果Mid对应的元素正好是最后一个等于target的元素,那么下一个寻找区间是[Mid+1, right]。区间里都是大于target的元素
    即mid+1就是第一个大于target的元素。mid = (l + r) / 2可以取到左边界。
    第一个大于target的元素 这个要求就是 左边界的值

    最后一个小于target的元素的下标,第一次使用二分查找时,如果Mid对应的元素正好是第一个等于target的元素, 那么下一个寻找区间是[left, mid-1],区间里都是小于target的元素
    即mid-1就是第一个大于target的元素。mid = (l + r) / 2永远只能取到左边界的值, 而mid = (l + r + 1) / 2才可以取到右边界。
    最后一个小于target的元素 这个要求就是 右边界的值,所以需要向上取整

    mpweixin用户 普通 2023年9月24日 下午9:48

    本打卡对应问题:【学习建议】关于做本项目的几点学习建议(视频讲解)
    具体打卡内容:

    打卡

    mpweixin用户 普通 2023年9月24日 下午9:46

    本打卡对应问题:【重要】如何把本项目写进简历 + 如何准备面试
    具体打卡内容:

    打卡!

    QQiing 普通 2023年9月24日 上午12:23

    本打卡对应问题:【二叉树专题】剑指 Offer 28. 对称的二叉树
    具体打卡内容:

    class Solution {
    public:
    bool checkSymmetricTree(TreeNode* root) {
    if(root NULL || (root->right NULL && root->left NULL))
    {
    return true;
    }
    return function(root->right, root->left);
    }
    bool function(TreeNode* rootright, TreeNode* rootleft)
    {
    if(rootright
    NULL && rootleft NULL)
    {
    return true;
    }
    if(rootright
    NULL || rootleft NULL)
    {
    return false;
    }
    if(rootright->val != rootleft->val)
    {
    return false;
    }
    return (function(rootright->right, rootleft->left) && function(rootright->left, rootleft->right));
    }

    };
    时间复杂度:O(n),空间复杂度:O(n)。

    QQiing 普通 2023年9月23日 下午11:28

    本打卡对应问题:【二叉树专题】剑指 Offer 27. 二叉树的镜像
    具体打卡内容:

    class Solution {
    public:
    TreeNode* mirrorTree(TreeNode* root) {
    if(root NULL)
    {
    return NULL;
    }
    TreeNode* left = mirrorTree(root->left);
    TreeNode* right = mirrorTree(root->right);
    root->right = left;
    root->left = right;
    return root;
    }
    };
    时间复杂度:O(n),空间复杂度:O(n)

    uu 永久会员 2023年9月23日 下午6:32

    本打卡对应问题:LeetCode20. 有效的括号🌟🌟🌟🌟🌟简单
    具体打卡内容:

    为什么二者调换顺序就是错误的呢?

    if(stack.isEmpty() || s.charAt(i) != stack.pop()) 
    if(s.charAt(i) != stack.pop() || stack.isEmpty()) 
    
    class Solution {
        public boolean isValid(String s) {
            if(s.length() % 2 != 0) {
                return false;
            }
            Stack<Character> stack = new Stack();
    
            for(int i = 0; i < s.length(); i++) {
                if(s.charAt(i) == '[') {
                    stack.push(']');
                }
                else if(s.charAt(i) == '{') {
                    stack.push('}');
                }
                else if(s.charAt(i) == '(') {
                    stack.push(')');
                }
                else {
                    if(stack.isEmpty() || s.charAt(i) != stack.pop()) {
                    // if(s.charAt(i) != stack.pop() || stack.isEmpty()) {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }
    
    uu 永久会员 2023年9月23日 下午6:22

    本打卡对应问题:LeetCode155. 最小栈🌟🌟🌟🌟🌟中等
    具体打卡内容:
    // 【思路】单链表 + 栈
    // 时空复杂度太大了。。。
    // class MinStack {
    //     Stack<Integer> stack;
    //     Node ans;
    //     //内部类
    //     class Node {
    //         int val;
    //         Node next;
    
    //         public Node(int val) {
    //             this.val = val;
    //         }
    //     }
    //     public MinStack() {
    //         this.stack = new Stack();
    //         this.ans = new Node(-1);
    //     }
    
    //     public void push(int val) {
    //         stack.push(val);
    //         Node head = ans;
    //         Node newnode = new Node(val);
    //         if(ans.next == null) {
    //             ans.next = newnode;
    //         } else {
    //             while(ans.next != null) {
    //                 if(ans.next.val < newnode.val) {
    //                     ans = ans.next;
    //                 }
    //                 else {
    //                     break;
    //                 }
    //             }
    //             newnode.next = ans.next;
    //             ans.next = newnode;
    //         }
    //         ans = head;
    //     }
    
    //     public void pop() {
    //         int p = stack.pop();
    //         Node head = ans;
    
    //         while(ans.next.val != p && ans.next != null) {
    //             ans = ans.next;
    //         }
    //         ans.next = ans.next.next;
    //         ans = head;
    //     }
    
    //     public int top() {
    //         return stack.peek();
    //     }
    
    //     public int getMin() {
    //         return ans.next.val;
    //     }
    // }
    
    class MinStack {
        Stack<Integer> stack1;
        Stack<Integer> stack2;
    
        public MinStack() {
            stack1 = new Stack();
            stack2 = new Stack();
        }
    
        public void push(int val) {
            stack1.push(val);
            if(stack2.isEmpty() || stack2.peek() >= val) {
                stack2.push(val);
            }
        }
    
        // == 和equals的区别:
        // == 对于基本数据类型比较的是值,而对于引用类型比较的就是引用的地址,即两个引用是否指向同一个对象实例
        //equals 对于没有重写equals方法的引用类型的比较和==是一样的
        //只是String,包装类等重写了equals方法,所以按重写后的规则进行比较,比较的是对象指向的内容是否相等
    
        //Integer内部有一个静态变量缓存池IntegerCache,里面声明了一个Integer[]数组,范围-128——127
        //Jvm在运行时创建了一 个缓存区域并创建了一个integer的数组。
        //这个数组存储了-128至127的值。
        //stack1.peek() == stack2.peek(),如果数值在-128–127之间。比较的是数值
    
        //intValue()方法,可以拆箱,把包装类型转换成基本数据类型,这个时候比较的就是数值,
    
        public void pop() {
            if(stack1.peek().equals(stack2.peek())){
                stack2.pop();
            }
            // if(stack2.peek().intValue() == stack1.peek().intValue()) {
            //     stack2.pop();
            // }
            stack1.pop();
        }
    
        public int top() {
            return stack1.peek();
        }
    
        public int getMin() {
            return stack2.peek();
        }
    }
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(val);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */
    
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(val);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */
    
    uu 永久会员 2023年9月23日 下午4:04

    本打卡对应问题:LeetCode225. 用队列实现栈🌟🌟🌟🌟🌟简单
    具体打卡内容:
    // 【思路】一个队列
    // 时间复杂度:除了入栈是O(n),其余操作是O(1)
    // 空间复杂度:O(n)
    class MyStack {
        Queue<Integer> queue;
    
        public MyStack() {
            queue = new LinkedList();
        }
    
        public void push(int x) {
            queue.offer(x);
            for(int i = 0; i < queue.size() - 1; i++) {
                queue.offer(queue.poll());
            }
        }
    
        public int pop() {
            return queue.poll();
        }
    
        public int top() {
            return queue.peek();
        }
    
        public boolean empty() {
            return queue.isEmpty();
        }
    }
    
    // 【思路】两个队列
    // 时间复杂度:除了入栈是O(n),其余操作是O(1)
    // 空间复杂度:O(n)
    // class MyStack {
    //     Queue<Integer> queue1;
    //     Queue<Integer> queue2;
    
    //     public MyStack() {
    //         queue1 = new LinkedList();
    //         queue2 = new LinkedList();
    //     }
    
    //     public void push(int x) {
    //         //队列1接受新入栈的元素
    //         queue1.offer(x);
    //         while(!queue2.isEmpty()) {
    //             queue1.offer(queue2.poll());
    //         }
    //         //交换队列,使得队列1始终为空
    //         Queue temp = queue1;
    //         queue1 = queue2;
    //         queue2 = temp;
    //     }
    
    //     public int pop() {
    //         return queue2.poll();
    //     }
    
    //     public int top() {
    //         return queue2.peek();
    //     }
    
    //     public boolean empty() {
    //         return queue2.isEmpty();
    //     }
    // }
    
    /**
     * Your MyStack object will be instantiated and called as such:
     * MyStack obj = new MyStack();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.top();
     * boolean param_4 = obj.empty();
     */
    
    泡芙 永久会员 2023年9月22日 下午5:20

    本打卡对应问题:分发饼干 简单🌟🌟🌟🌟
    具体打卡内容:
    • Time:O(nlogn+mlogm),排序时间复杂度O(nlogn+mlogm),遍历数组时间复杂度O(n+m)
    • Space:O(logn+logm),排序的额外空间开销
    class Solution {
        // 思路1:优先考虑饼干,小饼干先喂饱小胃口(遍历饼干)
        public int findContentChildren(int[] g, int[] s) {
            // 先将饼干和胃口排序(从小到大)
            Arrays.sort(g);
            Arrays.sort(s);
    
            int n = g.length; // 孩子的数量
            int m = s.length; // 饼干的数量
            int res = 0; // 存放结果
    
            // 遍历饼干
            for (int i = 0; i < m; i ++) {
                // 从胃口小的开始喂
                if (res < n && g[res] <= s[i]) {
                    res ++;
                }
            }
            return res;
        }
    }
    
    class Solution {
        // 思路2:优先考虑胃口,先喂饱大胃口(遍历孩子)
        public int findContentChildren(int[] g, int[] s) {
            // 先将饼干和胃口排序(从小到大)
            Arrays.sort(g);
            Arrays.sort(s);
    
            int n = g.length - 1; // 孩子的数量
            int m = s.length - 1; // 饼干的数量
            int res = 0; // 存放结果
    
            // 遍历孩子
            for (int i = n; i >= 0; i --) {
                // 从胃口大的开始喂
                if (m >= 0 && s[m] >= g[i]) {
                    res ++;
                    m --;
                }
            }
            return res;
        }
    }
    
    泡芙 永久会员 2023年9月22日 下午3:08

    本打卡对应问题:对称二叉树 🌟🌟🌟简单
    具体打卡内容:
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root == null || (root.left == null && root.right == null)) {
                return true;
            }
            // 调用递归函数,比较左节点,右节点
            return f(root.left, root.right);
        }
    
        // 判断 A 和 B 是否互为镜像二叉树
        boolean f(TreeNode A, TreeNode B){
            // 两个节点都为null
            if (A == null && B == null) {
                return true;
            }
            // 一个为 null 一个不为 null
            if (A == null || B == null) {
                return false;
            }
            // 两个节点的值不相等
            if (A.val != B.val) {
                return false;
            }
            return f(A.left, B.right) && f(A.right, B.left);
        }
    }
    
    泡芙 永久会员 2023年9月22日 下午2:08

    本打卡对应问题:二叉树的镜像 🌟🌟🌟简单
    具体打卡内容:
    class Solution {
        // 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
        public TreeNode mirrorTree(TreeNode root) {
            if (root == null || (root.left == null && root.right == null)) {
                return root;
            }
    
            // 利用函数定义,先翻转左右子树
            TreeNode left = mirrorTree(root.left);
            TreeNode right = mirrorTree(root.right);
    
            // 然后交换左右子节点
            root.left = right;
            root.right = left;
    
            return root;
        }
    }
    
    泡芙 永久会员 2023年9月22日 上午11:27

    本打卡对应问题:平衡二叉树 🌟🌟🌟🌟🌟简单
    具体打卡内容:

    先序遍历 + 判断深度 (从顶至底)

    • Time:O(n^2),最好情况下(为“满二叉树”),每层执行复杂度× 层数复杂度=O(n × logn)。但最坏情况下(退化成链表),高度为O(n),时间复杂度为O(n^2)
    • Space:最差情况下(当树退化为链表时),递归深度可达到 n
    class Solution {
        public boolean isBalanced(TreeNode root) {
            if (root == null) {
                return true;
            }
    
            // 当前子树、当前子树的左子树、当前子树的右子树 是否是平衡树
            return Math.abs(maxDeaxth(root.left) - maxDeaxth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    
        int maxDeaxth(TreeNode root) {
            if (root == null) {
                return 0;
            }
    
            return 1 + Math.max(maxDeaxth(root.left), maxDeaxth(root.right));
        }
    }
    

    后序遍历 + 剪枝 (从底至顶)

    • Time:O(n),N 为树的节点数量,计算树的深度需要遍历所有节点
    • Space:O(n),最差情况下(当树退化为链表时),递归深度可达到 n
    class Solution {
        public boolean isBalanced(TreeNode root) {
            return maxDeaxth(root) != -1;
        }
    
        int maxDeaxth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = maxDeaxth(root.left);
            int right = maxDeaxth(root.right);
    
            if (left == -1 || right == -1 ||Math.abs(left - right) > 1) {
                return -1;
            }
    
            return 1 + Math.max(left, right);
        }
    }
    
    泡芙 永久会员 2023年9月22日 上午10:07

    本打卡对应问题:二叉树的最大深度 🌟🌟🌟🌟🌟简单
    具体打卡内容:
    • Time:O(n),N 为树的节点数量,计算树的深度需要遍历所有节点
    • Space:O(n),最差情况下(当树退化为链表时),递归深度可达到 n
    class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            // 此树深度=左子树的深度与右子树的深度中的最大值+1
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    }
    
    LilyBoy 永久会员 2023年9月21日 下午9:43

    本打卡对应问题:【索引专题】索引分类相关
    具体打卡内容:

    1、介绍一下索引的分类,以及他们的主要区别是什么?
    按数据结构:哈希索引、有序数组、全文索引、B+树索引
    按存储特性:聚簇索引(主键索引)、二级索引(辅助索引)
    按字段:普通索引、唯一索引、主键索引、前缀索引
    按个数:单个索引、联合索引

    2、介绍一下什么是复合索引?什么样的情况下我们会使用复合索引?
    把多个单个的字段组合起来形成一个索引,(a,b,c)的形式就是联合索引;
    联合索引会遵循“最左匹配原则”,
    一般需要查询多个列时需要创建联合索引,可以在普通索引的基础上创建联合索引,也就是使用覆盖索引进行优化,可以省去普通索引在查询过程中出现的回表查询插座,

    3、唯一索引了解吗?在使用的时候,有什么需要注意的不?
    不允许为Null,unique关键字进行修饰,不允许出现重复值,

    4、我们有时候会听到索引下推,你知道什么是索引下推吗?那覆盖索引又是什么意思呢?
    现在我们知道,对于联合索引(a, b),在执行 select * from table where a > 1 and b = 2 语句的时候,只有 a 字段能用到索引,那在联合索引的 B+Tree 找到第一个满足条件的主键值(ID 为 2)后,还需要判断其他条件是否满足(看 b 是否等于 2),那是在联合索引里判断?还是回主键索引去判断呢?

    在 MySQL 5.6 之前,只能从 ID2 (主键值)开始一个个回表,到「主键索引」上找出数据行,再对比 b 字段值。

    而 MySQL 5.6 引入的索引下推优化(index condition pushdown), 可以在联合索引遍历过程中,对联合索引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。

    当你的查询语句的执行计划里,出现了 Extra 为 Using index condition,那么说明使用了索引下推的优化

    阿尚 普通 2023年9月21日 下午6:52

    本打卡对应问题:二叉树最大宽度 🌟🌟🌟中等
    具体打卡内容:
    //关键:若根节点序号为1,则左节点的序号为父节点序号的两倍,右节点的序号为父节点序号的两倍+1
    class Solution {
        public int widthOfBinaryTree(TreeNode root) {
            if(root == null) return 0;
    
            LinkedList<TreeNode> nodeQueue = new LinkedList<>();//节点队列
            LinkedList<Integer> valQueue = new LinkedList<>();//节点序号队列
    
            int res = 0;
    
            nodeQueue.offer(root);
            valQueue.offer(1);
    
            while(!nodeQueue.isEmpty()){
                int layerSize = nodeQueue.size();
                int temp = valQueue.peekLast() - valQueue.peekFirst() + 1;
                res = Math.max(res, temp);
    
                for(int i = 0; i < layerSize; i++){
                    TreeNode node = nodeQueue.pollFirst();
                    int val = valQueue.pollFirst();
    
                    if(node.left != null){
                        nodeQueue.offer(node.left);
                        valQueue.offer(val * 2);
                    }
                    if(node.right != null){
                        nodeQueue.offer(node.right);
                        valQueue.offer(val * 2 + 1);
                    }
                }
            }
    
            return res;
        }
    }
    
    uu 永久会员 2023年9月21日 下午6:19

    本打卡对应问题:LeetCode138. 复制带随机指针的链表🌟🌟中等
    具体打卡内容:
    /*
    // Definition for a Node.
    class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    */
    
    // 浅拷贝只复制指向某个对象的指针,而不复制对象本身,新旧对象还是共享同一块内存。
    // 但深拷贝会另外创造一个一模一样的对象,新对象跟原对象不共享内存,修改新对象不会改到原对象。
    // 时间复杂度:O(n)
    // 空间复杂度:O(n)
    class Solution {
        public Node copyRandomList(Node head) {
            if(head == null) return null;
            //复制在同一条链上
            Node headsub = head;
            Node headpre = head;
            while(headsub != null) {
                headsub = headsub.next;
                Node temp = new Node(headpre.val);
                temp.next = headsub;;
                headpre.next = temp;
                headpre = headsub;
            }
            headpre = head;
            while(headpre != null) {
                headsub = headpre.next;
                headsub.random = headpre.random == null ? null :headpre.random.next;
                headpre = headsub.next;
            }
            //拆分
            headpre = head;
            headsub = head.next;
    
            Node newHead = headsub;
            while(headpre != null) {
                headpre.next = headsub.next;
                headpre = headpre.next;
                headsub.next = headpre == null ? null : headpre.next;
                headsub = headsub.next;
            }
            return newHead;
        }
    }
    
    uu 永久会员 2023年9月21日 下午5:25

    本打卡对应问题:LeetCode382. 链表随机节点🌟🌟🌟中等
    具体打卡内容:

    看到题目结果返回的是数组,就想用数组求解,可是时空复杂度均不理想。

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        ArrayList val = new ArrayList();
    
        public Solution(ListNode head) {
            ListNode cnt = head;
            int i = 0;
            while(cnt != null) {
                val.add(i, cnt.val);
                i++;
                cnt = cnt.next;
            }
        }
    
        public int getRandom() {
            Random r = new Random();
            int m = r.nextInt(val.size());
            int ans = Integer.parseInt(String.valueOf(val.get(m)));
            return ans;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(head);
     * int param_1 = obj.getRandom();
     */
    
    uu 永久会员 2023年9月21日 下午4:47

    本打卡对应问题:LeetCode148. 排序链表🌟🌟中等
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    
    // 【思路】二路归并 + 有序列表排序
    // 时间复杂度:O(n log n)
    // 空间复杂度:O(n)
    class Solution {
        public ListNode sortList(ListNode head) {
            //函数目的
    
            //结束条件
            if(head == null || head.next == null) {
                return head;
            }
    
            //关系式
            ListNode left = head;
            ListNode temp = findMiddle(head);
            ListNode right = temp.next;
            temp.next = null;
    
            ListNode lHead = sortList(left);
            ListNode rHead = sortList(right);
    
            return mergeOrdered(lHead, rHead);
    
        }
    
        ListNode findMiddle(ListNode head) { //若是偶数则返回前一个
            if(head == null) return head;
            ListNode slow = head;
            ListNode fast = head.next;
            while(fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    
        ListNode mergeOrdered(ListNode head1, ListNode head2) { //合并两个有序链表
            ListNode ans = new ListNode(-1);
            ListNode temp = ans;
    
            while(head1 != null && head2 != null) {
                if(head1.val < head2.val) {
                    temp.next = head1;
                    head1 = head1.next;
                }
                else {
                    temp.next = head2;
                    head2 = head2.next;
                }
                temp = temp.next;
            }
    
            temp.next = head1 == null ? head2 : head1;
            return ans.next;
        }
    }
    
    // 时间复杂度:O(n^2) > O(n log n)
    // 空间复杂度:O(n)
    // class Solution {
    //     public ListNode sortList(ListNode head) {
    //         ListNode newhead = new ListNode(-1);
    //         ListNode ans = newhead;
    
    //         while(head.next != null) {
    //             ListNode head0 = head;
    //             ListNode smaller = head;
    //             ListNode pre = head;
    //             while(head0.next != null) {
    //                 if(smaller.val > head0.next.val) {
    //                     smaller = head0.next;
    //                     pre = head0;
    //                 }
    //                 head0 = head0.next;
    //             }
    //             if(smaller != pre) {
    //                 pre.next = smaller.next;
    //                 smaller.next = null;
    //                 newhead.next = smaller;
    //             }
    //             else {
    //                 head = head.next;
    //                 newhead.next = smaller;
    //             }
    //             newhead = newhead.next;
    //         }
    //         newhead.next = head;
    //         return ans.next;
    //      }
    // }
    
    uu 永久会员 2023年9月21日 下午3:19

    本打卡对应问题:LeetCode61. 旋转链表🌟🌟🌟中等
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    
    // 时间复杂度:O(2n)
    // 空间复杂度:O(1)
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            ListNode tail = head;
            int count = 1, diff = 0;
            if(head == null || k == 0) return head;
            while(tail.next != null) {
                count++;
                tail = tail.next;
            }
            // 找到新头节点的位置
            if(k <= count){
                diff = Math.abs(count - k);
            } else {
                diff = count - k % count;
            }
            // 连成环
            tail.next = head;
            for(int i = 0; i < diff; i++) {
                tail = tail.next;
            }
            // 找到新头节点,然后破环
            head = tail.next;
            tail.next = null;
            return head;
        }
    }
    
    uu 永久会员 2023年9月21日 下午2:44

    本打卡对应问题:LeetCode21. 合并两个有序链表🌟🌟🌟简单
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    
    // 时间复杂度:O(n)
    // 空间复杂度:O(1)
    class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode head = new ListNode(-1);
            ListNode ans = head;
    
            while(list1 != null) {
                if(list2 == null) {
                    head.next = list1;
                    break;
                }
                head.next = list1.val < list2.val ? list1 : list2;
                if(head.next == list1) {
                    list1 = list1.next;
                } else if(head.next == list2) {
                    list2 = list2.next;
                }
                head = head.next;
            }
            if(list2 != null) {
                head.next = list2;
            }
            return ans.next;
        }
    }
    
    泡芙 永久会员 2023年9月21日 下午2:30

    本打卡对应问题:【作业11】二叉树层序遍历(变形版)
    具体打卡内容:
    class Solution {
        public List<List<Integer>> decorateRecord(TreeNode root) {
            if (root == null) {
                return new ArrayList<>();
            }
    
            Queue<TreeNode> queue = new LinkedList<>();
            List<List<Integer>> res = new LinkedList<>();
    
            int sum = 1;
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                LinkedList<Integer> level = new LinkedList<>();
                for (int i = 0; i < size; i ++) {
                    TreeNode temp = queue.poll();
                    // 奇数行从左到右打印
                    if (sum % 2 == 1) {
                        level.add(temp.val);
                    } else {
                        // 偶数行从右到左打印
                        level.addFirst(temp.val);
                    }
    
                    if (temp.left != null) {
                        queue.offer(temp.left);
                    }
                    if (temp.right != null) {
                        queue.offer(temp.right);
                    }
                }
                res.add(level);
                sum ++;
            }
            return res;
        }
    }
    
    LilyBoy 永久会员 2023年9月21日 下午12:06

    本打卡对应问题:【索引专题】索引优化相关
    具体打卡内容:

    1、字段加索引,你是否在自己的项目中用过呢?你觉得什么样的字段适合加索引?(PS:从索引区分度,查找频率真,增删频繁角度考虑)
    账户申请表、改期表、操作表
    研发人员开通账号:状态字段,频繁查询需要进行加索引;

    索引区分度大

    频繁查询
    不为null
    用于条件查询

    曾删该不适合创建索引
    联合索引
    避免创建冗余索引

    2、mysql怎么创建索引?(PS:说实话,有些人踢踢而谈,但是还真的不知道怎么给字段加索引)
    create index 索引名 on 表(列名)
    create unique index 索引名 on 表(列名)
    drop index 索引

    3、那你觉得,字段加了索引,查找的时候一定会走索引吗?(PS:可以回答索引失效的几个经典因素)
    like ‘%**’
    or前后列没有加索引
    函数计算
    发生隐式转换

    4、刚才你的索引失效的例子,都是因为人为没有写好 sql 导致的,那如果排除人为的情况,sql 正确书写,那就一定会走索引吗?(PS:走不走索引,是经过优化器权衡预测的,所以这里需要回答系统是如何预测的)
    不一定:
    优化器、基数(索引区分度)、采样统计、比较全表扫描、扫喵行数、出现预测错误

    5、如果我想要强制走某个索引,能实现吗?可以怎么做?
    可以,force index

    6、如何一条 sql 执行的很慢,我们可以怎么来排查原因?
    偶尔慢:写入内存redolog日志刷盘、等待锁释放
    一直慢:没有加索引、索引失效、选错了索引

    7、刚才说到了模糊匹配失效,为什么使用模糊匹配会失效,你能给我解释一下底层原理吗?

    CrazyJavaBoy 永久会员 2023年9月21日 上午10:38

    本打卡对应问题:LeetCode209. 长度最小的子数组🌟🌟🌟🌟中等
    具体打卡内容:
    class Solution {
        //滑动窗口
        public int minSubArrayLen(int target, int[] nums) {
            if(nums == null || nums.length < 1) {
                return 0;
            }
            int sum = 0;
            int l = 0;
            int r = 0;
            int min = nums.length + 1;
            while(r < nums.length) {
                sum += nums[r];
                while(sum >= target) {
                    min = Math.min(min, r - l + 1);
                    sum -= nums[l];
                    l++;
                }
                r++;
            }
            return min == nums.length + 1 ? 0 : min;
        }
    }
    
    CrazyJavaBoy 永久会员 2023年9月21日 上午9:58

    本打卡对应问题:LeetCode27.移除元素🌟🌟🌟🌟🌟简单
    具体打卡内容:
    class Solution {
        // 快慢指针
        public int removeElement(int[] nums, int val) {
            if(nums == null || nums.length < 1) {
                return 0;
            }
            int fast = 0;
            int slow = 0;
            while(fast < nums.length) {
                if(nums[fast] != val) {
                   nums[slow++] = nums[fast]; 
                }
                fast++;
            }
            return slow;
        }
    }
    
    uu 永久会员 2023年9月20日 下午4:55

    本打卡对应问题:Leectode142. 环形链表 II🌟🌟🌟🌟中等
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    
    // 【思路】快慢指针
    // 时间复杂度:O(4n)->O(n)
    // 空间复杂度:O(1)
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if(head == null || head.next == null) {
                return null;
            }
            ListNode slow = head;
            ListNode fast = head;
            int pre = 0;
            int sub = 0;
    
    
            while(fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                pre += 2;
                sub += 1;
                if(fast == slow) {
                    break;
                }
            }
            if(fast == null || fast.next == null) {
                return null;
            }
    
            int circle = pre - sub;
    
            fast = head;
            slow = head;
            for(int i =0; i < circle; i++) {
                fast = fast.next;
            }
            while(fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    
    // 【思路】哈希表
    // 时间复杂度:O(n)
    // 空间复杂度:O(n)
    // public class Solution {
    //     public ListNode detectCycle(ListNode head) {
    //         Set visited = new HashSet();
    //         ListNode ans = head;
    //         while(ans != null) {
    //             if(visited.contains(ans)) {
    //                 return ans;
    //             }
    //             else {
    //                 visited.add(ans);
    //             }
    //             ans = ans.next;
    //         }
    //         return null;
    //     }
    // }
    
    uu 永久会员 2023年9月20日 下午4:03

    本打卡对应问题:LeetCode141. 环形链表🌟🌟🌟🌟🌟简单
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    
     // 【思路】用快慢指针,想到了追及问题,最多快的跑多一圈
     // 时间复杂度:O(2n)->O(n)
     // 空间复杂度:O(1)
    public class Solution {
        public boolean hasCycle(ListNode head) {
            if(head == null || head.next == null) {
                return false;
            }
            ListNode slow = head;
            ListNode fast = head;
    
    
            while(fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow) {
                    return true;
                }
            }
            return false;
        }
    }
    
    uu 永久会员 2023年9月20日 下午3:34

    本打卡对应问题:LeetCode25. K 个一组翻转链表🌟🌟🌟困难
    具体打卡内容:

    思路和视频一样,但是reverseKGroup的递归关系式写地很乱写不出来

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    
    // 时间复杂度:O( n ~ n^2)
    // 空间复杂度:O(1)
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            //函数目的:递归k位反转
    
            //终止条件
            ListNode temp = head;
            for(int i = 1; i < k; i++) {
                if(temp != null) {
                    temp = temp.next;
                } else {
                    return head;
                }
            }
            if(temp == null) return head;
            ListNode r = temp.next;
            temp.next = null;
    
            //关系式
            ListNode newHead = reverseList(head);
            ListNode newTemp = reverseKGroup(r, k); 
    
            head.next = newTemp; //反转使得首位排末尾
            return newHead;       
        }
    
        ListNode reverseList(ListNode head) {
            //函数目的:反转链表
    
            //终止条件
            if(head == null || head.next == null) {
                return head;
            }
    
            //关系式
            ListNode newHead = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
    
        }
    }
    
    泡芙 永久会员 2023年9月20日 下午3:16

    本打卡对应问题:LeetCode239. 滑动窗口最大值🌟🌟🌟🌟困难
    具体打卡内容:

    由于队列是单调递减的,所以每次窗口变动时,只需要判断队首的值是否还在窗口中就行了。
    队列中存放数组下标的值:因为要判断队首的值是否在窗口范围内,由数组下标取值很方便,而由值取数组下标不是很方便。

    双端队列中存下标值,队首的值是目标值

    • Time:O(n),线性遍历占用O(n),每个元素最多仅入队和出队一次,因此单调队列deque占用O(2n)
    • Space:O(k),双端队列deque最多同时存储k个元素(窗口大小)
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            // 双端队列:保存当前窗口最大值的数组位置,保证队列中数组位置的数值从大到小排序
            Deque<Integer> deque = new LinkedList<>();
            // 结果列表res的窗口个数(n - k + 1)
            int res[] = new int[nums.length - k + 1];
            int index = 0;
    
            for (int i = 0; i < nums.length; i ++) {
                // 将deque内所有<=nums[i]的元素删除
                while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                    deque.pollLast();
                }
    
                // 添加当前值对应的数组下标
                deque.add(i);
    
                // 判断当前队列中队首的值是否有效
                if (i - deque.peek() >= k) {
                    deque.poll();
                }
                // 当前窗口长度为k时,保存队列最底部的值(最大值)
                if (i + 1 >= k) {
                    res[index++] = nums[deque.peek()];
                }
            }
            return res;
        }
    }
    
    谁仁 普通 2023年9月20日 上午10:25

    本打卡对应问题:【二叉树专题】多次被考察真题:剑指 Offer 32 – III. 从上到下打印二叉树
    具体打卡内容:

    void printBinaryTree(TreeNode* root, int layer) {
    if (root nullptr) {
    return;
    }
    if (layer
    1) {
    cout << root->val << ” “;
    } else if (layer % 2 1) {
    printBinaryTree(root->right, layer – 1);
    cout << root->val << ” “;
    } else {
    printBinaryTree(root->left, layer – 1);
    cout << root->val << ” “;
    }
    }//时间复杂度是 O(n),空间复杂度是 O(n)

    谁仁 普通 2023年9月20日 上午10:16

    本打卡对应问题:【二叉树专题】剑指 Offer 32 – II. 从上到下打印二叉树
    具体打卡内容:

    // 后序遍历二叉搜索树
    void postorderTraversal(TreeNode* root) {
    if (root NULL) {
    return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf(“%d “, root->val);
    }//时间负载O(n),空间复杂度O(n)

    uu 永久会员 2023年9月20日 上午10:02

    本打卡对应问题:LeetCode92. 反转链表 II🌟🌟🌟中等
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    
    // 【思路】递归处理
    // 时间复杂度:O(n)
    // 空间复杂度:O(n)
    // class Solution {
    //     ListNode res = null;
    
    //     public ListNode reverseBetween(ListNode head, int left, int right) {
    //         //函数目的:反转left-right
    
    //         //结束条件
    //         if(left == 1) {
    //             return reverseList(head, right);
    //         }
    //         //关系式
    //         else {
    //             head.next = reverseBetween(head.next, left - 1, right - 1);
    //             return head;
    //         }
    
    //     }
    
    //     ListNode reverseList(ListNode head, int n) {
    //         //函数目的:反转1-n位
    
    //         //结束条件
    //         if(n == 1) {
    //             res = head.next;
    //             return head;
    //         }
    //         //关系式
    //         ListNode newHead = reverseList(head.next, --n);
    //         head.next.next = head;
    //         head.next = res;
    //         return newHead;
    //     }
    // }
    
    //【思路】头插法-穿针引线
    // 时间复杂度:O(n)
    // 空间复杂度:O(1)
    class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
            int diff = right - left;
            ListNode pre = dummyNode;
    
            if(diff < 1) {
                return head;
            }
    
            //找到pre
            while(left > 1) {
                pre = pre.next;
                left--;
            }
            //找到suc
            ListNode suc = pre.next;
    
            while(diff > 0) {
                ListNode nxt = suc.next;
                suc.next = nxt.next;
                nxt.next = pre.next;
                pre.next = nxt;
                diff--;
            }
            return dummyNode.next;
        }
    }
    
    
    uu 永久会员 2023年9月20日 上午8:03

    本打卡对应问题:LeetCode206. 反转链表🌟🌟🌟🌟🌟简单
    具体打卡内容:
    // 【思路】递归
    // 时间复杂度:O(n)
    // 空间复杂度:O(n)
    class Solution {
        public ListNode reverseList(ListNode head) {
            //函数目的:反转栈
    
            //结束条件
            if(head == null || head.next == null) {
                return head;
            }
            //关系式
            ListNode newHead = reverseList(head.next);
    
            // 不能用newHead,因为newHead要作为表头返回!!!
            // newHead.next = head;
            // head.next = null;
            // newHead = head;
            // return newHead; 
    
            head.next.next = head;
            head.next = null;
            return newHead;
        }
    }
    
    CrazyJavaBoy 永久会员 2023年9月19日 下午11:55

    本打卡对应问题:Java基础突击八股文
    具体打卡内容:

    finally后面的语句分几种情况
    异常被捕获:finally代码正常执行并且finally后面正常的代码还是可以继续执行
    异常未被捕获:finally代码正常执行,并将异常向上一层调用方抛出,但是finally后面正常的代码不再执行

    String类为啥要设计成不可变的?补充:在String类中有个成员变量hash表示该串的哈希值,在第一次调用hashCode方法时字符串的哈希值被计算并赋值给hash,之后调用hashCode方法便可以直接取hash字段返回。

    泡芙 永久会员 2023年9月19日 下午11:53

    本打卡对应问题:LeetCode347. 前 K 个高频元素🌟🌟🌟🌟中等
    具体打卡内容:

    优先队列

    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            // 设置一个map集合,key存放数字,value存放出现次数
            Map<Integer, Integer> map = new HashMap<>();
            // 统计出现次数
            for (int num : nums) {
                // get的时候有可能key不存在,赋默认值0
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
    
            // 建立一个小根堆,用来存放key值,堆内元素按照key对应的value值从大到小排序
            PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
                public int compare(Integer a, Integer b) {
                    return map.get(a) - map.get(b);
                }
            });
    
            // 将map中的数字,插入到小根堆中
            for (Integer key : map.keySet()) {
                if (queue.size() < k) {
                    queue.offer(key);
                } else if (map.get(key) > map.get(queue.peek())) {
                    queue.poll();
                    queue.offer(key);
                }
            }
    
            // 将小根堆中的k个数字放到数组中
            int res[] = new int[k];
            int index = 0;
            while (!queue.isEmpty()) {
                res[index++] = queue.poll();
            }
            return res;
        }
    }
    

    法二:

    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            // 设置一个map集合,key存放数字,value存放出现次数
            Map<Integer, Integer> map = new HashMap<>();
            // 统计出现次数
            for (int num : nums) {
                // get的时候有可能key不存在,赋默认值0
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
    
            PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> {
                return e2.getValue().compareTo(e1.getValue());
            });
    
            // PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
    
            // 将map中的数字,插入到小根堆中
            queue.addAll(map.entrySet());
    
            // 将小根堆中的k个数字放到数组中
            int res[] = new int[k];
            int index = 0;
            while (index < k && !queue.isEmpty()) {
                res[index++] = queue.poll().getKey();
            }
            return res;
        }
    }
    

    定义优先队列的排序规则

    // 定义优先队列的排序规则1
    PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
        public int compare(Integer a, Integer b) {
            return map.get(a) - map.get(b);
        }
    });
    
    // 定义优先队列的排序规则2
    PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> {
        return e2.getValue().compareTo(e1.getValue());
    });
    
    // 定义优先队列的排序规则3
    PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());
    
    uu 永久会员 2023年9月19日 下午11:01

    本打卡对应问题:LeetCode206. 反转链表🌟🌟🌟🌟🌟简单
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    
    // 时间复杂度:O(n)
    // 空间复杂度:O(1)
    class Solution {
        public ListNode reverseList(ListNode head) {
    
            ListNode ans = new ListNode(0, null);
            if(head == null) return null;
            while(head.next != null) {
                ListNode temp = new ListNode(0, null);
                ans.val = head.val;
                head = head.next;
                temp.next = ans;
                ans = temp;
    
            }
            ans.val = head.val;
            return ans;
    
        }
    }
    
    uu 永久会员 2023年9月19日 下午7:34

    本打卡对应问题:LeetCode160. 相交链表🌟🌟🌟🌟🌟简单
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    
    // 以下两种时空复杂度一样
    // 时间复杂度:O(n)
    // 空间复杂度:O(1)
    
    // 【思路】消去差值
    // public class Solution {
    //     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int lena = 0, lenb = 0;
            ListNode a = headA;
            ListNode b = headB;
            while(a != null) {
                lena++;
                a = a.next;
            }
            while(b != null) {
                lenb++;
                b = b.next;
            }
            int diff = Math.abs(lena - lenb);
            Boolean flag = lena > lenb ? true : false;
            a = headA;
            b = headB;
            while(a != null && b != null) {
                if(flag && diff > 0) {
                    a = a.next;
                    diff--;
                    continue;
                }else if(diff > 0) {
                    b = b.next;
                    diff--;
                    continue;
                }
                if(a == b) {
                    return  a;
                }
                else {
                    a = a.next;
                    b = b.next;
                }
            }
            return null;
        }
    }
    
    // 【代码优化】
    // public class Solution {
    //     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //         if(headA == null || headB == null) {
    //             return null;
    //         }
    //         ListNode a = headA, b = headB;
    //         while(a != b) {
    //             a = a == null ? headB : a.next;
    //             b = b == null ? headA : b.next;
    //         }
    //         return a;
    //     }
    // }
    
    uu 永久会员 2023年9月19日 下午5:17

    本打卡对应问题:剑指 Offer 06. 从尾到头打印链表🌟🌟🌟🌟🌟简单
    具体打卡内容:
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    
    // 【思路】用栈,后进先出
    class Solution {
        public int[] reversePrint(ListNode head) {
            Stack<Integer> s = new Stack<Integer>();
            int i = 0;
            while(head != null) {
                s.push(head.val);
                head = head.next;
                i++;
            } 
            int[] ans = new int[i];
            for(int j = 0; j < i; j++) {
                ans[j] = s.pop();
            }
            return ans;
        }
    }
    
    uu 永久会员 2023年9月19日 下午5:04

    本打卡对应问题:LeetCode19. 删除链表的倒数第 N 个结点🌟🌟🌟🌟🌟中等
    具体打卡内容:

    /**
    * Definition for singly-linked list.
    * public class ListNode {
    * int val;
    * ListNode next;
    * ListNode() {}
    * ListNode(int val) { this.val = val; }
    * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    * }
    */

    // 【思路】单指针
    // class Solution {
    // public ListNode removeNthFromEnd(ListNode head, int n) {
    // ListNode cnt = head;
    // int count = 2;
    // if(cnt.next null) return null;
    // while(cnt.next.next != null) {
    // count++;
    // cnt = cnt.next;
    // }
    // if(n
    1) {
    // cnt.next = null;
    // return head;
    // }
    // int i = count – n;
    // if(i 0) {
    // return head = head.next;
    // }
    // cnt = head;
    // while(i > 1) {
    // cnt = cnt.next;
    // i–;
    // }
    // cnt.next = cnt.next.next;
    // return head;
    // }
    // }

    // 【思路】双指针
    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode pre = head;
    ListNode sub = head;
    if(sub.next null) return null;
    while(sub.next != null) {
    sub = sub.next;
    n–;
    if(n > -1) {
    continue;
    }
    pre = pre.next;
    }
    if(pre
    head && n 1) {
    return head.next;
    }
    pre.next = pre.next.next;
    return head;
    }
    }