from 2022-08-15 to 2022-08-21

leetcode 623: 在二叉树中增加一行

class Solution {
        public TreeNode addOneRow(TreeNode root, int val, int depth) {
            if(depth == 1) {
                TreeNode newRoot = new TreeNode(val);
                newRoot.left = root;
                return newRoot;
            } else {
                recursion(root, val, depth - 1);
                return root;
            }
        }

        public void recursion(TreeNode root, int val, int depth) {
            if(root == null) {
                return;
            }
            if(depth == 1) {
                TreeNode newLeft = new TreeNode(val);
                newLeft.left = root.left;
                root.left = newLeft;
                TreeNode newRight = new TreeNode(val);
                newRight.right = root.right;
                root.right = newRight;
            } else {
                recursion(root.left, val, depth - 1);
                recursion(root.right, val, depth - 1);
            }
        }

    }

leetcode 641：设计循环双端队列

    public class MyCircularDeque {

        private List<Integer> values;

        private int last = 0;

        private int capacity = 0;

        public MyCircularDeque(int k) {
            values = new LinkedList<>();
            capacity = k;
        }

        public boolean insertFront(int value) {
            if(last >= capacity) {
                return false;
            }
            values.add(0, value);
            last++;
            return true;
        }

        public boolean insertLast(int value) {
            if(last >= capacity) {
                return false;
            }
            values.add(last, value);
            last++;
            return true;
        }

        public boolean deleteFront() {
            if(last <= 0) {
                return false;
            }
            values.remove(0);
            last--;
            return true;
        }

        public boolean deleteLast() {
            if(last <= 0) {
                return false;
            }
            values.remove(last - 1);
            last--;
            return true;

        }

        public int getFront() {
            if(last <= 0) {
                return -1;
            }
            return values.get(0);
        }

        public int getRear() {
            if(last <= 0) {
                return -1;
            }
            return values.get(last - 1);
        }

        public boolean isEmpty() {
            return last == 0;
        }

        public boolean isFull() {
            return last >= capacity;
        }
    }

leetcode 1656：设计有序流

class OrderedStream {
        private String[] values;
        private int ptr = 1;

        public OrderedStream(int n) {
            values = new String[n + 1];
        }

        public List<String> insert(int idKey, String value) {
            values[idKey] = value;
            List<String> res = new ArrayList<>();
            for (int i = ptr; i < values.length; i++) {
                if (values[i] == null) {
                    ptr = i;
                    return res;
                } else {
                    res.add(values[i]);
                }
            }
            return res;
        }
    }

leetcode 1032: 层数最深叶子节点的和

class Solution {
        public int deepestLeavesSum(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int levelSum = 0;
            Deque<TreeNode> level = new ArrayDeque<>();
            level.offer(root);
            while (!level.isEmpty()) {
                int levelSize = level.size();
                levelSum = 0;
                for(int i = 0; i < levelSize; i++) {
                    TreeNode node = level.poll();
                    levelSum += node.val;
                    if (node.left != null) {
                        level.offer(node.left);
                    }
                    if(node.right != null) {
                        level.offer(node.right);
                    }
                }
                
            }
            return levelSum;
        }
    }

leetcode 1224. 最大相等频率

class Solution {
        int[] cnt = new int[100010], sum = new int[100010];
        public int maxEqualFreq(int[] nums) {
            Arrays.fill(cnt, 0); Arrays.fill(sum, 0);
            int n = nums.length, max = 0, ans = 0;
            for (int i = 0; i < n; i++) {
                int t = nums[i], cur = ++cnt[t], len = i + 1;
                sum[cur]++; sum[cur - 1]--;
                max = Math.max(max, cur);
                if (max == 1) ans = len;
                if (max * sum[max] + 1 == len) ans = len;
                if ((max - 1) * (sum[max - 1] + 1) + 1 == len) ans = len;
            }
            return ans;
        }
}

leetcode 1450: 在既定时间做作业的学生人数

class Solution {

        public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
            int res = 0;
            for(int i = 0; i < startTime.length; i++) {
                if(queryTime >= startTime[i] && queryTime < endTime[i]) {
                    res++;
                }
            }
            return res;
        }
    }

leetcode 654: 最大二叉树

class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            return helper(nums, 0, nums.length - 1);
        }

        private TreeNode helper(int[] nums, int left, int right) {
            if(left < right) {
                return null;
            }
            int max = Integer.MIN_VALUE;
            int maxIndex = left;
            for(int i = left; i <= right; i++) {
                if(nums[i] > max) {
                    max = nums[i];
                    maxIndex = i;
                }
            }
            TreeNode root = new TreeNode(max);
            root.left = helper(nums, left, maxIndex - 1);
            root.right = helper(nums, maxIndex + 1, right);
            return root;
        }


    }