class Solution {
public:
vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
}
};
6418. 有相同颜色的相邻元素数目
给你一个下标从 0 开始、长度为 n 的数组 nums 。一开始，所有元素都是 未染色 （值为 0 ）的。
给你一个二维整数数组 queries ，其中 queries[i] = [indexi, colori] 。
对于每个操作，你需要将数组 nums 中下标为 indexi 的格子染色为 colori 。
请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作 之后 ，相邻元素颜色相同的数目。
更正式的，answer[i] 是执行完前 i 个操作后，0 <= j < n - 1 的下标 j 中，满足 nums[j] == nums[j + 1] 且 nums[j] != 0 的数目。
示例 1：
输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]] 输出：[0,1,1,0,2] 解释：一开始数组 nums = [0,0,0,0] ，0 表示数组中还没染色的元素。 - 第 1 个操作后，nums = [2,0,0,0] 。相邻元素颜色相同的数目为 0 。 - 第 2 个操作后，nums = [2,2,0,0] 。相邻元素颜色相同的数目为 1 。 - 第 3 个操作后，nums = [2,2,0,1] 。相邻元素颜色相同的数目为 1 。 - 第 4 个操作后，nums = [2,1,0,1] 。相邻元素颜色相同的数目为 0 。 - 第 5 个操作后，nums = [2,1,1,1] 。相邻元素颜色相同的数目为 2 。
示例 2：
输入：n = 1, queries = [[0,100000]] 输出：[0] 解释：一开始数组 nums = [0] ，0 表示数组中还没染色的元素。 - 第 1 个操作后，nums = [100000] 。相邻元素颜色相同的数目为 0 。
提示：
1 <= n <= 1051 <= queries.length <= 105queries[i].length == 20 <= indexi <= n - 11 <= colori <= 105原站题解
golang 解法, 执行用时: 300 ms, 内存消耗: 28.1 MB, 提交时间: 2023-05-08 09:55:08
func colorTheArray(n int, queries [][]int) []int {
ans := make([]int, len(queries))
a := make([]int, n+2) // 避免讨论下标出界的情况
cnt := 0
for qi, q := range queries {
i, c := q[0]+1, q[1] // 下标改成从 1 开始
if a[i] > 0 {
if a[i] == a[i-1] {
cnt--
}
if a[i] == a[i+1] {
cnt--
}
}
a[i] = c
if a[i] == a[i-1] {
cnt++
}
if a[i] == a[i+1] {
cnt++
}
ans[qi] = cnt
}
return ans
}
java 解法, 执行用时: 4 ms, 内存消耗: 95.9 MB, 提交时间: 2023-05-08 09:54:56
class Solution {
public int[] colorTheArray(int n, int[][] queries) {
int q = queries.length, cnt = 0;
int[] ans = new int[q], a = new int[n + 2]; // 避免讨论下标出界的情况
for (int qi = 0; qi < q; qi++) {
int i = queries[qi][0] + 1, c = queries[qi][1]; // 下标改成从 1 开始
if (a[i] > 0)
cnt -= (a[i] == a[i - 1] ? 1 : 0) + (a[i] == a[i + 1] ? 1 : 0);
a[i] = c;
cnt += (a[i] == a[i - 1] ? 1 : 0) + (a[i] == a[i + 1] ? 1 : 0);
ans[qi] = cnt;
}
return ans;
}
}
python3 解法, 执行用时: 240 ms, 内存消耗: 48.7 MB, 提交时间: 2023-05-08 09:54:15
'''
由于每次修改只会影响当前元素与其左右元素的关系，所以模拟即可。
用 cnt 统计相邻相同的个数。
代码实现时，可以先去掉当前元素对cnt的影响，修改颜色后，再加上当前元素对cnt的影响。
'''
class Solution:
def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
ans = []
a, cnt = [0] * (n + 2), 0 # 避免讨论下标出界的情况
for i, c in queries:
i += 1 # 下标改成从 1 开始
if a[i]: cnt -= (a[i] == a[i - 1]) + (a[i] == a[i + 1])
a[i] = c
cnt += (a[i] == a[i - 1]) + (a[i] == a[i + 1])
ans.append(cnt)
return ans