【经典算法】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。

相关文章

使用Redis快速实现共享Session登录的详细步骤

使用Redis快速实现共享Session登录的详细步骤

《使用Redis快速实现共享Session登录的详细步骤》在Web开发中,Session通常用于存储用户的会话信息,允许用户在多个页面之间保持登录状态,Redis是一个开源的高性能键值数据库,广泛用于... 目录前言实现原理：步骤：使用Redis实现共享Session登录1. 引入Redis依赖2. 配置R
阅读更多...
SpringBoot实现RSA+AES自动接口解密的实战指南

SpringBoot实现RSA+AES自动接口解密的实战指南

《SpringBoot实现RSA+AES自动接口解密的实战指南》在当今数据泄露频发的网络环境中,接口安全已成为开发者不可忽视的核心议题,RSA+AES混合加密方案因其安全性高、性能优越而被广泛采用,本... 目录一、项目依赖与环境准备1.1 Maven依赖配置1.2 密钥生成与配置二、加密工具类实现2.1
阅读更多...
在Java中实现线程之间的数据共享的几种方式总结

在Java中实现线程之间的数据共享的几种方式总结

《在Java中实现线程之间的数据共享的几种方式总结》在Java中实现线程间数据共享是并发编程的核心需求,但需要谨慎处理同步问题以避免竞态条件,本文通过代码示例给大家介绍了几种主要实现方式及其最佳实践,... 目录1. 共享变量与同步机制2. 轻量级通信机制3. 线程安全容器4. 线程局部变量（ThreadL
阅读更多...
python使用Akshare与Streamlit实现股票估值分析教程（图文代码）

python使用Akshare与Streamlit实现股票估值分析教程（图文代码）

《python使用Akshare与Streamlit实现股票估值分析教程（图文代码）》入职测试中的一道题,要求:从Akshare下载某一个股票近十年的财务报表包括,资产负债表,利润表,现金流量表,保存... 目录一、前言二、核心知识点梳理1、Akshare数据获取2、Pandas数据处理3、Matplotl
阅读更多...
分布式锁在Spring Boot应用中的实现过程

分布式锁在Spring Boot应用中的实现过程

《分布式锁在SpringBoot应用中的实现过程》文章介绍在SpringBoot中通过自定义Lock注解、LockAspect切面和RedisLockUtils工具类实现分布式锁,确保多实例并发操作... 目录Lock注解LockASPect切面RedisLockUtils工具类总结在现代微服务架构中，分布
阅读更多...
Java使用Thumbnailator库实现图片处理与压缩功能

Java使用Thumbnailator库实现图片处理与压缩功能

《Java使用Thumbnailator库实现图片处理与压缩功能》Thumbnailator是高性能Java图像处理库,支持缩放、旋转、水印添加、裁剪及格式转换,提供易用API和性能优化,适合Web应... 目录1. 图片处理库Thumbnailator介绍2. 基本和指定大小图片缩放功能2.1 图片缩放的
阅读更多...
Spring Boot集成/输出/日志级别控制/持久化开发实践

Spring Boot集成/输出/日志级别控制/持久化开发实践

《SpringBoot集成/输出/日志级别控制/持久化开发实践》SpringBoot默认集成Logback,支持灵活日志级别配置（INFO/DEBUG等）,输出包含时间戳、级别、类名等信息,并可通过... 目录一、日志概述1.1、Spring Boot日志简介1.2、日志框架与默认配置1.3、日志的核心作用
阅读更多...
Python使用Tenacity一行代码实现自动重试详解

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门：一行代码实现优雅重试精细控制：让重试按我
阅读更多...
破茧 JDBC:MyBatis 在 Spring Boot 中的轻量实践指南

破茧 JDBC:MyBatis 在 Spring Boot 中的轻量实践指南

《破茧JDBC:MyBatis在SpringBoot中的轻量实践指南》MyBatis是持久层框架,简化JDBC开发,通过接口+XML/注解实现数据访问,动态代理生成实现类,支持增删改查及参数... 目录一、什么是 MyBATis二、 MyBatis 入门2.1、创建项目2.2、配置数据库连接字符串2.3、入
阅读更多...
Springboot项目启动失败提示找不到dao类的解决

Springboot项目启动失败提示找不到dao类的解决

《Springboot项目启动失败提示找不到dao类的解决》SpringBoot启动失败,因ProductServiceImpl未正确注入ProductDao,原因：Dao未注册为Bean,解决：在启... 目录错误描述原因解决方法总结***************************APPLICA编
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2