【Leetcode -748.最短补全词 -762.二进制表示中质数个计算置位】

简介: 【Leetcode -748.最短补全词 -762.二进制表示中质数个计算置位】

Leetcode -748.最短补全词

题目:给你一个字符串 licensePlate 和一个字符串数组 words ,请你找出 words 中的 最短补全词 。

补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。

如果某个字母在 licensePlate 中出现不止一次,那么该字母在补全词中的出现次数应当一致或者更多。

例如:licensePlate = “aBc 12c”,那么它的补全词应当包含字母 ‘a’、‘b’ (忽略大写)和两个 ‘c’ 。可能的 补全词 有 “abccdef”、“caaacab” 以及 “cbca” 。

请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。

示例 1:

输入:licensePlate = “1s3 PSt”, words = [“step”, “steps”, “stripe”, “stepple”]

输出:“steps”

解释:最短补全词应该包括 “s”、“p”、“s”(忽略大小写) 以及 “t”。

“step” 包含 “t”、“p”,但只包含一个 “s”,所以它不符合条件。

“steps” 包含 “t”、“p” 和两个 “s”。

“stripe” 缺一个 “s”。

“stepple” 缺一个 “s”。

因此,“steps” 是唯一一个包含所有字母的单词,也是本例的答案。

示例 2:

输入:licensePlate = “1s3 456”, words = [“looks”, “pest”, “stew”, “show”]

输出:“pest”

解释:licensePlate 只包含字母 “s” 。所有的单词都包含字母 “s” ,其中 “pest”、“stew”、和 “show” 三者最短。

答案是 “pest” ,因为它是三个单词中在 words 里最靠前的那个。

提示:

1 <= licensePlate.length <= 7

licensePlate 由数字、大小写字母或空格 ’ ’ 组成

1 <= words.length <= 1000

1 <= words[i].length <= 15

words[i] 由小写英文字母组成

思路:思路是先统计 licensePlate 中的字母出现的次数,不管大小写,用 hash 数组统计;然后在 words 数组中也另外定义一个 temp 数组统计第 i 个字符串中的字母出现的次数;当 hash 数组中的某一个数比 temp 数组中对应的数大,即 licensePlate 中某一个字母出现的次数比 words 中第 i 个字符串对应字母出现的次数多,说明当前 words 中第 i 个字符串不符合题意;否则一直遍历hash数组,如果hash数组中的值都小于或等于temp数组中的值,即说明当前字符串符合题意,记录此下标;注意在记录下标前,还要比较当前字符串与上一个记录的字符串的长度,取长度较小的字符串;

char* shortestCompletingWord(char* licensePlate, char** words, int wordsSize)
    {
        //定义一个数组并初始化为0
        //index 为返回字符串在 words 中的下标
        int hash[26] = { 0 };
        int index = -1;
        //将 licensePlate 中的字母找出来,统计字母出现的次数,不管大小写
        for (int i = 0; i < strlen(licensePlate); i++)
        {
            if (licensePlate[i] >= 'A' && licensePlate[i] <= 'Z')
            {
                hash[licensePlate[i] - 'A']++;
            }
            else if (licensePlate[i] >= 'a' && licensePlate[i] <= 'z')
            {
                hash[licensePlate[i] - 'a']++;
            }
        }
        // i 和 j 访问 words 中字符串的第 j 个字母
        for (int i = 0; i < wordsSize; i++)
        {
            //每次遍历完一个字符串时,重新定义 temp 数组,temp数组统计这个字符串的字母出现的次数
            int temp[26] = { 0 };
            for (int j = 0; j < strlen(words[i]); j++)
                temp[words[i][j] - 'a']++;
            // k 遍历26个字母对应的数字,
            //当 hash 数组(即licensePlate)中出现的字母的次数大于当前 temp 数组存放字符串的字母的次数时,证明当前字符串不符合题意,跳出循环
            //当 k 等于26,即遍历完 26 个字母时,证明当前字符串是符合题意的字符串
            int k = 0;
            while (k < 26 && hash[k] <= temp[k])
                k++;
            //符合题意的字符串
            if (k == 26)
            {
                //如果是第一个符合题意的字符串,直接将下标赋给index
                if (index == -1)
                {
                    index = i;
                }
                //如果不是第一个,比较之前以 index 为下标的字符串和当前以 i 为下标的字符串的长度,取较短的字符串的下标
                else
                {
                    if (strlen(words[i]) < strlen(words[index]))
                        index = i;
                }
            }
        }
        //返回字符串
        return words[index];
    }

