Huahua’s Tech Road

花花酱 LeetCode 60. Permutation Sequence

By zxi on September 29, 2019

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Solution: Math

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

C++

// Author: Huahua

class Solution {

public:

string getPermutation(int n, int k) {

vector<int> num;

vector<int> fact(10, 1);

for (int i = 1; i <= 9; i++) {

num.push_back(i);

fact[i] = fact[i - 1] * i;

}

string s;

k--;

while (n--) {

int d = k / fact[n];

k %= fact[n];

s += ('0' + num[d]);

for (int i = d + 1; i <= 9; i++)

num[i - 1] = num[i];

}

return s;

}

};

花花酱 LeetCode 59. Spiral Matrix II

By zxi on September 29, 2019

Given a positive integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int> > generateMatrix(int n) {

vector<vector<int>> ans(n, vector<int>(n));

int dir = 2, x = 0, y = 0;

int max_x = n - 1, max_y = n - 1;

int min_x = 0, min_y = 1;

int i = 0;

while (++i <= n*n) {

ans[y][x] = i;

switch (dir) {

// up

case 1: if (--y == min_y) { dir = 2; ++min_y; } break;

// right

case 2: if (++x == max_x) { dir = 3; --max_x; } break;

// down

case 3: if (++y == max_y) { dir = 4; --max_y; } break;

// left

case 4: if (--x == min_x) { dir = 1; ++min_x; } break;

}

return ans;

}

};

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 60. Permutation Sequence

Solution: Math

C++

花花酱 LeetCode 59. Spiral Matrix II

Solution: Simulation

C++

花花酱 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++