Insertion Sort List

Sort a linked list using insertion sort.

Problem link

Solution

  • insertion sort: the sub-array on the left are sorted, new elements are inserted into the proper position on the left
  • need to search from head every time for the new node to find a place to insert
  • quite complicated, runs slower and painful to debug…
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *p1 = NULL, *cur, *ret = head, *next, *p2=NULL;
        while (head){
            cur = ret;
            while (cur!=head && cur->val <= head->val){
                p1 = cur;
                cur = cur->next;
            }
            if (cur!=ret){
                if (cur!=head){ // p1->val < head->val < cur->val
                    // insert between p1 and cur
                    next = head->next;
                    p1->next = head;
                    head->next  = cur;
                    head = next;
                    if (p2){
                        p2->next = next;
                    }
                }else{
                    p2 = head;
                    head = head->next;
                }
            }else{ // insert before ret/cur, head node replaces the old head
                if (cur->val > head->val){
                    next = head->next;
                    head->next = cur;
                    ret = head;
                    head = next;
                    if (p2){
                        p2->next = next;
                    }
                }else{ // no need to delete/insert node
                    p2 = head;
                    head = head->next;
                }
            }
        }
        return ret;
    }
};

Dummy head ndoe solution

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode* dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode* left;
        ListNode* tmp;
        head = dummy;
        while (head && head->next){ // evaluting next node to avoid storing the pre pointer
            left = dummy;
            while (head->next->val > left->next->val){
                left = left->next;
            }
            if (head->next!=left->next){ // insert head right before left
                // first delete head->next
                tmp = head->next;
                head->next = head->next->next;
                // insert head->next between left and left->next
                tmp->next = left->next;
                left->next = tmp;
            }else{
                head = head->next;    
            }
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};
Advertisements
Insertion Sort List

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Problem link

Solution

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string>> vv;
        vector<int> v;
        rec(vv, v, n);
        return vv;
    }
    
    void rec(vector<vector<string>> &vv, vector<int> &v, int n){
        for (int i=0; i<n; ++i){
            if (!conflict(v, i)){
                v.push_back(i);
                if (v.size()==n){
                    vv.push_back(conv(v));
                }else{
                    rec(vv, v, n);
                }
                v.pop_back();
            }
        }
    }
    
    vector<string> conv(vector<int> &v){
        int n=v.size();
        vector<string> vs(n, string(n,'.'));
        for (int i=0; i<n; ++i){
            vs[i][v[i]] = 'Q';
        }
        return vs;
    }
    
    bool conflict(vector<int> &assign, int new_queen){
        // check for conflict with all previously existing queens
        for (int i=0; i<assign.size(); i++){
            if (assign[i]==new_queen || assign.size()-i == abs(new_queen - assign[i])){
                return true;
            }
        }
        return false;
    }
};
N-Queens

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.


Problem link

Solution

  • use stack for backtracking
class Solution {
public:
    int totalNQueens(int n) {
        vector<int> assign;
        int sol_count = 0;
        int i;
        
        while (true){
            // place a new queen
            for (i=0; i<n; i++){
                if (!conflict(assign, i)){
                    assign.push_back(i);
                    if (assign.size()==n) {
                        // found a solution, backtracking
                        sol_count++;
                        if (!backtrack(assign, n))
                            return sol_count;
                    }
                    break;
                }
            }
            
            // no way to place it, backtracking
            if (i==n){
                if (!backtrack(assign, n)){
                    return sol_count;
                }
            }
        }
    }
    
private:
    bool backtrack(vector<int> &assign, int n){
        // iteratively backtrack starting from the last element in 
        // the assignment by increasing the last element by one
        int i;
        while (!assign.empty()){
            i = assign.back()+1;
            assign.pop_back();
            while (i<n){
                if (!conflict(assign, i)){
                    assign.push_back(i);
                    return true;
                }
                i++;
            }
        }
        return false;
    }
    
    bool conflict(vector<int> &assign, int new_queen){
        // check for conflict with all previously existing queens
        for (int i=0; i<assign.size(); i++){
            if (assign[i]==new_queen || assign.size()-i == abs(new_queen - assign[i])){
                return true;
            }
        }
        return false;
    }
};

A recursive solution

  • much easier to write
class Solution {
public:
    int totalNQueens(int n) {
        vector<int> assign;
        int sol_count = 0;
        rec(assign, n, sol_count);
        return sol_count;
    }
    
    void rec(vector<int> &assign, int n, int &sol_count){
        for (int i=0; i<n; i++){
            if (!conflict(assign, i)){
                assign.push_back(i);
                if (assign.size()==n){
                    ++sol_count;
                }else{
                    rec(assign, n, sol_count);    
                }
                assign.pop_back();
            }
        }
    }
    
    bool conflict(vector<int> &assign, int new_queen){
        // check for conflict with all previously existing queens
        for (int i=0; i<assign.size(); i++){
            if (assign[i]==new_queen || assign.size()-i == abs(new_queen - assign[i])){
                return true;
            }
        }
        return false;
    }
};
N-Queens II

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Problem link

Solution

  • greedy algorithm O(n) wouldn’t work, for instance, “aaabaa”
  • two DP problems: 1. find the min cut; 2. check palindrome
  • reference: http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning-ii.html
