2022-0830

• 第一题：
• 第二题 topk问题
• 第三题 树的遍历和插入

[toc]

第一题：#

1394. 找出数组中的幸运数 - 力扣（LeetCode）

哈希表？数组？没啥意思

class Solution {
    public int findLucky(int[] arr) {
        int[] counts = new int[501];
        for(int a : arr) {
            counts[a]++;
        }
        for (int i = 500;i>=1;i--) {
            if (counts[i] == i) {
                return i;
            }
        }
        return -1;
    }
}

---

第二题 topk问题#

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）

topk问题别急着用sort，太简单

升级方法是堆（优先队列）， 要求最小的几个，那其实就要搞个大顶堆

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Queue<Integer> pqueue = new PriorityQueue<>((a,b)->(b-a));
        if (k == 0) {
            return new int[]{};
        }
        for (int i = 0; i < arr.length;i++) {
            if (i < k) {
                pqueue.offer(arr[i]);
                continue;
            }
            if (pqueue.peek() > arr[i]) {
                pqueue.poll();
                pqueue.offer(arr[i]);
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k;i++) {
            res[i] = pqueue.poll();
        }
        return res;
    }
}

再升级的话用快排思想，每次划分后，挑可能有k的那一边继续划分，具体比较难理解就不管了，先放个答案在这，后面自己有空重写下

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        randomizedSelected(arr, 0, arr.length - 1, k);
        int[] vec = new int[k];
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }

    private void randomizedSelected(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = randomizedPartition(arr, l, r);
        int num = pos - l + 1;
        if (k == num) {
            return;
        } else if (k < num) {
            randomizedSelected(arr, l, pos - 1, k);
        } else {
            randomizedSelected(arr, pos + 1, r, k - num);
        }
    }

    // 基于随机的划分
    private int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l;
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

第三题 树的遍历和插入#

最大二叉树 II - 提交记录 - 力扣（LeetCode）

sb题目，看不懂题意， 其实就是把要插入的值优先右边放，直到某个点比自己小，那就可以取代这个点的位置，把这个点当成自己的左节点即可 ，题意写的乱七八糟的

/**
 * 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 TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (val > root.val) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        dfs(root, val, null, true);
        return root;
    }

    boolean dfs(TreeNode node, int val, TreeNode parent, boolean isLeft) {
        if (node == null || node.val < val) {
            TreeNode newNode = new TreeNode(val);
            if (isLeft) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
            newNode.left = node;
            return true;
        }

        if(dfs(node.right, val, node, false)  ) {
            return true;
        }
        return false;
    }
}