Posts tagged as “medium”

花花酱 LeetCode 1391. Check if There is a Valid Path in a Grid

By zxi on March 22, 2020

Given a m x ngrid. Each cell of the grid represents a street. The street of grid[i][j] can be:

1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.

You will initially start at the street of the upper-left cell (0,0). A valid path in the grid is a path which starts from the upper left cell (0,0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.

Notice that you are not allowed to change any street.

Return true if there is a valid path in the grid or false otherwise.

Example 1:

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

Example 2:

Input: grid = [[1,2,1],[1,2,1]]
Output: false
Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)

Example 3:

Input: grid = [[1,1,2]]
Output: false
Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).

Example 4:

Input: grid = [[1,1,1,1,1,1,3]]
Output: true

Example 5:

Input: grid = [[2],[2],[2],[2],[2],[2],[6]]
Output: true

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

Solution: BFS

Need to check both sides (x, y) -> (tx, ty) and (tx, ty) -> (x, y) to make sure a path exist.

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

C++

// Author: Huahua

class Solution {

public:

bool hasValidPath(vector<vector<int>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<int> dirs{0, -1, 0, 1, 0}; // [up, left, down, right]

vector<set<int>> rules{

{1, 3}, {0, 2}, {1, 2},

{2, 3}, {0, 1}, {0, 3}};

queue<int> q{{0}};

vector<int> seen(m * n);

seen[0] = 1;

while (!q.empty()) {

int cx = q.front() % n;

int cy = q.front() / n;

q.pop();

if (cx == n - 1 && cy == m - 1) return true;

for (int d : rules[grid[cy][cx] - 1]) {

int x = cx + dirs[d];

int y = cy + dirs[d + 1];

int key = y * n + x;

if (x < 0 || x >= n || y < 0 || y >= m || seen[key]

|| !rules[grid[y][x] - 1].count((d + 2) % 4)) continue;

seen[key] = 1;

q.push(key);

}

return false;

}

};

花花酱 LeetCode 393. UTF-8 Validation

By zxi on March 20, 2020

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For 1-byte character, the first bit is a 0, followed by its unicode code.
For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

Char. number range | UTF-8 octet sequence

(hexadecimal) | (binary)

--------------------+---------------------------------------------

0000 0000-0000 007F | 0xxxxxxx

0000 0080-0000 07FF | 110xxxxx 10xxxxxx

0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx

0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.

Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 2:

data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.

Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

Solution: Bit Operation

Check the first byte of a character and find out the number of bytes (from 0 to 3) left to check. The left bytes must start with 0b10.

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

C++

// Author: Huahua

class Solution {

public:

bool validUtf8(vector<int>& data) {

int left = 0;

for (int d : data) {

if (left == 0) {

if ((d >> 3) == 0b11110) left = 3;

else if ((d >> 4) == 0b1110) left = 2;

else if ((d >> 5) == 0b110) left = 1;

else if ((d >> 7) == 0b0) left = 0;

else return false;

} else {

if ((d >> 6) != 0b10) return false;

--left;

}

return left == 0;

}

};

花花酱 LeetCode 1382. Balance a Binary Search Tree

By zxi on March 15, 2020

Given a binary search tree, return a balanced binary search tree with the same node values.

A binary search tree is balanced if and only if the depth of the two subtrees of every node never differ by more than 1.

If there is more than one answer, return any of them.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct.

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The tree nodes will have distinct values between 1 and 10^5.

Solution: Inorder + recursion

Use inorder traversal to collect a sorted array from BST. And then build a balanced BST from this sorted array in O(n) time.

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* balanceBST(TreeNode* root) {

vector<int> vals;

function<void(TreeNode*)> inorder = [&](TreeNode* root) {

if (!root) return;

inorder(root->left);

vals.push_back(root->val);

inorder(root->right);

};

function<TreeNode*(int, int)> build = [&](int l, int r) {

if (l > r) return (TreeNode*)nullptr;

int m = l + (r - l) / 2;

auto root = new TreeNode(vals[m]);

root->left = build(l, m - 1);

root->right = build(m + 1, r);

return root;

};

inorder(root);

return build(0, vals.size() - 1);

}

};

花花酱 LeetCode 1381. Design a Stack With Increment Operation

By zxi on March 15, 2020

Design a stack which supports the following operations.

Implement the CustomStack class:

CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
int pop() Pops and returns the top of stack or -1 if the stack is empty.
void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Solution: Simulation

Time complexity:
init: O(1)
pop: O(1)
push: O(1)
inc: O(k)

C++

// Author: Huahua

class CustomStack {

public:

CustomStack(int maxSize): max_size_(maxSize) {}

void push(int x) {

if (data_.size() == max_size_) return;

data_.push_back(x);

}

int pop() {

if (data_.empty()) return -1;

int val = data_.back();

data_.pop_back();

return val;

}

void increment(int k, int val) {

for (int i = 0; i < min(static_cast<size_t>(k),

data_.size()); ++i)

data_[i] += val;

}

private:

int max_size_;

vector<int> data_;

};

/**

* Your CustomStack object will be instantiated and called as such:

* CustomStack* obj = new CustomStack(maxSize);

* obj->push(x);

* int param_2 = obj->pop();

* obj->increment(k,val);

花花酱 LeetCode 306. Additive Number

By zxi on March 14, 2020

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Constraints:

num consists only of digits '0'-'9'.
1 <= num.length <= 35

Solution: DFS

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

C++

using SV = std::string_view;

class Solution {

public:

bool isAdditiveNumber(SV s) {

auto add = [](SV s1, SV s2) {

const int l1 = s1.length(), l2 = s2.length();

string s3(max(l1, l2) + 1, '0');

for (int i = 0; i < s3.size() - 1; ++i) {

int n1 = i < l1 ? s1[l1 - i - 1] - '0' : 0;

int n2 = i < l2 ? s2[l2 - i - 1] - '0' : 0;

s3[i] += n1 + n2;

if (s3[i] > '9') {

s3[i] -= 10;

++s3[i + 1];

}

while (s3.back() == '0' && s3.length() > 1) s3.pop_back();

return string{rbegin(s3), rend(s3)};

};

auto isValid = [](SV s) { return s.length() == 1 || s[0] != '0'; };

function<bool(SV, SV, SV)> additive = [&](SV s1, SV s2, SV right) {

if (!isValid(s1) || !isValid(s2)) return false;

string s3 = add(s1, s2);

const int l3 = s3.length();

if (right.substr(0, l3) != s3) return false;

if (right.length() == l3) return true;

return additive(s2, s3, right.substr(l3));

};

for (int i = 1; i <= s.size(); ++i)

for (int j = 1; i + j <= s.size(); ++j)

if (additive(s.substr(0, i), s.substr(i, j), s.substr(i + j)))

return true;

return false;

}

};

Python3

class Solution:

def isAdditiveNumber(self, num: str) -> bool:

n = len(num)

def valid(s): return len(s) == 1 or s[0] != '0'

def additive(s1, s2, right):

if not valid(s1) or not valid(s2): return False

s3 = str(int(s1) + int(s2))

if right.startswith(s3):

if right == s3: return True

return additive(s2, s3, right[len(s3):])

return False

for l1 in range(1, n // 2 + 1):

for l2 in range(1, n + 1 - l1):

if additive(num[:l1], num[l1:l1+l2], num[l1+l2:]):

return True

return False