Problem

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

Analysis

We traverse the string and add up each char by its value.
We need to handle a special case such as: IV, in which we have V-I = 4
In this case, we need to have I+V – 2*I = 4

Solution

class Solution {
public:
    int romanToInt(string s) {
        if(s.empty()) return 0;
        unordered_map<char, int> map({{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},  {'C', 100}, {'D', 500}, {'M', 1000}});
        int val = 0;
        for(int i=0; i<s.size(); i++){
            //Traverse and add the value
            val += map[s[i]];
            
            //Handle case like: IV = 4, as in the traverse we have added I(1) and V(5), we need to substract twice of I
            if(i>0 && map[s[i]] > map[s[i-1]])
                val -= 2*map[s[i-1]];
        }
        return val;
    }
};

Problem

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Analysis

See http://bangbingsyb.blogspot.com/2014/11/leetcode-integer-to-roman.html

Time complexity: O(13*3) = O(1)

Solution

// I: 1
// IV: 4
// V: 5
// IX: 9
// X: 10
// XL: 40
// L: 50
// XC: 90
// C: 100
// CD: 400
// D: 500
// CM: 900
// M: 1000

class Solution {
public:
    string intToRoman(int num) {
        // build the dictionary to value maps
        string dict[13] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int val[13] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string ret;
        int remain = num;
        
        // build the roman results from interger
        for(int i=0; i<13; i++){ if(remain >= val[i]){
                int count = remain/val[i];
                remain = remain%val[i];
                
                for(int j=0; j<count; j++){
                    ret.append(dict[i]);
                }
            }
            
            if(remain == 0) break;
        }
        
        return ret;
    }
};

Problem

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Analysis

This problem is similar to http://mytechroad.com/leetcode-c-permutations/
The only difference is that the number may be repeated, thus we need to deal with the special case when
– nums[i-1] is used, and nums[i]==num[i-1]

Time complexity: O(n!), the same analysis with previous problem

Solution

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> allPer;
        if(nums.size()==0) return allPer;
        vector<int> currPer;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        findAllPer(nums, allPer, currPer, used);
        return allPer;
        
    }
    
    void findAllPer(vector<int>& nums, vector<vector<int>>& allPer, vector<int>& currPer, vector<bool>& used){
        if(currPer.size() == nums.size()){
            allPer.push_back(currPer);
            return;
        }
        
        for(int i=0; i<nums.size(); i++){
            //Case 1: if current number is used, skip
            if(used[i]) continue;
            //Case 2: if current number is not used, but previous number is equal to current number, skip
            if(i>0 && nums[i]==nums[i-1] && used[i-1]) continue;
            
            //Otherwise: DFS to find all permutation 
            used[i] = true;
            currPer.push_back(nums[i]);
            findAllPer(nums, allPer, currPer, used);
            currPer.pop_back();
            used[i] = false;
        }
    }
};

Problem

Analysis

Check http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html
In specific, we have the following steps
Step 1: scan from right to left, find the first index that violates the non-decreasing property, denote as vioIdx
Step 2: scan from right to left, find the first index of number that is smaller than vioIdx, and swap the values
Step 3: reverse the array on the right side of the value

Solution

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //Step 1: from right to left, find the first one that violates the non-decreasing trend
        int vioIdx = nums.size()-1;
        while(vioIdx > 0 && nums[vioIdx] <= nums[vioIdx-1]){
                vioIdx--;
        }
        
        if(vioIdx > 0){
            vioIdx--;
            //Step 2: from right to left, find the first one that is larger than nums[vioIdx]
            int rightIdx = nums.size()-1;
            while(rightIdx > 0 && nums[rightIdx] <= nums[vioIdx]){
                rightIdx--;
            }
            
            int swap = nums[vioIdx];
            nums[vioIdx] = nums[rightIdx];
            nums[rightIdx] = swap;
            
            //Step 3: preparation, reverse the array from the righthand side of vioidx
            vioIdx++;
        }
        
        //Step 3: reverse 
        int end = nums.size()-1;
        while(end>vioIdx){
            int swap = nums[vioIdx];
            nums[vioIdx] = nums[end];
            nums[end] = swap;
            vioIdx++;
            end--;
        }
    }
};

Problem

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Analysis

We can use DFS approach, we maintain a temporary vector for current permutation
– then we traverse the array to add unused nums to the vector
– that means we need a vector to keep track which num has been used

Time complexity:
– T(n) = n*T(n-1) + 1, thus it is O(n!)
– reference: https://stackoverflow.com/questions/41627749/time-complexity-of-permutation-function

