Weekly Contest 156

Posted on | In , | |
Words count in article: 1.4k | Reading time ≈ 7

Unique Number of Occurrences

Given an array of integers arr, write a function that returns true if and only if the number of occurrences of each value in the array is unique.

Constraints:

  • 1 <= arr.length <= 1000
  • -1000 <= arr[i] <= 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        vector<int> countarr(2005, 0);
        vector<int> countnum(1000,0);
        for(int i=0; i<arr.size(); i++)
        {
            countarr[arr[i]+1000]++;
        }
        for(int i=0; i<=2000; i++)
        {
            if(countarr[i] != 0)
            {
                if(countnum[countarr[i]] != 0)
                    return false;
                else
                    countnum[countarr[i]]++;
            }
        }
        return true;
        
    }
};

Get Equal Substrings Within Budget

给你两个长度相同的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

Instead of two string, we can imagine an array of the same size with absolute differences. Then, the problem is to find the longest subarray with the sum not exceeding maxCost.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int i=0; 
        int j=0;
        while(i < s.size())
        {
            maxCost -= abs(s[i]-t[i++]);
            if(maxCost < 0) maxCost += abs(s[j] - t[j++]);
        }
        return i-j;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        vector<int> ab(s.size(), 0);
        for(int i=0; i<s.size(); i++)
        {
            ab[i] = abs(s[i]-t[i]);
        }
        
        int ii = 0;
        int jj = 0;
        while(jj < s.size())
        {
            maxCost -= ab[jj++];
            if(maxCost < 0) maxCost += ab[ii++];
        }
        return jj-ii;
    }
};

Remove All Adjacent Duplicates in String II

Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made.

It is guaranteed that the answer is unique.

1
2
3
4
5
6
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
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:
    string removeDuplicates(string s, int k) {
        if(s.size() == 0)
            return "";
        vector<char>  stack(100005, 0);
        int curidx = 0;
        for(int i=0; i<s.size(); i++)
        {
            char tmpch = s[i];
            int tmpnum = 1;
            for(int j=curidx-1; j>=0; j--)
            {
                if(stack[j] == tmpch)
                    tmpnum++;
                else
                    break;
            }
            if(tmpnum >= k)
            {
                curidx -= k-1;
            }
            else
            {
                stack[curidx] = tmpch;
                curidx++;
            }
        }
        string ret = "";
        for(int i=0; i<curidx; i++)
        {
            ret += stack[i];
        }
        return ret;
    }
};

Minimum Moves to Reach Target with Rotations

我们在一个 n*n 的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。蛇会从左上角（(0, 0) 和 (0, 1)）开始移动。我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（(n-1, n-2) 和 (n-1, n-1)）。

每次移动，蛇可以这样走：

  • 如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
  • 如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
  • 如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c+1)）移动到 （(r, c)、(r+1, c)）。
  • 如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。

返回蛇抵达目的地所需的最少移动次数。

如果无法到达目的地，请返回 -1。

1
2
3
4
5
6
7
8
9
输入：grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
输出：11
解释：
一种可能的解决方案是 [右, 右, 顺时针旋转, 右, 下, 下, 下, 下, 逆时针旋转, 右, 下]。
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
class Solution {
public:
    bool canRotate(vector<vector<int>>& g, int i, int j) {
      return i < g.size() - 1 && j < g[i].size() - 1 && (g[i + 1][j] & 1) == 0 && (g[i][j + 1] & 1) == 0 && (g[i + 1][j + 1] & 1) == 0;
    }
    bool canGoDown(vector<vector<int>>& g, int i, int j, bool vertical) {
      if (vertical) return i < g.size() - 2 && (g[i + 2][j] & 1) == 0;
      return i < g.size() - 1 && (g[i + 1][j] & 1) == 0 && (g[i + 1][j + 1] & 1) == 0;
    }
    bool canGoRight(vector<vector<int>>& g, int i, int j, bool vertical) {
      if (!vertical) return j < g[i].size() - 2 && (g[i][j + 2] & 1) == 0;
      return j < g[i].size() - 1 && (g[i][j + 1] & 1) == 0 && (g[i + 1][j + 1] & 1) == 0;
    }
    int minimumMoves(vector<vector<int>>& grid, int steps = 0) {
      queue<array<int, 3>> q1, q2;
      q1.push({ 0, 0, false }); // not vertical.
      while (!q1.empty()) {
        while (!q1.empty()) {
          auto& a = q1.front();
          if (a[0] == grid.size() - 1 && a[1] == grid[a[0]].size() - 2) return steps;
          if ((grid[a[0]][a[1]] & (a[2] ? 2 : 4)) == 0) {
            grid[a[0]][a[1]] = grid[a[0]][a[1]] | (a[2] ? 2 : 4);
            if (canGoDown(grid, a[0], a[1], a[2])) q2.push({ a[0] + 1, a[1], a[2] });
            if (canGoRight(grid, a[0], a[1], a[2])) q2.push({ a[0], a[1] + 1, a[2] });
            if (canRotate(grid, a[0], a[1])) q2.push({ a[0], a[1], a[2] ? false : true });
          }
          q1.pop();
        }
        ++steps;
        swap(q1, q2);
      }
      return -1;
    }
};
Donate? comment?