class Solution {
public:
    int minCut(string s) {  
            int len = s.size();  
            int D[len+1]; 
            bool P[len][len];  
            // auxilary storage initialization
            for(int i = 0; i <= len; i++){ // D[i] is the min cut between i:n
                //the worst case is cutting by each char  
                D[i] = len-i; 
            }
            for(int i = 0; i < len; i++){
                for(int j = 0; j < len; j++){
                    P[i][j] = false;        
                }    
            }
            for(int i = len-1; i >= 0; i--){// from last to first to reuse
                for(int j = i; j < len; j++){  
                      if(s[i] == s[j] && (j-i<2 || P[i+1][j-1])){  
                           P[i][j] = true;  
                           D[i] = min(D[i],D[j+1]+1);  
                      }  
                 }  
            }  
            return D[0]-1;  
      }  
};

A solution with O(n) extra space

  • cut[i] store the min cut for the first i elements
  • advancing the pivot node i
class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        vector<int> cut(n+1, 0);  // number of cuts for the first k characters
        for (int i = 0; i <= n; i++) cut[i] = i-1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

            for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome
                cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
        }
        return cut[n];
    }
};
Palindrome Partitioning II

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Problem link

Solution

  • 2D dynamic programming
class Solution {
public:
    string longestPalindrome(string s) {
        int n = 0;
        int start;
        bool pal[1000][1000] = {false};
        for (int i=s.size()-1; i>=0; --i){
            // reverse the order of i so that shorter subtrings are considered first
            for (int j=i; j<s.size(); ++j){
                if ((i+1>=j-1||pal[i+1][j-1]) && s[i]==s[j]){
                    pal[i][j] = true;
                    if (n<j-i+1){
                        n = j-i+1;
                        start=i;
                    }
                } 
            }
        }
        return s.substr(start, n); 
    }
};
Longest Palindromic Substring

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Problem link

Solution

  • progressively increase the size of substrings
  • use simple recursion, yet there are lots of duplication checks
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> vv;
        if (s.empty()) return vv;
        vector<string> v;
        rec(vv, v, s, 0, s.size()-1);
        return vv;
    }
    
    void rec(vector<vector<string>> &vv, vector<string> &v, string &s, int l, int r){
        for (int i=l; i<=r; ++i){
            string str = s.substr(l, i-l+1);
            if (check(str)){ // if pass the test
                v.push_back(str);
                if (i+1<=r){
                    rec(vv, v, s, i+1, r);
                }else{ // i==r
                    vv.push_back(v);
                }
                v.pop_back();
            }
        }
    }
    
    bool check(string &s){
        // check if the string is a palindrome
        int l = 0;
        int r = s.size()-1;
        while (l<=r){
            if (s[l]!=s[r]) return false;
            ++l;
            --r;
        }
        return true;
    }
};

An improved solution

  • saving the palindrome answers in a matrix
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<string>> vv;
        vector<string> v;
        vector<vector<bool>> pal(s.size(), vector<bool>(s.size(), false));
        // two pointer method
        for (int i=s.size()-1; i>=0; --i){ 
            // reverse the order of i so that shorter subtrings are considered first
            for (int j=i; j<s.size(); ++j){
                if (s[i]==s[j] && (i+1>=j-1||pal[i+1][j-1])) pal[i][j] = true;
            }
        }
        rec(vv, v, s, pal, 0);
        return vv; 
    }
    
    void rec(vector<vector<string>> &vv, vector<string> &v, string &s, vector<vector<bool>> &pal, int l){
        for (int i=l; i<= s.size()-1; ++i){
            if (pal[l][i]){ // if pass the test
                v.push_back(s.substr(l, i-l+1));
                if (i+1<=s.size()-1){
                    rec(vv, v, s, pal, i+1);
                }else{ // i==r
                    vv.push_back(v);
                }
                v.pop_back();
            }
        }
    }
};
Palindrome Partitioning

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ mn ≤ length of list.

Problem link

Solution

  • should have written test cases myself
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (m==n || !head) return head;
        int i=1;
        ListNode* pre=NULL, *next=NULL, *last=NULL, *old_head = head;
        while (head){
            if (i==m){ // start position
                last = pre;
            }else if (m<i && i<n){ // in between
                next = head->next;
                head->next = pre;
            }else if (i==n){ // end position
                next = head->next;
                head->next = pre;
                if (last){ // head doesn't change
                    last->next->next = next;
                    last->next = head;
                    return old_head;
                } else { // current node becomes the new head 
                    old_head->next = next;
                    return head;
                }
            }
            pre = head;
            if (m<i && i<=n){
                head = next;
            }else{
                head = head->next;    
            }
            ++i;
        }
        return old_head;
    }
};

Dummy head solution

  • always put the dummy head in front of the linked list
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (m==n) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        // head is right before mth node
        for (int i=0; i<m-1; i++){
            head = head -> next;
        }
        
        // reverse the following n-m+1 nodes
        ListNode* pre = head;
        head = head->next;
        ListNode* cur = head;
        ListNode* next;
        bool init = false;
        while (n>=m){
            for (int i=0; i<n-m; i++){ // move to the end of the list to be reversed
                cur = cur->next;
            }
            if (!init){
                init = true;
                next = cur->next;
            }
            pre->next = cur;
            pre = cur;
            cur = head;
            n--;
        }
        pre->next = next;
        head = dummy->next;
        delete dummy;
        return head;
    }
};

An improved solution

  • don’t need to search from the front of the reverse list each time, just put cur in the front of the previous visited nodes
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (m==n) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        // head is right before mth node
        for (int i=0; i<m-1; i++){
            head = head -> next;
        }
        // reverse the following n-m+1 nodes 
        ListNode* pre = head -> next;
        ListNode* cur = pre -> next;
        for (int i=0; i<n-m; i++){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        head->next->next = cur;
        head->next = pre;
        head = dummy->next;
        delete dummy;
        return head;
    }
};
Reverse Linked List II