Leetcode -762.二进制表示中质数个计算置位

题目:给你两个整数 left 和 right ,在闭区间[left, right] 范围内,统计并返回 计算置位位数为质数 的整数个数。

计算置位位数 就是二进制表示中 1 的个数。

例如, 21 的二进制表示 10101 有 3 个计算置位。

示例 1:

输入:left = 6, right = 10

输出:4

解释:

6 -> 110 (2 个计算置位,2 是质数)

7 -> 111 (3 个计算置位,3 是质数)

9 -> 1001 (2 个计算置位,2 是质数)

10-> 1010 (2 个计算置位,2 是质数)

共计 4 个计算置位为质数的数字。

示例 2:

输入:left = 10, right = 15

输出:5

解释:

10 -> 1010 (2 个计算置位, 2 是质数)

11 -> 1011 (3 个计算置位, 3 是质数)

12 -> 1100 (2 个计算置位, 2 是质数)

13 -> 1101 (3 个计算置位, 3 是质数)

14 -> 1110 (3 个计算置位, 3 是质数)

15 -> 1111 (4 个计算置位, 4 不是质数)

共计 5 个计算置位为质数的数字。

提示:

1 <= left <= right <= 10^6

0 <= right - left <= 10^4

思路:思路是先统计这个数的二进制中有多少个 1 ,用 ans 统计,然后判断 ans 是否是质数,是则返回 true,否则返回 false;

//判断是否是质数
    bool isPrime(int temp)
    {
        //1 和 2 不是质数
        if (temp < 2)
            return false;
        //质数是只可以被 1 和本身整除的数字
        for (int i = 2; i < temp; i++)
        {
            if (temp % i == 0)
                return false;
        }
        return true;
    }
    int countPrimeSetBits(int left, int right)
    {
        int ret = 0;
        //生成从 left 到 right 的数
        for (int i = left; i <= right; i++)
        {
            //ans 统计这个数二进制中 1 的个数
            int ans = 0;
            //计算 i 在二进制表示中 1 的个数
            for (int j = 0; j < 32; j++)
            {
                if (i >> j & 1 == 1)
                    ans++;
            }
            //判断 ans 是否是质数,是则 ret 统计返回的答案
            if (isPrime(ans))
                ret++;
        }
        return ret;
    }
目录
相关文章
|
3月前
|
算法 Java
LeetCode第67题二进制求和
这篇文章是关于LeetCode第67题二进制求和的解题思路和代码实现的分享。作者通过分析题目要求和二进制加法的规则,提供了一个Java语言的解决方案,并在最后总结了二进制在算法中的重要性。
LeetCode第67题二进制求和
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5月前
|
存储 SQL 算法
LeetCode题目67:二进制求和
LeetCode题目67:二进制求和
|
5月前
|
算法 数据挖掘 大数据
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
深入解析力扣172题:阶乘后的零(计算因子5的方法详解及模拟面试问答)
|
5月前
|
算法 Java Go
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
65 2
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
6月前
【力扣】67. 二进制求和
【力扣】67. 二进制求和
|
6月前
|
JavaScript
【leetcode】204. 计数质数 暴力 & 埃拉托斯特尼法
【leetcode】204. 计数质数 暴力 & 埃拉托斯特尼法
38 0
力扣1873 计算特殊奖金
力扣1873 计算特殊奖金