Huahua's Tech Road

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

}

};

花花酱 LeetCode 66. Plus One

By zxi on April 10, 2019

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution: Big Integer

Process from right to left (lest significant to most signification). Use carry to indicate whether need +1 for next digit or not.

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

c++

class Solution {

public:

vector<int> plusOne(vector<int>& digits) {

int carry = 1;

for (int i = digits.size() - 1; i >= 0; --i) {

digits[i] += carry;

carry = digits[i] / 10;

digits[i] %= 10;

}

if (carry) digits.insert(begin(digits), carry);

return digits;

}

};

花花酱 LeetCode Weekly Contest 131 (1021, 1022, 1023, 1024)

By zxi on April 7, 2019

LeetCode 1021. Remove Outermost Parentheses

Solution: Track # of opened parentheses

Let n denote the # of opened parentheses after current char, keep ‘(‘ if n > 1 and keep ‘)’ if n > 0

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

C++

// Author: Huahua

class Solution {

public:

string removeOuterParentheses(string S) {

string ans;

int n = 0;

for (char c : S) {

if (c == '(' && n++) ans += c;

if (c == ')' && --n) ans += c;

}

return ans;

}

};

LeetCode 1022. Sum of Root To Leaf Binary Numbers

Solution: Recursion + Math

Keep tracking the number from root to current node.

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

C++

class Solution {

public:

int sumRootToLeaf(TreeNode* root) {

return sums(root, 0);

}

private:

static constexpr int kMod = 1e9 + 7;

int sums(TreeNode* root, int c) {

if (!root) return 0;

c = ((c << 1) | root->val) % kMod;

if (!root->left && !root->right) {

return c;

}

return sums(root->left, c) + sums(root->right, c);

}

};

LeetCode 1023. Camelcase Matching

Solution: String…

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> camelMatch(vector<string>& queries, string p) {

vector<bool> ans;

for (const string& q : queries)

ans.push_back(match(q, p));

return ans;

}

private:

bool match(const string& q, const string& p) {

int m = p.length();

int n = q.length();

int i = 0;

int j = 0;

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

if (j == m && isupper(q[i])) return false;

if ((j == m || isupper(p[j])) && islower(q[i])) continue;

if ((isupper(p[j]) || isupper(q[i])) && p[j] != q[i]) return false;

if (islower(p[j]) && p[j] != q[i]) continue;

++j;

}

return i == n && j == m;

}

};

LeetCode 1024. Video Stitching

Solution 1: DP

Time complexity: O(nT^2)
Space complexity: O(T^2)

C++

// Author: Huahua, 16 ms / 9.5 MB

class Solution {

public:

int videoStitching(vector<vector<int>>& clips, int T) {

constexpr int kInf = 101;

// dp[i][j] := min clips to cover range [i, j]

vector<vector<int>> dp(T + 1, vector<int>(T + 1, kInf));

for (const auto& c : clips) {

int s = c[0];

int e = c[1];

for (int l = 1; l <= T; ++l) {

for (int i = 0; i <= T - l; ++i) {

int j = i + l;

if (s > j || e < i) continue;

if (s <= i && e >= j) dp[i][j] = 1;

else if (e >= j) dp[i][j] = min(dp[i][j], dp[i][s] + 1);

else if (s <= i) dp[i][j] = min(dp[i][j], dp[e][j] + 1);

else dp[i][j] = min(dp[i][j], dp[i][s] + 1 + dp[e][j]);

}

return dp[0][T] == kInf ? -1 : dp[0][T];

}

};

C++/V2

// Author: Huahua, running time: 20 ms / 9.4 MB

class Solution {

public:

int videoStitching(vector<vector<int>>& clips, int T) {

constexpr int kInf = 101;

// dp[i][j] := min clips to cover range [i, j]

vector<vector<int>> dp(T + 1, vector<int>(T + 1));

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

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

dp[i][j] = i < j ? kInf : 0;

for (const auto& c : clips) {

const int s = min(c[0], T);

const int e = min(c[1], T);

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

for (int i = 0, j = l; j <= T; ++i, ++j)

dp[i][j] = min(dp[i][j], dp[i][s] + 1 + dp[e][j]);

}

return dp[0][T] == kInf ? -1 : dp[0][T];

}

};

花花酱 LeetCode 273. Integer to English Words

By zxi on April 3, 2019

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ – 1.

Example 1:

Input: 123
Output: "One Hundred Twenty Three"

Example 2:

Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

Solution: Recursion

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

constexpr char * kUnder20[] = {"One", "Two", "Three", "Four", "Five",

"Six", "Seven", "Eight", "Nine","Ten",

"Eleven", "Twelve", "Thirteen", "Fourteen",

"Fifteen", "Sixteen", "Seventeen", "Eighteen",

"Nineteen"};

constexpr char * kUnder100[] = {"Twenty", "Thirty", "Forty", "Fifty",

"Sixty", "Seventy", "Eighty", "Ninety"};

constexpr char * kHTMB[] = {"Hundred", "Thousand", "Million", "Billion"};

constexpr long kP[] = {100, 1000, 1000*1000, 1000*1000*1000};

class Solution {

public:

string numberToWords(int n) {

if (n == 0) return "Zero";

return convert(n).substr(1);

}

private:

string convert(int n) {

if (n == 0) return "";

if (n < 20) return string(" ") + kUnder20[n - 1]; // 1 - 19

if (n < 100) return string(" ") + kUnder100[n / 10 - 2] + convert(n % 10); // 20 ~ 99

for (int i = 3; i >= 0; --i)

if (n >= kP[i]) return convert(n / kP[i]) + " " + kHTMB[i] + convert(n % kP[i]);

return "";

}

};