leetcode
leetcode 2101 ~ 2150
删除字符使频率相同

删除字符使频率相同

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.0 MB


/*
 * 思路:
 * 1. 使用流处理计算字母频率。
 * 2. 统计频率分布。
 * 3. 判断是否满足题目要求的频率情况。
 */

import java.util.Map;
import java.util.stream.Collectors;

public class SolutionStream {
    public boolean equalFrequency(String word) {
        Map<Character, Long> freqMap = word.chars()
                .mapToObj(c -> (char) c)
                .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
        Map<Long, Long> countMap = freqMap.values().stream()
                .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
        if (countMap.size() == 1 && countMap.containsKey(1L)) {
            return true;
        }
        if (countMap.size() == 2) {
            long minFreq = countMap.keySet().stream().min(Long::compare).orElse(0L);
            long maxFreq = countMap.keySet().stream().max(Long::compare).orElse(0L);
            if (minFreq == 1 && countMap.get(minFreq) == 1) {
                return true;
            }
            if (maxFreq == minFreq + 1 && countMap.get(maxFreq) == 1) {
                return true;
            }
        }
        return false;
    }
}

解释

方法:

这个题解的核心思路是尝试删除字符串中任一字符,然后检查剩余字符的频率是否一致。首先,利用Counter统计字符串中每个字符的出现频率,然后将这些频率排序。之后,算法尝试两种可能的删除方式:1)删除出现频率最少的字符后检查剩余字符的频率是否一致;2)删除出现频率最多的字符后检查剩余字符的频率是否一致。如果其中任一操作后所有字符的频率都相同,则返回true,否则返回false。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么题解中提到尝试删除频率最少和最多的字符,而没有考虑删除其他位置的字符?
这种策略基于一个观察,即影响字符频率统一性的往往是频率最高和最低的字符。删除频率最少的字符可能会将其频率降至0,从而可能帮助实现其它字符频率的一致性。同理,删除频率最高的字符可能会降低频率差异,使其他字符的频率更接近。这种方法是基于减少频率差异的最直接方式,而删除中间频率的字符通常不会直接影响频率的一致性,因此效率较低,不是首选策略。
🦆
在恢复初始状态并尝试删除最大频率的字符后,是否需要重新排序lc列表?
不需要重新排序lc列表。因为仅仅是对列表中的一个元素进行增减,这不会改变列表中元素的相对顺序。即使是对最小或最大频率的元素进行修改,只要这些修改不导致元素之间的顺序关系改变(例如从大到小变为从小到大),原来的排序状态依然有效。
🦆
当删除一个字符后,如果剩余字符的频率不完全一致但差异很小(例如一种频率多一个),这种情况下算法是否还能正确处理?
算法设计是为了检查删除一个字符后是否可以使所有剩余字符的频率完全相同。如果存在小的频率差异(例如一个字符的频率比其他字符多一个),则该算法还是会返回false,因为它严格要求所有的频率必须一致。对于这种情况,算法不会误判,但也不会提供容错处理,即不考虑接近但不完全相同的频率情况。
🦆
算法在检查剩余字符频率是否相同时使用了filter函数和set函数,这种方法在何种情况下可能会导致错误判断?
使用filter和set函数进行频率检查通常是安全的,因为filter函数用于移除频率中的零值(即完全删除的字符),而set用于检查频率的唯一性。潜在的问题可能出现在不正确处理元素频率为0的情况,或者误解set函数的功能,误以为它能处理除0以外的细微频率差异。只要正确实现,这种方法不会导致错误判断。

相关问题