Recursive & DP - Binary Tree Maximum Path Sum

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        if(root == null){
            return 0;
        }
        int[] result = new int[2];
        result = maxPathSumTracker(root);
        return result[1];
    }
 
    private int[] maxPathSumTracker(TreeNode node){
        int[] result = new int[2];
        if(node == null){
            result[1] = Integer.MIN_VALUE;
            return result;
        }
        int[] resultLeft = maxPathSumTracker(node.left);
        int[] resultRight = maxPathSumTracker(node.right);
        result[0] = Math.max(Math.max(resultLeft[0], resultRight[0]) + node.val,  node.value);
        result[1] = Math.max(Math.max(resultLeft[1], resultRight[1]), Math.max(resultLeft[0] + node.val + resultRight[0], result[0]));
        return result;
    }
}

Bit Solution - Find missing element in an array *

There are few solutions: 

   1. Add from 1 to N, and minus each element from the array, the remaining is the result;

   2. Improved from solution 1, as the sum could be too large. Use the XOR for from 0 to N, and then XOR each element in the array, the remaining is the result. 

   3. But solution 1 and 2 are not good for duplicates, so another solution is proposed,as an array size of the biggest element in the array, loop the array then find the one(s) appear zero times.

   4. Improved from solution 3, as the integer array takes O(n) space, and bit is enough for this problem. Use integer which is 32 bits instead of array which could save 31 times space. 1 means appearance, and 0 otherwise. 

public class FindMissingK {

public static void main(String[] args) {

int[] input = { 3, 1, 2, 4, 0 };

System.out.println(findMissKValue(input, 5));

}

private static int findMissKValue(int[] inputs, int n) {

int process = 0;

for (int i = 1; i <= n; i++) {

process = process ^ i;

}

for (int i = 0; i < inputs.length; i++) {

// if (inputs[i] != 0) {

process = process ^ inputs[i];

// }

}

return process;

}

}

String Solution - Find positions of each word (in dictionary) in a given text *

http://en.wikipedia.org/wiki/Aho–Corasick_string_matching_algorithm, KMP are two optical ways to resolve this problem, but they are too complicated for a one hour interview. So the solution below is an acceptable solution. Loop the dict and find one a time in the pass in text.

public class FindInstrumentName {

public static void main(String[] args) {

String[] inputs = { "dog", "cat", "pig" };

String text = "a dogkcat pig playcat,pigdone";

Map<Integer, String> test = findInstruments(inputs, text);

Set<Integer> resSet = test.keySet();

Iterator it = resSet.iterator();

System.out.println(text.length());

while (it.hasNext()) {

int curIndex = (Integer) it.next();

System.out.println(curIndex + "->" + test.get(curIndex));

}

}

private static Map<Integer, String> findInstruments(String[] dict,

String text) {

Map<Integer, String> result = new HashMap<Integer, String>();

for (int i = 0; i < dict.length; i++) {

findInstrumentOps(dict[i], text, result);

}

return result;

}

private static void findInstrumentOps(String word, String text,

Map<Integer, String> result) {

for (int i = 0; i <= text.length() - word.length(); i++) {

int j = 0;

int index = i;

while (j < word.length()) {

if (!(isValiedCharacter(text.charAt(i)))) {

i++;

continue;

}

if (text.charAt(i) != word.charAt(j)) {

break;

}

if (j == word.length() - 1) {

result.put(index, word);

}

i++;

j++;

}

}

}

private static boolean isValiedCharacter(char c) {

if (c <= 'z' && c >= 'a') {

return true;

}

return false;

}

}

Loop Solution - Palindrome Number

public class Solution {
    public boolean isPalindrome(int x) {
     
        if(x < 0){
            return false;
        }
     
        // Stack<Integer> processStack = new Stack<Integer>();
        // Queue<Integer> processQueue = new LinkedList<Integer>();
        // //int divide = x / 10;
        // //int remain = x % 10;
        // while(x / 10 != 0 || x % 10 != 0){
        //     processStack.push(x % 10);
        //     processQueue.offer(x % 10);
        //     x = x / 10;
        // }
     
        // while(!processStack.isEmpty() && !processQueue.isEmpty()){
        //     if(processStack.pop() != processQueue.poll()){
        //         return false;
        //     }
        // }
     
        // if(!processStack.isEmpty() || !processQueue.isEmpty()){
        //     return false;
        // }
     
        // return true;
     
        int size = 0;
        int base = x;
        while(base / 10 != 0 || base % 10 != 0){
            ++size;
            base = base / 10;
        }
        int[] process = new int[size];
        while((x / 10 != 0 || x % 10 != 0) && size >= 0){
            process[--size] = x % 10;
            x = x / 10;
        }
        int lpS = 0;
        int lpE = process.length - 1;
        while(lpS < lpE){
            if(process[lpS] != process[lpE]){
                return false;
            }
            lpS++;
            lpE--;
        }
     
        return true;
    }
}

Loop Solution - Minimum Window Substring ***??

