LeetCode.1170

Stella981
• 阅读 635

这是小川的第412次更新,第444篇原创

看题和准备

今天介绍的是LeetCode算法题中Easy级别的第263题(顺位题号是1170)。在一个非空字符串s上定义一个函数f(s),该函数计算s中最小字符的出现频率。例如,如果s ="dcce",则f(s)= 2,因为最小字符为"c",其频率为2。

现在,给定字符串数组querieswords,返回一个整数数组answer, 其中每个answer[i]是使得f(queries[i]) < f(W)的单词数量,其中Wwords中的单词。

例如:

输入:queries = ["cbd"], words = ["zaaaz"] 输出:[1] 说明:在第一个查询中,我们有f("cbd")= 1f("zaaaz")= 3,因此f("cbd")<f("zaaaz")

输入:queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] 输出:[1,2] 说明:在第一个查询中,仅f("bbb")<f("aaaa"),所以answer[0] = 1。 在第二个查询中,f("cc")<f("aaa")f("cc")<f("aaaa"),所以answer[1] = 2

注意

  • 1 <= queries.length <= 2000
  • 1 <= words.length <= 2000
  • 1 <= queries[i].lengthwords[i].length <= 10
  • queries[i][j]words[i][j]是英文小写字母。

第一种解法

题目的意思是要求在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<len; i++) {
        int query = minFrequency(queries[i]);
        int count = 0;
        for (int j=0; j<len2; j++) {
            int word = minFrequency(words[j]);
            if (query < word) {
                count++;
            }
        }
        result[i] = count;
    }
    return result;
}

/**
 * 找到字符串中的最小字符的出现次数
 * @param s
 * @return
 */
public int minFrequency(String s) {
    int[] arr = new int[26];
    int count = 0;
    for (int i=0; i<s.length(); i++) {
        arr[s.charAt(i)-'a']++;
    }
    for (int j=0; j<26; j++) {
        if (arr[j] != 0) {
            count = arr[j];
            break;
        }
    }
    return count;
}

第二种解法

针对第一种解法中,在内层循环多次计算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<len2; j++) {
        wordFreq[j] = minFrequency(words[j]);
    }
    int[] result = new int[len];
    for (int i=0; i<len; i++) {
        int query = minFrequency(queries[i]);
        int count = 0;
        for (int j=0; j<len2; j++) {
            if (query < wordFreq[j]) {
                count++;
            }
        }
        result[i] = count;
    }
    return result;
}

/**
 * 找到字符串中的最小字符的出现次数
 * @param s
 * @return
 */
public int minFrequency(String s) {
    int[] arr = new int[26];
    int count = 0;
    for (int i=0; i<s.length(); i++) {
        arr[s.charAt(i)-'a']++;
    }
    for (int j=0; j<26; j++) {
        if (arr[j] != 0) {
            count = arr[j];
            break;
        }
    }
    return count;
}

第三种解法

对于前面两种解法,我们还能再简化下吗?比如,将两层循环变成一层循环?要想变一层循环,那么在计算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<len; i++) {
        result[i] = sum[minFrequency(queries[i])];
    }
    return result;
}

/**
 * 找到字符串中的最小字符的出现次数
 * @param s
 * @return
 */
public int minFrequency(String s) {
    int[] arr = new int[26];
    int count = 0;
    for (int i=0; i<s.length(); i++) {
        arr[s.charAt(i)-'a']++;
    }
    for (int j=0; j<26; j++) {
        if (arr[j] != 0) {
            count = arr[j];
            break;
        }
    }
    return count;
}

小结

算法专题目前已更新LeetCode算法题文章**269+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构**】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
3年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
DaLongggggg DaLongggggg
3年前
python百题大冲关-确定字符串是否是另一个的旋转
挑战介绍实现一个算法来识别一个字符串s2是否是另一个字符串s1的旋转。旋转的解释如下:如果将s1从某个位置断开,拆分成两个字符串(可能有一个为空字符串),再将这两个字符串调换顺序后拼接起来,能够得到s2,那么说字符串s2是字符串s1的旋转。本次挑战中,你需要在rotation.py文件中补充函数is_subst
Stella981 Stella981
3年前
LeetCode算法题
这是悦乐书的第258次更新,第271篇原创<br/01看题和准备今天介绍的是LeetCode算法题中Easy级别的第125题(顺位题号是551)。您将获得一个表示学生出勤记录的字符串。该记录仅包含以下三个字符:'A':缺席。'L':迟到。'P':在场。如果学生的出勤记录不超过一个“A”(缺席)或超过两个
Easter79 Easter79
3年前
SpringBoot自定义序列化的使用方式
场景及需求:项目接入了SpringBoot开发,现在需求是服务端接口返回的字段如果为空,那么自动转为空字符串。例如:\    {        "id":1,        "name":null    },    {        "id":2,        "name":"x
Stella981 Stella981
3年前
LeetCode.1128
这是小川的第394次更新,第428篇原创<br/01看题和准备今天介绍的是LeetCode算法题中Easy级别的第259题(顺位题号是1128)。给定多米诺骨牌列表,当且仅当(ac且bd)或(ad且bc),dominoesia,
Wesley13 Wesley13
3年前
Mysql 查询所有课程的成绩第2名到第3名的学生信息及该课程成绩
 查询所有课程的成绩第2名到第3名的学生信息及该课程成绩1\.查询课程ID为‘01’的课程的成绩第2名到第3名的学生信息及该课程成绩SELECT  d.,c.排名,c.s_score,c.c_idFROM  (SELECTa.s_id,a.s_score,a.c_id,@i:@i1AS排名FROMs
Stella981 Stella981
3年前
SpringBoot自定义序列化的使用方式
场景及需求:项目接入了SpringBoot开发,现在需求是服务端接口返回的字段如果为空,那么自动转为空字符串。例如:\    {        "id":1,        "name":null    },    {        "id":2,        "name":"x
Stella981 Stella981
3年前
LeetCode.1029
这是小川的第383次更新,第412篇原创<br/01看题和准备今天介绍的是LeetCode算法题中Easy级别的第245题(顺位题号是1029)。公司计划采访的人数为2N。将第i个人飞往城市A的费用是i0,将第i个人飞到城市B的费用是费用i1。返回将