We can traverse each node in the range $[0,..,n-1]$. If a node has not been visited, we start from this node and search for adjacent nodes until we encounter a cycle or a node that has already been visited. If we encounter a cycle, we update the answer.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the number of nodes.

Similar problems:

- [2127. Maximum Employees to Be Invited to a Meeting](https://github.com/doocs/leetcode/blob/main/solution/2100-2199/2127.Maximum%20Employees%20to%20Be%20Invited%20to%20a%20Meeting/README.md)

We define $f[i]$ as the minimum cost from station $0$ to station $i$ when arriving at station $i$ by the regular route, and $g[i]$ as the minimum cost from station $0$ to station $i$ when arriving at station $i$ by the express route. Initially, $f[0]=0, g[0]=\infty$.

Next, we consider how to transition the states of $f[i]$ and $g[i]$.

If we arrive at station $i$ by the regular route, we can either come from station $i-1$ by the regular route or switch from the express route at station $i-1$ to the regular route. Therefore, we can get the state transition equation:

where $a_i$ represents the cost of taking the regular route from station $i-1$ to station $i$.

If we arrive at station $i$ by the express route, we can either switch from the regular route at station $i-1$ to the express route or continue on the express route from station $i-1$. Therefore, we can get the state transition equation:

where $b_i$ represents the cost of taking the express route from station $i-1$ to station $i$.

We denote the answer array as $cost$, where $cost[i]$ represents the minimum cost from station $0$ to station $i$. Since we can reach station $i$ from any route, we have $cost[i]=\min\{f[i], g[i]\}$.

Finally, we return $cost$.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the number of stations.

We can use a hash table or array `cnt` to count the total weight of each item in `items1` and `items2`. Then, we traverse the values in ascending order, adding each value and its corresponding total weight to the result array.

The time complexity is $O(n + m)$ and the space complexity is $O(n + m)$, where $n$ and $m$ are the lengths of `items1` and `items2` respectively.

From the problem description, we know that for any $i < j$, if $j - i \neq nums[j] - nums[i]$, then $(i, j)$ is a bad pair.

We can transform the equation to $i - nums[i] \neq j - nums[j]$. This inspires us to use a hash table $cnt$ to count the occurrences of $i - nums[i]$.

We iterate through the array. For the current element $nums[i]$, we add $i - cnt[i - nums[i]]$ to the answer, then increment the count of $i - nums[i]$ by $1$.

Finally, we return the answer.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the array.

遍历数组 $tasks$，对于每个任务 $task$，当前时间 $ans$ 加一，表示从上一次执行任务到现在已经过去了一天，如果此时 $day[task] \gt ans$，说明任务 $task$ 需要在第 $day[task]$ 天才能被执行，因此我们更新当前时间 $ans = \max(ans, day[task])$。然后更新 $day[task]$ 的值为 $ans + space + 1$，表示任务 $task$ 下一次可以被执行的时间为 $ans + space + 1$。

We can use a hash table $day$ to record the next time each task can be executed. Initially, all values in $day$ are $0$. We use a variable $ans$ to record the current time.

We iterate through the array $tasks$. For each task $task$, we increment the current time $ans$ by one, indicating that one day has passed since the last task execution. If $day[task] > ans$ at this time, it means that task $task$ can only be executed on the $day[task]$ day. Therefore, we update the current time $ans = \max(ans, day[task])$. Then we update the value of $day[task]$ to $ans + space + 1$, indicating that the next time task $task$ can be executed is at $ans + space + 1$.

After the iteration, we return $ans$.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the array $tasks$.

时间复杂度 $O(n)$，其中 $n$ 为数组 $nums$ 的长度。空间复杂度 $O(1)$。

We observe that to make the array $nums$ non-decreasing or monotonically increasing, the elements towards the end of the array should be as large as possible. Therefore, it is unnecessary to replace the last element $nums[n-1]$ of the array $nums$ with multiple smaller numbers.

In other words, we can traverse the array $nums$ from the end to the beginning, maintaining the current maximum value $mx$, initially $mx = nums[n-1]$.

- If the current element $nums[i] \leq mx$, there is no need to replace $nums[i]$. We simply update $mx = nums[i]$.

- Otherwise, we need to replace $nums[i]$ with multiple numbers that sum to $nums[i]$. The maximum of these numbers is $mx$, and the total number of replacements is $k=\left \lceil \frac{nums[i]}{mx} \right \rceil$. Therefore, we need to perform $k-1$ operations, which are added to the answer. Among these $k$ numbers, the smallest number is $\left \lfloor \frac{nums[i]}{k} \right \rfloor$. Therefore, we update $mx = \left \lfloor \frac{nums[i]}{k} \right \rfloor$.

After the traversal, we return the total number of operations.

The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

We notice that the length of the array $nums$ is no more than $200$. Therefore, we can directly enumerate $i$, $j$, $k$, and check whether they meet the conditions. If they do, we increment the count of the triplet.

The time complexity is $O(n^3)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.

We can first store the elements of $nums$ in a hash table or array $vis$. Then, for each element $x$ in $nums$, we check if $x+diff$ and $x+diff+diff$ are also in $vis$. If they are, we increment the count of the triplet.

After the enumeration, we return the answer.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the array $nums$.