Java 第 32 课 6050. 字符串的总引力 781. 森林中的兔子

• [2063. 所有子字符串中的元音](https://leetcode-cn.com/problems/vowels-of-all-substrings/)
• [6050. 字符串的总引力](https://leetcode-cn.com/problems/total-appeal-of-a-string/)
• [781. 森林中的兔子](https://leetcode-cn.com/problems/rabbits-in-forest/)

class Solution:
    def countVowels(self, word: str) -> int:
        v, ans, pre = 'aeiou', 0, 0
        for i, c in enumerate(word):           
            pre += i + 1 if c in v else 0 
            ans += pre        
        return ans

class Solution {
    public long countVowels(String word) {
        long ans = 0, pre = 0;
        // String vowel = "aeiou";
        // Set set = new HashSet<>(){
        //     { add('a'); add('e'); add('i'); add('o'); add('u'); }};
        char[] t = word.toCharArray();
        for (int i = 0; i < t.length; i++){
            // pre += vowel.indexOf(t[i]) == -1 ? 0 : i + 1;
            // pre += set.contains(t[i]) ? i + 1 : 0;
            // pre += isValid(t[i]) ? i + 1 : 0;
            char c = t[i];
            pre += c == 'a' || c == 'e' || c== 'o' || c == 'i' || c == 'u' ? i + 1 : 0;
            ans += pre;
        }
        return ans;
    }

    private boolean isValid(char c) {
        return c == 'a' || c == 'e' || c== 'o' || c == 'i' || c == 'u';
    }
}

dp[i] 以下标 i 结尾的子串的总引力；
哈希表 d 记录当前每个字母出现过的最大下标；
当前字母为 c 下标为 i，如果是第一次出现，以下标 i 结尾的子串共有 i + 1 个，则新增的贡献为 i + 1 个 c；
否则，假设上一个 c 的下标为 j，则只对 j 后面的子串才有贡献，即新增 i - j 个 c。
所以状态转移方程为 dp[i + 1] = dp[i] + i - d.get(c, -1) # 在 dp[i] 的基础上新增 i - d.get(c, -1) 个 c

class Solution:
    def appealSum(self, s: str) -> int:
        d, n = defaultdict(int), len(s)
        dp = [0] * (n + 1)
        for i in range(n):
            c = s[i]
            # 以下标 i 结尾的子串共有 i + 1 个，'abc' -> 'abc', 'bc', 'c'
            # 如果 c 己经存在，所以只对 d[c] 后面的子串才有贡献。
            # 'abcb' -> 'cb', 'b'
            dp[i+1] = dp[i] + i - d.get(c, -1)
            d[c] = i
        return sum(dp)

class Solution {
    public long appealSum(String s) {
        long ans = 0, pre = 0;
        int n = s.length();
        // Map map = new HashMap<>();
        // for (int i = 0; i < n; i++){
        //     char c = s.charAt(i);
        //     pre += i - map.getOrDefault(c, -1);
        //     ans += pre;
        //     map.put(c, i);
        // }
        
        int[] idx = new int[26]; // 数组实现 4 ms
        Arrays.fill(idx, -1);
        for (int i = 0; i < n; i++){
            int c = s.charAt(i) - 'a';
            pre += i - idx[c];
            ans += pre;
            idx[c] = i;
        }
        return ans;
    }
}

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        n, ans = len(answers), 0
        cnt = Counter(answers)
        for k, v in cnt.items():
            ans += (v + k) // (k + 1) * (k + 1)
            #ans += ceil(v/(k+1)) * (k + 1)
        return ans

class Solution {
    public int numRabbits(int[] answers) {
        int ans = 0;
        Map map = new HashMap<>();
        for (int x : answers) 
            map.put(x, map.getOrDefault(x, 0) + 1);       
        for (Map.Entry entry : map.entrySet()) {
            int k = entry.getKey(), v =  entry.getValue();
            ans += (k + v) / (k + 1) * (k + 1);
        }  
        return ans;
    }
}