Abu*_*nka 6 html javascript string algorithm node.js
我这里有一个小问题。我正在解决我书中的一些随机问题。这是任务：
任务
平衡字符串是字符串中每个字符出现的次数与其他字符相同的字符串。例如，“ ab ”、“ aaabbb ”和“ ababaabb ”是平衡的，而“ abb ”和“ abbbaa ”则不是。
此外，字符串还可能包含通配符“*”。此通配符可以代表您希望的任何其他字符。此外，通配符必须代表另一个字符；它们不能闲置不用。百搭平衡字符串是这样一种字符串，其中所有通配符都可以通过这种方式转换为字符以生成简单的平衡字符串。
这个挑战涉及编写一个函数 balance(s) 来检查 s 是否平衡。
输入仅限于包含大小写字母字符和“*”通配符的字符串。输入字符串将匹配正则表达式
^[A-Za-z*] $ *
其他例子：
平衡（“a”）？真的
平衡（“ab”）？真的
平衡（“abc”）？真的
平衡（“abcb”）？错误的
平衡（“Aaa”）？错误的
平衡（“***********”）？真的
我已经能够得到一些答案，但我的算法真的让我失望。我在想是否有什么我可以做的来调整这段代码：
function balanced(s) {
const cMap = {};
for (let c of s) {
cMap[c] ? cMap[c]++ : (cMap[c] = 1);
}
const freq = new Set(Object.values(cMap));
if(s.includes('*')){
return true;
}
if (freq.size === 0 || freq.size === 1){
return true;
}
if (freq.size === 1) {
const max = Math.max(...freq);
const min = Math.min(...freq);
}
return false;
}
思考这个问题的另一种方法是简单地做一些算术。为了平衡，替换星号后的每个唯一字符必须出现相同的次数。因此，次数 ( counts) 乘以唯一字符数 ( letters) 必须等于输入字符串的长度（包括星号）。这count必须至少与单个字符的最大计数一样大。输出中的的数量letters必须至少与输入中唯一字母的数量一样大。唯一的其他限制是，由于字母取自小写和大写字母，因此它们的数量不能超过 52 个。
换句话说：
A string (of length `n`) is balanceable if
there exist positive integers `count` and `letters`
such that
`count` * `letters` = `n` and
`letters` <= 52 and
`letters` >= number of unique letters in the input (ignoring asterisks) and
`count` >= max of the counts of each individual (non-asterisk) letter in the input
通过辅助函数来查找数字的所有因子对，我们可以直接编写以下逻辑：
A string (of length `n`) is balanceable if
there exist positive integers `count` and `letters`
such that
`count` * `letters` = `n` and
`letters` <= 52 and
`letters` >= number of unique letters in the input (ignoring asterisks) and
`count` >= max of the counts of each individual (non-asterisk) letter in the input
// double counts [x, x] for x^2 -- not an issue for this problem
const factorPairs = (n) =>
[...Array (Math .floor (Math .sqrt (n)))] .map ((_, i) => i + 1)
.flatMap (f => n % f == 0 ? [[f, n / f], [n / f, f]] : [])
const balanced = ([...ss]) => {
const chars = [...new Set (ss .filter (s => s != '*'))]
const counts = ss .reduce (
(counts, s) => s == '*' ? counts : ((counts [s] += 1), counts),
Object .fromEntries (chars .map (l => [l, 0]))
)
const maxCount = Math.max (... Object.values (counts))
return factorPairs (ss .length) .some (
([count, letters]) =>
letters <= 52 &&
letters >= chars .length &&
count >= maxCount
)
}
const tests = [
'a', 'ab', 'abc', 'abcb', 'Aaa', '***********',
'****rfdd****', 'aaa**bbbb*', 'aaa**bbbb******',
'C****F***R***US***R**D***YS*****H***', 'C****F***R***US***R**D***YS*****H**',
'KSFVBX'
]
tests .forEach (s => console .log (`balanced("${s}") //=> ${balanced(s)}`))factorPairs只是将一个数字分解为有序的数字对。例如，factorPairs (36)产量[[1, 36], [36, 1], [2, 18], [18, 2], [3, 12], [12, 3], [4, 9], [9, 4], [6, 6], [6, 6]]。因为我们只检查一个是否存在，所以我们不需要改进此函数以更符合逻辑的顺序返回值或仅返回[6, 6]一次（只要输入是完全平方数）。
我们测试上述的每个结果（如[count, letters]），直到找到一个匹配的结果并返回true，或者我们遍历列表而没有找到一个结果并返回false。
所以在测试这个： 时'C****F***R***US***R**D***YS*****H***'，我们有一个长度为 的字符串36。我们最终得到这些8独特的字符：['C', 'F', 'R', 'U', 'S', 'D', 'Y', 'H']，这些计数：{C: 1, F: 1, R: 2, U: 1, S: 2, D: 1, Y: 1, H: 1}，我们的maxCount是2
然后我们测试生成的各种因子对36
count: 1, letters: 36（失败，因为count小于 2）count: 36, letters: 1（失败，因为letters小于 8）count: 2, letters: 18 （成功，返回true）我们不需要测试剩余的因子对。
使用 18 个字母（每个字母两次）的示例可以是：
C****F***R***US***R**D***YS*****H*** CCaabFFbcRcdUUSdeeRffDDgYYSghhiiHHjj - 平衡
请注意，这不一定是唯一有效的一对。例如，如果我们做到了count: 4, letters: 9，我们也可以让它工作：
C****F***R***US***R**D***YS*****H*** CCCCFFFFRRRUUUSUDDRDYDSYYYSSxxxxHHHH - 平衡
但问题是是否存在这样的解，所以当找到第一个解时我们就停止了。
另一方面，如果我们在输入中少一个星号，我们将测试这个：'C****F***R***US***R**D***YS*****H**'，长度为35。我们最终得到相同的8独特字符：['C', 'F', 'R', 'U', 'S', 'D', 'Y', 'H']，并且这些相同的计数：{C: 1, F: 1, R: 2, U: 1, S: 2, D: 1, Y: 1, H: 1}，而我们的maxCount仍然是2。
然后我们测试生成的各种因子对35
count: 1, letters: 35（失败，因为count小于 2）count: 35, letters: 1（失败，因为letters小于 8）count: 5, letters: 7（失败，因为letters小于 8）count: 7, letters: 5（失败，因为letters小于 8）我们已经用完了因子对，所以我们返回false。
代码本身并没有什么特别有趣的地方。它在每一步都做了显而易见的事情。（尽管请注意对输入字符串的解构balanced，将字符串转换为字符数组。）但它使用赋值语句和语句做了一些我通常不喜欢做的事情return。我更喜欢尽可能使用表达式而不是语句。我也更喜欢提取辅助函数，即使它们只使用一次，如果它们有助于澄清流程的话。所以我可能会重写如下所示：
.as-console-wrapper {max-height: 100% !important; top: 0}C****F***R***US***R**D***YS*****H*** CCaabFFbcRcdUUSdeeRffDDgYYSghhiiHHjj - balanced
但这在逻辑上并没有改变。算法是一样的。
您可以计算字符数并维护最大计数变量。
返回带 1 的键的长度检查结果，或通过调整星数来检查不带星的每个字符。
最后检查此属性是否为假，计数为零或仅为undefined。
function balanced(string) {
let max = 0,
stars = 0,
counts = [...string].reduce((r, c) => {
if (c === '*') {
stars++;
return r;
}
r[c] = (r[c] || 0) + 1;
if (max < r[c]) max = r[c];
return r;
}, {}),
keys = Object.keys(counts);
if (keys.length <= 1) return true;
return keys.every(c => {
if (counts[c] === max) return true;
if (stars >= max - counts[c]) {
stars -= max - counts[c];
return true;
}
}) && (!stars || stars % keys.length === 0);
}
console.log(balanced("a")); // true
console.log(balanced("ab")); // true
console.log(balanced("abc")); // true
console.log(balanced("***********")); // true
console.log(balanced("****rfdd****")); // true
console.log(balanced("aaa**bbbb*")); // true
console.log(balanced("abcb")); // false
console.log(balanced("Aaa")); // false.as-console-wrapper { max-height: 100% !important; top: 0; }