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; }
