Huahua's Tech Road

花花酱 LeetCode Weekly Contest 133

By zxi on April 20, 2019

LeetCode 1029 Two City Scheduling

Solution1: DP

dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]

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

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int twoCitySchedCost(vector<vector<int>>& costs) {

int n = costs.size();

vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2));

dp[0][0] = 0;

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

dp[i][0] = dp[i - 1][0] + costs[i - 1][1];

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

dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0],

dp[i - 1][j] + costs[i - 1][1]);

}

return dp[n][n / 2];

}

};

Solution 2: Greedy

Sort by cost_a – cost_b

Choose the first n/2 people for A, rest for B

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

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int twoCitySchedCost(vector<vector<int>>& costs) {

int n = costs.size();

sort(begin(costs), end(costs), [](const auto& c1, const auto& c2){

return c1[0] - c1[1] < c2[0] - c2[1];

});

int ans = 0;

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

ans += i < n/2 ? costs[i][0] : costs[i][1];

return ans;

}

};

1030. Matrix Cells in Distance Order

Solution: Sorting

Time complexity: O(RC*log(RC))
Space complexity: O(RC)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

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

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

ans.push_back({i, j});

std::sort(begin(ans), end(ans), [r0, c0](const vector<int>& a, const vector<int>& b){

return (abs(a[0] - r0) + abs(a[1] - c0)) < (abs(b[0] - r0) + abs(b[1] - c0));

});

return ans;

}

};

1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution: Prefix sum

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

C++

// Author: Huahua

class Solution {

public:

int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {

const int n = A.size();

vector<int> s(n + 1, 0);

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

s[i + 1] = s[i] + A[i];

int ans = 0;

for (int i = 0; i <= n - L; ++i) {

int ls = s[i + L] - s[i];

int ms = max(maxSum(s, 0, i - M - 1, M),

maxSum(s, i + L, n - M, M));

ans = max(ans, ls + ms);

}

return ans;

}

private:

int maxSum(const vector<int>& s, int start, int end, int l) {

int ans = INT_MIN;

for (int i = start; i <= end; ++i)

ans = max(ans, s[i + l] - s[i]);

return ans;

}

};

1032. Stream of Characters

Solution: Trie

Time complexity:

