我正在處理以下問題陳述：如果字符串的所有字符出現相同的次數，則該字符串是有效的。如果我們可以只刪除字符串中 1 個索引處的 1 個字符，并且剩余的字符將出現相同的次數，這也是有效的。給定一個字符串 s，判斷它是否有效。如果是，返回YES，否則返回NO。例如，如果s=abc，它是一個有效的字符串，因為頻率是 {a:1,b:1,c:1}。所以是s=abcc因為我們可以刪除一個c并且在剩余的字符串中每個字符都有 1 個。s=abccc 但是，如果字符串無效，因為我們只能刪除 1 次出現 c。這將留下{a:1,b:1,c:2}.我想出了下面的代碼，但它沒有按預期工作，并且在此輸入上失敗abcdefghhgfedecba。它正在打印“NO”，但該輸入應該是“YES”。private static String isValid(String s) { if (s == null || s.equals("")) { return "NO"; } Map<Character, Integer> frequencies = new HashMap<>(); for (char ch : s.toLowerCase().toCharArray()) frequencies.put(ch, frequencies.getOrDefault(ch, 0) + 1); int count = 0; // Iterating over values only for (Integer value : frequencies.values()) { if (value == 2) { count++; } } if (count >= 1) { return "YES"; } return "NO";}我在這里做什么錯了？做到這一點的最佳和有效方法是什么？
3 回答
慕尼黑5688855
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";
}
慕勒3428872
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);
}
}
添加回答
舉報
0/150
提交
取消