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

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

题目描述

定义一个函数 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 256
int 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有不同的字符,返回-1
    if (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;
}

说明:

  • 使用两个数组 freq1freq2 来存储两个字符串中每个字符出现的频次。
  • 在统计 s2 的频次时,检查 s1 是否包含 s2 中的每个字符。
  • 遍历两个频次数组,找到各自的最小频次。
  • 返回较小的最小频次。
Python3版本
from collections import Counter
def 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 main
import (
  "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有不同的字符,返回-1
  if 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; // 如果字符在第一个字符串中不存在,标记为true
                continue;
            }
            freqMap.get(c)[1]++; // 更新第二个字符串中的频次
            int minFreq = Math.min(freqMap.get(c)[0], freqMap.get(c)[1]); // 获取当前字符在两个字符串中的最小频次
            minFreqCommon = Math.min(minFreqCommon, minFreq); // 更新最小共同频次
        }
        
        // 如果两个字符串有不同的字符,返回-1
        if (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中的mallocfree来动态分配和释放内存,以及使用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结构体来存储字符和它在两个字符串中的频次。然而,为了简化代码,我们实际上没有使用这个结构体,而是使用了两个整型数组freq1freq2来分别存储两个字符串中每个字符的频次。

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;
        }
    }
    // 如果两个字符串有不同的字符,返回-1
    if (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 Counter
def minFreq(s1: str, s2: str) -> int:
    merged = s1 + s2
    freq_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 -1
    return min_freq
# 示例
s1 = "abcc"
s2 = "aaabbbcc"
result = minFreq(s1, s2)
print(f"The minimum frequency of the smallest character is: {result}")
Golang版本
package main
import (
  "fmt"
)
func minFreq(s1, s2 string) int {
  merged := s1 + s2
  freqMap := 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

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

相关文章
|
6天前
|
机器学习/深度学习 数据采集 搜索推荐
Python基于深度学习算法实现图书推荐系统项目实战
Python基于深度学习算法实现图书推荐系统项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
4天前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
13 5
|
5天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
25 4
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机分类模型(SVC算法)项目实战
|
4天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
10 1
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
Python实现GBDT(梯度提升树)分类模型(GradientBoostingClassifier算法)并应用网格搜索算法寻找最优参数项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
Python实现PCA降维和KNN人脸识别模型(PCA和KNeighborsClassifier算法)项目实战
|
6天前
|
机器学习/深度学习 数据采集 算法
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战
Python实现WOA智能鲸鱼优化算法优化支持向量机回归模型(LinearSVR算法)项目实战