樊轶群的个人网站

// 0808. Soup Servings
class Solution {
    double[][] dp = new double[200][200];

    public double soupServings(int n) {
        return n > 4800 ? 1 : f((n + 24) / 25, (n + 24) / 25);
    }

    public double f(int a, int b) {
        if (a <= 0 && b <= 0) {
            return 0.5;
        } else if (a <= 0) {
            return 1;
        } else if (b <= 0) {
            return 0;
        }
        if (dp[a][b] > 0) return dp[a][b];
        dp[a][b] = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3));
        return dp[a][b];
    }
}

学习笔记：
这是一道动态规划的题目，要将分汤的四种情况都进行分析。

// 0799. Champagne Tower
class Solution {
    public double champagneTower(int poured, int query_row, int query_glass) {
        double[][] glasses = new double[query_row + 1][query_row + 1];
        glasses[0][0] = poured;
        for (int i = 1; i <= query_row; ++i) {
            glasses[i][0] = Math.max((glasses[i - 1][0] - 1) / 2, 0.0);
            for (int j = 1; j <= i; ++j) {
                glasses[i][j] = Math.max((glasses[i - 1][j - 1] - 1) / 2, 0.0) + Math.max((glasses[i - 1][j] - 1) / 2, 0.0);
            }
        }
        if (glasses[query_row][query_glass] > 1) {
            return 1.0;
        }
        return glasses[query_row][query_glass];
    }
}

学习笔记：
这是一道有趣的动态规划题目，香槟塔往下流的时候会少1，然后平分给下面两个。
我们需要使用逆向思维，下面那一杯接到的酒就上上面两个流下来的加起来。

// 1732. Find the Highest Altitude
class Solution {
    public int largestAltitude(int[] gain) {
        int prefixSum = 0;
        int ans = 0;
        for (int g : gain) {
            prefixSum += g;
            ans = Math.max(ans, prefixSum);
        }
        return ans;
    }
}

学习笔记：
这是一道简单题，就是简单求前缀和，返回前缀和的最大值。

import java.util.Arrays;

// 0891. Sum of Subsequence Widths
class Solution {
    public int sumSubseqWidths(int[] nums) {
        final long MOD = 1000000007;
        Arrays.sort(nums);
        long ans = 0L;
        int len = nums.length;
        long[] powerBased2 = new long[len];
        powerBased2[0] = 1L;
        for (int i = 1; i < len; ++i) {
            powerBased2[i] = (powerBased2[i - 1] << 1) % MOD;
        }
        for (int i = 0; i < len; ++i) {
            ans = (ans + (powerBased2[i] - powerBased2[len - 1 - i]) * nums[i]) % MOD;
        }
        return (int) ans;
    }
}

学习笔记：
今天这是一道数学题，先发现和顺序无关，那就排序。
然后就看这个数成为最小值的次数，和成为最大值的次数。
然后移项整理出结果。

import java.util.ArrayList;
import java.util.List;

// 0792. Number of Matching Subsequences
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        char[] charArray = s.toCharArray();
        int len = charArray.length;
        List<List<Integer>> charsIndexes = new ArrayList<>();
        for (int i = 0; i < 123; ++i) {
            charsIndexes.add(new ArrayList<>());
        }
        for (int i = 0; i < len; ++i) {
            charsIndexes.get(charArray[i]).add(i);
        }
        int ans = 0;
        for (String word : words) {
            ans += isMatching(word, charsIndexes);
        }
        return ans;
    }

    private int isMatching(String word, List<List<Integer>> charsIndexes) {
        int preIndex = -1;
        for (char c : word.toCharArray()) {
            List<Integer> charIndexes = charsIndexes.get(c);
            if (charIndexes.size() == 0) {
                return 0;
            }
            int currentIndex = binarySearch(preIndex, charIndexes);
            if (currentIndex <= preIndex) {
                return 0;
            }
            preIndex = currentIndex;
        }
        return 1;
    }

    private int binarySearch(int preIndex, List<Integer> charIndexes) {
        int left = 0;
        int right = charIndexes.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (charIndexes.get(mid) <= preIndex) {
                left = mid + 1;
            } else{
                right = mid;
            }
        }
        return charIndexes.get(left);
    }
}

学习笔记：
如果要你判断一个字符串是不是另一个字符串的子序列，其实可以使用双指针算法。
那么多个字符串是不是字符串s的子序列呢？理所当然想到循环呗。
结果这题目就是不让循环通过的。
所以得用巧办法了。
记录每种字母出现的索引。
然后遍历每个字符串的时候，去找可能出现的最左的那个字母索引。
所以这里也用到了二分搜索，是二分搜索中的搜索左边界。

// 0775. Global and Local Inversions
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (Math.abs(i - nums[i]) > 1) {
                return false;
            }
        }
        return true;
    }
}

学习笔记：
这看上去其实是一道有难度的数学找规律题目，不容易啊。
如果是局部倒置，那么一定就是全局倒置。所以，全局倒置是包含局部倒置的。
由于题目中已经给出了如下一个关键条件：
数组nums长度为n，并且数字是由0到n-1构成的。
所以我们可以根据偏差量来进行判断，一旦数字和他的索引的偏差量大于1就false了。

