Huahua’s Tech Road

花花酱 LeetCode 54. Spiral Matrix

By zxi on April 12, 2019

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

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

Example 2:

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

Solution: Simulation

Keep track of the current bounds (left, right, top, bottom).

Init: left = 0, right = n – 1, top = 0, bottom = m – 1

Each time we move in one direction and shrink the bounds and turn 90 degrees:
1. go right => –top
2. go down => –right
3. go left => ++bottom
4. go up => ++left

C++

class Solution {

public:

vector<int> spiralOrder(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

int l = 0;

int t = 0;

int r = matrix[0].size();

int b = matrix.size();

const int total = (r--) * (b--);

int d = 0;

int x = 0;

int y = 0;

vector<int> ans;

while (ans.size() < total - 1) {

if (d == 0) {

while (x < r) ans.push_back(matrix[y][x++]);

++t;

} else if (d == 1) {

while (y < b) ans.push_back(matrix[y++][x]);

--r;

} else if (d == 2) {

while (x > l) ans.push_back(matrix[y][x--]);

--b;

} else if (d == 3) {

while (y > t) ans.push_back(matrix[y--][x]);

++l;

}

d = (d + 1) % 4;

}

if (ans.size() != total) ans.push_back(matrix[y][x]);

return ans;

}

};

花花酱 LeetCode 417. Pacific Atlantic Water Flow

By zxi on April 11, 2019

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

The order of returned grid coordinates does not matter.
Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

Solution: DFS/BFS

Be careful with the input range, easy to TLE with a naive implementation. Have to search from the boards.

Time complexity: O(mn)
Space complexity: O(mn)

DFS

// Author: Huahua, running time: 48 ms

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

const int n = matrix.size();

const int m = matrix[0].size();

vector<vector<int>> p(n, vector<int>(m));

vector<vector<int>> a(n, vector<int>(m));

for (int x = 0; x < m; ++x) {

dfs(matrix, x, 0, 0, p); // top

dfs(matrix, x, n - 1, 0, a); // bottom

}

for (int y = 0; y < n; ++y) {

dfs(matrix, 0, y, 0, p); // left

dfs(matrix, m - 1, y, 0, a); // right

}

vector<pair<int, int>> ans;

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

for (int j = 0; j < m; ++j)

if (p[i][j] && a[i][j]) ans.emplace_back(i, j);

return ans;

}

private:

void dfs(vector<vector<int>>& b, int x, int y, int h, vector<vector<int>>& v) {

if (x < 0 || y < 0 || x == b[0].size() || y == b.size()) return;

if (v[y][x] || b[y][x] < h) return;

v[y][x] = true;

dfs(b, x + 1, y, b[y][x], v);

dfs(b, x - 1, y, b[y][x], v);

dfs(b, x, y + 1, b[y][x], v);

dfs(b, x, y - 1, b[y][x], v);

}

};

BFS

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

const int n = matrix.size();

const int m = matrix[0].size();

const vector<int> dirs{0, 1, 0, -1, 0};

auto bfs = [&](queue<pair<int, int>>& q, vector<vector<int>>& v) {

while (!q.empty()) {

const int y = q.front().first;

const int x = q.front().second;

q.pop();

const int h = matrix[y][x];

v[y][x] = true;

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

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx == m || ty == n || matrix[ty][tx] < h) continue;

if (v[ty][tx]) continue;

q.push({ty, tx});

}

};

queue<pair<int, int>> qp;

queue<pair<int, int>> qa;

vector<vector<int>> vp(n, vector<int>(m));

vector<vector<int>> va(n, vector<int>(m));

for (int x = 0; x < m; ++x) {

qp.push({0, x}); // top

qa.push({n - 1, x}); // bottom

}

for (int y = 0; y < n; ++y) {

qp.push({y, 0}); // left

qa.push({y, m - 1}); // right

}

bfs(qp, vp);

bfs(qa, va);

vector<pair<int, int>> ans;

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

for (int j = 0; j < m; ++j)

