方格染色

一、题目描述：

有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。

如样例所示: s = RGRGR

我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。

示例：

示例 1：

输入： s = RRRR

输出：0

示例 2：

输入： s = RRGR

输出：1

示例 3：

输入： s = RGRG

输出：1---->将第二个R涂成G，从第一个R后面分割

二、思路分析：

使用两个变量分别记录分割线左右两边出现的R和G的次数。定义lCount记录分割线左边出现的G的次数，定义rCount记录分割线右边出现的R。

当我们获取到这两个值时，在循环时，只需要取这两个值和的最小值即可。

大体考虑之后，我们还需要考虑边界情况：

• 当全是G时，我们需要把所有的R换成G，即rCount的值；
• 当全书R时，将全部的R换成G，即分割线在最后一个R的后面。结果应该就为lCount的值。

优化

使用一次循环记录R出现的次数(lCount)，将此时的rCount结果记录为右边都是'GGGG'的结果。

在记录G出现次数时可以和记录涂改个数放到同一个循环中。最后再求一下左半边为 'RRRR'的情况。

三、AC 代码：

function squareStaining(s) {
  let lCount = 0,
    rCount = 0
  let n = s.length
  for (let i = 0; i < n; i++) {
    rCount += s[i] === 'R' ? 1 : 0
  }
  let res = rCount // 整个s为右边 GGGG
  for (let i = 0; i < n - 1; i++) {
    lCount += s[i] === 'G' ? 1 : 0
    rCount -= s[i] === 'R' ? 1 : 0
    res = Math.min(res, lCount + rCount)
  }
  // 整个s为左半边 RRRR
  res = Math.min(res, lCount)
  return res
}

四、总结：

一开始可能会想到使用两个数组分别存放R和G出现的次数，但是为了简化操作，我们可以将出现的次数都是用两个变量来保存，通过循环，使各自增加或减少。

作者：ClyingDeng

链接：https://juejin.cn/post/6952678617327337480

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。