Weekly Contest 157

Posted on | In , | |
Words count in article: 685 | Reading time ≈ 4

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).

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int minCostToMoveChips(vector<int>& chips) {
        int cnt[2] = {0, 0};
        for(auto p: chips)
            cnt[p % 2]++;
        return cnt[0] < cnt[1] ? cnt[0] : cnt[1];
    }
};

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> m;
        int ret = 0;
        
        for(int i=arr.size()-1; i>=0; i--)
        {
            m[arr[i]] = 1 + m[arr[i] + difference];
            ret = max(ret, m[arr[i]]);
        }
        return ret;
    }
};

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int dfs(vector<vector<int>>& g, int i, int j) {
      if (i < 0 || j < 0 || i >= g.size() || j >= g[i].size() || g[i][j] <= 0)  return 0;
      g[i][j] = -g[i][j];
      auto res = max({ dfs(g, i + 1, j), dfs(g, i, j + 1), dfs(g, i - 1, j), dfs(g, i, j - 1) });
      g[i][j] = -g[i][j];
      return g[i][j] + res;
    }
    int getMaximumGold(vector<vector<int>>& grid, int res = 0) {
      for (auto i = 0; i < grid.size(); ++i)
        for (auto j = 0; j < grid[i].size(); ++j)
          res = max(res, dfs(grid, i, j));
      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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int countVowelPermutation(int n) {
      int[][] moves = { {1}, {0, 2}, {0, 1, 3, 4}, {2, 4}, { 0 } };
      int[] v = { 1, 1, 1, 1, 1 };
      while (--n > 0) {
        int[] v1 = { 0, 0, 0, 0, 0 };
        for (int i = 0; i < 5; ++i) {
          for (int j : moves[i])
            v1[j] = (v1[j] + v[i]) % 1000000007;
        }
        v = v1;
      }
      return (int)(((long)v[0] + v[1] + v[2] + v[3] + v[4]) % 1000000007);
    }
}
Donate? comment?