class Solution {
public:
    string minWindow(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (S.size()<T.size()){return "";}
           
        map<char,int>mp; // store chars occurrence of T
        for(int i=0;i<T.size();i++){mp[T[i]]++;}
       
        int res_len=INT_MAX; // result length
        int res_p=0;//result start posiion
       
        int p=0; //pointer start
        int q=S.size()-1; //pointer end
       
        while (mp[S[p]]==0){if(p>=S.size()){return "";} p++;} //remove irralevent starting chars
        while (mp[S[p]]==0){q--;if(q<0){return "";}} // remove irralevent ending chars
       
        map<char,int> tab; //store chars occurrence of S[p:q]
        for (int i=p;i<=q;i++){tab[S[i]]++;}
                   
        while (tab[S[q]]>mp[S[q]] || mp[S[q]]==0){ // move q to left find the 1st covered substring
           tab[S[q]]--;
           q--;
        }
           
        for (int i=0;i<T.size();i++){  // if no covered substring found, return ""
            if (tab[T[i]]<mp[T[i]]){return "";}
        }
   
        if (q-p+1<res_len){res_len=q-p+1; res_p=p;} //store the result
       
       
        while (p<q){
            if (q-p+1<res_len){res_len=q-p+1; res_p=p;} //store the result
            if (mp[S[p]]==0){p++;continue;} // if current char is not in T, go next
            if (tab[S[p]]>mp[S[p]]){tab[S[p]]--;p++;continue;} // if more chars in this substring, go next
           
            q++;
            while (q<S.size() && S[q]!=S[p]){ if (mp[S[q]]>0){tab[S[q]]++;} q++;} //move q to find a substring covers T
            if (q>=S.size()){q=S.size()-1;}else{tab[S[q]]++;}
           
            if (S[q]==S[p]){ tab[S[p]]--; if (tab[S[p]]<mp[S[p]]){break;} p++;continue;}      
            break;
        }
       
        return S.substr(res_p,res_len);
    }
};

Bit Operation Solution - Divide Two Integers ??

public class Solution {
    public int divide(int dividend, int divisor) {
        long a = Math.abs((long) dividend), b=Math.abs((long) divisor);
        long[] res= dividePos(a,b);
        long temp = dividend>0&&divisor<0||dividend<0&&divisor>0?-res[0]:res[0];
        return (int) temp;
    }
   
    public long[] dividePos(long a, long b){
        long[] res = new long[2];
        if(a<b){
            res[0]=0;
            res[1]=a;
        }else if(a==b){
            res[0]=1;
            res[1]=0;
        }else{
            long[] temp=dividePos(a>>1,b);
            res[0] = temp[0]<<1;
            res[1] = temp[1]<<1;
            if((a & 1)==1) res[1]+=1;
            if(res[1]>=b){
                res[0]+=1;
                res[1]-=b;
            }
        }
        return res;
    }
}

N Queen II ?

class Solution {
public:
    int res;
     
    bool isValid(int A[], int r){
        for (int i=0;i<r;i++){
            if ( (A[i]==A[r])||(abs(A[i]-A[r])==(r-i))){
                return false;
            }
        }
        return true;
    }
    void nqueens(int A[], int cur, int n){
        if (cur==n){ res++;return;}
        else{
            for (int i=0;i<n;i++){
                A[cur]=i;
                if (isValid(A,cur)){
                    nqueens(A,cur+1,n);
                }
            }
        }
    }
    int totalNQueens(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        res=0;
        int *A = new int[n];
        nqueens(A,0,n);
        return res;
    }
};

N Queen ?

class Solution {
public:

    vector<vector<string> > res;
   
    void printres(vector<int> A,int n){
        vector<string> r;
        for(int i=0;i<n;i++){
            string str(n,'.');
            str[A[i]]='Q';
            r.push_back(str);
        }
        res.push_back(r);
    }
   
   
    bool isValid(vector<int> A, int r){
        for (int i=0;i<r;i++){
            if ( (A[i]==A[r])||(abs(A[i]-A[r])==(r-i))){
                return false;
            }
        }
        return true;
    }
   
    void nqueens(vector<int> A, int cur, int n){
        if (cur==n){printres(A,n);}
        else{
            for (int i=0;i<n;i++){
                A[cur]=i;
                if (isValid(A,cur)){
                    nqueens(A,cur+1,n);
                }
            }
        }
    }
     
    vector<vector<string> > solveNQueens(int n) {
        res.clear();
        vector<int> A(n,-1);
        nqueens(A,0,n);
        return res;
    }
};

Binary Solution - Median of Two Sorted Arrays ?

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        return median(A, 0, A.length, B);
    }

    public double median(int[] a, int i, int j, int[] b) {
        if (j  > valueAt(b, i*b)) {
            return median(a, i, i*a, b);
        } else if (valueAt(a, i*a) < valueAt(b, i*b - 1)) {
            return median(a, i*a + 1, j, b);
        } else {
            return (a.length + b.length) % 2 == 1 ? valueAt(a, i*a):
                (valueAt(a, i*a) + Math.max(valueAt(a, i*a - 1), valueAt(b, i*b - 1))) / 2.0;
        }
    }

    public int valueAt(int[] arr, int i) {
        if (i = arr.length) return Integer.MAX_VALUE;
        else return arr[i];
    }
}

