樊轶群的个人网站

// 0658. Find K Closest Elements
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = 0;
        int right = arr.length - 1;
        int middle = 0;
        while (left + 1 < right) {
            middle = (left + right) / 2;
            if (arr[middle] == x) {
                left = middle;
                right = middle;
                break;
            } else if (arr[middle] > x) {
                right = middle;
            } else {
                left = middle;
            }
        }
        if (left != right) {
            if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                middle = right;
            } else {
                middle = left;
            }
        }
        List<Integer> ans = new ArrayList<>();
        ans.add(arr[middle]);
        left = middle - 1;
        right = middle + 1;
        while (ans.size() < k) {
            if (left < 0) {
                ans.add(arr[right]);
                ++right;
            } else if (right >= arr.length) {
                ans.add((arr[left]));
                --left;
            } else if (Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
                ans.add(arr[right]);
                ++right;
            } else {
                ans.add((arr[left]));
                --left;
            }
        }
        ans.sort((Integer i1, Integer i2) -> (i1 - i2));
        return ans;
    }
}

学习笔记：
这道题是二分法的题目。
我先用二分法找到了最接近的元素，然后再往两头扩展一个个加进去。
没想到速度那么慢，用了11ms，比很多人都慢。
但我看快的方法也都差不多，只不过是指针往两边跑，最后把元素加入ans里面。

// 1460. Make Two Arrays Equal by Reversing Sub-arrays
class Solution {
    public boolean canBeEqual(int[] target, int[] arr) {
        int[] quantityTarget = new int[1001];
        int[] quantityArr = new int[1001];
        for (int t : target) ++quantityTarget[t];
        for (int a : arr) ++quantityArr[a];
        for (int i = 0; i < 1001; ++i) {
            if (quantityTarget[i] != quantityArr[i]) {
                return false;
            }
        }
        return true;
    }
}

学习笔记：
这道题其实就是一个计数问题，可以用桶，可以用哈希表。
为什么元素一样，就可以排成一样的呢，我们可以想一下冒泡排序，就是不断交换两个相邻元素，达成某一种顺序，那么既然可以无限次翻转，那么只要元素一致一定存在方法翻过去。

// 0782. Transform to Chessboard
class Solution {
    public int movesToChessboard(int[][] board) {
        int length = board.length;
        int[] rawRow = new int[length];
        int[] antiRow = new int[length];
        int zeroInFirstRow = 0;
        int oneInFirstRow = 0;
        for (int i = 0; i < length; ++i) {
            rawRow[i] = board[0][i];
            antiRow[i] = 1 - rawRow[i];
            if (rawRow[i] == 0) ++zeroInFirstRow;
            else ++oneInFirstRow;
        }
        if (length % 2 == 0 && zeroInFirstRow != oneInFirstRow) return -1;
        if (length % 2 == 1 && Math.abs(zeroInFirstRow - oneInFirstRow) != 1) return -1;
        for (int i = 1; i < length; ++i) {
            if (board[i][0] == rawRow[0]) {
                for (int j = 0; j < length; ++j) {
                    if (board[i][j] != rawRow[j]) return -1;
                }
            } else {
                for (int j = 0; j < length; ++j) {
                    if (board[i][j] != antiRow[j]) return -1;
                }
            }
        }
        int[] rawColumn = new int[length];
        int[] antiColumn = new int[length];
        int zeroInFirstColumn = 0;
        int oneInFirstColumn = 0;
        for (int i = 0; i < length; ++i) {
            rawColumn[i] = board[i][0];
            antiColumn[i] = 1 - rawColumn[i];
            if (rawColumn[i] == 0) ++zeroInFirstColumn;
            else ++oneInFirstColumn;
        }
        if (length % 2 == 0 && zeroInFirstColumn != oneInFirstColumn) return -1;
        if (length % 2 == 1 && Math.abs(zeroInFirstColumn - oneInFirstColumn) != 1) return -1;
        for (int i = 1; i < length; ++i) {
            if (board[0][i] == rawColumn[0]) {
                for (int j = 0; j < length; ++j) {
                    if (board[j][i] != rawColumn[j]) return -1;
                }
            } else {
                for (int j = 0; j < length; ++j) {
                    if (board[j][i] != antiColumn[j]) return -1;
                }
            }
        }
        if (length % 2 == 1) {
            int ans = 0;
            int firstCell;
            if (zeroInFirstRow - oneInFirstRow == 1) firstCell = 0;
            else firstCell = 1;
            for (int i = 0; i < length; i += 2) {
                if (rawRow[i] != firstCell) ++ans;
            }
            if (zeroInFirstColumn - oneInFirstColumn == 1) firstCell = 0;
            else firstCell = 1;
            for (int i = 0; i < length; i += 2) {
                if (rawColumn[i] != firstCell) ++ans;
            }
            return ans;
        }
        int ans0Stage1 = 0;
        int ans1Stage1 = 0;
        int ans0Stage2 = 0;
        int ans1Stage2 = 0;
        int firstCell = 0;
        for (int i = 0; i < length; i += 2) {
            if (rawRow[i] != firstCell) ++ans0Stage1;
            else ++ans1Stage1;
        }
        for (int i = 0; i < length; i += 2) {
            if (rawColumn[i] != firstCell) ++ans0Stage2;
            else ++ans1Stage2;
        }
        return Math.min(ans0Stage1, ans1Stage1) + Math.min(ans0Stage2, ans1Stage2);
    }
}

