leetcode
leetcode 1101 ~ 1150
比较字符串最小字母出现频次

比较字符串最小字母出现频次

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 16.5 MB


/*
 * 思路:
 * 1. 定义函数f(s)来计算字符串s中字典序最小字母的出现频次。
 * 2. 使用Java Stream API来处理queries和words数组。
 * 3. 对于每个查询queries[i],计算其f值,并统计满足f(queries[i]) < f(words[j])的词的数量。
 * 4. 返回结果数组。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public static int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] wordFreqs = Arrays.stream(words).mapToInt(Solution::f).toArray();
        return Arrays.stream(queries)
                     .mapToInt(query -> (int) Arrays.stream(wordFreqs)
                                                  .filter(wordFreq -> f(query) < wordFreq)
                                                  .count())
                     .toArray();
    }

    private static int f(String s) {
        return s.chars()
                .mapToObj(c -> (char) c)
                .collect(Collectors.groupingBy(c -> c, Collectors.counting()))
                .entrySet()
                .stream()
                .min(Map.Entry.comparingByKey())
                .map(Map.Entry::getValue)
                .orElse(0L)
                .intValue();
    }

    public static void main(String[] args) {
        String[] queries = {"cbd"};
        String[] words = {"zaaaz"};
        System.out.println(Arrays.toString(numSmallerByFrequency(queries, words)));
    }
}

解释

方法:

此题解采用了前缀和的思想。首先,定义一个辅助函数 f(s),用于计算字符串 s 中按字典序最小的字母出现的次数。然后,对于词汇表 words 中的每个单词,计算其 f 值,并将对应的计数值加 1,存储在一个长度为 12 的数组 count 中,因为单词的最大长度为 10,所以 f 值的范围是 1 到 10。接着,从后往前对 count 数组进行累加,使得 count[i] 表示 f 值大于等于 i 的单词数量。最后,对于每个查询,通过查询 count 数组得到满足条件的单词数量。

时间复杂度:

O(nL + m)

空间复杂度:

O(m)

代码细节讲解

🦆
为什么在处理count数组时选择从后向前累加而不是从前向后?
在处理count数组时,选择从后向前累加是为了计算前缀和,具体地,这样可以使count[i]表示所有f值大于等于i的单词数量。如果从前向后累加,我们将得到后缀和,这不符合题目需要查询的条件,即查询所有f值大于某个特定值的单词数量。从后向前累加可以直接在查询时通过count[f(s) + 1]得到满足条件的单词数量,这样更直接有效。
🦆
在函数f中,为什么选择用'z'作为初始的ch变量,这里有没有其他字符作为起始值的可能性?
在函数f中,选择'z'作为初始的ch变量是因为'z'是英文字母表中字典序最大的字母。这样做的目的是为了在遍历字符串s的过程中,任何一个字母都不会比'z'大,从而确保能够正确地找到最小的字母。理论上,任何大于或等于's'中最小字母的字符都可以作为初始值,但使用'z'是一个保守而安全的选择,因为它简化了逻辑且总是可行的。
🦆
count数组长度为12的具体依据是什么,考虑到单词最大长度为10,为何不是长度为11?
count数组长度设为12而非11是为了方便处理边界情况,具体地,在计算查询结果时,我们需要访问count[f(s) + 1]。如果f(s)的最大值为10,那么f(s) + 1的最大值为11。如果数组长度只有11,那么访问count[11]将会越界。因此,将数组长度设为12可以避免这种越界错误,确保代码的安全和正确执行。
🦆
在实际编码中,如何保证每个单词的长度都不超过10,是否有必要在输入时进行检查?
在实际编码中,确保每个单词的长度不超过10通常需要在输入处理阶段进行检查。这是因为如果输入数据不符合预期的约束,可能会导致程序错误或异常行为。进行长度检查可以增加程序的健壮性,防止因输入不符导致的问题。在函数或方法的开始部分添加检查逻辑,如果发现任何单词长度超过10,可以抛出异常或返回错误信息,从而确保后续逻辑处理的正确性和稳定性。

相关问题