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
2
3
Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

Constraints:

  • 1 <= chips.length <= 100
  • 1 <= chips[i] <= 10^9

题解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        int n = chips.size();
        int mina = 0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int j = 0; j < n; j++) {
                if (j != i) {
                    temp += abs(chips[i]-chips[j])&1;
                }
            }
            mina = min(mina, temp);
        }
        return mina;
    }
};


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
2
3
Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].

Constraints:

  • 1 <= arr.length <= 10^5
  • -10^4 <= arr[i], difference <= 10^4

题解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        const int n = arr.size();
        map<int, int> mm;
        
        for (int i = 0; i < n; i++) {
            if (mm.find(arr[i]-difference) == mm.end()) mm[arr[i]] = 1;
            else mm[arr[i]] = mm[arr[i]-difference]+1;
        }
        int maxa = 0;
        for (auto it : mm) maxa = max(maxa, it.second);
        return maxa;
    }
};


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
2
3
4
5
6
7
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Constraints:

  • 1 <= grid.length, grid[i].length <= 15
  • 0 <= grid[i][j] <= 100
  • There are at most 25 cells containing gold.

题解

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int dp[20][20];
        int n = grid.size();
        int m = grid[0].size();
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] > 0)
                    res = max(res, grid[i][j]+dfs(grid, i, j));
        return res;
    }
    
private:
    int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    int dfs(vector<vector<int> >& grid, int x, int y) {
        int temp = grid[x][y];
        int res = 0;
        grid[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x+dir[i][0];
            int ny = y+dir[i][1];
            if (nx < grid.size() && nx >= 0 && ny >= 0 && ny < grid[0].size() && grid[nx][ny] > 0) {
                res = max(res, grid[nx][ny]+dfs(grid, nx, ny));
            }
        }
        grid[x][y] = temp;
        return res;
    }
};


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
2
3
Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Constraints:

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

题解

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

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution
{
public:
    int countVowelPermutation(int n);
};

int Solution::countVowelPermutation(int n)
{
    vector<vector<long>> dp(n+1, vector<long>(5, 0));
    
    int MOD = 1e9 + 7;
    
    /* dp[i][j] denotes the number of valid strings of length n */
    
    for(int i = 0; i < 5; i++)
        dp[1][i] = 1;
    
    for(int i = 1; i < n; i++)
    {
        dp[i+1][0] = (dp[i][1] + dp[i][2] + dp[i][4]) %MOD;
        
        dp[i+1][1] = (dp[i][0] + dp[i][2]) % MOD;
        
        dp[i+1][2] = (dp[i][1] + dp[i][3]) % MOD;
        
        dp[i+1][3] = dp[i][2];
        
        dp[i+1][4] = (dp[i][2] + dp[i][3]) % MOD;
    }
    
    int res = 0;
    for(int i = 0; i < 5; i++)
        res = (res + dp[n][i]) % MOD;
    
    return res;
}