Day 57 #37, #40, Sudoku Solver, Combination Sum II

Search in Rotated Sorted Array
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

------------------------------------------
set up three 2D arrays as caches to store used numbers in each row, column and sub-block

class Solution {
public:
    bool sudoku (vector<vector<char> > &board, vector<vector<bool> > &rows, 
            vector<vector<bool> > &cols, vector<vector<bool> > &subs, int index) {
        if (index == 81) {
            return true;
        }
        int rowIndex = index / 9;
        int colIndex = index % 9;
        
        if (board[rowIndex][colIndex] == '.') {
            for (int i = 0; i < 9; i++) {
                if (!(rows[rowIndex][i] || cols[colIndex][i] || subs[(rowIndex / 3) * 3 + colIndex / 3][i])) {
                    board[rowIndex][colIndex] = '1' + i;
                    rows[rowIndex][i] = true;
                    cols[colIndex][i] = true;
                    subs[rowIndex / 3 * 3 + colIndex / 3][i] = true;
                    
                    // if conditions is false, backtrack
                    if (!sudoku(board, rows, cols, subs,index + 1)) {
                        board[rowIndex][colIndex] = '.';
                        rows[rowIndex][i] = false;
                        cols[colIndex][i] = false;
                        subs[rowIndex / 3 * 3 + colIndex / 3][i] = false;
                    }else {
                        return true;
                    }
                }
            }
            return false;
        }else {
            // if slot is filled already
            return sudoku(board, rows, cols, subs,index + 1);
        }
    }

    void solveSudoku(vector<vector<char> > &board) {
        // declare and populate caches
        vector<vector<bool> > rows(9,vector<bool>(9,false));
        vector<vector<bool> > cols(9,vector<bool>(9,false));
        vector<vector<bool> > subs(9,vector<bool>(9,false));
        for (int rowIndex = 0; rowIndex < 9; rowIndex++) {
            for (int colIndex = 0; colIndex < 9; colIndex++) {
                if (board[rowIndex][colIndex] != '.') {
                    int val = board[rowIndex][colIndex] - '1';
                    rows[rowIndex][val] = true;
                    cols[colIndex][val] = true;
                    subs[(rowIndex / 3) * 3 + colIndex / 3][val] = true;
                }
            }
        }
        
        // recursive call starts here
        sudoku(board,rows,cols,subs,0);
    }
};

Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
------------------------------------------------------------
Similar to #39 Combination Sum

class Solution {
public:
    void comb (vector<int>& candidates, int target, vector<vector<int> > &ret, vector<int> cur,int start) {
        if (target == 0) {
            ret.push_back(cur);
        }else {
            for (int i = start; i < candidates.size(); i++) {
                if (target - candidates[i] >= 0) {
                    vector<int> v= cur;
                    v.push_back(candidates[i]);
                    comb(candidates,target-candidates[i],ret,v,i+1); // no element can be re-used, so i + 1
                }
                
                // skip duplicates 
                while (candidates.size() - 1 > i && candidates[i] == candidates[i + 1]) {
                    i++;
                }
            }
        }
    }

    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        vector<vector<int> > ret;
        vector<int> cur;
        comb(num,target,ret,cur,0);
        return ret;
    }
};

类似

class Solution {
public:
    void helper(vector<vector<int>> &rt,vector<int>& candidates, vector<int> cur,int target,int index) {
        if (target == 0) {
            rt.push_back(cur);
            return;
        }
        
         if (target < 0 || index >= candidates.size()) return;
        
        vector<int> temp = cur;
        temp.push_back(candidates[index]);
        helper(rt,candidates,temp,target - candidates[index],index + 1);

        while (index + 1 < candidates.size() && candidates[index] == candidates[index + 1]) {
            index++;
        }
        helper(rt,candidates,cur,target,index + 1);
        
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<vector<int>> rt;
        vector<int> cur;
        helper(rt,candidates,cur,target,0);
        
        return rt;
    }
};

