这是小川的第 412次更新,第 444篇原创
看题和准备
今天介绍的是 LeetCode算法题中 Easy级别的第 263题(顺位题号是 1170)。在一个非空字符串s上定义一个函数 f(s)
,该函数计算 s
中最小字符的出现频率。例如,如果 s ="dcce"
,则 f(s)= 2
,因为最小字符为 "c"
,其频率为2。
现在,给定字符串数组 queries
和 words
,返回一个整数数组 answer
,
其中每个 answer[i]
是使得 f(queries[i]) < f(W)
的单词数量,其中 W
是 words
中的单词。
例如:
输入:queries = [“cbd”], words = [“zaaaz”]
输出:[1]
说明:在第一个查询中,我们有 f("cbd")= 1
, f("zaaaz")= 3
,因此 f("cbd")<f("zaaaz")< code>。</f("zaaaz")<>
输入:queries = [“bbb”,”cc”], words = [“a”,”aa”,”aaa”,”aaaa”]
输出:[1,2]
说明:在第一个查询中,仅 f("bbb")<f("aaaa")< code>,所以<code>answer[0] = 1</code>。<br>在第二个查询中,<code>f("cc")<f("aaa")< code>,<code>f("cc")<f("aaaa")< code>,所以<code>answer[1] = 2</code>。</f("aaaa")<></code></f("aaa")<></code></f("aaaa")<>
注意:
- 1
第一种解法
题目的意思是要求在 words
中,找出最小字符出现次数小于 queries
中字符串最小字符出现次数的单词个数,最后以 queries
的长度作为 int
数组返回。
因此,我们直接翻译题目即可,使用两层循环,外层循环遍历 queries
中的字符串,找到 queries[i]
中最小字符的出现次数,接着遍历 words
中的单词,比较两个最小字符出现次数,如果 queries
中的比较小,就计数,内层循环结束后,将计数结果添加到 answer
数组中,最后返回。
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int len = queries.length, len2 = words.length;
int[] result = new int[len];
for (int i=0; i
第二种解法
针对第一种解法中,在内层循环多次计算 words
中单词的最小字符出现次数,我们可以抽到循环外面处理。先将每个单词的最小字符出现次数都算出来,存入一个长度和 words
相同的 int
数组中,在内层循环中,就可以直接遍历这个 int
数组了,而不用每个全部重新算一遍。
public int[] numSmallerByFrequency2(String[] queries, String[] words) {
int len = queries.length, len2 = words.length;
int[] wordFreq = new int[len2];
for (int j=0; j
第三种解法
对于前面两种解法,我们还能再简化下吗?比如,将两层循环变成一层循环?要想变一层循环,那么在计算 queries
中的字符串时,就需要一次拿到结果,不使用循环,也就是说像在数组中取值一样。
我们先来观察下第二个例子。在处理完 words
中的单词时,会得到一个数组 wordFreq
,在此基础上再做下变化,做计数处理,将最小字符出现次数作为新数组的索引,再来累计次数,就会得到下面四个:
count[4] = 1; //"aaaa"代表的单词
count[3] = 1; //"aaa"代表的单词
count[2] = 1; //"aa"代表的单词
count[1] = 1; //"a"代表的单词
再来观察下 queries
数组,字符串 "bbb"
和 "cc"
,去和 words
中的单词比较时,会有以下规律:
大于"bbb"的有1位,记为arr[3] = 1
大于"cc"的有2位,记为arr[2] = 2
如果接着往下写:
大于1的有3位,arr[1] = 3
大于0的有4位,arr[0] = 4
我们发现,以 queries
中的字符串最小字符出现次数为索引的 arr
数组,其实就是上面 count
数组的倒序元素累加之和:
arr[3] = count[4] = 1;
arr[2] = arr[3] + count[3] = 1+1 = 2
arr[i-1] = arr[i]+count[i];
分析出来这其中的原理后,剩下就是将代码写出来了,此解法比前面两种解法速度上快很多。
public int[] numSmallerByFrequency3(String[] queries, String[] words) {
int len = queries.length;
int[] wordFreq = new int[11];
for (String word : words) {
wordFreq[minFrequency(word)]++;
}
int[] sum = new int[11];
for (int i=sum.length-1; i>0; i--) {
sum[i-1] = sum[i]+wordFreq[i];
}
int[] result = new int[len];
for (int i=0; i
算法专题目前已更新 LeetCode算法题文章 269+篇,公众号对话框回复【 数据结构与算法】、【 算法】、【 数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!
Original: https://www.cnblogs.com/xiaochuan94/p/11570371.html
Author: 程序员小川
Title: LeetCode.1170-比较字符串中最小字符的出现频率(Compare Strings by Frequency of the Smallest Char)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/572962/
转载文章受原作者版权保护。转载请注明原作者出处!