【经典算法】LeetCode 1170:比较字符串最小字母出现频次(Java/C/Python3实现含注释说明,中等)

2024-04-24 22:36
文章标签 java leetcode 算法 实现 中等 比较 字符串 最小 说明 经典 python3 注释 字母 频次 1170

本文主要是介绍【经典算法】LeetCode 1170:比较字符串最小字母出现频次(Java/C/Python3实现含注释说明,中等)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • 作者主页： 🔗进朱者赤的博客

  • 精选专栏：🔗经典算法

  • 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

  • ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞
    ————————————————-

  • 标签(题目类型)：字符串处理，哈希表

题目描述

定义一个函数 f(s)，统计 s 中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。现在，给你两个字符串数组待查表 queries 和词汇表 words 。
对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。示例 1：输入：queries = ["cbd"], words = ["zaaaz"]
输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
示例 2：输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
提示：1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j]、words[i][j] 都由小写英文字母组成。

原题：LeetCode 1170

思路及实现

方式一

思路

首先，我们需要统计两个字符串中每个字符出现的频次。然后，我们找到两个频次映射中最小的频次。最后，比较这两个最小频次，返回其中较小的一个。如果两个字符串中有不同的字符，则返回-1。

代码实现

Java版本
import java.util.HashMap;
import java.util.Map;public class Solution {public int minFreq(String s1, String s2) {// 统计s1中每个字符出现的频次Map<Character, Integer> freq1 = countFreq(s1);// 统计s2中每个字符出现的频次Map<Character, Integer> freq2 = countFreq(s2);// 检查两个字符串是否有不同的字符if (!freq1.keySet().containsAll(freq2.keySet()) || !freq2.keySet().containsAll(freq1.keySet())) {return -1;}int minFreq1 = Integer.MAX_VALUE;int minFreq2 = Integer.MAX_VALUE;// 找到两个频次映射中的最小频次for (int freq : freq1.values()) {minFreq1 = Math.min(minFreq1, freq);}for (int freq : freq2.values()) {minFreq2 = Math.min(minFreq2, freq);}// 返回较小的最小频次return Math.min(minFreq1, minFreq2);}private Map<Character, Integer> countFreq(String s) {Map<Character, Integer> freq = new HashMap<>();for (char c : s.toCharArray()) {freq.put(c, freq.getOrDefault(c, 0) + 1);}return freq;}
}

说明：

  • countFreq 方法用于统计字符串中每个字符出现的频次。
  • 在 minFreq 方法中，我们首先检查两个字符串是否有不同的字符，如果有，则返回-1。
  • 然后，我们遍历两个频次映射，找到各自的最小频次。
  • 最后，返回两个最小频次中的较小值。
C语言版本
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>#define MAX_CHAR 256int minFreq(char *s1, char *s2) {int freq1[MAX_CHAR] = {0};int freq2[MAX_CHAR] = {0};int minFreq1 = INT_MAX;int minFreq2 = INT_MAX;int hasDiffChar = 0;// 统计s1中每个字符出现的频次for (int i = 0; s1[i]; i++) {freq1[s1[i]]++;}// 统计s2中每个字符出现的频次for (int i = 0; s2[i]; i++) {freq2[s2[i]]++;if (freq1[s2[i]] == 0) {hasDiffChar = 1;}}// 如果s1和s2有不同的字符，返回-1if (hasDiffChar) {return -1;}// 找到两个频次数组中的最小频次for (int i = 0; i < MAX_CHAR; i++) {if (freq1[i] != 0) {minFreq1 = (minFreq1 > freq1[i]) ? freq1[i] : minFreq1;}if (freq2[i] != 0) {minFreq2 = (minFreq2 > freq2[i]) ? freq2[i] : minFreq2;}}// 返回较小的最小频次return (minFreq1 < minFreq2) ? minFreq1 : minFreq2;
}int main() {char s1[] = "abcc";char s2[] = "aabb";printf("The minimum frequency of the smallest character is: %d\n", minFreq(s1, s2));return 0;
}

说明：

  • 使用两个数组 freq1 和 freq2 来存储两个字符串中每个字符出现的频次。
  • 在统计 s2 的频次时，检查 s1 是否包含 s2 中的每个字符。
  • 遍历两个频次数组，找到各自的最小频次。
  • 返回较小的最小频次。