Loop Solution - ZigZag Conversion ??

public class Solution {
    public String convert(String s, int nRows) {
        if(nRows < 0 || s == null){
            return null;
        }
        if(s.length() == 0 || s.length() == 1 || nRows == 1 || s.length() <= nRows){
            return s;
        }
        int process = 2 * nRows - 2;
        int numOfColumns = (s.length() / process) * (nRows - 1);
        if(s.length() % process != 0){
            if(s.length() % process > nRows){
                numOfColumns = numOfColumns + ((s.length() % process) - nRows) + 1;
            }else{
                numOfColumns = numOfColumns + 1;
            }
        }
        char[][] result = new char[nRows][numOfColumns];
        int loop = 0;
        while(loop < s.length()){
            int curColumn = (loop / process) * (nRows - 1);
            if(loop % process > nRows - 1){
                curColumn = curColumn + ((loop % process) - (nRows - 1));
                int curRow = nRows - ((loop % process) - (nRows - 1)) - 1;
                result[curRow][curColumn] = s.charAt(loop);
            }else{
                result[loop % process][curColumn] = s.charAt(loop);
            }
            loop++;
        }
        StringBuilder resultString = new StringBuilder();
        for(int i = 0; i < nRows; i++){
            for(int j = 0; j < numOfColumns; j++){
                if(result[i][j] != '\u0000'){
                    resultString.append(result[i][j]);  
                }
            }
        }
        return resultString.toString();
    }
}

Loop Solution - Regular Expression Matching ?

public class Solution {
    public boolean isMatch(String s, String p) {
        if(p.isEmpty()){
            return s.isEmpty();
        }
       
        if(p.length() == 1 || p.charAt(1)!='*'){
            if(s.length()<1 || (p.charAt(0)!='.' && p.charAt(0)!=s.charAt(0)))
                return false;
            return isMatch(s.substring(1),p.substring(1));
        }else{
            while(!s.isEmpty() && (p.charAt(0)=='.' || p.charAt(0)==s.charAt(0))){
                if(isMatch(s, p.substring(2))){
                    return true;
                }
                else{
                    s = s.substring(1);
                }
            }
            return isMatch(s, p.substring(2));
        }
    }
}

Loop Solution - Longest Substring Without Repeating Characters *

This is a loop approach. The hard part is how to update the cur position when loop to a char same as between current position and loop position. (use while loop from cur position to the first char same as loop position) The other hard part is during the while loop to the first Char, need to update the char count array (256), chars between old cur to new cur (first dup as loop position + 1) to be count as 0, since a new count will begin, they are free if appear after loop, as they will count into next substring. All before cur current position, count will be 0. 

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null){
            return Integer.MIN_VALUE;
        }
        int maxLength = 0;
        int curPos = 0;
        int loopPos = 0;
        boolean[] record = new boolean[256];
        while(loopPos < s.length()){
            if(record[s.charAt(loopPos)]){
                if((loopPos - curPos) > maxLength){
                    maxLength = loopPos - curPos;
                }
                while(s.charAt(curPos) != s.charAt(loopPos)){
                    record[s.charAt(curPos)] = false;
                    curPos++;
                }
                loopPos++;
                curPos++;
               
            }else{
                record[s.charAt(loopPos)] = true;
                loopPos++;
            }
        }
        if(s.length() - curPos > maxLength){
            maxLength = s.length() - curPos;
        }
        return maxLength;
    }
}

Loop Solution - Add Two Numbers

This problem can be converted to be reverse first then reverse back after summing. Be careful of the carry digit, and update it after sum calculation.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //boolean nextAdd = false;
        int carry = 0;
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode node = newHead;
        while(l1 != null && l2 != null){
            int curValue = 0;
            if(l1.val + l2.val + carry > 9){
                curValue = (carry + l1.val + l2.val - 10);
                carry = 1;
            }else{
                curValue = l1.val + l2.val + carry;
                carry = 0;
            }
            node.next = new ListNode(curValue);
            l1 = l1.next;
            l2 = l2.next;
            node = node.next;
        }
       
        while(l1 != null){
            int curValue = 0;
            if(l1.val + carry > 9){
                curValue = l1.val + carry - 10;
                carry = 1;
            }else{
                curValue = l1.val + carry;
                carry = 0;
            }
            node.next = new ListNode(curValue);
            l1 = l1.next;
            node = node.next;
        }
       
        while(l2 != null){
            int curValue = 0;
            if(l2.val + carry > 9){
                curValue = l2.val + carry - 10;
                carry = 1;
            }else{
                curValue = l2.val + carry;
                carry = 0;
            }
            node.next = new ListNode(curValue);
            l2 = l2.next;
            node = node.next;
        }
       
        if(carry == 1){
            node.next = new ListNode(1);
            node = node.next;
        }
       
        return newHead.next;
    }
}