Solution

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> allPer;
        vector<int> currPer;
        //keep track of whether nums[i] has been used
        vector<bool> used(nums.size(), false);
        getAllPermute(nums, allPer, currPer, used);
        return allPer;
    }
    
    //recursively find all permutation
    void getAllPermute(vector<int>& nums, vector<vector<int>>& allPer, vector<int>& currPer, vector<bool>& used){
        if(currPer.size()==nums.size()){
            allPer.push_back(currPer);
            return;
        }
        
        for(int i=0; i<nums.size(); i++){
            //if nums[i] has already been used, skip
            if(used[i]) continue;
            
            //otherwise, add to the permutation, and recursively build the array
            currPer.push_back(nums[i]);
            used[i] = true;
            getAllPermute(nums, allPer, currPer, used);
            currPer.pop_back();
            used[i] = false;
        }
    }
};

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Analysis

We can recursively merge two lists into one list

Let k denote the number of lists
Let n denote the average length of each list
Time complexity: T(k) = 2T(k/2) + O(nk), thus we have O(nk*log k)
Space complexity:

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return NULL;
        if(lists.size() == 1) return lists[0];
        
        //merge each two lists into one
        vector<ListNode*> newLists;
        int n = lists.size();
        for(int i=0; i<n/2; i++){
            ListNode* currList = helper(lists[i], lists[n-1-i]);
            newLists.push_back(currList);
        }
        if(n%2 != 0){
            newLists.push_back(lists[n/2]);
        }
        
        //recursively merge all the lists
        return mergeKLists(newLists);
    }
    
    //merge two lists
    ListNode* helper(ListNode* l1, ListNode* l2){
        ListNode* dummyHead = new ListNode(-1);
        ListNode* l = dummyHead;
        while(l1 && l2){
            if(l1->val <= l2->val){
                l->next = l1;
                l1 = l1->next;
            }else{
                l->next = l2;
                l2 = l2->next;
            }
            l = l->next;
        }
        l->next = l1? l1 : l2;
        return dummyHead->next;
    }
};

Problem

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

Analysis

We can use DFS to recursive build the solution, i.e.,
let sol denote current solution,
let allSol denote all solutions,
let remain denote current remaining value to reach target in sol,
let start denote current traversing index in vector candidates
– we need to define terminate condition of DFS (i.e., when remain == 0)
– decide how/when to recursive build sol

Time complexity: O(2^n)
Space complexity: O(d) where d is the depth

Solution

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> allSol; 
        if(candidates.empty()) return allSol;
        
        vector<int> sol;
        int remain = target;
        int start = 0;
        sort(candidates.begin(), candidates.end());
        findComb(allSol, sol, start, remain, candidates);
        return allSol;
    }
    
    //DFS
    void findComb(vector<vector<int>>& allSol, vector<int>& sol, int start, int remain, vector<int>& candidates){
        //check terminate state
        if(remain == 0){
            allSol.push_back(sol);
            return;
        }
        
        //recursive construct solution
        for(int i=start; i<candidates.size(); i++){
            if(i>start && candidates[i-1] == candidates[i]) continue;
            if(candidates[i] <= remain){
                //push back
                sol.push_back(candidates[i]);
                findComb(allSol, sol, i, remain - candidates[i], candidates);
                //pop back
                sol.pop_back();
            }else{
                break;
            }
        }
    }
};

Problem

Implement pow(x, n).

Analysis

Divide and conquer, first compute pow(x, n/2), then use it to compute pow(x,n). Need to consider
– n is odd or even
– if n is odd, need to consider n is positive or negative

Solution

class Solution {
public:
    double myPow(double x, int n) {
        if(x==0) return 0;
        if(n==0) return 1;
        
        //divide and conquer
        int half = n/2;
        double val = myPow(x, half);
        //check if n is odd or even
        if(n%2 == 0)
            return val*val;
        else{
            //check if n is positive or negative
            if(n>0) return val*val*x;
            else return val*val/x;
        }
        
    }
};

Problem

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

Analysis

We can use an integer (validIdx) to keep track of current valid length, then we traverse the array
– when nums[i] has been repeated, continue
– otherwise, write it to the array, and advance validIdx

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

Solution

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int validIdx = 0;
        int curr = nums[0];
        for(int i=0; i<nums.size(); i++){
            //if repeat continue
            if(nums[i] == curr){
                continue;
            }
            //otherwise write the array, and move index
            else{
                nums[validIdx] = curr;
                curr = nums[i];
                validIdx=validIdx+1;
            }
        }
        nums[validIdx] = curr;
        return (validIdx+1);
    }
};

Problem

Given n non-negative integers a₁, a₂, …, a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Analysis

We can use double pointers to solve this problem, let left and right denote the index of left and right pointer respectively, then we have
– height[left] < height[right], left++
– height[left] >= height[right], right–

Solution

class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size()<=1) return 0;
        int left = 0;
        int right = height.size()-1;
        int max = 0;
        
        //two pointer
        while(left < right){
            //compute size
            int curr = min(height[left], height[right]) * (right - left);
            if(max < curr) max = curr;
            
            if(height[left] < height[right]){
                left++;
            }else{
                right--;
            }
        }
        return max;
    }
};