Python3版本
from collections import Counterdef minFreq(s1: str, s2: str) -> int:# 统计s1和s2中每个字符出现的频次freq1 = Counter(s1)freq2 = Counter(s2)# 检查两个字符串是否有不同的字符if not freq1.keys() == freq2.keys():return -1# 找到两个频次映射中的最小频次min_freq1 = min(freq1.values())min_freq2 = min(freq2.values())# 返回较小的最小频次return min(min_freq1, min_freq2)# 测试
s1 = "abcc"
s2 = "aabb"
print(f"The minimum frequency of the smallest character is: {minFreq(s1, s2)}")

说明：

  • 使用Python的内置 Counter 类来统计字符出现的频次。
  • 检查两个 Counter 对象的键是否相同，如果不相同，返回-1。

// 返回较小的最小频次
return (minFreq1 < minFreq2) ? minFreq1 : minFreq2;
}

int main() {
char s1[] = “abcc”;
char s2[] = “aaabbbcc”;
int result = minFreq(s1, s2);
printf(“The minimum frequency of the smallest character is: %d\n”, result);
return 0;
}


> 说明：
> - 使用两个数组 `freq1` 和 `freq2` 来分别统计 `s1` 和 `s2` 中每个字符出现的频次。
> - 遍历 `s2` 的同时检查是否有 `s1` 中不存在的字符，如果有，则设置 `hasDiffChar` 为 1。
> - 在找到最小频次后，比较 `minFreq1` 和 `minFreq2` 并返回较小的值。#### Python3版本```python
from collections import Counterdef minFreq(s1: str, s2: str) -> int:# 统计s1和s2中每个字符出现的频次freq1 = Counter(s1)freq2 = Counter(s2)# 检查两个字符串是否有不同的字符if not freq1.keys() == freq2.keys():return -1# 找到两个频次映射中的最小频次min_freq1 = min(freq1.values())min_freq2 = min(freq2.values())# 返回较小的最小频次return min(min_freq1, min_freq2)# 示例
s1 = "abcc"
s2 = "aaabbbcc"
result = minFreq(s1, s2)
print(f"The minimum frequency of the smallest character is: {result}")

说明：

  • 使用Python的 collections.Counter 来统计字符频次。
  • 检查两个字符串的字符集合是否相同。
  • 找到并返回最小的频次。
Golang版本
package mainimport ("fmt"
)func minFreq(s1, s2 string) int {freq1 := make(map[rune]int)freq2 := make(map[rune]int)minFreq1 := int(^uint(0) >> 1)minFreq2 := int(^uint(0) >> 1)hasDiffChar := false// 统计s1中每个字符出现的频次for _, ch := range s1 {freq1[ch]++}// 统计s2中每个字符出现的频次for _, ch := range s2 {freq2[ch]++if _, ok := freq1[ch]; !ok {hasDiffChar = true}}// 如果s1和s2有不同的字符，返回-1if hasDiffChar {return -1}// 找到两个频次映射中的最小频次for _, freq := range freq1 {if freq < minFreq1 {minFreq1 = freq}}for _, freq := range freq2 {if freq < minFreq2 {minFreq2 = freq}}// 返回较小的最小频次if minFreq1 < minFreq2 {return minFreq1}return minFreq2
}func main() {s1 := "abcc"s2 := "aaabbbcc"result := minFreq(s1, s2)fmt.Printf("The minimum frequency of the smallest character is: %d\n", result)
}

说明：

  • 使用两个map来统计字符频次。
  • 在遍历 s2 的同时检查是否有 s1 中不存在的字符。
  • 找到并返回最小的频次。

复杂度分析

  • 时间复杂度都是O(n + m)，其中n和m分别是两个字符串的长度。因为我们需要遍历两个字符串各一次来统计字符频次。
  • 空间复杂度是O(k)，其中k是字符集的大小（对于ASCII字符集，k=256）。这是因为我们需要一个固定大小的数组或哈希表来存储每个字符的频次。

方式二

思路

我们可以先将两个字符串合并，然后统计合并后字符串中每个字符的出现频次。接着，找到最小的频次，并确保这个最小频次在两个原字符串中都有出现（即最小频次对应的字符在两个字符串中都有）。如果两个字符串中有不同的字符，则返回-1。

代码实现

Java版本

在Java中，可以使用HashMap来存储每个字符在两个字符串中出现的频次。之后，可以遍历HashMap找到共同存在的最小频次。