build O(sum(len(w))
query O(max(len(w))

Space complexity: O(sum(len(w))

C++

// Author: Huahua, 320 ms, 95 MB

class TrieNode {

public:

~TrieNode() {

for (auto node : next_)

delete node;

}

void reverse_build(const string& s, int i) {

if (i == -1) {

is_word_ = true;

return;

}

const int idx = s[i] - 'a';

if (!next_[idx]) next_[idx] = new TrieNode();

next_[idx]->reverse_build(s, i - 1);

}

bool reverse_search(const string& s, int i) {

if (i == -1 || is_word_) return is_word_;

const int idx = s[i] - 'a';

if (!next_[idx]) return false;

return next_[idx]->reverse_search(s, i - 1);

}

private:

bool is_word_ = false;

TrieNode* next_[26] = {0};

};

class StreamChecker {

public:

StreamChecker(vector<string>& words) {

root_ = std::make_unique<TrieNode>();

for (const string& w : words)

root_->reverse_build(w, w.length() - 1);

}

bool query(char letter) {

s_ += letter;

return root_->reverse_search(s_, s_.length() - 1);

}

private:

string s_;

unique_ptr<TrieNode> root_;

};

Java

// Author: Huahua, running time: 133 ms

class StreamChecker {

class TrieNode {

public TrieNode() {

isWord = false;

next = new TrieNode[26];

}

public boolean isWord;

public TrieNode next[];

}

private TrieNode root;

private StringBuilder sb;

public StreamChecker(String[] words) {

root = new TrieNode();

sb = new StringBuilder();

for (String word : words) {

TrieNode node = root;

char[] w = word.toCharArray();

for (int i = w.length - 1; i >= 0; --i) {

int idx = w[i] - 'a';

if (node.next[idx] == null) node.next[idx] = new TrieNode();

node = node.next[idx];

}

node.isWord = true;

}

public boolean query(char letter) {

sb.append(letter);

TrieNode node = root;

for (int i = sb.length() - 1; i >= 0; --i) {

int idx = sb.charAt(i) - 'a';

if (node.next[idx] == null) return false;

if (node.next[idx].isWord) return true;

node = node.next[idx];

}

return false;

}

花花酱 Binary Search II SP17

By zxi on April 20, 2019

Binary Search I SP5

For the given function g(x) and a range [l, r] find the smallest int number m such that g(m) is True, if not found, return r + 1.

花花酱 LeetCode 38. Count and Say

By zxi on April 17, 2019

Problem

https://leetcode.com/problems/count-and-say/

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the n^th term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

Solution: Recursion + Simulation

C++

// Author: Huahua, 4 ms, 8.6 MB

class Solution {

public:

string countAndSay(int n) {

string ans = "1";

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

ans = say(ans);

return ans;

}

private:

string say(const string& n){

string ans;

int s = 0, l = n.length();

for (int e = 1; e <= l; ++e)

if (e == l || n[s] != n[e]) {

int count = e - s;

ans += '0' + count;

ans += n[s];

s = e;

}

return ans;

}

};

花花酱 LeetCode 279. Perfect Squares

By zxi on April 17, 2019

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solution 1: DP

dp[i] := ans
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} 1 <= j * j <= i

dp[5] = min{
dp[5 – 2 * 2] + 1 = dp[1] + 1 = (dp[1 – 1 * 1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1 * 1] + 1 = dp[3] + 1 = (dp[3 – 1 * 1] + 1) + 1 = dp[1] + 2 = dp[1 – 1*1] + 1 + 2 = dp[0] + 3 = 3
};

dp[5] = 2

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

C++

// Author: Huahua, running time: 104 ms

class Solution {

public:

int numSquares(int n) {

vector<int> dp(n + 1, INT_MAX >> 1);

dp[0] = 0;

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

for (int j = 1; j * j <= i; ++j)

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

return dp[n];

}

};

花花酱 LeetCode Weekly Contest 132 (1025,1026,1027,1028)

By zxi on April 13, 2019

1025. Divisor Game

Solution: Recursion with Memoization

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

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

bool divisorGame(int N) {

cache_ = vector<int>(N + 1, -1);

return canWin(N);

}

private:

vector<int> cache_;

bool canWin(int N) {

if (N == 1) return false;

if (cache_[N] != -1) return cache_[N];

bool win = false;

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

if (N % i == 0)

win |= !canWin(N - i);

return cache_[N] = win;

}

};

1026. Maximum Difference Between Node and Ancestor

Solution: Resolution, pass min / max of ancestor nodes

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

C++

class Solution {

public:

int maxAncestorDiff(TreeNode* root) {

if (!root) return 0;

return maxDiff(root, root->val, root->val);

}

private:

int maxDiff(TreeNode* root, int l, int r) {

if (!root) return 0;

int cur = max(abs(root->val - l), abs(root->val - r));

l = min(l, root->val);

r = max(r, root->val);

return max(cur, max(maxDiff(root->left, l, r),

maxDiff(root->right, l, r)));

}

};

1027. Longest Arithmetic Sequence

Solution 1: Brute Force + Pruning

Time complexity: O(n^3) ~ O(n^2) in practice
Space complexity: O(n)

C++

// Author: Huahua, running time: 352 ms

class Solution {

public:

int longestArithSeqLength(vector<int>& A) {

int n = A.size();

unordered_set<int> h;

int ans = 2;

for (int a: A) h.insert(a);

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

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

int d = (A[j] - A[i]);

int t = A[j] + d;

int l = 2;

if (!h.count(t)) continue;

int k = j + 1;

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

if (A[k] == t) {

t += d;

++l;

}

ans = max(ans, l);

}

return ans;

}

};

1028. Recover a Tree From Preorder Traversal

Solution: Recursion

Check the current depth and expected depth, if don’t match, return nullptr.

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

C++

// Author: Huahua, running time: 24 ms

class Solution {

public:

TreeNode* recoverFromPreorder(string S) {

int i = 0;

return recover(S, i, 0);

}

private:

TreeNode* recover(const string& s, int& i, int depth) {

const int d = getD(s, i);

if (d != depth) { i -= d; return nullptr; }

auto root = new TreeNode(getVal(s, i));

root->left = recover(s, i, d + 1);

root->right = recover(s, i, d + 1);

return root;

}

int getD(const string& s, int& i) {

int d = 0;

while (i < s.length() && s[i] == '-') {++d; ++i;}

return d;

}

int getVal(const string& s, int& i) {

int val = 0;

while (i < s.length() && isdigit(s[i]))

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

return val;

}

};