Loop Solution - Longest Palindromic Substring **

The idea is to loop the String, for each char to find the longest palindrome, case 1 center is one letter and case 2 is that center is another two letters are equal.

Some questions need to be clarified: like lower case upper case, like space or other specials

public class Solution {
    public String longestPalindrome(String s){
        if(s == null || s.length() == 0){
            return s;
        }
        int maxLength = 0;
        String maxString = null;
        int i  = 0;
        while(i < s.length()){
            int curLength = 1;
            int next = i + 1;
            int prev = i - 1;
            while(prev >= 0 && next < s.length()){
                if(s.charAt(prev) == s.charAt(next)){
                    curLength = curLength + 2;
                    next++;
                    prev--;
                }else{
                    break;
                }
            }
            if(curLength > maxLength){
                maxLength = curLength;
                if(next > s.length()){
                    next = s.length();
                }
                maxString = s.substring(prev + 1, next);
            }
            //case 2: even palidrome
            if(i + 1 < s.length() && s.charAt(i + 1) == s.charAt(i)){
                prev = i - 1;
                next = i + 2;
                curLength = 2;
                while(prev >= 0 && next < s.length()){
                    if(s.charAt(prev) == s.charAt(next)){
                        curLength = curLength + 2;
                        next++;
                        prev--;
                    }else{
                        break;
                    }
                }
                if(curLength > maxLength){
                    maxLength = curLength;
                    maxString = s.substring(prev + 1, next);
                }
            }
            i++;
        }
        return maxString;
    }
}

Loop Solution - Reverse Integer

The idea is to set result to be 0, and then result * 10 + x % 10, then use next digit of x, which is x / 10 …until x == 0

public class Solution {
    public int reverse(int x) {
        int result = 0;
        while(x != 0){
            result = result * 10 + x % 10;
            x = x / 10;
        }
        return result;
    }
}

Loop Solution - String to Integer

since it is integer, don't worry about decimal point or e, and be careful of the first digit is + or -. Remember to result = 10 * result + cur Number.

public class Solution {
    public int atoi(String str) {
        if(str ==  null || str.length() == 0){
            return 0;
        }
        str = str.trim();
        int digits = 0;
        if(str.charAt(0) == '+' || str.charAt(0) == '-'){
            digits = str.length() - 1;
        }else{
            digits = str.length();
        }
        long result = 0;
        int loopDigit = str.length() - digits;
        while(loopDigit < str.length()){
            if(str.charAt(loopDigit) < 48 || str.charAt(loopDigit) > 57) {
                break;
            }
            result = 10 * result + (str.charAt(loopDigit) - 48);
            loopDigit++;
        }
        if(str.charAt(0) == '-'){
            result = result * (-1);
        }
        if(result > Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }
        if(result < Integer.MIN_VALUE){
            return Integer.MIN_VALUE;
        }
        return (int)result;
    }
}

Loop Approach - Container with Most Water *

The idea is to loop the array, from both side to middle.

public class Solution {
    public int maxArea(int[] height) {
        if(height == null || height.length < 2){
            return 0;
        }
        int begin = 0;
        int end = height.length - 1;
        int curMax = 0;
        while(begin < end){
            if(curMax < (end - begin) * (height[end] > height[begin]?height[begin]:height[end])){
                curMax = (end - begin) * (height[end] > height[begin]?height[begin]:height[end]);
            }
            if(height[begin] < height[end]){
                begin++;
            }else{
                end--;
            }
        }
        return curMax;
    }
}

Loop Solution - Integer to Roman

The idea is to loop by dividing the target number. Notice that 4 and 9 cases, which are different from regular cases. And if processed as 9, the next number is also different, which skip 5 cases.

Just be careful and calmed. Resolve it level by level until reach target to be 0 as target % 1.

public class Solution {
    public String intToRoman(int num) {
        if(!(num >= 1 || num < 4000)){
            return null;
        }
        StringBuilder res = new StringBuilder();
        while(num > 0){
            if(num >= 1000){
                int dividing = num / 1000;
                num = num % 1000;
                for(int i = 0; i < dividing; i++){
                    res.append("M");
                }
            }else if(num >= 500){
                if(num >= 900){
                    res.append("CM");
                    num = num % 100;
                }else{
                    res.append("D");
                    num = num % 500;
                }
            }else if(num >= 100){
                if(num >= 400){
                    res.append("CD");
                }else{
                    int dividing = num / 100;
                    for(int i = 0; i < dividing; i++){
                        res.append("C");
                    }
                }
                num = num % 100;
            }else if(num >= 50){
                if(num >= 90){
                    res.append("XC");
                    num = num % 10;
                }else{
                    res.append("L");
                    num = num % 50;
                }
            }else if(num >= 10){
                if(num >= 40){
                    res.append("XL");
                }else{
                    int dividing = num / 10;
                    for(int i = 0; i < dividing; i++){
                        res.append("X");
                    }
                }
                num = num % 10;
            }else if(num >= 5){
                if(num == 9){
                    res.append("IX");
                    num = num % 1;
                }else{
                    res.append("V");
                    num = num % 5;
                }
            }else if(num > 0){
                if(num == 4){
                    res.append("IV");
                }else{
                    for(int i = 0; i < num; i++){
                        res.append("I");
                    }
                }
                num = num % 1;
            }
        }
        return res.toString();
    }
}