import java.util.HashMap;
import java.util.Map;public class MinFrequency {/*** 找到两个字符串中共同存在的最小字符频次。* 如果两个字符串有不同的字符，返回-1。** @param s1 第一个字符串* @param s2 第二个字符串* @return 最小字符频次，或-1（如果字符集不同）*/public static int minFreq(String s1, String s2) {// 使用HashMap存储字符频次，键为字符，值为字符在两个字符串中的频次对Map<Character, int[]> freqMap = new HashMap<>();// 遍历第一个字符串，统计字符频次（只记录频次，不区分字符串）for (char c : s1.toCharArray()) {freqMap.putIfAbsent(c, new int[2]); // 如果字符不存在，则初始化频次对为[0, 0]freqMap.get(c)[0]++; // 更新第一个字符串中的频次}// 遍历第二个字符串，更新字符频次并检查字符是否存在于第一个字符串中int minFreqCommon = Integer.MAX_VALUE; // 初始化最小共同频次为最大值boolean hasDiffChar = false; // 标记是否有不同的字符for (char c : s2.toCharArray()) {if (!freqMap.containsKey(c)) {hasDiffChar = true; // 如果字符在第一个字符串中不存在，标记为truecontinue;}freqMap.get(c)[1]++; // 更新第二个字符串中的频次int minFreq = Math.min(freqMap.get(c)[0], freqMap.get(c)[1]); // 获取当前字符在两个字符串中的最小频次minFreqCommon = Math.min(minFreqCommon, minFreq); // 更新最小共同频次}// 如果两个字符串有不同的字符，返回-1if (hasDiffChar) {return -1;}// 返回最小共同频次return minFreqCommon == Integer.MAX_VALUE ? -1 : minFreqCommon;}public static void main(String[] args) {String s1 = "abcc";String s2 = "aaabbbcc";int result = minFreq(s1, s2);System.out.println("The minimum frequency of the smallest common character is: " + result);}
}

说明：

  • 在这个Java实现中，我们使用了HashMap<Character, int[]>来存储每个字符在两个字符串中的频次对。int[]数组的第一个元素存储字符在s1中的频次，第二个元素存储字符在s2中的频次。
  • 我们首先遍历s1来初始化freqMap，并只记录字符的频次，不区分它来自哪个字符串。然后，我们遍历s2，同时更新字符在s2中的频次，并检查字符是否存在于s1中。如果字符在s1中不存在，我们将hasDiffChar标记为true。同时，我们计算每个字符在两个字符串中的最小频次，并更新minFreqCommon为当前找到的最小值。
  • 最后，我们检查hasDiffChar是否为true，如果是，则返回-1；否则，返回minFreqCommon作为最小共同频次。注意，如果minFreqCommon没有被任何字符的最小频次更新过（即仍然是初始值Integer.MAX_VALUE），我们也返回-1。
C语言版本

的C语言版本可以使用stdlib.h中的malloc和free来动态分配和释放内存，以及使用string.h中的函数来处理字符串。下面是一个简单的C语言实现，该实现使用哈希表来统计两个字符串中每个字符的频次，并找出最小共同频次。

请注意，C语言标准库并没有直接提供哈希表，因此我们需要自己实现一个简单的哈希表或者使用结构体数组来模拟哈希表的行为：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>#define HASH_SIZE 256 // 假设ASCII字符集typedef struct {char ch;int freq1; // 字符在s1中出现的频次int freq2; // 字符在s2中出现的频次
} CharFreq;CharFreq hashTable[HASH_SIZE];// 初始化哈希表
void initHashTable() {memset(hashTable, 0, sizeof(hashTable));
}// 哈希函数，简单使用字符的ASCII值作为索引
unsigned int hash(char c) {return (unsigned int)c;
}// 更新字符频次
void updateFreq(const char *str, int *freq) {for (int i = 0; str[i] != '\0'; i++) {unsigned int index = hash(str[i]);freq[index]++;}
}// 找到最小共同频次
int findMinCommonFreq(const char *s1, const char *s2) {initHashTable();int freq1[HASH_SIZE] = {0};int freq2[HASH_SIZE] = {0};// 更新s1中字符的频次updateFreq(s1, freq1);// 更新s2中字符的频次，并查找最小共同频次int minCommonFreq = INT_MAX;for (int i = 0; s2[i] != '\0'; i++) {unsigned int index = hash(s2[i]);if (freq1[index] == 0) {// 如果s2中的字符在s1中不存在，则无法找到共同频次return -1;}int commonFreq = freq1[index] < freq2[index] ? freq1[index] : freq2[index];minCommonFreq = commonFreq < minCommonFreq ? commonFreq : minCommonFreq;freq2[index]++;}return (minCommonFreq == INT_MAX) ? -1 : minCommonFreq;
}int main() {const char *s1 = "abcc";const char *s2 = "aaabbbcc";int minFreq = findMinCommonFreq(s1, s2);if (minFreq != -1) {printf("The minimum frequency of the smallest common character is: %d\n", minFreq);} else {printf("No common character found in both strings.\n");}return 0;
}

