# LeetCode Weekly Contest 157

## 文章目录

## 1217.Play with Chips

There are some chips, and the i-th chip is at position `chips[i]`

.

You can perform any of the two following types of moves **any number of times** (possibly zero) **on any chip**:

- Move the
`i`

-th chip by 2 units to the left or to the right with a cost of**0**. - Move the
`i`

-th chip by 1 unit to the left or to the right with a cost of**1**.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

**Example 1:**

1 | Input: chips = [1,2,3] |

**Constraints:**

`1 <= chips.length <= 100`

`1 <= chips[i] <= 10^9`

### 题解

简单题，因为数据范围很小，可以考虑暴力，时间复杂度为 `O(n^2)`

1 | class Solution { |

## 1218.Longest Arithmetic Subsequence of Given Difference

Given an integer array `arr`

and an integer `difference`

, return the length of the longest subsequence in `arr`

which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals `difference`

.

**Example 1:**

1 | Input: arr = [1,2,3,4], difference = 1 |

**Constraints:**

`1 <= arr.length <= 10^5`

`-10^4 <= arr[i], difference <= 10^4`

### 题解

从前往后遍历，每遍历到一个数字的时候判断前面是否有满足的数，即 \(arr[i]-difference\)，用 map 存储次数。

1 | class Solution { |

## 1219.Path with Maximum Gold

In a gold mine `grid`

of size `m * n`

, each cell in this mine has an integer representing the amount of gold in that cell, `0`

if it is empty.

Return the maximum amount of gold you can collect under the conditions:

- Every time you are located in a cell you will collect all the gold in that cell.
- From your position you can walk one step to the left, right, up or down.
- You can't visit the same cell more than once.
- Never visit a cell with
`0`

gold. - You can start and stop collecting gold from
**any**position in the grid that has some gold.

**Example 1:**

1 | Input: grid = [[0,6,0],[5,8,7],[0,9,0]] |

**Constraints:**

`1 <= grid.length, grid[i].length <= 15`

`0 <= grid[i][j] <= 100`

- There are at most
**25**cells containing gold.

### 题解

数据范围同样很小，遍历每一个位置作为起点，然后 **dfs + 回溯** 更新最大值。

1 | class Solution { |

## 1220.Count Vowels Permutation

Given an integer `n`

, your task is to count how many strings of length `n`

can be formed under the following rules:

- Each character is a lower case vowel (
`'a'`

,`'e'`

,`'i'`

,`'o'`

,`'u'`

) - Each vowel
`'a'`

may only be followed by an`'e'`

. - Each vowel
`'e'`

may only be followed by an`'a'`

or an`'i'`

. - Each vowel
`'i'`

**may not**be followed by another`'i'`

. - Each vowel
`'o'`

may only be followed by an`'i'`

or a`'u'`

. - Each vowel
`'u'`

may only be followed by an`'a'.`

Since the answer may be too large, return it modulo `10^9 + 7.`

**Example 1:**

1 | Input: n = 1 |

**Constraints:**

`1 <= n <= 2 * 10^4`

### 题解

占个坑，使用 DP 或者数学推公式（矩阵快速幂）

#### DP

1 | class Solution |