樊轶群的个人网站

// 1753. Maximum Score From Removing Stones
class Solution {
    public int maximumScore(int a, int b, int c) {
        return Math.min((a + b + c) / 2, a + b + c - Math.max(Math.max(a, b), c));
    }
}

学习笔记：
这是一道贪心、数学的题目。
就分两个情况，一种是可以刚好用完的，一种用不完的。
用不完的话就是要看哪个最大，那最大的那个就是导致用不完的罪魁祸首。

// 1760. Minimum Limit of Balls in a Bag
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int l = 1;
        int r = 1;
        for (int num : nums) r = Math.max(r, num);
        while (l < r) {
            int mid = (l + r) / 2;
            int operations = 0;
            for (int num : nums) {
                operations += (num - 1) / mid;
            }
            if (operations > maxOperations) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return r;
    }
}

学习笔记：
今天这是一道特别经典的二分查找的题目。
用到的是查找左边界的二分查找。

// 1971. Find if Path Exists in Graph
class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges) {
            uf.union(edge[0], edge[1]);
        }
        return uf.find(source) == uf.find(destination);
    }
}

class UnionFind {
    int[] parents;

    public UnionFind(int n) {
        parents = new int[n];
        for (int i = 0; i < n; ++i) {
            parents[i] = i;
        }
    }

    int find(int son) {
        if (parents[son] == son) {
            return son;
        }
        parents[son] = find(parents[son]);
        return parents[son];
    }

    void union(int a, int b) {
        int parentOfA = find(a);
        int parentOfB = find(b);
        if (parentOfA != parentOfB) {
            parents[parentOfA] = parentOfB;
        }
    }
}

学习笔记：
这是一道简单题，入门的图题。
宽搜深搜都能用，但我前几天并查集生疏了，今天就当练习默写并查集了。
今天我把最后一句parents[parentOfA] = parentOfB;写成了parents[a] = parentOfB;闹了个大乌龙，答错了。

import java.util.ArrayList;

// 1703. Minimum Adjacent Swaps for K Consecutive Ones
class Solution {
    public int minMoves(int[] nums, int k) {
        ArrayList<Integer> ones = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == 1) {
                ones.add(i);
            }
        }
        int sum = 0;
        int mid = k / 2;
        for (int i = 0; i < k; ++i) {
            sum += Math.abs(ones.get(i) - ones.get(mid));
        }
        int ans = sum;
        for (int i = 0; k + i < ones.size(); ++i) {
            mid = k / 2 + i;
            sum -= Math.abs(ones.get(mid) - ones.get(i));
            sum += Math.abs(ones.get(k + i) - ones.get(mid + 1));
            sum += (ones.get(mid + 1) - ones.get(mid)) * (k / 2);
            sum -= (ones.get(mid + 1) - ones.get(mid)) * (k - 1 - k / 2);
            ans = Math.min(ans, sum);
        }
        int offset = 0;
        for (int i = 1; i < k; ++i) {
            offset += (i - 1) / 2 + 1;
        }
        return ans - offset;
    }
}

学习笔记：
这是一道超级困难的题目，要O(n)的复杂度才可以过。
而且做的时候没有一点思绪，能想到的也都是暴力的解法。
上了YouTube看到了Huifeng Guan的解法后才理解。
但是当中还需要分析奇偶情况分开解，着实让人想吐。

// 1764. Form Array by Concatenating Subarrays of Another Array
class Solution {
    public boolean canChoose(int[][] groups, int[] nums) {
        int i = 0;
        int j = 0;
        while (i < groups.length && j < nums.length) {
            while (j < nums.length && groups[i][0] != nums[j]) {
                ++j;
            }
            if (isSame(groups[i], nums, j)) {
                j += groups[i].length;
                ++i;
            } else {
                ++j;
            }
        }
        return groups.length == i;
    }

    private boolean isSame(int[] group, int[] nums, int start) {
        if (nums.length - start < group.length) {
            return false;
        }
        for (int i = 1; i < group.length; ++i) {
            if (group[i] != nums[start + i]) {
                return false;
            }
        }
        return true;
    }
}

学习笔记：
和昨天一样是贪心算法的题目，同样也是中等难度。
同时也是二维数组的题目。
不过今天这题的代码明显要复杂，道理简单好理解，但是实现起来要考虑各种细节怎么运算。