Day 56 #33, #34, Search in Rotated Sorted Array, Search for a Range

Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
------------------------------------------------------------
reference with excellent explanation
array is half sorted and the half rotated. Always start with the sorted half then determine which half that our target resides in

class Solution {
public:
    int search(int A[], int n, int target) {
        int start = 0, end = n - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (A[mid] == target) {
                return mid;
            }
            // first half is sorted
            if (A[start] <= A[mid]) {
                if (A[start] <= target && target <= A[mid]) {
                    end = mid - 1;
                }else {
                    start = mid + 1;
                }
            }else { // second half is sorted
                if (A[mid] <= target && target <= A[end]) {
                    start = mid + 1;
                }else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
};

Update on Dec-15-2014
A[end] would never have a chance to be equal to A[mid]. However, A[start] would in the cases that only contain two elements
that's why A[start] <= A[mid]  

Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
-----------------------------------------------------------------
注意掌握以下第一种方法
binary search
if hit target, continue searching to expand the range

class Solution {
public:
    void bin (int A[], int start, int end, int target, vector<int> &ret) {
        if (start > end) return;
        int mid = start + (end - start) / 2;
        if (A[mid] == target) {
            if (mid < ret[0] || ret[0] == -1) {
                ret[0] = mid;
                bin(A,start,mid - 1, target, ret);
            }
            if (mid > ret[1]) {
                ret[1] = mid;
                bin(A,mid + 1,end, target, ret);
            }
        }else if (A[mid] < target) {
            bin(A,mid + 1,end, target, ret);
        }else {
            bin(A,start,mid - 1, target, ret);
        }
    }

    vector<int> searchRange(int A[], int n, int target) {
        vector<int> ret(2,-1);
        bin(A,0,n-1,target,ret);
        return ret;
    }
};

class Solution {
public:
    void leftSearch(int A[], int left, int right, int target, vector<int> &range) {
        if (left > right) {
            return;
        }
        
        int mid = left + (right - left) / 2;
        if (A[mid] == target) {
            range[0] = mid;
            leftSearch(A,left,mid - 1,target,range);
        }else if (A[mid] < target) {
            leftSearch(A,mid + 1,right,target,range);
        }
    }
    
    void rightSearch(int A[], int left, int right, int target, vector<int> &range) {
        if (left > right) {
            return;
        }
        
        int mid = left + (right - left) / 2;
        if (A[mid] == target) {
            range[1] = mid;
            rightSearch(A,mid + 1,right,target,range);
        }else if (A[mid] > target) {
            rightSearch(A,left,mid - 1,target,range);
        }
    }
    

    vector<int> searchRange(int A[], int n, int target) {
        int left = 0;
        int right = n - 1;
        vector<int> range(2,-1);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                range[0] = mid;
                range[1] = mid;
                leftSearch(A,left,mid - 1,target,range);
                rightSearch(A,mid + 1,right,target,range);
                break;
            }else if (A[mid] < target) {
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        
        return range;
    }
};

iterative，用2个额外二分法函数，一个是找连续target的起始点，一个是找连续target的终止点
设置好循环的终止条件就行

Day 55 #32, Longest Valid Parentheses

Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
--------------------------------------------------------------
COME_BACK
DP
dp[i] contains the value of the longest valid parentheses that starts at index i to the end of string s. It is zero if s[i] == ')' or if the corresponding s[j] == '('

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.length() + 1,0);
        int longest = 0;
        
        for (int i = s.length() - 2; i >= 0; i--) {
            if (s[i] == ')') continue;
            int farRight = i + 1 + dp[i + 1];
            if (s[farRight] == ')') dp[i] = 2 + dp[i + 1] + dp[farRight + 1];
            longest = max(longest,dp[i]);
        }
        
        return longest;
    }
};

Solution #2, from internet, stack contains the parentheses whose indexes could not be matched.

The workflow of the solution is as below.