Loop Solution - Valid Sudoku

The idea is to loop each vertical and horizontal and each 3*3 qualified square, by verify each of those units are unique numbers. A set helps.

The key is to not afraid, just analyze what the problem is, what is the way to resolve such a problem! Loop is necessary, make the decision that loop!

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean isValid = true;
//Horizontally
for(int i = 0; i < 9; i++){
Set<Integer> processH = new HashSet<Integer>();
for(int j = 0; j < 9; j++){
if(board[i][j] != '.' && !processH.add(board[i][j] - '0')){
isValid = false;
}
}
}
//Vertically
for(int j = 0; j < 9; j++){
Set<Integer> processV = new HashSet<Integer>();
for(int i = 0; i < 9; i++){
if(board[i][j] != '.' && !processV.add(board[i][j] - '0')){
isValid = false;
}
}
}
//each 3*3
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
Set<Integer> processS = new HashSet<Integer>();
for(int m = 0; m < 3; m++){
for(int n = 0; n < 3; n++){
if(board[i * 3 + m][j * 3 + n] != '.' && !processS.add(board[i * 3 + m][j * 3 + n] - '0')){
isValid = false;
}
}
}
}
}
return isValid;
    }
}

Recursive DFS Solution - Sudoku Solver ***

The idea is to set flags for each position, as row, column and square with the number on it. Recursive call, with the current position, if  not '.', try recursive call itself for next depth (each depth is actually the cell inside), else loop from 1 to 9, if the number is not in any flags, row, column and square, then change the current position to that number, and recursive call with updated depth. If the recursive call returns false, revert the previous change, and do for next iteration.

This is a DFS process by recursive call.

public class Solution {
public void solveSudoku(char[][]board){
if(board == null){
return;
}
boolean[][] rowB = new boolean[10][10];
boolean[][] colB = new boolean[10][10];
boolean[][] gridB = new boolean[10][10];

for(int i = 0; i < 81; i++){
int rowN = i / 9;
int colN = i % 9;
int gridN = rowN / 3 * 3 + colN / 3;
if(board[rowN][colN] != '.'){
int num = board[rowN][colN] - '0';
rowB[rowN][num] = true;
colB[colN][num] = true;
gridB[gridN][num] = true;
}
}

solveOps(board, rowB, colB, gridB, 0);
}

private boolean solveOps(char[][] board, boolean[][] rowB, boolean[][] colB, boolean[][] gridB, int depth){
if(depth == 81){
return true;
}
int rowIndex = depth / 9;
int colIndex = depth % 9;
int gridIndex = rowIndex / 3 * 3 + colIndex / 3;

if(board[rowIndex][colIndex] != '.'){
return solveOps(board, rowB, colB, gridB, depth + 1);
}

for(int num = 1; num <= 9; num++){
if(!rowB[rowIndex][num] && !colB[colIndex][num] && !gridB[gridIndex][num]){
rowB[rowIndex][num] = true;
colB[colIndex][num] = true;
gridB[gridIndex][num] = true;
board[rowIndex][colIndex] = (char)(num + '0');

if(solveOps(board, rowB, colB, gridB, depth + 1)) {return true;};

board[rowIndex][colIndex] = '.';
rowB[rowIndex][num] = false;
colB[colIndex][num] = false;
gridB[gridIndex][num] = false;
}
}

return false;
    }
}

Loop Solution - Roman to Integer *

The idea is to loop the String, take each char for count. A map is implemented to save Roman char to numbers. And notice if (index) < (index+1), use (i + 1) - (i) to the result. This affect the loop condition too.


public class Solution {
    public int romanToInt(String s) {
        if(s == null){
            return 0;
        }
        Map<Character, Integer> romanIntegerTable = new HashMap<Character,Integer>();
        romanIntegerTable.put('I', 1);
        romanIntegerTable.put('V', 5);
        romanIntegerTable.put('X', 10);
        romanIntegerTable.put('L', 50);
        romanIntegerTable.put('C', 100);
        romanIntegerTable.put('D', 500);
        romanIntegerTable.put('M', 1000);
     
        int result = 0;
        int index = 0;
        while(index < s.length() - 1){
         
            if(!romanIntegerTable.containsKey(s.charAt(index)) || !romanIntegerTable.containsKey(s.charAt(index + 1))){
                return Integer.MIN_VALUE;
            }
         
            if(romanIntegerTable.get(s.charAt(index)) < romanIntegerTable.get(s.charAt(index + 1))){
                result += (romanIntegerTable.get(s.charAt(index + 1)) - romanIntegerTable.get(s.charAt(index++)));
                index++;
            }else{
                result += romanIntegerTable.get(s.charAt(index++));
            }
            //index++;
        }
        if(index == s.length() - 1){
            result += romanIntegerTable.get(s.charAt(index));
        }
        return result;
    }
}