// 1785. Minimum Elements to Add to Form a Given Sum
class Solution {
    public int minElements(int[] nums, int limit, int goal) {
        long sum = 0L;
        for (int num : nums) {
            sum += num;
        }
        long diff = Math.abs(sum - goal);
        if (diff == 0) {
            return 0;
        }
        return (int) ((diff - 1) / limit + 1);
    }
}

学习笔记：
这是一道贪心算法的题目，写是中等，但是代码挺简单的。
不过有一个陷阱，就是向上取整的时候先减除完再加，但如果是0的话就会出问题。

// 1945. Sum of Digits of String After Convert
class Solution {
    public int getLucky(String s, int k) {
        char[] charArray = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char c : charArray) {
            sb.append((c - 96));
        }
        char[] chars = sb.toString().toCharArray();
        int sum = 0;
        while (k != 0) {
            --k;
            sum = 0;
            for (char c : chars) {
                sum += c - 48;
            }
            if (sum < 10) return sum;
            chars = String.valueOf(sum).toCharArray();
        }
        return sum;
    }
}

学习笔记：
今天又是一道简单题，感觉不是特别简单。
需要用到创冲循环并且类型要转来转去的。

import java.util.Arrays;

// 1697. Checking Existence of Edge Length Limited Paths
class Solution {
    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        int edgeQuantity = edgeList.length;
        int queryQuantity = queries.length;
        Arrays.sort(edgeList, (int[] edge1, int[] edge2) -> (edge1[2] - edge2[2]));
        int[][] queryList = new int[queryQuantity][4];
        for (int i = 0; i < queryQuantity; ++i) {
            queryList[i][0] = queries[i][0];
            queryList[i][1] = queries[i][1];
            queryList[i][2] = queries[i][2];
            queryList[i][3] = i;
        }
        Arrays.sort(queryList, (int[] query1, int[] query2) -> (query1[2] - query2[2]));
        UnionFind uf = new UnionFind(n);
        int currentIndex = 0;
        boolean[] ans = new boolean[queryQuantity];
        for (int i = 0; i < queryQuantity; ++i) {
            int target = queryList[i][2];
            while (currentIndex < edgeQuantity && edgeList[currentIndex][2] < target) {
                uf.union(edgeList[currentIndex][0], edgeList[currentIndex][1]);
                ++currentIndex;
            }
            if (uf.find(queryList[i][0]) == uf.find(queryList[i][1])) {
                ans[queryList[i][3]] = true;
            }
        }
        return ans;
    }
}

class UnionFind {
    int[] parents;

    public UnionFind(int n) {
        parents = new int[n];
        for (int i = 0; i < n; ++i) {
            parents[i] = i;
        }
    }

    public int find(int son) {
        if (parents[son] == son) {
            return son;
        }
        parents[son] = find(parents[son]);
        return parents[son];
    }

    public void union(int a, int b) {
        int parentOfA = find(a);
        int parentOfB = find(b);
        if (parentOfA != parentOfB) {
            parents[parentOfA] = parentOfB;
        }
    }
}

学习笔记：
这是一道并查集的题目，而且优先方案就是并查集。
可惜我太久没有做并查集的题目了，默写都默不出来了，丢人啊。

// 1832. Check if the Sentence Is Pangram
class Solution {
    public boolean checkIfPangram(String sentence) {
        char[] chars = sentence.toCharArray();
        int[] letter = new int[123];
        for (char c : chars) {
            letter[c] = 1;
        }
        int ans = 0;
        for (int i = 97; i < 123; ++i) {
            if (letter[i] != 1) return false;
        }
        return true;
    }
}

学习笔记：
这是一道水题，简单题，就是计数检查字符串一遍就完事儿了。

// 1781. Sum of Beauty of All Substrings
class Solution {
    public int beautySum(String s) {
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        int ans = 0;
        for (int i = 0; i < len; ++i) {
            int[] frequencies = new int[123];
            int maxFrequency = 0;
            for (int j = i; j < len; ++j) {
                ++frequencies[charArray[j]];
                if (frequencies[charArray[j]] > maxFrequency) {
                    maxFrequency = frequencies[charArray[j]];
                }
                int minFrequency = len;
                for (int k = 97; k < 123; ++k) {
                    if (frequencies[k] != 0 && frequencies[k] < minFrequency) {
                        minFrequency = frequencies[k];
                    }
                }
                ans += maxFrequency - minFrequency;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道中等题，当我以为解法很特殊的时候，却发现啥也不是。
就是双重循环，就是数组。太简陋了这道题目。