樊轶群的个人网站

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        Queue<TreeNode> upperFloor = new LinkedList<>();
        int layer = 0;
        upperFloor.add(root);
        while (++layer < depth - 1) {
            int queueSize = upperFloor.size();
            for (int i = 0; i < queueSize; ++i) {
                TreeNode peek = upperFloor.poll();
                if (peek.left != null) {
                    upperFloor.add(peek.left);
                }
                if (peek.right != null) {
                    upperFloor.add(peek.right);
                }
            }
        }
        for (TreeNode node : upperFloor) {
                node.left = new TreeNode(val, node.left, null);
                node.right = new TreeNode(val, null, node.right);
        }
        return root;
    }
}

学习笔记：
这是一道二叉树的题目，也是可以使用深度优先搜索和宽度优先搜索。
深度优先搜索写得代码会特别巧妙，解题的方法自己递归调用自己。
宽度优先搜索也比较符合直觉，把要插入的楼上一层找出来后插入一层。

// 1403. Minimum Subsequence in Non-Increasing Order
class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        int[] buckets = new int[101];
        int sum = 0;
        for (int num : nums) {
            ++buckets[num];
            sum += num;
        }
        int target = sum / 2 + 1;
        sum = 0;
        int i = 100;
        List<Integer> ans = new ArrayList<>();
        while (sum < target) {
            if (buckets[i] != 0) {
                --buckets[i];
                ans.add(i);
                sum += i;
            } else {
                --i;
            }
        }
        return ans;
    }
}

学习笔记：
这道题比去年七夕节的情侣牵手要无聊太多了。
这是一道排序算法和贪心算法的题目。
不过我也探索了很多，Collections.sort()其实会调用Arrays.sort()。Arrays.sort()会根据不同情况选择三种排序，如果是基本类型，则会选择快速排序DualPrivotQuicksort.sort()，如果是引用类型使用的是蒂姆排序TimSort.sort()，除非用户请求的是使用LegacyMergeSort才会用祖传的归并排序Arrays.legacyMergeSort()。Tim排序发明人是Tim Peters，也是Python之禅的作者。有机会一定要研究研究。
这道题用上面这些都不是最佳，都是3ms，而如果用了桶排序，就可以到1ms打败100%的用户。

// 0899. Orderly Queue
class Solution {
    public String orderlyQueue(String s, int k) {
        if (k == 1) {
            String ans = s;
            StringBuilder sb = new StringBuilder(s);
            int loop = s.length();
            while (--loop > 0) {
                sb.append(sb.charAt(0)).deleteCharAt(0);
                if (sb.toString().compareTo(ans) < 0) {
                    ans = sb.toString();
                }
            }
            return ans;
        } else {
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            s = String.valueOf(charArray);
            return s;
        }
    }
}

学习笔记：
StringBuilder有deleteCharAt操作起来非常快，可惜StringBuilder没有compare函数，所以每次对比要转成String去和ans比较，不然只要ans是StringBuilder，最后把ans转String返回就好了。
String转char数组一开始我翻了一个错误，一开始用了getBytes但实际上返回的是byte类型的数组而不是char类型的，排序一样但要转回来麻烦。
char数组转回来的时候我脑子又抽了，用了toString，结果忘记这个不是转去String而是为了打印用的函数。
最后用了valueOf函数，但其实有copyValueOf也可以，而且一模一样，查了资料说是对char数组来说完全一致，只是为了早期的代码不需要再去做无谓的修改就一直保留着这两个函数。

// 0622. Design Circular Queue
class MyCircularQueue {

    private final int[] nums;
    private int size;
    private final int capacity;
    private int front;
    private int rear;

    public MyCircularQueue(int k) {
        nums = new int[k];
        size = 0;
        capacity = k;
        front = 0;
        rear = 0;
    }

    public boolean enQueue(int value) {
        if (size == capacity) return false;
        nums[rear] = value;
        ++size;
        rear = (rear + 1) % capacity;
        return true;
    }

    public boolean deQueue() {
        if (size == 0) return false;
        --size;
        front = (front + 1) % capacity;
        return true;
    }

    public int Front() {
        if (size == 0) return -1;
        return nums[front];
    }

    public int Rear() {
        if (size == 0) return -1;
        return nums[(rear + capacity - 1) % capacity];
    }

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

    public boolean isFull() {
        return size == capacity;
    }
}

