279. Perfect Squares

Difficulty: Medium

Frequency: N/A

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

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    int numSquares(int n) {
        if (n <= 0) return -1;
        vector<int> countSquares(n + 1, INT_MAX);
        countSquares[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                countSquares[i] = min(countSquares[i], countSquares[i - j * j] + 1);
            }
        }
        return countSquares[n];
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

264. Ugly Number II

Difficulty: Medium

Frequency: N/A

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

1. The naive approach is to call isUgly for every number until you reach the n^th one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L₁, L₂, and L₃.
4. Assume you have U_k, the k^th ugly number. Then U_k+1 must be Min(L₁ * 2, L₂ * 3, L₃ * 5).

---

My solution:

Data structure:

Steps:

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n <= 0) return -1;
        vector<int> ugly(n, 0);
        ugly[0] = 1;
        int idx_2 = 0, idx_3 = 0, idx_5 = 0;
        for (int i = 1; i < n; i++) {
            ugly[i] = min(min(ugly[idx_2] * 2, ugly[idx_3] * 3), ugly[idx_5] * 5);
            if (ugly[i] == ugly[idx_2] * 2) idx_2++;
            if (ugly[i] == ugly[idx_3] * 3) idx_3++;
            if (ugly[i] == ugly[idx_5] * 5) idx_5++;
        }
        return ugly[n - 1];
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

010. Regular Expression Matching

Difficulty: Hard

Frequency: N/A

 

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

---

My solution:

Data structure:

string

Steps:

1. Check empty input

2. If the second char is not *, check the first char. Continue if they match, or it is .

3. If the second char is *, check whether the t.substr(2) matches s. If not, check whether

    p[0] == ‘.’ or p[0] == s[0].

Complexity:

Runtime:

Space:

Test cases:

Corner cases:

Code:

class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p[1] != '*') {
            if(p[0] == s[0] || (p[0] == '.' && s[0] != '\0')) {
                return isMatch(s.substr(1), p.substr(1));
            } else {
                return false;
            }
        } else {
            if (isMatch(s, p.substr(2))) return true;
            int idx = 0;
            while (idx < s.size() && (s[idx] == p[0] || p[0] == '.')) {
                if (isMatch(s.substr(++idx), p.substr(2))) return true;
            }
            return false;
        }
    }
};

---

Another solution:

Data structure:

steps:

Complexity:

Runtime:

Space:

Code:

---

Things to learn:

1. Need to understand basic regular expression, like .* means zero or more any characters