number-of-adjacent-elements-with-the-same-color

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Since at each query, only one element is being recolored, we just need to focus on its neighbors.

If an element that is changed on the i-th query had the same color as its right element answer decreases by 1. Similarly contributes its left element too.

After changing the color, if the element has the same color as its right element answer increases by 1. Similarly contributes its left element too.

Algorithms

You are given an integer <code>n</code> representing an array <code>colors</code> of length <code>n</code> where all elements are set to 0&#39;s meaning uncolored. You are also given a 2D integer array <code>queries</code> where <code>queries[i] = [indexi, colori]</code>. For the <code>ith</code> query:

<ul>
	<li>Set <code>colors[indexi]</code> to <code>colori</code>.</li>
	<li>Count the number of adjacent pairs in <code>colors</code> which have the same color (regardless of <code>colori</code>).</li>
</ul>

Return an array <code>answer</code> of the same length as <code>queries</code> where <code>answer[i]</code> is the answer to the <code>ith</code> query.

&nbsp;
Example 1:

<div class="example-block">
Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

Output: [0,1,1,0,2]

Explanation:

<ul>
	<li>Initially array colors = [0,0,0,0], where 0 denotes uncolored elements of the array.</li>
	<li>After the 1st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.</li>
	<li>After the 2nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.</li>
	<li>After the 3rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.</li>
	<li>After the 4th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.</li>
	<li>After the 5th query colors = [2,1,1,1]. The count of adjacent pairs with the same color is 2.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: n = 1, queries = [[0,100000]]

Output: [0]

Explanation:

After the 1st query colors = [100000]. The count of adjacent pairs with the same color is 0.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i].length&nbsp;== 2</code></li>
	<li><code>0 &lt;= indexi&nbsp;&lt;= n - 1</code></li>
	<li><code>1 &lt;=&nbsp; colori&nbsp;&lt;= 105</code></li>
</ul>

第 344 场周赛

weekly-contest-344

colorTheArray

资深工程师

Number of Adjacent Elements With the Same Color

Array

给定一个整数&nbsp;<code>n</code>&nbsp;表示一个长度为&nbsp;<code>n</code> 的数组&nbsp; <code>colors</code>，初始所有元素均为 0 ，表示是 未染色 的。同时给定一个二维整数数组&nbsp;<code>queries</code>，其中&nbsp;<code>queries[i] = [indexi, colori]</code>。对于第&nbsp;<code>i</code> 个&nbsp;查询：

<ul>
	<li>将&nbsp;<code>colors[indexi]</code>&nbsp;染色为 <code>colori</code>。</li>
	<li>统计&nbsp;<code>colors</code>&nbsp;中颜色相同的相邻对的数量（无论 <code>colori</code>）。</li>
</ul>

请你返回一个长度与 <code>queries</code>&nbsp;相等的数组&nbsp;<code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>是前 <code>i</code>&nbsp;个操作的答案。

&nbsp;

示例 1：

<div class="example-block">
输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

输出：[0,1,1,0,2]

解释：

<ul>
	<li>一开始 colors = [0,0,0,0]，其中 0 表示数组中未染色的元素。</li>
	<li>在第 1 次查询后&nbsp;colors = [2,0,0,0]。颜色相同的相邻对的数量是 0。</li>
	<li>在第 2&nbsp;次查询后 colors = [2,2,0,0]。颜色相同的相邻对的数量是 1。</li>
	<li>在第 3&nbsp;次查询后 colors = [2,2,0,1]。颜色相同的相邻对的数量是 1。</li>
	<li>在第 4&nbsp;次查询后 colors = [2,1,0,1]。颜色相同的相邻对的数量是 0。</li>
	<li>在第 5&nbsp;次查询后 colors = [2,1,1,1]。颜色相同的相邻对的数量是 2。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入：n = 1, queries = [[0,100000]]

输出：[0]

解释：

在第一次查询后&nbsp;colors = [100000]。颜色相同的相邻对的数量是 0。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i].length&nbsp;== 2</code></li>
	<li><code>0 &lt;= indexi&nbsp;&lt;= n - 1</code></li>
	<li><code>1 &lt;=&nbsp; colori&nbsp;&lt;= 105</code></li>
</ul>

有相同颜色的相邻元素数目

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给定一个整数 n 表示一个长度为 n 的数组  colors，初始所有元素均为 0 ，表示是 未染色 的。同时给定一个二维整数数组 queries，其中 queries[i] = [indexi, colori]。对于第 i 个 查询：

 * 将 colors[indexi] 染色为 colori。
 * 统计 colors 中颜色相同的相邻对的数量（无论 colori）。

请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作的答案。

 

示例 1：

输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

输出：[0,1,1,0,2]

解释：

 * 一开始 colors = [0,0,0,0]，其中 0 表示数组中未染色的元素。
 * 在第 1 次查询后 colors = [2,0,0,0]。颜色相同的相邻对的数量是 0。
 * 在第 2 次查询后 colors = [2,2,0,0]。颜色相同的相邻对的数量是 1。
 * 在第 3 次查询后 colors = [2,2,0,1]。颜色相同的相邻对的数量是 1。
 * 在第 4 次查询后 colors = [2,1,0,1]。颜色相同的相邻对的数量是 0。
 * 在第 5 次查询后 colors = [2,1,1,1]。颜色相同的相邻对的数量是 2。

示例 2：

输入：n = 1, queries = [[0,100000]]

输出：[0]

解释：

在第一次查询后 colors = [100000]。颜色相同的相邻对的数量是 0。

 

提示：

 * 1 <= n <= 105
 * 1 <= queries.length <= 105
 * queries[i].length == 2
 * 0 <= indexi <= n - 1
 * 1 <=  colori <= 105