3 回答

TA贡献1848条经验 获得超2个赞
下面的代码工作正常。我在这里做的是将每个字符的频率存储在一个数组中,然后将其转换为列表,因为我们将需要稍后的时间点。接下来我将列表转换为设置并从中删除零,因为列表中将存在与输入字符串中不存在的字符相对应的零。如果 set 在删除零后只有一个元素意味着所有元素都具有相同的频率,因此返回 true。如果 set 有两个以上的元素意味着我们无法通过在一个地方删除一个字符来使其成为有效字符串,因此返回 false. 现在,如果 set 有两个值,我们从 set 中取最小值和最大值。如果有一个频率是第一个 if 条件的字符,我们可以使它有效。现在第二个条件是,如果差异 b/w max 和 min 为 1 并且 max 只有一个频率,那么我们可以从 max 中删除一个字符并使其有效。
static String isValid(String s) {
Integer arr[] = new Integer[26];
Arrays.fill(arr, 0);
//fill the frequency of every character in array arr
for (int i = 0; i < s.length(); i++) {
arr[s.charAt(i) - 97]++;
}
//convert array to list of integer
List<Integer> arrList = Arrays.asList(arr);
//convert list to set and remove zero bcos zero correspond to char that is not present
HashSet<Integer> set = new HashSet<Integer>(arrList);
set.remove(new Integer(0));
int len = set.size();
// if size==1 means all freq are same
if (len == 1)
return "YES";
else if (len == 2) {
List<Integer> list = new ArrayList<>(set);
int x = list.get(0);
int y = list.get(1);
int max = (x > y) ? x : y;
int min = (x < y) ? x : y;
// if min elemnnt has value one and freuency one
if (Collections.frequency(arrList, min) == 1 && min == 1) {
return "YES";
}
//if max-min==1 and there are only one elemnt with value=max
else if (max - min == 1) {
if ((Collections.frequency(arrList, max) == 1)) {
return "YES";
} else {
return "NO";
}
}
// if no of element is more than
else {
return "NO";
}
} else
return "NO";
}

TA贡献1848条经验 获得超6个赞
计算频率是正确的想法,尽管我不确定您为什么要检查地图中的值是否为2
. 一旦我计算了这些频率,我将创建一个具有每个频率的字符数的反向映射,然后:
如果地图的大小为 1,则表示所有字符具有相同的频率 - 字符串有效。
如果集合的大小为 2:
如果最小频率为 1 并且只有一个字符具有该频率,则该字符串有效,因为可以简单地删除该字符
如果最小频率比最大频率小 1,并且只有一个字符具有最大频率,则该字符串有效,因为可以删除该字符。
在任何其他情况下,该字符串将无效。
private static boolean isValid(String s) {
TreeMap<Long, Long> frequencyCounts =
s.chars()
.boxed()
// Frequency map
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
.values()
.stream()
// Frequency of frequencies map
.collect(Collectors.groupingBy
(Function.identity(),
TreeMap::new,
Collectors.counting()));
if (frequencyCounts.size() == 1) {
return true;
}
if (frequencyCounts.size() == 2) {
Iterator<Map.Entry<Long, Long>> iter = frequencyCounts.entrySet().iterator();
Map.Entry<Long, Long> minEntry = iter.next();
long minFrequency = minEntry.getKey();
long numMinFrequency = minEntry.getValue();
if (minFrequency == 1L && numMinFrequency == 1L) {
return true;
}
Map.Entry<Long, Long> maxEntry = iter.next();
long maxFrequency = maxEntry.getKey();
long numMaxFrequency = maxEntry.getValue();
if (numMaxFrequency == 1L && maxFrequency == minFrequency + 1L) {
return true;
}
}
return false;
}
编辑:
为了回答评论中的问题,频率图和“频率频率”图也可以用 Java 7 的语法构造,尽管它可能不那么优雅:
Map<Character, Long> frequencies = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
if (frequencies.containsKey(c)) {
frequencies.put(c, frequencies.get(c) + 1L);
} else {
frequencies.put(c, 1L);
}
}
TreeMap<Long, Long> frequencyCounts = new TreeMap<>();
for (Long freq : frequencies.values()) {
if (frequencyCounts.containsKey(freq)) {
frequencyCounts.put(freq, frequencyCounts.get(freq) + 1L);
} else {
frequencyCounts.put(freq, 1L);
}
}
添加回答
举报