题目:给你一个字符串 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];
}
题目:给你两个整数 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;
}