1. Scan the string from beginning to end.
2. If current character is '(', push its index to the stack. If current character is ')' and the character at the index of the top of stack is '(', we just find a matching pair so pop from the stack. Otherwise, we push the index of ')' to the stack.
3. After the scan is done, the stack will only contain the indices of characters which cannot be matched. Then let's use the opposite side - substring between adjacent indices should be valid parentheses.
4. If the stack is empty, the whole input string is valid. Otherwise, we can scan the stack to get longest valid substring as described in step 3.

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length(), longest = 0;
        stack<int> st;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') st.push(i);
            else {
                if (!st.empty()) {
                    if (s[st.top()] == '(') st.pop();
                    else st.push(i);
                }
                else st.push(i);
            }
        }
        if (st.empty()) longest = n;
        else {
            int a = n, b = 0;
            while (!st.empty()) {
                b = st.top(); st.pop();
                longest = max(longest, a-b-1);
                a = b;
            }
            longest = max(longest, a);
        }
        return longest;
    }
};

Updated on Oct-30th-2014
Mine

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                st.push(i);
            }else if (s[i] == ')'){
                // found a match
                if (!st.empty() && s[st.top()] == '(') {
                    st.pop();
                } // not found
                else {
                    st.push(i);
                }
            }
            
        }
        // the whole string is valid
        if (st.empty()) return s.length();
        
        int first = s.length();        
        int longest = 0;
        while (!st.empty()) {
            int cur = st.top();
            st.pop();
            longest = max(longest,first - cur - 1);
            first = cur;
        }
        
        // for cases that have valid parentheses at the beginning
        if (first != 0) {
            longest = max(longest,first - 0);
        }
        
        return longest;
    }
};

Updated on Oct-30th-2014
refactoried of previous solutio, setup two sentinels indicating the beginning and end of string

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ')' && st.size() > 1 && s[st.top()] == '(') {
                st.pop();
            }else {
                st.push(i);
            }
        }

        st.push(s.length());
        int longest = 0;
        while (st.size() > 1) {
            int cur = st.top();
            st.pop();
            longest = max(longest,cur - st.top() - 1);
        }
        
        return longest;
    }
};

Java, updated on Aug-26th-2018
Solution #1 DP,
ToDo, 这题2个方法都要死记

class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        int longest = 0;
        
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) == ')') continue;
            int farRight = i + dp[i + 1] + 1;
            if (farRight < n && s.charAt(farRight) == ')') {
                dp[i] = dp[i + 1] + 2 + dp[farRight + 1];
                longest = Math.max(dp[i], longest);
            }
        }
        
        return longest;
    }
}

Solution #2, stack

class Solution {
        
    public int longestValidParentheses(String s) {
        Stack stC = new Stack<>();
        Stack stI = new Stack<>();
        stI.add(-1);
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!stC.isEmpty() && c == ')' && stC.peek() == '(') {
                stC.pop();
                stI.pop();
            }else {
                stC.add(c);
                stI.add(i);
            }
        }
        
        int longest = 0;
        int cur = s.length();
        while (!stI.isEmpty()) {
            int i = stI.pop();
            longest = Math.max(longest, cur - i - 1);
            cur = i;
        }
        
        return Math.max(0, longest);
    }
}

Solution #3 简单到爆。WOW!!!
考虑"(()" ，光走第一个loop不会得到结果
再考虑"(()(()"，中途抵消掉时增加长度也不会得到正确结果

class Solution {
    public int longestValidParentheses(String s) {
        int longest = 0;
        int left = 0, right = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            }else {
                right++;
            }
            
            if (left == right) longest = Math.max(longest, left + right);
            else if (right > left) {
                right = 0;
                left = 0;
            }
        }
        
        left = 0;
        right = 0;
        
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            }else {
                right++;
            }
            
            if (left == right) longest = Math.max(longest, left + right);
            else if (left > right) {
                right = 0;
                left = 0;
            }
        }
        
        return longest;
    }
}