学习笔记：
这是一道超级困难的题目，虽然说是矩阵，但其实还可以用上什么位运算和数学。
提交了很多遍也没有对，一开始看懂了如何去判定合法性，然后在计算步数上一直栽跟头。
因为左上角的那个值并不一定就本该在左上角。
还需要根据横第一个行和竖第一列分为1阶段和2阶段，各自取最小求和。

// 0655. Print Binary Tree
class Solution {
    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> values = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean hasNextLevel = true;
        int bigBlank = 0;
        while (hasNextLevel) {
            bigBlank = bigBlank * 2 + 1;
            hasNextLevel = false;
            int queueSize = queue.size();
            List<String> rowOfValues = new ArrayList<>();
            for (int i = 0; i < queueSize; ++i) {
                TreeNode front = queue.poll();
                if (front == null) {
                    rowOfValues.add("");
                    queue.offer(null);
                    queue.offer(null);
                } else {
                    rowOfValues.add(String.valueOf(front.val));
                    queue.offer(front.left);
                    queue.offer(front.right);
                    if (front.left != null || front.right != null) hasNextLevel = true;
                }
            }
            values.add(rowOfValues);
        }
        int smallBlank = (bigBlank - 1) / 2;
        List<List<String>> ans = new ArrayList<>();
        for (int i = 0; i < values.size(); ++i) {
            List<String> rowOfValues = values.get(i);
            List<String> rowOfAns = new ArrayList<>();
            for (int j = 0; j < smallBlank; ++j) rowOfAns.add("");
            for (int j = 0; j < rowOfValues.size() - 1; ++j) {
                rowOfAns.add(rowOfValues.get(j));
                for (int k = 0; k < bigBlank; ++k) rowOfAns.add("");
            }
            rowOfAns.add(rowOfValues.get(rowOfValues.size() - 1));
            for (int j = 0; j < smallBlank; ++j) rowOfAns.add("");
            bigBlank = smallBlank;
            smallBlank = (smallBlank - 1) / 2;
            ans.add(rowOfAns);
        }
        return ans;
    }
}

学习笔记：
这是一道很繁琐的二叉树的题目。
先要找到规律，每个节点每一层的间隙是多大，发现间隙分为大间隙和小间隙还有推导公式后，开始用宽度优先遍历来写。
第一遍遍历无法完成，因为不知道二叉树深度到底有多大，只能将节点数值先存一下，第二次遍历再把空格填进去。

// 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence
class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] words = sentence.split(" ");
        int ans = 1;
        for (String word : words) {
            int i = 0;
            int j = 0;
            while (i < word.length() && j < searchWord.length() && word.charAt(i) == searchWord.charAt(j)) {
                ++i;
                ++j;
                if (j == searchWord.length()) return ans;
            }
            ++ans;
        }
        return -1;
    }
}

学习笔记：
今天又是一道字符串的水题。

// 0654. Maximum Binary Tree
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length - 1);
    }

    private TreeNode construct(int[] nums, int left, int right) {
        if (left > right) return null;
        if (left == right) return new TreeNode(nums[left]);
        int maxValue = -1;
        int mid = 0;
        for (int i = left; i <= right; ++i) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                mid = i;
            }
        }
        TreeNode node = new TreeNode(maxValue);
        node.left = construct(nums, left, mid - 1);
        node.right = construct(nums, mid + 1, right);
        return node;
    }
}