Loop Solution - Longest Common Prefix

The idea is to take the first as a sample String. Loop through the same String, and inside the loop, compare each char by order with each of the other Strings in the array, see if it matches. If yes, add the char to the result, otherwise exit the loop, return the result.


public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        if(strs.length == 1){
            return strs[0];
        }
        String sample = strs[0];
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < sample.length(); i++){
            boolean isPrefix = true;
            for(int j = 1; j < strs.length; j++){
                if(i < strs[j].length()){
                    if(strs[j].charAt(i) != sample.charAt(i)){
                        isPrefix = false;
                    }
                }else{
                    isPrefix = false;
                    break;
                }
            }
            if(isPrefix){
                result.append(sample.charAt(i));
            }else{
                break;
            }
        }
        return result.toString();
    }
}

Loop Solution - Two Sum

The idea is to use a map to record array information, one is for values to index to retrieve index results, and the other one is to record each value's appearance times. Leetcode test cases are friendly that don't have duplicates, but it is necessary to clarify and check it.

It is not necessary to sort since sort cost more than O(n). For other cases, since we have outer loop, sort is necessary since the code requires a way to mark out loops. And 3Sum or more are itself cost more than O(n), sort is NOT added any more time complexity.

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if(numbers == null || numbers.length == 0){
            return null;
        }
        Map<Integer, Integer> process = new HashMap<Integer, Integer>();
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        for(int i = 0; i < numbers.length; i++){
            process.put(numbers[i], i);
            if(count.containsKey(numbers[i])){
                count.put(numbers[i], count.get(numbers[i]) + 1);
            }else{
                count.put(numbers[i], 1);
            }
        }
       
        int index1 = 0;
        int index2 = 0;
        for(int i = 0; i < numbers.length; i++){
            if(process.containsKey(target - numbers[i]) && (i != process.get(target - numbers[i]) || (i == process.get(target - numbers[i]) && count.get(numbers[i]) > 1))){
                index1 = i + 1;
                index2 = process.get(target - numbers[i]) + 1;
                if(index1 > index2){
                    int temp = index1;
                    index1 = index2;
                    index2 = temp;
                }
                break;
            }
        }
        int[] result = new int[2];
        result[0] = index1;
        result[1] = index2;
        return result;
    }
}

Loop Approach Solution - 3Sum Closest

The idea is same as 3Sum, but add a distance check and update the result each time/approach. Watch how the loop work. This one doesn't case duplicates anyway better to have.

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        if(num == null || num.length < 3){
            return Integer.MIN_VALUE;
        }
        Arrays.sort(num);
        int i = 0;
        int result = num[0] + num[1] + num[2];
        int distance = Integer.MAX_VALUE;
        while(i < num.length - 2){
            int curTarget = target - num[i];
            int start = i + 1;
            int end = num.length - 1;
            while(start < end){
                if(Math.abs(num[start] + num[end] - curTarget) < distance){
                    distance = Math.abs(num[start] + num[end] - curTarget);
                    result = num[start] + num[end] + num[i];
                }
                if(num[start] + num[end] < curTarget){
                    start++;
                }else if(num[start] + num[end] > curTarget){
                    end--;
                } else{
                    return target;
                }
            }
            i++;
        }
        return result;
    }
}

Loop Approach Solution - 3Sum

The idea is to convert this to two number sum question by add one outside loop. To avoid duplicates by comparing with previous (0 case excluded as -1). Sort is must have before all operations.

Loop condition is another factor, and how it loops. Only loop after current out side index is sufficient.

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        if(num == null || num.length < 3){
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        for(int i = 0; i < num.length - 2; i++){
            if (i > 0 && num[i] == num[i - 1]) {
continue;
}
            int curTar = 0 - num[i];
            int start = i + 1;
            int end = num.length - 1;
            while(start < end){
                if(num[start] + num[end] > curTar){
                    end--;
                }else if(num[start] + num[end] < curTar){
                    start++;
                }else{
                    ArrayList<Integer> result = new ArrayList<Integer>();
                    result.add(num[i]);
                    result.add(num[start]);
                    result.add(num[end]);
                    results.add(result);
                    while(++start< --end && num[start] == num[start - 1] && num[end] == num[end + 1]);
                }
            }
        }
        return results;
    }
}

Loop Approach Solution - 4Sum

The idea is to narrow down 4 to 2, by two extra outside loops. The hard part is to avoid duplicated, by three different necessary moves: skip directly by skipping 0 case (-1), skip from second iteration by default pre value to -1 and set it in iterations, skip by a while loop for all pre on both sides(++ and --). Sort is must have before all operations.

