Huahua’s Tech Road

花花酱 LeetCode 1210. Minimum Moves to Reach Target with Rotations

By zxi on September 29, 2019

In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).

In one move the snake can:

Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Rotate clockwise if it’s in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).
Rotate counterclockwise if it’s in a vertical position and the two cells to its right are both empty. In that case the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).

Return the minimum number of moves to reach the target.

If there is no way to reach the target, return -1.

Example 1:

Input: 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]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

Example 2:

Input: grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
Output: 9

Constraints:

2 <= n <= 100
0 <= grid[i][j] <= 1
It is guaranteed that the snake starts at empty cells.

Solution1: BFS

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua, 48 ms, 18.1 MB

class Solution {

public:

inline int pos(int x, int y) {

return y * 100 + x;

}

inline int encode(int p1, int p2) {

return (p1 << 16) | p2;

}

int minimumMoves(vector<vector<int>>& grid) {

int n = grid.size();

queue<pair<int, int>> q;

unordered_set<int> seen;

q.push({pos(0, 0), pos(1, 0)}); // tail, head

seen.insert(encode(pos(0, 0), pos(1, 0)));

int steps = 0;

auto valid = [&](int x, int y) {

bool v = x >= 0 && x < n && y >= 0 && y < n && !grid[y][x];

return v;

};

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int y0 = p.first / 100;

int x0 = p.first % 100;

int y1 = p.second / 100;

int x1 = p.second % 100;

if (x0 == n - 2 && y0 == n - 1 &&

x1 == n - 1 && y1 == n - 1) {

return steps;

}

bool h = y0 == y1;

for (int i = 0; i < 3; ++i) {

int tx0 = x0;

int ty0 = y0;

int tx1 = x1;

int ty1 = y1;

int rx = x0;

int ry = y0;

switch (i) {

case 0: // down

++ty0;

++ty1;

break;

case 1: // right

++tx0;

++tx1;

break;

case 2: // rotate

++rx;

++ry;

if (h) { // clockwise

--tx1;

++ty1;

} else { // counterclockwise

++tx1;

--ty1;

}

break;

}

if (!valid(tx0, ty0) || !valid(tx1, ty1) || !valid(rx, ry)) continue;

int key = encode(pos(tx0, ty0), pos(tx1, ty1));

if (seen.count(key)) continue;

seen.insert(key);

q.push({pos(tx0, ty0), pos(tx1, ty1)});

}

++steps;

}

return -1;

}

};

Solution 2: DP

dp[i][j].first = min steps to reach i,j (tail pos) facing right
dp[i][j].second = min steps to reach i, j (tail pos) facing down
ans = dp[n][n-1].first

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua, 16 ms, 12.1MB

class Solution {

public:

int minimumMoves(vector<vector<int>>& grid) {

constexpr int kInf = 1e9;

const int n = grid.size();

vector<vector<pair<int, int>>> dp(n + 1,

vector<pair<int, int>>(n + 1, {kInf, kInf}));

dp[0][1].first = dp[1][0].first = -1;

for (int i = 1; i <= n; ++i)

for (int j = 1; j <= n; ++j) {

bool h = false;

bool v = false;

if (!grid[i - 1][j - 1] && j < n && !grid[i - 1][j]) {

dp[i][j].first = min(dp[i - 1][j].first, dp[i][j - 1].first) + 1;

h = true;

}

if (!grid[i - 1][j - 1] && i < n && !grid[i][j - 1]) {

dp[i][j].second = min(dp[i - 1][j].second, dp[i][j - 1].second) + 1;

v = true;

}

if (v && j < n && !grid[i][j])

dp[i][j].second = min(dp[i][j].second, dp[i][j].first + 1);

if (h && i < n && !grid[i][j])

dp[i][j].first = min(dp[i][j].first, dp[i][j].second + 1);

}

return dp[n][n - 1].first >= kInf ? -1 : dp[n][n - 1].first;

}

};

花花酱 LeetCode 1209. Remove All Adjacent Duplicates in String II

By zxi on September 29, 2019

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.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

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"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Constraints:

1 <= s.length <= 10^5
2 <= k <= 10^4
s only contains lower case English letters.

Solution: Stack

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string removeDuplicates(string s, int k) {

vector<pair<char, int>> st{{'*', 0}};

for (char c : s)

if (c != st.back().first)

st.emplace_back(c, 1);

else if (++st.back().second == k)

st.pop_back();

string ans;

for (const auto& p : st)

ans.append(p.second, p.first);

return ans;

}

};

花花酱 LeetCode 1208. Get Equal Substrings Within Budget

By zxi on September 29, 2019

You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Example 1:

Input: s = "abcd", t = "bcdf", cost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

Example 2:

Input: s = "abcd", t = "cdef", cost = 3
Output: 1
Explanation: Each charactor in s costs 2 to change to charactor in t, so the maximum length is 1.