学习笔记：
这里可以使用数组来实现一个循环队列。
数组大小确定后就不动了，所以可以使用final，然后capacity也确定了也是final。
本来思考的是不用size变量，两个指针都是0开始，但后来发现满和空都是重叠无法判断。
所以做法其实可以数组多开一个位置，这样满就不重叠了。

// 1374. Generate a String With Characters That Have Odd Counts
class Solution {
    public String generateTheString(int n) {
        char[] ans = new char[n];
        Arrays.fill(ans, 'b');
        ans[0] = "ab".charAt(n & 1);
        return new String(ans);
    }
}

学习笔记：
这是一道特别简单的字符串题目。
如果n是奇数，就产生n个b。如果是偶数，就将第一位修改成a。
思路就是这样，但如何不通过if语句来玩呢，这里就用了切割一段字符串了，substring可以用，但就一个字符的话用charat最好。接下来判断奇偶用%2是可以，但位运算的&1明显更高级也更快速。

// 1161. Maximum Level Sum of a Binary Tree
class Solution {
    public int maxLevelSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 1;
        int ans = 0;
        int levelSum;
        int maxLevelSum = Integer.MIN_VALUE;
        int levelSize;
        while (!q.isEmpty()) {
            levelSum = 0;
            levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                TreeNode peek = q.poll();
                levelSum += peek.val;
                if (peek.left != null) {
                    q.offer(peek.left);
                }
                if (peek.right != null) {
                    q.offer(peek.right);
                }
            }
            if (levelSum > maxLevelSum) {
                maxLevelSum = levelSum;
                ans = level;
            }
            ++level;
        }
        return ans;
    }
}

学习笔记：
这是一道二叉树相关的题目，使用深度优先搜索和宽度优先搜索都可以做。
不过既然是统计每一层内的总值找出最大的层号，用宽度优先搜索来做会更加自然一些。宽度优先搜索会使用到队列，Java中的队列的函数有6个，功能是加入队尾、看一眼队首、移除队首3种，但在遇到队列空了或者满了的特殊情况的应对不同。

// 0952. Largest Component Size by Common Factor
class Solution {
    public int largestComponentSize(int[] nums) {
        int maxValue = 0;
        for (int num : nums) {
            if (num > maxValue) {
                maxValue = num;
            }
        }
        UnionFind unionFind = new UnionFind(maxValue + 1);
        for (int num : nums) {
            for (int i = 2; i * i <= num; ++i) {
                if (num % i == 0) {
                    unionFind.union(num, i);
                    unionFind.union(num, num / i);
                }
            }
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            int parentOfNum = unionFind.find(num);
//            if (hashMap.get(parentOfNum) == null) {
//                hashMap.put(parentOfNum, 1);
//            } else {
//                hashMap.put(parentOfNum, hashMap.get(parentOfNum) + 1);
//            }
            hashMap.merge(parentOfNum, 1, Integer::sum);
        }
        int ans = 1;
        for (Integer componentSize : hashMap.values()) {
            if (componentSize > ans) {
                ans = componentSize;
            }
        }
        return ans;
    }
}

class UnionFind {
    private final ArrayList<Integer> parent = new ArrayList<>();

    public UnionFind(int n) {
        for (int i = 0; i < n; ++i) {
            parent.add(i);
        }
    }

    public int find(int son) {
        if (parent.get(son) == son) {
            return son;
        }
        parent.set(son, find(parent.get(son)));
        return parent.get(son);
    }

    public void union(int a, int b) {
        int parentOfA = find(a);
        int parentOfB = find(b);
        if (parentOfA != parentOfB) {
            parent.set(parentOfA, parentOfB);
        }
    }
}

学习笔记：
这是一道并查集的题目，也考查了对于求因数的基本功。
1.
并查集中难写的是find函数，其中递归调用那段最容易卡住。
先从parent中找到目前son的老大，然后对这个老大再递归调用寻找老大的老大，最终找到后将最大的老大设置到parent中索引为son的位置上。在递归的过程中，中间节点的小老大也会被一起指向最大的老大。
2.
这里用了hashmap来存储每一个给的数字最终老大的小弟数量。
如果一开始没有在hashmap里就认为原本是0，设定为1。
否则就将原本的数字加上1。
这一段我写的比较朴素，使用了if-else语句。但有存在两种高级写法。
merge函数是一种，这个会比较难以理解，还用到了lambda表达式。
getOrDefault函数时另一种，这个函数特别好理解，有就get没有就按default来。