Details is to notice the loop condition. And only loop ranges after the current index at outside loop is sufficient!

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        if(num == null || num.length < 4){
            return new ArrayList<ArrayList<Integer>>();
        }
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
     
        for(int s1 = 0; s1 < num.length - 3; s1++){
            if(s1 > 0 && num[s1] == num[s1 - 1]){ //Skip 0 case
                continue;
            }
            int curT = target - num[s1];
            int preS2 = -1;  //record previous position of s2 [0,0,0,0] vs [1, 0, 0, 0, 0] aroused this idea (fail either before)
            for(int s2 = s1 + 1; s2 < num.length - 2; s2++){ //Track previous s2 but need to start checkin at the second loop to not touch s1, that is why set pre first... the first iteration skips checks
                if( preS2 != -1 && num[s2] == num[preS2]){
                    continue;
                }
                preS2 = s2;
                int curTarget = curT - num[s2];
                int s3 = s2 + 1;
                int s4 = num.length - 1;
                while(s3 < s4){
                    if(num[s3] + num[s4] > curTarget){
                        s4--;
                    }else if(num[s3] + num[s4] < curTarget){
                        s3++;
                    }else{
                        ArrayList<Integer> result = new ArrayList<Integer>();
                        result.add(num[s1]);
                        result.add(num[s2]);
                        result.add(num[s3]);
                        result.add(num[s4]);
                        results.add(result);
                        while(++s3 < --s4 && num[s3] == num[s3 - 1] && num[s4] == num[s4 + 1]); //Skip duplicates
                    }
                }
            }
        }    
        return results;
    }
}

Recursive Solution - Letter Combinations of a Phone Number

A map is created to store the relations between numbers and Strings. Other than this, it is a typical recursive approach.

public class Solution {
    Map<Character, String> keyboards = new HashMap<Character, String>();
   
    public ArrayList<String> letterCombinations(String digits) {
       
        ArrayList<String> results = new ArrayList<String>();
       
        if(digits == null || digits.length() == 0){
            results.add(""); //guarantee results is not null/empty.
            return results;
        }
       
        if(keyboards.get('2') == null){
            buildMap();
        }
       
        ArrayList<String> preResults = letterCombinations(digits.length() < 2? null : digits.substring(1));
        String cur = keyboards.get(digits.charAt(0));
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < cur.length(); i++){
            res.delete(0, res.length());
            res.append(cur.charAt(i));
            // if(preResults.size() == 0){
            //     results.add(res.toString());
            // }else{
                for(String preResult : preResults){
                    res.delete(1, res.length());
                    res.append(preResult);
                    results.add(res.toString());
                }
            //}
        }
        return results;
    }
   
    private void buildMap(){
        keyboards.put('2', "abc");
        keyboards.put('3', "def");
        keyboards.put('4', "ghi");
        keyboards.put('5', "jkl");
        keyboards.put('6', "mno");
        keyboards.put('7', "pqrs");
        keyboards.put('8', "tuv");
        keyboards.put('9', "wxyz");
        keyboards.put('0', " ");
    }
}

Loop Solution - Remove Nth Node From End of List

The idea is to find the K node, by extend range and move the range. Set newHead made the code easier.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode nEndNode = head;
        newHead.next = head;
        for(int i = 1; i < n; i++){
            nEndNode = nEndNode.next;
        }
        ListNode preNode = newHead;
        while(nEndNode.next != null){
            nEndNode = nEndNode.next;
            preNode = head;
            head = head.next;
        }
        preNode.next = head.next;
        return newHead.next;
    }
}

Recursive Solution - Generate Parentheses *

It can be resolved by classic recursive approach. The idea is to keep both left parenthesis and right parenthesis to be n. The advantage here is that String operations like + does generate a new reference each time, so we don't need to worry about cleaning after each add.

Basic principle is to add left, update left amount, and then add right, update right amount, by recursive calls. If both are n, add result, if only left reach first (guaranteed since call recursive first than right), only recursive call right, and left should always bigger than right, reason as above.

public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> results = new ArrayList<String>();
        generateParenthesisOps(n, 0, 0, "", results);
        return results;
    }
   
    private void generateParenthesisOps(int n, int left, int right, String s, ArrayList<String> results){
        if(left < right){
            return;
        }
        if(left == n && right == n){
            results.add(s);
            return;
        }
        if(left == n){
            generateParenthesisOps(n, left, right + 1, s+")", results);
            return;
        }
        generateParenthesisOps(n, left + 1, right, s + "(", results);
        generateParenthesisOps(n, left, right + 1, s + ")", results);
    }
}

