047. Permutations II

Difficulty: Medium

Frequency: N/A

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> results;
        vector<int> tmp;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        permuteHelper(nums, used, tmp, results);
        return results;
    }
    void permuteHelper(vector<int> nums, vector<bool> used, vector<int> tmp, vector<vector<int>> &results) {
        if(tmp.size() == nums.size()) {
            results.push_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if(used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            tmp.push_back(nums[i]);
            permuteHelper(nums, used, tmp, results);
            tmp.pop_back();
            used[i] = false;
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. How to skip duplicate element
2. Avoid using lookup from previous result set.
Advertisements

089. Gray Code

Difficulty: Medium

Frequency: N/A

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.


My solution:
Data structure:
vector
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> result;
        result.push_back(0);
        for (int i = 0; i < n; i++) {
            int highBit = 1 << i;
            for (int j = result.size() - 1; j >= 0; j--) {
                result.push_back(highBit + result[j]);
            }
        }
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. How to do it in backtracking way?

046. Permutations

Difficulty: 

Frequency: 

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> results;
        vector<int> tmp_vec;
        permute_helper(nums, results, tmp_vec);
        return results;
    }
    void permute_helper(vector<int> nums, vector<vector<int>> &results, vector<int> tmp_vec) {
        if (nums.empty()) {
            results.push_back(tmp_vec);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            tmp_vec.push_back(nums[i]);
            vector<int> new_nums = nums;
            new_nums.erase(new_nums.begin() + i);
            permute_helper(new_nums, results, tmp_vec);
            tmp_vec.pop_back();
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

320. (locked)Generalized Abbreviation

Difficulty: Medium

Frequency: N/A

Write a function to generate the generalized abbreviations of a word.
Example:
Given word = "word", return the following list (order does not matter):
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
        vector<string> generateAbbreviations(string word) {
                vector<string> results;
                string tmp;
                helper(word, 0, tmp, results);
                return results;
        }
        void helper(string word, int idx, string tmp, vector<string> &results) {
                if (idx == word.size()) {
                        results.push_back(tmp);
                        return;
                }
                helper(word, idx + 1, tmp + word[idx], results);
                for (int i = 1; i < word.size() - idx; i++)
                        helper(word, idx + 1 + i, tmp + to_string(i) + word[idx + 1], results);
                helper(word, word.size(), tmp + to_string(word.size() - idx), results);
        }
};


Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

294. (locked)Flip Game II

Difficulty: Medium

Frequency: N/A

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm’s runtime complexity.


My solution:
Data structure:
string, backtracking
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool canWin(string s) {
        for (int i = -1; i = s.find("++", i + 1) >= 0; ) {
            if(!canWin(s.substr(0, i) + "--" + s.substr(i + 2)))
                return true;
        } 
        return false;
    }
}

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

227. Basic Calculator II

Difficulty:  Medium

Frequency:  N/A

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.


My solution:
Data structure:
string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
class Solution {
public:
    int calculate(string s) {
        istringstream input('+' + s + '+');
        int result = 0, curr = 0, next;
        char op;
        while (input >> op) {
            if (op == '+' || op == '-') {
                result += curr;
                input >> curr;
                curr = op == '+' ? curr : -curr;
            } else {
                input >> next;
                if (op == '*') curr *= next;
                else curr /=next;
            }
        }
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

273. Integer to English Words

Difficulty: Medium

Frequency: 

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

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Hint:

  1. Did you see a pattern in dividing the number into chunk of words? For example, 123 and 123000.
  2. Group the number by thousands (3 digits). You can write a helper function that takes a number less than 1000 and convert just that chunk to words.
  3. There are many edge cases. What are some good test cases? Does your code work with input such as 0? Or 1000010? (middle chunk is zero and should not be printed out)

My solution:
Data structure:
string, unordered_map
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
1. 0
2. 1000010
3. 10
4. 30
5. 100
6. 1000
Code:
class Solution {
public:
    string digits[20] = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    string tens[10] = {"Zero", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

    string int2string(int n) {
        if (n >= 1000000000) {
            return int2string(n / 1000000000) + " Billion" + int2string(n % 1000000000);
        } else if (n >= 1000000) {
            return int2string(n / 1000000) + " Million" + int2string(n % 1000000);
        } else if (n >= 1000) {
            return int2string(n / 1000) + " Thousand" + int2string(n % 1000);
        } else if (n >= 100) {
            return int2string(n / 100) + " Hundred" + int2string(n % 100);
        } else if (n >= 20) {
            return  " " + tens[n / 10] + int2string(n % 10);
        } else if (n >= 1) {
            return " " + digits[n];
        } else {
            return "";
        }
    }

    string numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        } else {
            string ret = int2string(num);
            return ret.substr(1, ret.length() - 1);
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: