Daily LeetCode – day0119 0809. Expressive Words

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还没有走完的情况。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0118 0795. Number of Subarrays with Bounded Maximum

// 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。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0117 1742. Maximum Number of Balls in a Box

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;
    }
}
学习笔记:
这是一道简单题,哈希表的题目。
简单计算各位之和,放入桶里面就行了。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0116 0878. Nth Magical Number

// 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个了。
先手是求最大公约数,然后最小公倍数,接下来就是二分查找。
这是向左边界进行搜索的二分查找。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0115 0808. Soup Servings

// 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];
    }
}
学习笔记:
这是一道动态规划的题目,要将分汤的四种情况都进行分析。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0114 0799. Champagne Tower

// 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,然后平分给下面两个。
我们需要使用逆向思维,下面那一杯接到的酒就上上面两个流下来的加起来。
发表在 每日LeetCode | 2条评论

Daily LeetCode – day0113 1732. Find the Highest Altitude

// 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;
    }
}
学习笔记:
这是一道简单题,就是简单求前缀和,返回前缀和的最大值。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0112 0891. Sum of Subsequence Widths

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;
    }
}
学习笔记:
今天这是一道数学题,先发现和顺序无关,那就排序。
然后就看这个数成为最小值的次数,和成为最大值的次数。
然后移项整理出结果。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0111 0792. Number of Matching Subsequences

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的子序列呢?理所当然想到循环呗。
结果这题目就是不让循环通过的。
所以得用巧办法了。
记录每种字母出现的索引。
然后遍历每个字符串的时候,去找可能出现的最左的那个字母索引。
所以这里也用到了二分搜索,是二分搜索中的搜索左边界。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0110 0775. Global and Local Inversions

// 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了。
发表在 每日LeetCode | 留下评论