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数组中的值，即说明当前字符串符合题意，记录此下标；注意在记录下标前，还要比较当前字符串与上一个记录的字符串的长度，取长度较小的字符串；
代码语言：javascript复制 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；
代码语言：javascript复制 //判断是否是质数
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;
}
