樊轶群的个人网站

// 1779. Find Nearest Point That Has the Same X or Y Coordinate
class Solution {
    public int nearestValidPoint(int x, int y, int[][] points) {
        int minManhattanDistance = Integer.MAX_VALUE;
        int ans = -1;
        for (int i = 0; i < points.length; ++i) {
            if (points[i][0] == x || points[i][1] == y) {
                int manhattanDistance = Math.abs(points[i][0] - x) + Math.abs(points[i][1] - y);
                if (manhattanDistance < minManhattanDistance) {
                    minManhattanDistance = manhattanDistance;
                    ans = i;
                }
            }
        }
        return ans;
    }
}

学习笔记：
本月的第一题，必然是简单题。
这道题是枚举算法把所有坐标点都计算出来求曼哈顿距离。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

// 0895. Maximum Frequency Stack
class FreqStack {
    Map<Integer, Integer> cnt;
    Map<Integer, ArrayList<Integer>> stack;
    int maxFrequency;

    public FreqStack() {
        cnt = new HashMap<>();
        stack = new HashMap<>();
        maxFrequency = 0;
    }

    public void push(int val) {
        int valCnt = cnt.getOrDefault(val, 0) + 1;
        cnt.put(val, valCnt);
        if (valCnt > maxFrequency) {
            maxFrequency = valCnt;
            stack.put(maxFrequency, new ArrayList<>());
        }
        stack.get(valCnt).add(val);
    }

    public int pop() {
        int top = stack.get(maxFrequency).remove(stack.get(maxFrequency).size() - 1);
        cnt.put(top, cnt.get(top) - 1);
        if (stack.get(maxFrequency).size() == 0) {
            --maxFrequency;
        }
        return top;
    }
}

学习笔记：
这是一道久违的设计的题目。
要设计一个特殊的栈，所以当然不能只用栈了，还用到了hashmap和arraylist。

// 1758. Minimum Changes To Make Alternating Binary String
class Solution {
    public int minOperations(String s) {
        int startFromZero = 0;
        int startFromOne = 0;
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        for (int i = 0; i < len; ++i) {
            if ((i & 1) == 0) {
                if (charArray[i] == '0') {
                    ++startFromOne;
                } else {
                    ++startFromZero;
                }
            } else {
                if (charArray[i] == '0') {
                    ++startFromZero;
                } else {
                    ++startFromOne;
                }
            }
        }
        return Math.min(startFromZero, startFromOne);
    }
}

学习笔记：
这是一道简单题，计数的题目。
就是分两种情况，0开始或者1开始然后统计一下就可以了。

// 0813. Largest Sum of Averages
class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int len = nums.length;
        double[] prefixSum = new double[len + 1];
        for (int i = 0; i < len; ++i) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        double[][] largestSums = new double[len + 1][k + 1];
        for (int i = 1; i <= len; ++i) {
            largestSums[i][1] = prefixSum[i] / i;
        }
        for (int j = 2; j <= k; ++j) {
            for (int i = j; i <= len; ++i) {
                for (int mid = j - 1; mid < i; ++mid) {
                    largestSums[i][j] = Math.max(largestSums[i][j], (prefixSum[i] - prefixSum[mid]) / (i - mid) + largestSums[mid][j - 1]);
                }
            }
        }
        return largestSums[len][k];
    }
}

学习笔记：
这虽然是一道中等题，但其实很苦难。
其实每一个数字分开，那是比较简单的，但是很难分得开，因为k是比较小的。
用的了动态规划和前缀和，主要是状态转移方程式特别难写难想。

// 1752. Check if Array Is Sorted and Rotated
class Solution {
    public boolean check(int[] nums) {
        int len = nums.length;
        int minNum = Integer.MAX_VALUE;
        int minNumIndex = -1;
        for (int i = 0; i < len; ++i) {
            if (nums[i] < minNum) {
                minNum = nums[i];
                minNumIndex = i;
            }
        }
        if (minNumIndex == 0) {
            for (int i = len - 1; i > 0; --i) {
                if (nums[i] == minNum) {
                    minNumIndex = i;
                } else {
                    break;
                }
            }
        }
        for (int i = 1; i < len; ++i) {
            if (nums[(minNumIndex + i) % len] < nums[(minNumIndex + i - 1) % len]) {
                return false;
            }
        }
        return true;
    }
}

学习笔记：
这是一道简单题，数组的基础应用加模运算。
就是拼成一个环，要循环回来，就利用到了模。

import java.util.HashMap;
import java.util.PriorityQueue;

// 0882. Reachable Nodes In Subdivided Graph
class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        HashMap<Integer, HashMap<Integer, Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            graph.put(i, new HashMap<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).put(edge[1], edge[2]);
            graph.get(edge[1]).put(edge[0], edge[2]);
        }
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> (b.remainingMoves - a.remainingMoves));
        pq.add(new Node(0, maxMoves));
        int ans = 0;
        boolean[] visited = new boolean[n];
        while (!pq.isEmpty()) {
            Node currNode = pq.poll();
            if (visited[currNode.nodeId]) {
                continue;
            } else {
                visited[currNode.nodeId] = true;
            }
            ans += 1;
            for (int adjNodeId : graph.get(currNode.nodeId).keySet()) {
                int middleNodeCount = graph.get(currNode.nodeId).get(adjNodeId);
                if (!visited[adjNodeId] && currNode.remainingMoves >= (middleNodeCount + 1)) {
                    pq.add(new Node(adjNodeId, currNode.remainingMoves - (middleNodeCount + 1)));
                }
                int reachedMiddleNodeCount = Math.min(currNode.remainingMoves, middleNodeCount);
                ans += reachedMiddleNodeCount;
                graph.get(currNode.nodeId).put(adjNodeId, middleNodeCount - reachedMiddleNodeCount);
                graph.get(adjNodeId).put(currNode.nodeId, middleNodeCount - reachedMiddleNodeCount);
            }
        }
        return ans;
    }
}