学习笔记：
这是一道二叉树、模拟算法、递归调用、分治的题目。
一开始没有读懂题目，就想着要做成一个二叉堆，后来发现左右方向要和原数组一致，才反应过来为什么题目没有说解不是唯一的任何解都可以。
读清楚题目之后，就变得简单了，就是找最大，然后二分。

// 1450. Number of Students Doing Homework at a Given Time
class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int ans = 0;
        for (int i = 0; i < startTime.length; ++i) {
            if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
                ++ans;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道超级大水题，就一个for循环里面有个if就没了，三分钟写完。

// 1224. Maximum Equal Frequency
class Solution {
    public int maxEqualFreq(int[] nums) {
        HashMap<Integer, Integer> numberFrequencyMap = new HashMap<>();
        HashMap<Integer, Integer> frequencyFrequencyMap = new HashMap<>();
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            int frequency = numberFrequencyMap.getOrDefault(nums[i], 0) + 1;
            numberFrequencyMap.put(nums[i], frequency);
            if (frequency > 1) {
                if (frequencyFrequencyMap.get(frequency - 1) == 1) {
                    frequencyFrequencyMap.remove(frequency - 1);
                } else {
                    frequencyFrequencyMap.put(frequency - 1, frequencyFrequencyMap.get(frequency - 1) - 1);
                }
            }
            frequencyFrequencyMap.put(frequency, frequencyFrequencyMap.getOrDefault(frequency, 0) + 1);
            if (possible(frequencyFrequencyMap)) ans = i + 1;
        }
        return ans;
    }

    private boolean possible(HashMap<Integer, Integer> ffm) {
        if (ffm.size() > 2) {
            return false;
        } else if (ffm.size() == 2) {
            Iterator<Map.Entry<Integer, Integer>> iterator = ffm.entrySet().iterator();
            Map.Entry<Integer, Integer> e1 = iterator.next();
            Map.Entry<Integer, Integer> e2 = iterator.next();
            if (e1.getKey() - e2.getKey() == 1 && e1.getValue() == 1) return true;
            if (e2.getKey() - e1.getKey() == 1 && e2.getValue() == 1) return true;
            if (e1.getKey() == 1 && e1.getValue() == 1) return true;
            if (e2.getKey() == 1 && e2.getValue() == 1) return true;
            return false;
        } else {
            Iterator<Map.Entry<Integer, Integer>> iterator = ffm.entrySet().iterator();
            Map.Entry<Integer, Integer> e1 = iterator.next();
            return e1.getKey() == 1 || e1.getValue() == 1;
        }
    }
}

学习笔记：
这道题是一道HashMap的题，情况特别多特别难。
由于情况非常复杂，我们应该自顶向下编程，先写好主函数，然后再把最关键的判定函数写出来。
主函数用了两次HashMap的getOrDefault函数，让代码显得优雅和精简。

当频率大于两种时，肯定不符合。

当频率达到两种时，会有两个情况符合：
11111222233334444，多一个的频率只有1次。
1222233334444，频率为1的只有1次。

当频率只有一种时，会有两个情况符合：
11111111111111，这个频率只出现了1次。
12345678，频率为1。

这里为了拿到HashMap的唯一Entry或唯二Entry属实麻烦，用上了迭代器iterator。

// 1302. Deepest Leaves Sum
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int ans = 0;
        int queueSize = 1;
        while (!queue.isEmpty()) {
            ans = 0;
            queueSize = queue.size();
            for (int i = 0; i < queueSize; ++i) {
                TreeNode node = queue.poll();
                ans += node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return ans;
    }
}

学习笔记：
今天的题目是二叉树的中等题。
虽然是中等，但是题目表述很清晰，我10分钟就写完跑通了。
和day0002那道有些像，就是宽度优先搜索一下，然后每一层记录一下总和，一旦发现空了就把当前层返回。

// 1656. Design an Ordered Stream
class OrderedStream {

    private final String[] stream;
    private int ptr;

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

    public List<String> insert(int idKey, String value) {
        stream[idKey] = value;
        List<String> ret = new ArrayList<>();
        while (stream[ptr] != null) {
            ret.add(stream[ptr]);
            ++ptr;
        }
        return ret;
    }
}

学习笔记：
这是一道数组的简单题，没啥特别的内容，为了降低判断次数，最好的方式就是数组再多开一位，这样就不用担心越界的问题，不需要每次都和n进行比较了。