Huahua's Tech Road

花花酱 LeetCode 982. Triples with Bitwise AND Equal To Zero

By zxi on January 26, 2019

Given an array of integers A, find the number of triples of indices (i, j, k) such that:

0 <= i < A.length
0 <= j < A.length
0 <= k < A.length
A[i] & A[j] & A[k] == 0, where & represents the bitwise-AND operator.

Example 1:

Input: [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

Note:

1 <= A.length <= 1000
0 <= A[i] < 2^16

Solution: Counting

Time complexity: O(n^2 + n * max(A))
Space complexity: O(max(A))

C++

// Author: Huahua, running time: 60 ms

class Solution {

public:

int countTriplets(vector<int>& A) {

const int n = *max_element(begin(A), end(A));

vector<int> count(n + 1);

for (int a: A)

for (int b: A)

++count[a & b];

int ans = 0;

for (int a : A)

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

if ((a & i) == 0) ans += count[i];

return ans;

}

};

花花酱 LeetCode 981. Time Based Key-Value Store

By zxi on January 26, 2019

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
If there are multiple such values, it returns the one with the largest timestamp_prev.
If there are no values, it returns the empty string ("").

Example 1:

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:   
TimeMap kv;   
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
kv.get("foo", 1);  // output "bar"   
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"   
kv.set("foo", "bar2", 4);   
kv.get("foo", 4); // output "bar2"   
kv.get("foo", 5); //output "bar2"

Example 2:

Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]

Note:

All key/value strings are lowercase.
All key/value strings have length in the range [1, 100]
The timestamps for all TimeMap.set operations are strictly increasing.
1 <= timestamp <= 10^7
TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

Solution: HashTable + Map

C++

// Author: Huahua, running time: 200 ms

class TimeMap {

public:

/** Initialize your data structure here. */

TimeMap() {}

void set(string key, string value, int timestamp) {

s_[key].emplace(timestamp, std::move(value));

}

string get(string key, int timestamp) {

auto m = s_.find(key);

if (m == s_.end()) return "";

auto it = m->second.upper_bound(timestamp);

if (it == begin(m->second)) return "";

return prev(it)->second;

}

private:

unordered_map<string, map<int, string>> s_;

};

花花酱 LeetCode 85. Maximal Rectangle

By zxi on January 26, 2019

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Solution: DP

Time complexity: O(m^2*n)
Space complexity: O(mn)

dp[i][j] := max length of all 1 sequence ends with col j, at the i-th row.
transition:
dp[i][j] = 0 if matrix[i][j] == ‘0’
= dp[i][j-1] + 1 if matrix[i][j] == ‘1’

C++

class Solution {

public:

int maximalRectangle(vector<vector<char> > &matrix) {

int r = matrix.size();

if (r == 0) return 0;

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

// dp[i][j] := max len of all 1s ends with col j at row i.

vector<vector<int>> dp(r, vector<int>(c));

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

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

dp[i][j] = (matrix[i][j] == '1') ? (j == 0 ? 1 : dp[i][j - 1] + 1) : 0;

int ans = 0;

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

for (int j = 0; j < c; ++j) {

int len = INT_MAX;

for (int k = i; k < r; k++) {

len = min(len, dp[k][j]);

if (len == 0) break;

ans = max(len * (k - i + 1), ans);

}

return ans;

}

};

花花酱 LeetCode 980. Unique Paths III

By zxi on January 20, 2019

On a 2-dimensional grid, there are 4 types of squares:

1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: [[0,1],[2,0]]
Output: 0
Explanation: 
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

Note:

1 <= grid.length * grid[0].length <= 20

count how many empty blocks there are and try all possible paths to end point and check whether we visited every empty blocks or not.

Solution: Brute force / DP

C++/DFS

class Solution {

public:

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

int sx = -1;

int sy = -1;

int n = 1;

for (int i = 0; i < grid.size(); ++i)

for (int j = 0; j < grid[0].size(); ++j)

if (grid[i][j] == 0) ++n;

else if (grid[i][j] == 1) { sx = j; sy = i; }

return dfs(grid, sx, sy, n);

}

private:

int dfs(vector<vector<int>>& grid, int x, int y, int n) {

if (x < 0 || x == grid[0].size() ||

y < 0 || y == grid.size() ||

grid[y][x] == -1) return 0;

if (grid[y][x] == 2) return n == 0;

grid[y][x] = -1;

int paths = dfs(grid, x + 1, y, n - 1) +

dfs(grid, x - 1, y, n - 1) +

dfs(grid, x, y + 1, n - 1) +

dfs(grid, x, y - 1, n - 1);

grid[y][x] = 0;

return paths;

};

C++/DP

class Solution {

public:

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

const int n = grid.size();

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

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

vector<vector<vector<short>>> cache(n, vector<vector<short>>(m, vector<short>(1 << n * m, -1)));

int sx = -1;

int sy = -1;

int state = 0;

auto key = [m](int x, int y) { return 1 << (y * m + x); };

function<short(int, int, int)> dfs = [&](int x, int y, int state) {

if (cache[y][x][state] != -1) return cache[y][x][state];

if (grid[y][x] == 2) return static_cast<short>(state == 0);

int paths = 0;

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

const int tx = x + dirs[i];

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

if (tx < 0 || tx == m || ty < 0 || ty == n || grid[ty][tx] == -1) continue;

if (!(state & key(tx, ty))) continue;

paths += dfs(tx, ty, state ^ key(tx, ty));

}

return cache[y][x][state] = paths;

};

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

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

if (grid[y][x] == 0 || grid[y][x] == 2) state |= key(x, y);

else if (grid[y][x] == 1) { sx = x; sy = y; }

return dfs(sx, sy, state);

}

};

花花酱 LeetCode 979. Distribute Coins in Binary Tree

By zxi on January 20, 2019

Given the root of a binary tree with N nodes, each node in the tree has node.valcoins, and there are N coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

Example 1:

Input: [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.

Example 3:

Input: [1,0,2]
Output: 2

Example 4:

Input: [1,0,0,null,3]
Output: 4

Note:

1<= N <= 100
0 <= node.val <= N

Solution: Recursion

Compute the balance of left/right subtree, ans += abs(balance(left)) + abs(balance(right))
balance(root) = balance(left) + balance(right) + root.val – 1

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

C++

class Solution {

public:

int distributeCoins(TreeNode* root) {

int ans = 0;

balance(root, ans);

return ans;

}

private:

int balance(TreeNode* root, int& ans) {

if (!root) return 0;

int l = balance(root->left, ans);

int r = balance(root->right, ans);

ans += abs(l) + abs(r);

return l + r + root->val - 1;

}

};