Binary Loop Solution - Merge k Sorted Lists **

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists.isEmpty()) return null;
        if(lists.size() == 1) return lists.get(0);
        // int k = lists.size();
        // int log = (int)(Math.log(k)/Math.log(2));
        // log = log < Math.log(k)/Math.log(2)? log+1:log; // take ceiling
        // for(int i = 1; i <= log; i++){
        //     for(int j = 0; j < lists.size(); j=j+(int)Math.pow(2,i)){
        //         int offset = j+(int)Math.pow(2,i-1);
        //         lists.set(j, mergeTwoLists(lists.get(j), (offset >= lists.size()? null : lists.get(offset))));
        //     }
        // }
        int index = lists.size();
        while(index > 1){
            int remain = index % 2;
            int middle = index / 2;
            for(int i = 0; i < middle; i++){
                lists.set(i + remain, mergeTwoLists(lists.get(i + remain), lists.get(i + middle + remain)));
            }
            index = middle + remain;
        }
        return lists.get(0);
    }
The idea is to binary merge the list heads in the list, and merge to first half. Notice for remaining case… Take the advantage that eventually the divide will be 1 by add the remaining to the next index each iteration!

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode head = l1.val > l2.val? l2:l1;
        if(head.equals(l1)){
            l1 = l2;
            l2 = head;
        }
        while(l2.next != null && l1 != null){
            if(l2.next.val > l1.val){
                ListNode tmp = l2.next;
                l2.next = l1;
                l1 = l1.next;
                l2 = l2.next;
                l2.next = tmp;
            }
            else
                l2 = l2.next;
        }
        if(l1 != null){
            l2.next = l1;
        }
        return head;
    }
}

Loop Solution: Swap Nodes in Pairs

Loop solution: notice the loop condition is node != null && node.next != null, and set the preNode.next to new swapped node too!

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        newHead.next = head;
        ListNode preNode = newHead;
        ListNode node = preNode.next;
        while(node != null && node.next != null){
            ListNode temp = node.next;
            preNode.next = temp;
            node.next = temp.next;
            temp.next = node;
            preNode = node;
            node = node.next;
        }
        return newHead.next;
    }
}

Recursive Loop Solution - Reverse Nodes in k-Group

Take the K list, and set next = recursive call instead of iteration, largely simplify the program. Reverse the K. Watch when list < K, return head.

When realized iteration is a mess, make a decision to use Recursive approach.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null || k < 2){
            return head;
        }
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        newHead.next = head;
        ListNode kNext = newHead.next;
        int index = 0;
        while(index < k && kNext != null){
            kNext = kNext.next;
            index++;
        }
        if(index < k){
            return newHead.next;
        }
        ListNode lp = head;
        ListNode next = reverseKGroup(kNext, k);
        while(lp.next != kNext){
            ListNode temp = lp.next;
            lp.next = next;
            next = lp;
            lp = temp;
        }
        newHead.next = lp;
        lp.next = next;
        return newHead.next;
    }
}

Loop Solution - Remove Duplicates from Sorted Array - Simpler code *

Same idea but simpler code (understand harder:)). Both keeping good ones and removing bad ones will work.

public class Solution {
    public int removeDuplicates(int[] A) {
        int count = 0;
    int len = A.length;
    for (int i = 0; i < len; i++) {
        if (count == 0 || A[i] != A[count - 1]) {
            A[count++] = A[i];
        }
    }
    return count;
    }
}

Loop Solution - Remove Element *

The idea is to loop the Array, and swap/replace the swap candidate index to next good index. Both will work.

public class Solution {
    public int removeElement(int[] A, int elem) {
        if(A == null || A.length == 0){
            return 0;
        }
       
        int begin = 0;
        int end = A.length - 1;
        while(begin <= end){
            if(A[end] == elem){
                end--;
                continue;
            }
            if(A[begin] == elem){
                A[begin] = A[end];
                A[end] = elem;
            }
            begin++;
        }
        return end + 1;
       
        // int index = 0;
        // int swapIndex = -1;
        // int res = A.length;
        // while(index < A.length){
        //     if(A[index] == elem){
        //         res--;
        //         if(swapIndex == -1){
        //             swapIndex = index;
        //         }
        //     }else{
        //         if(swapIndex != -1){
        //             A[swapIndex] = A[index];
        //             //A[index] = elem;
        //             swapIndex++;
        //         }
        //     }
        //     index++;
        // }
        // return res;
    }
}

Loop Solution - Implement strStr()

The idea is to loop the String and i < needle, s.length() - needle.length + 1, compare all possible cases.

public class Solution {
    public String strStr(String haystack, String needle) {
        if(needle == null || haystack == null || needle.length() > haystack.length()){
            return null;
        }
        if(haystack.length() == 0 || needle.length() == 0){
            return haystack;
        }
        for(int i = 0; i < haystack.length() - needle.length() + 1; i++){
            for(int j = i; j < i + needle.length(); j++){
                if(needle.charAt(j - i) != haystack.charAt(j)){
                    break;
                }
                if(j == i + needle.length() - 1 && needle.charAt(j - i) == haystack.charAt(j)){
                    return haystack.substring(i);
                }
            }
        }
        return null;
    }
}