class Node {
    int nodeId;
    int remainingMoves;

    public Node(int nodeId, int remainingMoves) {
        this.nodeId = nodeId;
        this.remainingMoves = remainingMoves;
    }
}

学习笔记：
这是一道困难题，用的是图相关的算法，迪杰斯特拉算法。
我们要把中间结点经过的数量也给梳理出来，考虑到只会经过一边，那另一边最多也就经过剩下那些中间节点了，就减一下就可以了。
为了实现迪杰斯特拉算法，这里采用了优先队列来存储等待开始遍历的结点。

import java.util.ArrayList;

// 0809. Expressive Words
class Solution {
    public int expressiveWords(String s, String[] words) {
        ArrayList<CharAndQuantity> charAndQuantities = new ArrayList<>();
        char[] sArray = s.toCharArray();
        int len = sArray.length;
        charAndQuantities.add(new CharAndQuantity(sArray[0], 1));
        for (int i = 1; i < len; ++i) {
            if (sArray[i] != sArray[i - 1]) {
                charAndQuantities.add(new CharAndQuantity(sArray[i], 1));
            } else {
                ++charAndQuantities.get(charAndQuantities.size() - 1).q;
            }
        }
        int ans = 0;
        for (String word : words) {
            ans += isStretchy(word, charAndQuantities);
        }
        return ans;
    }

    private int isStretchy(String word, ArrayList<CharAndQuantity> charAndQuantities) {
        char[] charArray = word.toCharArray();
        int len = charArray.length;
        char currentChar;
        int currentQuantity;
        int j = 0;
        for (int i = 0; i < len; ) {
            currentChar = charArray[i];
            currentQuantity = 0;
            while (i < len && charArray[i] == currentChar) {
                ++currentQuantity;
                ++i;
            }
            if (j < charAndQuantities.size()) {
                CharAndQuantity charAndQuantity = charAndQuantities.get(j);
                if (charAndQuantity.c == currentChar && (charAndQuantity.q > 2 || charAndQuantity.q == currentQuantity) && charAndQuantity.q >= currentQuantity) {
                    ++j;
                } else {
                    return 0;
                }
            } else {
                return 0;
            }
        }
        if (j == charAndQuantities.size()) return 1;
        return 0;
    }
}

class CharAndQuantity {
    char c;
    int q;

    public CharAndQuantity(char c, int q) {
        this.c = c;
        this.q = q;
    }
}

学习笔记：
这是一道字符串数组的题目。
我们需要使用自顶向下的编程思路，原始思路是使用双指针来遍历两个字符串。
但是字符串s其实是不变的，所以可以提前用辅助的对象数组统计好字符和出现次数来加速。
要考虑的条件比较多，字符得对上，数量可以刚好，也可以三个以上，但又不能比原先的还多。
用了辅助数组还需要考虑数组的越界（不过双指针也是需要另外一个字符串的越界的）。
还要考虑word走完，s还没有走完的情况。

// 0795. Number of Subarrays with Bounded Maximum
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int ans = 0;
        int lastBigger = -1;
        int lastIn = -1;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > right) {
                lastBigger = i;
                lastIn = -1;
            } else if (nums[i] >= left) {
                lastIn = i;
            }
            if (lastIn != -1) {
                ans += lastIn - lastBigger;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道非常巧妙的数组题目。
我们要把数字分成三类，比范围大的，在范围内的，比范围小的。也可以理解为210三种。
然后记录上一次出现比范围大的数字的索引，还有上一次出现范围内的数字的索引。
这样只从左往右遍历一次就可以算出结果。
每一个位子往左看，能符合条件的其实就是上一次出现范围内的（包括自己先在位子）减去上一次出现大于范围的。
20101
那2就不用加，
到0也没得加，
到1可以加2，
到0还是可以加2，
到1可以加4。

import java.util.HashMap;

// 1742. Maximum Number of Balls in a Box
class Solution {
    public int countBalls(int lowLimit, int highLimit) {
        HashMap<Integer, Integer> numberQuantity = new HashMap<>();
        for (int i = lowLimit; i <= highLimit; ++i) {
            int j = i;
            int number = 0;
            while (j != 0) {
                number += j % 10;
                j /= 10;
            }
            numberQuantity.put(number, numberQuantity.getOrDefault(number, 0) + 1);
        }
        int ans = 0;
        for (Integer value : numberQuantity.values()) {
            if (value > ans) {
                ans = value;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道简单题，哈希表的题目。
简单计算各位之和，放入桶里面就行了。

// 0878. Nth Magical Number
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        int c = lcm(a, b);
        long left = Math.min(a, b);
        long right = left * n;
        while (left < right) {
            long mid = left + (right - left) / 2;
            long count = mid / a + mid / b - mid / c;
            if (count == n) {
                right = mid;
            } else if (count > n) {
                right = mid;
            } else if (count < n){
                left = mid + 1;
            }
        }
        return (int) (left % (1e9 + 7));
    }

    private int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

学习笔记：
这道题目是一道不容易的题目，很考验基本功。
先用一波数学分析，这样就可以快速求出某个数字是第n个了。
先手是求最大公约数，然后最小公倍数，接下来就是二分查找。
这是向左边界进行搜索的二分查找。