jsp和html做的招聘网站,怎么把别人网站模板下载出来,室内装修设计师,烟台芝罘区住房建设局网站文章目录 题目描述与示例题目描述输入描述输入描述 示例一输入输出说明 示例二输入输出说明 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
有一个字符串数组 words 和一个字符串 chars 。
假如可以用 chars 中的字… 文章目录 题目描述与示例题目描述输入描述输入描述 示例一输入输出说明 示例二输入输出说明 解题思路代码PythonJavaC时空复杂度 华为OD算法/大厂面试高频题算法练习冲刺训练 题目描述与示例
题目描述
有一个字符串数组 words 和一个字符串 chars 。
假如可以用 chars 中的字母拼写出 words 中的某个“单词”字符串那么我们就认为你掌握了这个单词。
words 的字符仅由 a-z 英文小写字母组成例如 “abc” chars 由 a-z 英文小写字母和 “?” 组成。其中英文问号 “?” 表示万能字符能够在拼写时当做任意一个英文字母。例如“?” 可以当做 “a” 等字母。
注意每次拼写时chars 中的每个字母和万能字符都只能使用一次。
输出词汇表 words 中你掌握的所有单词的个数。没有掌握任何单词则输出 0。
输入描述
第 1 行输入数组 words 的个数记为 N。 从第 2 行开始到第 N1 行一次输入数组 words 的每个字符串元素。 第 N2 行输入字符串 chars。
输入描述
输出一个整数表示词汇表 words 中你掌握的单词个数。
示例一
输入
4
cat
bt
hat
tree
atach输出
2说明
atach可以拼写出单词cat和hat因此掌握的单词是2个。
示例二
输入
4
cat
bt
hat
tree
at?ch输出
3说明
at?ch可以拼写出单词cat、hat和bt因此掌握的单词是3个。
解题思路
统计元素频率很显然需要使用哈希表进行。
唯一需要特殊处理的就是字符?可以代表万能字符。
假设某一单词word和字符串chars对应的计数器分别为cnt_word和cnt_chars问号字符?出现的次数为num。那么在逐一比较word中字符出现次数和chars中元素出现字符时若出现cnt_word[k] cnt_chars[k]则可以使用cnt_word[k] - cnt_chars[k]个?来作为万能字符。若发现此时?出现的次数为num已经小于cnt_word[k] - cnt_chars[k]则无法拼凑出单词word。
代码
Python
# 题目【哈希表】2023C-掌握单词个数
# 分值100
# 作者许老师-闭着眼睛学数理化
# 算法哈希表
# 代码看不懂的地方请直接在群上提问# 检查cnt_chars能否完全拼写出cnt_word的函数
# 其中num为cnt_chars中问号字符的个数
def check(cnt_chars, cnt_word, num):# 遍历cnt_word中的所有键kfor k in cnt_word.keys():# 如果chars中k出现的个数大于等于word# 则可以直接使用这些字符k来拼写出word中的kif cnt_chars[k] cnt_word[k]:continue# 如果chars中k出现的个数小于wordelse:# 则需要使用cnt_word[k] - cnt_chars[k]个万能字符# 才能使得字符k能够被在chars中被全部拼写num - cnt_word[k] - cnt_chars[k]# 若使用完之后num的个数小于0则说明万能字符的个数不足# 不可能完成拼写# 直接返回Falseif num 0:return False# 如果能够顺利退出上述循环即通过了检查返回Truereturn Truefrom collections import Counter# 输入words的个数
n int(input())
words list()
# 循环n次输入n个单词
for _ in range(n):words.append(input())# 输入chars字符串
chars input()# 获得chars字符串对应的元素频率哈希表
cnt_chars Counter(chars)ans 0
# 获得chars中问号字符的个数
num cnt_chars[?]# 遍历words中的每一个单词word
for word in words:# 构建word对应的哈希表计数器cnt_word Counter(word)# 调用check函数将结果加入ans中ans int(check(cnt_chars, cnt_word, num))print(ans)Java
import java.util.*;public class Main {static boolean check(HashMapCharacter, Integer cntChars, HashMapCharacter, Integer cntWord, int num) {for (char k : cntWord.keySet()) {if (cntChars.getOrDefault(k, 0) cntWord.getOrDefault(k, 0)) {continue;} else {num - cntWord.getOrDefault(k, 0) - cntChars.getOrDefault(k, 0);if (num 0) {return false;}}}return true;}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n Integer.parseInt(scanner.nextLine());ListString words new ArrayList();for (int i 0; i n; i) {words.add(scanner.nextLine());}String chars scanner.nextLine();HashMapCharacter, Integer cntChars new HashMap();for (char c : chars.toCharArray()) {cntChars.put(c, cntChars.getOrDefault(c, 0) 1);}int ans 0;int num cntChars.getOrDefault(?, 0);for (String word : words) {HashMapCharacter, Integer cntWord new HashMap();for (char c : word.toCharArray()) {cntWord.put(c, cntWord.getOrDefault(c, 0) 1);}ans check(cntChars, cntWord, num) ? 1 : 0;}System.out.println(ans);}
}C
#include iostream
#include unordered_map
#include vector
using namespace std;bool check(unordered_mapchar, int cntChars, unordered_mapchar, int cntWord, int num) {for (auto kv : cntWord) {char k kv.first;if (cntChars[k] cntWord[k]) {continue;} else {num - cntWord[k] - cntChars[k];if (num 0) {return false;}}}return true;
}int main() {int n;cin n;cin.ignore(); // To consume the newline charactervectorstring words(n);for (int i 0; i n; i) {cin words[i];}cin.ignore(); // To consume the newline characterstring chars;getline(cin, chars);unordered_mapchar, int cntChars;for (char c : chars) {cntChars[c];}int ans 0;int num cntChars[?];for (string word : words) {unordered_mapchar, int cntWord;for (char c : word) {cntWord[c];}ans check(cntChars, cntWord, num) ? 1 : 0;}cout ans endl;return 0;
}时空复杂度
时间复杂度O(NM)。其中M为每一个单词word的字符种类个数最高为26。单次调用check()函数的时间复杂度为O(M)。
空间复杂度O(N)。 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