说明：
这个C语言实现中，我们定义了一个CharFreq结构体来存储字符和它在两个字符串中的频次。然而，为了简化代码，我们实际上没有使用这个结构体，而是使用了两个整型数组freq1和freq2来分别存储两个字符串中每个字符的频次。
hash函数简单地将字符的ASCII值作为哈希索引。在实际情况中，可能需要一个更复杂的哈希函数来减少哈希冲突。
updateFreq函数遍历字符串并更新对应字符的频次。
findMinCommonFreq函数首先初始化哈希表和频次数组，然后分别更新两个字符串中字符的频次，并查找最小共同频次。如果两个字符串中有不同的字符，则返回-1。
在main函数中，我们调用findMinCommonFreq并打印结果。如果结果为-1，则表示两个字符串中没有共同字符。

C++版本

由于c语言着实太麻烦了，下面单独补充c++的版本

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>int minFreq(std::string s1, std::string s2) {std::string merged = s1 + s2;std::unordered_map<char, int> freqMap;int minFreq = INT_MAX;// 统计合并后字符串中每个字符的频次for (char c : merged) {freqMap[c]++;}// 遍历频次映射，找到最小频次for (const auto& pair : freqMap) {char c = pair.first;int freq = pair.second;// 检查最小频次对应的字符是否在两个字符串中都出现过if (freqMap[c] >= merged.size() / 2 && freq < minFreq) {minFreq = freq;}}// 如果两个字符串有不同的字符，返回-1if (s1.find_first_not_of(s2) != std::string::npos || s2.find_first_not_of(s1) != std::string::npos) {return -1;}return minFreq;
}int main() {std::string s1 = "abcc";std::string s2 = "aaabbbcc";int result = minFreq(s1, s2);std::cout << "The minimum frequency of the smallest character is: " << result << std::endl;return 0;
}
Python3版本
from collections import Counterdef minFreq(s1: str, s2: str) -> int:merged = s1 + s2freq_map = Counter(merged)min_freq = float('inf')# 找到最小频次，并检查该字符是否在两个字符串中都出现过for char, freq in freq_map.items():if freq >= len(merged) // 2 and freq < min_freq:min_freq = freq# 检查两个字符串是否有不同的字符if set(s1) != set(s2):return -1return min_freq# 示例
s1 = "abcc"
s2 = "aaabbbcc"
result = minFreq(s1, s2)
print(f"The minimum frequency of the smallest character is: {result}")
Golang版本
package mainimport ("fmt"
)func minFreq(s1, s2 string) int {merged := s1 + s2freqMap := make(map[rune]int)minFreq := int(^uint(0) >> 1)// 统计合并后字符串中每个字符的频次for _, ch := range merged {freqMap[ch]++}// 遍历频次映射，找到最小频次for _, freq := range freqMap {if freq >= len(merged)/2 && freq < minFreq {minFreq = freq}}// 检查两个字符串是否有不同的字符if len(s1) != len(s2) || s1 != s2 {return -1}return minFreq
}func main() {s1 := "abcc"s2 := "aaabbbcc"result := minFreq(s1, s2)fmt.Printf("The minimum frequency of the smallest character is: %d\n", result)
}

复杂度分析

总结

方式优点缺点时间复杂度空间复杂度
方式一不依赖内建函数，灵活性强，可适用于不同数据结构和需求代码量较大，实现相对复杂，需要手动处理字符频次统计和比较O(m + n)O(k)，其中k是字符集大小
方式二代码简洁，易于理解，利用内建函数简化操作依赖内建函数，可能不是最优解，合并字符串增加了空间和时间开销O(m + n)O(m + n)
优化后的方式二避免了合并字符串的开销，直接在遍历过程中统计频次仍然依赖内建函数，但减少了不必要的合并操作O(m + n)O(k)，其中k是字符集大小

