javascript - 处理字符串中相同出现的字符

Question

我这里有个小问题。我正在解决我书中的一些随机问题。这是任务:
任务
平衡字符串是字符串中的每个字符出现的次数与其他字符相同的字符串。例如，“ab”、“aaabbb”和“ababaabb”是平衡的，但“abb”和“abbbaa”不是。
此外，字符串还可以包含通配符“*”。此通配符可以表示您希望的任何其他字符。此外，通配符必须代表另一个字符；它们不能闲置。通配符平衡字符串是一个字符串，其中所有通配符都可以转换为字符，从而产生一个简单的平衡字符串。
这个挑战涉及编写一个函数balanced(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;
}

Answer 1

以数学方式进行
考虑这个问题的另一种方法是简单地做一些算术。为了平衡，替换星号后的每个唯一字符必须出现相同的次数。因此，次数 (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

使用辅助函数来查找数字的所有因子对，我们可以直接编写以下逻辑:

// 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)}`))

.as-console-wrapper {max-height: 100% !important; top: 0}

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 - balanced

Note that this is not necessarily the only pair that will work. For instance, if we'd made it to count: 4, letters: 9, we could also make it work:

C****F***R***US***R**D***YS*****H***CCCCFFFFRRRUUUSUDDRDYDSYYYSSxxxxHHHH - balanced

But the question is whether there was any such solution, so we stop when finding the first one.

If, on the other hand, we had one fewer asterisk in the input, we would test this: 'C****F***R***US***R**D***YS*****H**', with a length of 35. We end up with the same 8 unique characters: ['C', 'F', 'R', 'U', 'S', 'D', 'Y', 'H'], and these same counts: {C: 1, F: 1, R: 2, U: 1, S: 2, D: 1, Y: 1, H: 1}, and our maxCount is still 2.

We then test the various factor-pairs generated for 35

• count: 1, letters: 35 (fails because count is less than 2)
• count: 35, letters: 1 (fails because letters is less than 8)
• count: 5, letters: 7 (fails because letters is less than 8)
• count: 7, letters: 5 (fails because letters is less than 8)

and we've run out of factor-pairs, so we return false.

An alternate formulation

There's nothing particularly interesting in the code itself. It does the obvious thing at each step. (Although do note the destructuring of the input string to balanced, turning the String into an array of characters.) But it does something I generally prefer not to do, using assignment statements and a return statement. I prefer to work with expressions instead of statements as much as possible. I also prefer to extract helper functions, even if they're only used once, if they help clarify the flow. So I'm might rewrite as shown here:

const range = (lo, hi) => 
  [... Array (hi - lo + 1)] .map ((_, i) =>  i + lo)

// double counts [x, x] for x^2 -- not an issue for this problem
const factorPairs = (n) =>
  range (1, Math .floor (Math .sqrt (n)))
    .flatMap (f => n % f == 0 ? [[f, n / f], [n / f, f]] : [])

const getUniqueChars = ([...ss]) => 
  [... new Set (ss .filter (s => s != '*'))] 

const maxOccurrences = ([...ss], chars) => 
  Math.max (... Object .values (ss .reduce (
    (counts, s) => s == '*' ? counts : ((counts [s] += 1), counts),
    Object .fromEntries (chars .map (l => [l, 0]))
  )))

const balanced = (
  str,
  chars = getUniqueChars (str),
  maxCount = maxOccurrences (str, chars)
) => factorPairs (str .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)}`))

.as-console-wrapper {max-height: 100% !important; top: 0}

但这在逻辑上没有任何改变。算法是一样的。

关于javascript - 处理字符串中相同出现的字符，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67977081/

上一篇：haskell - 当 newtype 是 Functor 时，是否会删除对 fmap 的调用？

下一篇：build - Vite "rollup failed to resolve"构建错误