Day 54 # 29, Divide Two Integers

Divide Two Integers
Divide two integers without using multiplication, division and mod operator. 
-----------------------------------------------------------------
keep multiplying divisor by 2 until divisor is larger than dividend, then divide it by 2
compute the difference between divisor and dividend, set it as the new dividend

class Solution {
public:
    int divide(int dividend, int divisor) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        long long a = abs((double)dividend);;
        long long b = abs((double)divisor);
        int sign = 1;
        if (dividend < 0) sign *= -1; 
        if (divisor < 0) sign *= -1; 
        
        int total = 0; 
        while (a >= b) {
            long long c = b;
            int count = 1;
            while (a >= (c<<1)) {
                c = c << 1;
                count = count << 1;
            }
            a = a - c;
            total += count;
        }
        return total*sign;
    }
};

Java, updated on Aug-6th-2018
原来同上，就是不断的对以下数组里的数进行循环相减，然后更新被除数
[divisor * 2, divisor * 2 ^ 2, divisor * 2 ^ 3, divisor * 2 ^ 4 ...]
注意处理溢出

class Solution {
    public int divide(int dividendInt, int divisorInt) {
        
        long dividend = Math.abs((long)dividendInt);
        long divisor = Math.abs((long)divisorInt);
        
        int sign = 1;
        if (dividendInt < 0) sign *= -1;
        if (divisorInt < 0) sign *= -1;
        
        long count = 0;
        while (dividend >= divisor) {
            int tempCount = 1;
            long tempDivisor = divisor;
            while ((tempDivisor << 1) < dividend) {
                tempCount <<= 1;
                tempDivisor <<= 1;
            }
            
            dividend -= tempDivisor;
            count += tempCount;
        }
        
        if (count > Integer.MAX_VALUE) {
            if (sign == 1) return Integer.MAX_VALUE;
            return Integer.MIN_VALUE; 
        }
        
        return (int) count * sign;
    }
}

Day 53, 28, Implement strStr()

Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
------------------------------------------------- 
KMP, O(n),

class Solution {
public:
    vector<int> computePrefixTable(string pattern) {
        int m = pattern.length();
        vector<int> table(m,0);
        int matchedLength = 0;
        
        for (int i = 1; i < m; i++) {
            // until find the next char at matchedLength is equal to char at i
            // or matchedLength is zero
            while (matchedLength > 0 && pattern[matchedLength] != pattern[i]) {
                matchedLength = table[matchedLength - 1];
            }
            if (pattern[matchedLength] == pattern[i]) {
                matchedLength++;
            }
            table[i] = matchedLength;
        }
        
        return table;
    }
    
    int KMP(string source, string pattern) {
        int n = source.length();
        int m = pattern.length();
        vector<int> table = computePrefixTable(pattern);
        int matchedLength = 0;
        
        for (int i = 0; i < n; i++) {
            while (matchedLength > 0 && pattern[matchedLength] != source[i]) {
                matchedLength = table[matchedLength - 1];
            }
            
            if (pattern[matchedLength] == source[i]) {
                matchedLength++;
            }
            if (matchedLength == m) {
                return i - m + 1;
            }
        }
        
        return -1;
    }

    int strStr(string haystack, string needle) {
        if (needle == "") return 0;
        if (haystack == "") return -1;
        return KMP(haystack,needle);
    }
};

Solution #2 O(m*n), improved brute force

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (*needle == NULL) return haystack;
        if (!*haystack) return NULL;
        char* adv = haystack;
        char* temp = needle;
        while (*++temp) {
            adv++;
        }
        
        while (*adv != NULL) {
            char* itr1 = haystack;
            char* itr2 = needle;
            while (*itr1 && *itr2 && *itr1 == *itr2) {
                itr1++;
                itr2++;
            }
            if (!*itr2) return haystack;
            haystack++;
            adv++;
        }
        return NULL;
    }
};