相似题目

相似题目难度链接
leetcode 349 两个数组的交集简单力扣-349
leetcode 350 两个数组的交集 II简单力扣-350
leetcode 242 有效的字母异位词简单力扣-242
leetcode 567 字符串的排列中等力扣-567
leetcode 451 排序字符串中的元音字母简单力扣-451

这些题目都与字符频次统计、字符串比较和数组交集相关，可以通过类似的方法解决。在解决这些题目时，可以根据具体需求选择合适的方式，比如利用哈希表统计频次、使用排序或者双指针等技巧。

欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

  • 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

  • —⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—

这篇关于【经典算法】LeetCode 1170:比较字符串最小字母出现频次(Java/C/Python3实现含注释说明,中等)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/933020。

相关文章

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》：本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI
阅读更多...
Python脚本实现自动删除C盘临时文件夹

Python脚本实现自动删除C盘临时文件夹

《Python脚本实现自动删除C盘临时文件夹》在日常使用电脑的过程中,临时文件夹往往会积累大量的无用数据,占用宝贵的磁盘空间,下面我们就来看看Python如何通过脚本实现自动删除C盘临时文件夹吧... 目录一、准备工作二、python脚本编写三、脚本解析四、运行脚本五、案例演示六、注意事项七、总结在日常使用
阅读更多...
Java实现Excel与HTML互转

Java实现Excel与HTML互转

《Java实现Excel与HTML互转》Excel是一种电子表格格式,而HTM则是一种用于创建网页的标记语言,虽然两者在用途上存在差异,但有时我们需要将数据从一种格式转换为另一种格式,下面我们就来看看... Excel是一种电子表格格式，广泛用于数据处理和分析，而HTM则是一种用于创建网页的标记语言。虽然两
阅读更多...
java图像识别工具类(ImageRecognitionUtils)使用实例详解

java图像识别工具类(ImageRecognitionUtils)使用实例详解

《java图像识别工具类(ImageRecognitionUtils)使用实例详解》：本文主要介绍如何在Java中使用OpenCV进行图像识别,包括图像加载、预处理、分类、人脸检测和特征提取等步骤... 目录前言1. 图像识别的背景与作用2. 设计目标3. 项目依赖4. 设计与实现 ImageRecogni
阅读更多...
Java中Springboot集成Kafka实现消息发送和接收功能

Java中Springboot集成Kafka实现消息发送和接收功能

《Java中Springboot集成Kafka实现消息发送和接收功能》Kafka是一个高吞吐量的分布式发布-订阅消息系统,主要用于处理大规模数据流,它由生产者、消费者、主题、分区和代理等组件构成,Ka... 目录一、Kafka 简介二、Kafka 功能三、POM依赖四、配置文件五、生产者六、消费者一、Kaf
阅读更多...
Java访问修饰符public、private、protected及默认访问权限详解

Java访问修饰符public、private、protected及默认访问权限详解

《Java访问修饰符public、private、protected及默认访问权限详解》：本文主要介绍Java访问修饰符public、private、protected及默认访问权限的相关资料,每... 目录前言1. public 访问修饰符特点：示例：适用场景：2. private 访问修饰符特点：示例：
阅读更多...
详解Java如何向http/https接口发出请求

详解Java如何向http/https接口发出请求

《详解Java如何向http/https接口发出请求》这篇文章主要为大家详细介绍了Java如何实现向http/https接口发出请求,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 用Java发送web请求所用到的包都在java.net下，在具体使用时可以用如下代码，你可以把它封装成一
阅读更多...
使用Python实现在Word中添加或删除超链接

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中，超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超
阅读更多...
windos server2022里的DFS配置的实现

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS？优势：应用场景：DFS配置步骤什么是DFS？DFS指的是分布式文件系统（Distr
阅读更多...
NFS实现多服务器文件的共享的方法步骤

NFS实现多服务器文件的共享的方法步骤

《NFS实现多服务器文件的共享的方法步骤》NFS允许网络中的计算机之间共享资源,客户端可以透明地读写远端NFS服务器上的文件,本文就来介绍一下NFS实现多服务器文件的共享的方法步骤,感兴趣的可以了解一... 目录一、简介二、部署1、准备1、服务端和客户端：安装nfs-utils2、服务端：创建共享目录3、服
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2