LeetCode——比较字符串最小字母出现频次

àì夳堔傛蜴生んèń 2023-10-12 13:37 7阅读 0赞

## 1、题目 ##

[1170. 比较字符串最小字母出现频次 - 力扣（Leetcode）][1170. _ - _Leetcode]

定义一个函数 `f(s)`，统计 `s` 中**（按字典序比较）最小字母的出现频次** ，其中 `s` 是一个非空字符串。

例如，若 `s = "dcce"`，那么 `f(s) = 2`，因为字典序最小字母是 `"c"`，它出现了 2 次。

现在，给你两个字符串数组待查表 `queries` 和词汇表 `words` 。对于每次查询 `queries[i]` ，需统计 `words` 中满足 `f(queries[i])` < `f(W)` 的 **词的数目** ，`W` 表示词汇表 `words` 中的每个词。

请你返回一个整数数组 `answer` 作为答案，其中每个 `answer[i]` 是第 `i` 次查询的结果。

**示例 1：**

输入：queries = ["cbd"], words = ["zaaaz"]
    输出：[1]
    解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。

**示例 2：**

输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
    输出：[1,2]
    解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。

**提示：**

*  `1 <= queries.length <= 2000`
 *  `1 <= words.length <= 2000`
 *  `1 <= queries[i].length, words[i].length <= 10`
 *  `queries[i][j]`、`words[i][j]` 都由小写英文字母组成

## 2、题目解读 ##

> 给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries\[i\] ，需统计 words 中满足 f(queries\[i\]) < f(W) 的 **词的数目** ，W 表示词汇表 words 中的每个词。
> 
> 其中f（String s）函数就是统计 s 中**（按字典序比较）最小字母的出现频次** 。
> 
> 1、我们可以先求出words数组中的每一字符串的**（按字典序比较）最小字母的出现频次** 并使用一w\[\]数组存储结果，再从小到大进行排序。
> 
> 然后是queries数组，求queries\[i\]的**（按字典序比较）最小字母的出现频次**，再通过二分的形式去求解答案。
> 
> 2、后缀和（官方题解）
> 
> [1170. 比较字符串最小字母出现频次 - 力扣（Leetcode）][1170. _ - _Leetcode 1]

## 3、代码 ##

class Solution {
      public int[] numSmallerByFrequency(String[] queries, String[] words) {
            int n = words.length;
            int[] nums = new int[n];//记录words里每个字符串 （按字典序比较）最小字母的出现频次
            for (int i = 0; i < n; ++i) {
                nums[i] = f(words[i]);
            }
            Arrays.sort(nums);//从小到大排序
            int m = queries.length;
            int[] ans = new int[m];//answer数组
            for (int i = 0; i < m; ++i) {
                int x = f(queries[i]);
                int l = 0, r = n;
                while (l < r) {//二分查询 求ans[i]
                    int mid = (l + r)/2;
                    if (nums[mid] > x) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                ans[i] = n - l;
            }
            return ans;
        }
    
        private int f(String s) {//f函数实现
            int[] cnt = new int[26];
            for (int i = 0; i < s.length(); ++i) {
                cnt[s.charAt(i) - 'a']++;
            }
            for (int x : cnt) {
                if (x > 0) {
                    return x;
                }
            }
            return 0;
        }
    }

官方题解 后缀和

class Solution {
        public int[] numSmallerByFrequency(String[] queries, String[] words) {
            int[] count = new int[12];
            for (String s : words) {
                count[f(s)]++;
            }
            for (int i = 9; i >= 1; i--) {
                count[i] += count[i + 1];
            }
            int[] res = new int[queries.length];
            for (int i = 0; i < queries.length; i++) {
                String s = queries[i];
                res[i] = count[f(s) + 1];
            }
            return res;
        }
    
        public int f(String s) {
            int cnt = 0;
            char ch = 'z';
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c < ch) {
                    ch = c;
                    cnt = 1;
                } else if (c == ch) {
                    cnt++;
                }
            }
            return cnt;
        }
    }

![7aba75768c544c5dbf4c9dba74391320.png][]

![0ac4e91f350d431d8d98fbba53d78d28.gif][]

[1170. _ - _Leetcode]: https://leetcode.cn/problems/compare-strings-by-frequency-of-the-smallest-character/description/
[1170. _ - _Leetcode 1]: https://leetcode.cn/problems/compare-strings-by-frequency-of-the-smallest-character/solutions/2297291/bi-jiao-zi-fu-chuan-zui-xiao-zi-mu-chu-x-pb50/
[7aba75768c544c5dbf4c9dba74391320.png]: https://img-blog.csdnimg.cn/7aba75768c544c5dbf4c9dba74391320.png
[0ac4e91f350d431d8d98fbba53d78d28.gif]: https://img-blog.csdnimg.cn/0ac4e91f350d431d8d98fbba53d78d28.gif