import java.util.PriorityQueue;

// 1710. Maximum Units on a Truck
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        PriorityQueue<BoxInformation> priorityQueue = new PriorityQueue<>((bi1, bi2) -> bi2.numberOfUnitsPerBox - bi1.numberOfUnitsPerBox);
        for (int[] boxType : boxTypes) {
            priorityQueue.offer(new BoxInformation(boxType[0], boxType[1]));
        }
        int ans = 0;
        while (truckSize > 0) {
            BoxInformation best = priorityQueue.poll();
            if (best == null) return ans;
            if (truckSize > best.numberOfBoxes) {
                ans += best.numberOfBoxes * best.numberOfUnitsPerBox;
            } else {
                ans += truckSize * best.numberOfUnitsPerBox;
            }
            truckSize -= best.numberOfBoxes;
        }
        return ans;
    }
}

class BoxInformation {
    Integer numberOfBoxes;
    Integer numberOfUnitsPerBox;

    public BoxInformation(Integer numberOfBoxes, Integer numberOfUnitsPerBox) {
        this.numberOfBoxes = numberOfBoxes;
        this.numberOfUnitsPerBox = numberOfUnitsPerBox;
    }
}

// 1710. Maximum Units on a Truck
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int len = boxTypes.length;
        Arrays.sort(boxTypes, (int[] bi1, int[] bi2) -> bi2[1] - bi1[1]);
        int ans = 0;
        int i = 0;
        while (truckSize > 0) {
            if (i < len) {
                if (truckSize > boxTypes[i][0]) {
                    ans += boxTypes[i][0] * boxTypes[i][1];
                } else {
                    ans += truckSize * boxTypes[i][1];
                }
                truckSize -= boxTypes[i][0];
                ++i;
            } else {
                return ans;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道简单题，可以使用排序二维数组。
使用了了优先队列+创建对象，可能是因为放进去之后拿出来的概率太高了，所以花了10ms。
使用ArrayList+创建对象，需要13ms。
使用LinkedList+创建对象，需要23ms。可以看出LinkedList的排序属实性能不行。
最后写了一版二维数组排序的，只需要8ms。

import java.util.HashSet;
import java.util.Set;

// 0805. Split Array With Same Average
class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        if (n == 1) return false;
        int mid = n / 2;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        for (int i = 0; i < n; ++i) {
            nums[i] = nums[i] * n - sum;
        }
        int leftCombinations = 1 << mid;
        int rightCombinations = 1 << n - mid;
        Set<Integer> leftSums = new HashSet<>();
        for (int i = 1; i < leftCombinations; ++i) {
            int total = 0;
            for (int j = 0; j < mid; ++j) {
                if ((i & (1 << j)) != 0) {
                    total += nums[j];
                }
            }
            if (total == 0) return true;
            leftSums.add(total);
        }
        for (int i = 1; i < rightCombinations - 1; ++i) {
            int total = 0;
            for (int j = mid; j < n; ++j) {
                if ((i & (1 << j - mid)) != 0) {
                    total += nums[j];
                }
            }
            if (total == 0) return true;
            if (leftSums.contains(total * -1)) return true;
        }
        return false;
    }
}

学习笔记：
这道是一道超级困难题。
如果使用深度优先搜索，需要2的30次方的时间，太离谱了。
所以我们要用折半搜索，先搜2的15次方，再搜2的15次方，然后拿左半去右半里面找有没有相反的数字。

// 0791. Custom Sort String
class Solution {
    public String customSortString(String order, String s) {
        int[] lettersQuantity = new int[123];
        for (char letter : s.toCharArray()) {
            ++lettersQuantity[letter];
        }
        StringBuilder sb = new StringBuilder();
        for (char letter : order.toCharArray()) {
            int quantity = lettersQuantity[letter];
            lettersQuantity[letter] = 0;
            for (int i = 0; i < quantity; ++i) {
                sb.append(letter);
            }
        }
        for (char c = 'a'; c <= 'z'; ++c) {
            int quantity = lettersQuantity[c];
            for (int i = 0; i < quantity; ++i) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

学习笔记：
这是一道简单的字符串题。
说是字符串，其实考验的是排序和贪心的算法。

// 0790. Domino and Tromino Tiling
class Solution {
    public int numTilings(int n) {
        if (n < 3) return n;
        final long MOD = 1000000007;
        long[] fullTiling = new long[n + 1];
        long[] partTiling = new long[n + 1];
        fullTiling[1] = 1;
        fullTiling[2] = 2;
        partTiling[1] = 0;
        partTiling[2] = 1;
        for (int i = 3; i <= n; ++i) {
            fullTiling[i] = (fullTiling[i - 1] + fullTiling[i - 2] + partTiling[i - 1] + partTiling[i - 1]) % MOD;
            partTiling[i] = (partTiling[i - 1] + fullTiling[i - 2]) % MOD;
        }
        return (int) fullTiling[n];
    }
}

学习笔记：
这是一道动态规划的题目，要仔细分析出四种不同的情况。
空的，上面凸出来的，下面凸出来的，满的。
也可以分为两种，部分完成和全部完成。
这两种思路都可以完成这道题目。