Example 3:

Input: s = "abcd", t = "acde", cost = 0
Output: 1
Explanation: You can't make any change, so the maximum length is 1.

Constraints:

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s and t only contain lower case English letters.

Solution 1: Binary Search

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int equalSubstring(string s, string t, int maxCost) {

const int n = s.length();

vector<int> c(n + 1);

auto cit = begin(c) + 1;

int ans = 0;

for (int i = 0; i < n; ++i, ++cit) {

*cit = c[i] + abs(s[i] - t[i]);

int len = cit - lower_bound(begin(c), cit, *cit - maxCost);

ans = max(ans, len);

}

return ans;

}

};

Solution 2: Sliding Window

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int equalSubstring(string s, string t, int maxCost) {

const int n = s.length();

int ans = 0;

for (int i = 0, j = 0, cost = 0; i < n && j < n; ++i) {

while (j < n) {

int c = abs(s[j] - t[j]);

if (cost + c > maxCost) break;

cost += c;

++j;

}

ans = max(ans, j - i);

cost -= abs(s[i] - t[i]);

}

return ans;

}

};

花花酱 LeeCode 1207. Unique Number of Occurrences

By zxi on September 29, 2019

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.

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2:

Input: arr = [1,2]
Output: false

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true

Constraints:

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000

Solution: HashTable

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool uniqueOccurrences(vector<int>& arr) {

unordered_map<int, int> c;

for (int a : arr) ++c[a];

unordered_set<int> s;

for (const auto& kv : c)

if (!s.insert(kv.second).second)

return false;

return true;

}

};

花花酱 LeetCode 1195. Fizz Buzz Multithreaded

By zxi on September 22, 2019

Write a program that outputs the string representation of numbers from 1 to n, however:

If the number is divisible by 3, output “fizz”.
If the number is divisible by 5, output “buzz”.
If the number is divisible by both 3 and 5, output “fizzbuzz”.

For example, for n = 15, we output: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz.

Suppose you are given the following code:

class FizzBuzz {
  public FizzBuzz(int n) { ... }               // constructor
  public void fizz(printFizz) { ... }          // only output "fizz"
  public void buzz(printBuzz) { ... }          // only output "buzz"
  public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
  public void number(printNumber) { ... }      // only output the numbers
}

Implement a multithreaded version of FizzBuzz with four threads. The same instance of FizzBuzz will be passed to four different threads:

Thread A will call fizz() to check for divisibility of 3 and outputs fizz.
Thread B will call buzz() to check for divisibility of 5 and outputs buzz.
Thread C will call fizzbuzz() to check for divisibility of 3 and 5 and outputs fizzbuzz.
Thread D will call number() which should only output the numbers.

Solution:

4 Semaphores

C++

// Author: Huahua

class Semaphore {

public:

Semaphore (int count = 0): count_(count) {}

inline void notify() {

unique_lock<std::mutex> lock(mtx_);

count_++;

cv_.notify_one();

}

inline void wait() {

unique_lock<std::mutex> lock(mtx_);

while (count_ == 0) cv_.wait(lock);

count_--;

}

private:

mutex mtx_;

condition_variable cv_;

int count_;

};

class FizzBuzz {

private:

int n;

Semaphore sn;

Semaphore s3;

Semaphore s5;

Semaphore s15;

public:

FizzBuzz(int n): n(n), sn(1), s3(0), s5(0), s15(0) {}

void fizz(function<void()> printFizz) {

for (int i = 3; i <= n; i += 3) {

if (i % 5 == 0) continue;

s3.wait();

printFizz();

sn.notify();

}

void buzz(function<void()> printBuzz) {

for (int i = 5; i <= n; i += 5) {

if (i % 3 == 0) continue;

s5.wait();

printBuzz();

sn.notify();

}

void fizzbuzz(function<void()> printFizzBuzz) {

for (int i = 15; i <= n; i += 15) {

s15.wait();

printFizzBuzz();

sn.notify();

}

void number(function<void(int)> printNumber) {

for (int i = 1; i <= n; ++i)

if (i % 15 == 0) { s15.notify(); sn.wait(); }

else if (i % 5 == 0) { s5.notify(); sn.wait(); }

else if (i % 3 == 0) { s3.notify(); sn.wait(); }

else { printNumber(i); }

}

};

Huahua's Tech Road

花花酱 LeetCode 1210. Minimum Moves to Reach Target with Rotations

Solution1: BFS

C++

Solution 2: DP

C++

花花酱 LeetCode 1209. Remove All Adjacent Duplicates in String II

Solution: Stack

C++

花花酱 LeetCode 1208. Get Equal Substrings Within Budget

Solution 1: Binary Search

C++

Solution 2: Sliding Window

C++

花花酱 LeeCode 1207. Unique Number of Occurrences

Solution: HashTable

C++

花花酱 LeetCode 1195. Fizz Buzz Multithreaded

C++