if (vp[i][j] && va[i][j]) ans.emplace_back(i, j);

return ans;

}

};

DP

// Author: Huahua, running time: 104 ms

class Solution {

public:

vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

const int n = matrix.size();

const int m = matrix[0].size();

vector<vector<int>> dp(n, vector<int>(m));

for (int x = 0; x < m; ++x) {

dp[0][x] |= 1;

dp[n - 1][x] |= 2;

}

for (int y = 0; y < n; ++y) {

dp[y][0] |= 1;

dp[y][m - 1] |= 2;

}

const vector<int> dirs{0, -1, 0, 1, 0};

while (true) {

bool changed = false;

for (int y = 0; y < n; ++y)

for (int x = 0; x < m; ++x)

for (int d = 0; d < 4; ++d) {

const int tx = x + dirs[d];

const int ty = y + dirs[d + 1];

if (tx < 0 || ty < 0 || tx == m || ty == n

|| matrix[y][x] < matrix[ty][tx]

|| (dp[y][x] | dp[ty][tx]) == dp[y][x]) continue;

dp[y][x] |= dp[ty][tx];

changed = true;

}

if (!changed) break;

}

vector<pair<int, int>> ans;

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

for (int j = 0; j < m; ++j)

if (dp[i][j] == 3) ans.emplace_back(i, j);

return ans;

}

};

花花酱 LeetCode 394. Decode String

By zxi on April 10, 2019

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution 1: Recursion

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

C++

// Author: Huahua, 4ms

class Solution {

public:

string decodeString(string s) {

if (s.empty()) return "";

string ans;

int i = 0;

int n = s.length();

int c = 0;

while (isdigit(s[i]) && i < n)

c = c * 10 + (s[i++] - '0');

int j = i;

if (i < n && s[i] == '[') {

int open = 1;

while (++j < n && open) {

if (s[j] == '[') ++open;

if (s[j] == ']') --open;

}

} else {

while (j < n && isalpha(s[j])) ++j;

}

// "def2[ac]" => "def" + decodeString("2[ac]")

// | |

// i j

if (i == 0)

return s.substr(0, j) + decodeString(s.substr(j));

// "3[a2[c]]ef", ss = decodeString("a2[c]") = "acc"

// | |

// i j

string ss = decodeString(s.substr(i + 1, j - i - 2));

while (c--)

ans += ss;

// "3[a2[c]]ef", ans = "abcabcabc", ans += decodeString("ef")

ans += decodeString(s.substr(j));

return ans;

}

};

花花酱 LeetCode 67. Add Binary

By zxi on April 10, 2019

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Solution: Big integer

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

C++

// Author: Huahua

class Solution {

public:

string addBinary(string a, string b) {

int carry = 0;

int i = a.length() - 1;

int j = b.length() - 1;

string ans;

while (i >= 0 || j >= 0) {

int s = (i >= 0 ? a[i--] - '0' : 0) +

(j >= 0 ? b[j--] - '0' : 0) +

carry;

carry = s >> 1;

ans += '0' + (s & 1);

}

if (carry) ans += '1';

return {rbegin(ans), rend(ans)};

}

};

花花酱 LeetCode 125. Valid Palindrome

By zxi on April 10, 2019

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Solution: Two pointers

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

C++

class Solution {

public:

bool isPalindrome(string s) {

int i = 0;

int j = s.length() - 1;

while (i < j) {

while (i < j && !isalnum(s[i])) ++i;

while (i < j && !isalnum(s[j])) --j;

if (tolower(s[i++]) != tolower(s[j--]))

return false;

}

return true;

}

};

Huahua's Tech Road

花花酱 LeetCode 54. Spiral Matrix

C++

花花酱 LeetCode 417. Pacific Atlantic Water Flow

DFS

BFS

DP

花花酱 LeetCode 394. Decode String

Solution 1: Recursion

C++

花花酱 LeetCode 67. Add Binary

C++

花花酱 LeetCode 125. Valid Palindrome

C++