Day 52, 25, Reverse Nodes in k-Group

Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
---------------------------------------------------------------------
Iterative, similar toDay 42, #92 Reverse Linked List II
How to tackle this using recursion? Later !!!
-- relax, it is easy,

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (k == 1) return head;
        if (head == NULL || head->next == NULL) return head;
        ListNode *newHead = head,*itr = head, *tail = NULL;
        int count = 0;
        while(itr != NULL) {
            itr = itr->next;
            count++;
            if (count == k) {
                ListNode* newTail = newHead, *itr2 = newHead;
                newHead = tail;
                while (count > 0) {
                    ListNode* next = itr2->next;
                    itr2->next = newHead;
                    newHead = itr2;
                    itr2 = next;
                    count--;
                }
                if (tail == NULL) {
                    head = newHead;
                }else  tail->next = newHead;
                newTail->next = itr2;
                tail = newTail;
                newHead = itr2;
            }
        }
        return head;
    }
};

Update on Feb-06-2015
Using dummy node

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (k <= 1 || head == NULL) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy;
        
        int count = 0;
        while (head != NULL) {
            count++;
            
            if (count == k) {
                // reverse
                ListNode *newHead = NULL, *itr = pre->next, *tempNext = head->next;
                while (itr != tempNext) {
                    ListNode *temp = itr->next;
                    itr->next = newHead;
                    newHead = itr;
                    itr = temp;
                }
                ListNode *tail = pre->next;
                pre->next = newHead;
                pre = tail;
                tail->next = tempNext;
                head = tempNext;
                count = 0;
            }else
                head = head->next;
        }
        
        return dummy->next;
    }
};

Day 51, #5, Longest Palindromic Substring(*) ATTENTION NEEDED

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.
 -------------------------------------------
Solution#1 O(n^2),
there are (2n - 1) centers for all possible palindromes

class Solution {
public:
    void pal (string s, int &left, int &right, int &maxLeft,int &maxRight) {
        while (left >= 0 && right < s.length()) {
            if (s[left] == s[right]) {
                left--;
                right++;
            }else {
                break;
            }
        }
        if (maxRight - maxLeft < right - left - 2) {
                maxLeft = left + 1;
                maxRight = right - 1;
        }
    }

    string longestPalindrome(string s) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (s.length() == 1) return s;
        int maxLeft = 0;
        int maxRight = 0;
        int center = 1;
        int max = 0;
        for (;center < s.length(); center++) {
            int left = center - 1;
            int right = center;
            pal(s,left,right,maxLeft,maxRight); // even
            left = center - 1;;
            right = center + 1;
            pal(s,left,right,maxLeft,maxRight); // odd
        }
        return s.substr(maxLeft,maxRight - maxLeft + 1);
    }
};

Solution#2 O(n) 
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
Jun-27-2015
Manacher's algorithm

class Solution {
public:
    string processString(string s) {
        if (s.length() == 0) return s;
        string rt = "";
        for (int i = 0; i < s.length(); i++) {
            rt = rt + "#" + s[i];
        }
        rt += '#';
        return rt;
    }

    string longestPalindrome(string s) {
        string t = processString(s);
        vector<int> p(t.length(),0);
        int center = 1, rightExpand = 1;
        
        for (int i = 1; i < t.length(); i++) {
            int i_mirror = center - (i - center); 
            if (rightExpand > i) {
                p[i] = min(rightExpand - i,p[i_mirror]);
            }
            
            while (i + 1 + p[i] > 0 && i + 1 + p[i] < t.length() && t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
                cout << p[i] << endl;
                p[i]++;
            }
            
            if (i + p[i] > rightExpand) {
                rightExpand = i + p[i];
                center = i;
            }
        }
        
        int longest = 0;
        int index = 0;
        for (int i = 0; i < p.size(); i++) {
            if (longest < p[i]) {
                index = i;
                longest = p[i];
            }
        }
        return s.substr((index - longest) / 2, longest);
    }
};