Reverse Integer

public class Solution {
    public int reverse(int x) {
        //  Actually, for overflow cases, what we need is a long integer. Or check the result whether it is larger than Integer.MAX_VALUE. I didnt check this case, because test cases should result in a "long" value, while this function needs a int return
        if(Math.abs(x) < 10) return x;
        boolean negativeFlag = false;
        if (x <0) {
            negativeFlag = true;
            x = -1*x;// one interesting thing is that if I pass Integer.MIN_VALUE in, x = -1 * x is the same value
        }
        // Solution 1 -- could be considered as "cheating", using String instead.
        // String origin = Integer.toString(x);
        // StringBuffer sb = new StringBuffer();
        // int i = 0;
        // while(i < origin.length()){
        //     sb.append(origin.charAt(i));
        //     i++;
        // }
        // sb = sb.reverse();
        // int result = Integer.valueOf(sb.toString());
        // if (negativeFlag) result*=-1;
        // return result;
     
        // Solution 2
     
        long result;
        int xCopy = x/10;
        int remainder = x%10;
        result = remainder ;
        while(xCopy >= 10){
            remainder = xCopy%10;
            xCopy = xCopy/10;
            result = result * 10 + remainder;
        }
        result = result * 10 + xCopy;
        if (negativeFlag) result*=-1;
        return (int)result;
    }
    // Both solutions are accepted by LeetCode
}

Remove Duplicates from Sorted Array II

This is my first version of code for this problem. The code below should be easy to understand. Actually, I think some variables are redundant. If these variables are removed, code gets improved, then we can finish this problem in-place. I will update the improvement sooner or later.

public class Solution {
public int removeDuplicates(int[] A) {
     
       int ALen = A.length;
       if (A == null || ALen == 0) return 0;
       if (ALen < 3) return ALen;
       int i = 1;
       int count = 1;
       int num = A[0];
       int currentNum;
       ArrayList<Integer> arrA = new ArrayList<Integer>();
       arrA.add(num);
       while(i < ALen){
           currentNum = A[i];
           if(num == currentNum && count < 2 ){
               count++;
               arrA.add(currentNum);
           }
           else{
               if(num != currentNum){
                   num = currentNum;
                   count = 1;
                   // length ++;
                   arrA.add(num);
               }//  The else case must be "count = 2", no need to deal with it, just move index to next
           }
           i ++;
       }
       i = 0;
       while(i<ALen){
        if(i < arrA.size()){
        A[i] = arrA.get(i);
        }
           i ++;
       }
       return arrA.size();
   }
}

Merge Two Sorted Lists

Well, this is too easy. I think this can be solved very quickly. My answer is shown as below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1==null) return l2;
        if (l2 == null) return l1;
        ListNode tmp1 = l1;
        ListNode tmp2 = l2;
        ListNode newHead = null;
        ListNode movingNode = null;
        while(tmp1!= null && tmp2!=null){
            if(tmp1.val <= tmp2.val){
             
                if(newHead == null){
                    newHead = tmp1;
             
                    movingNode = newHead;
                }
                else {
                    movingNode.next = tmp1;
                    movingNode = movingNode.next;
                }
                tmp1 = tmp1.next;
            }
            else{
                if(newHead == null){
                    newHead = tmp2;
                    movingNode = newHead;
                }
                else {
                    movingNode.next = tmp2;
                    movingNode = movingNode.next;
                }
                tmp2 = tmp2.next;                  
            }
        }
        if(tmp1 == null && tmp2 != null) movingNode.next = tmp2;
        else if(tmp2 == null && tmp1 != null)movingNode.next = tmp1;
     
        return newHead;
    }
}

Validate Binary Search Tree

This question is almost same as the one in CtCi. The only difference is that Leetcode considers
 "The left subtree of a node contains only nodes with keys less than the node's key.", while CtCi think "less than or equal to" is also okay. Whatever the difference is, the code remains almost the same. 


When I attacked this problem at first, I thought that the max value of left subtree should be less than or equal to root.val, and the min value of right subtree larger than. And all the subtrees should follow this pattern. Although I tried many times to keep track of the leftMax of left subtree, and rightMin of right subtree, both of these 2 get changed when some leaves are traversed. This is really frustrating, since this should be very easy to solve. 
Finally, I turn to CtCi for help. After understanding its answer, I put the code into Leetcode. Accepted. But nothing exciting, I need more practices. 
The CtCi's answer is very good. Short, understandable, brief. 
Now let me talk a little bit about its code.
The most brilliant part is to pass root.val as rightMin. Actually, leftMax and rightMin are lower and upper limits. Now, please check the comments below: 


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        return checkBST(root,null,null);

    }
    
    public boolean checkBST(TreeNode root, Integer leftMax, Integer rightMin){
        if(root == null) return true;        
        if((leftMax != null && root.val <= leftMax) ||
       (rightMin!=null && root.val >= rightMin))// if rightMin NOT null, root is left of the node(val = rightMin)
        // Thus, if we take CtCi's definition, this condition should be  (rightMin!=null && root.val > rightMin)
        // since left child could be equal to root
        return false;

        
        if( checkBST(root.left,leftMax,root.val) &&// check left subtree, now let root.val be upper limit 
        checkBST(root.right,root.val,rightMin)) //check right subtree, now let root.val be lower limit
        return true;
        else return false;
        
    }

}

Flatten Binary Tree to Linked List

This problem is quite easy, but I got stuck in some trivial part. I will talk about it latter. First, let us focus on my algorithm for this problem. According to the given example, we can know that to flatten one tree is to flatten the root.left first, then add root.right to be right child of the rightmost node of root.left, finally flatten root.right. Obviously, this is a recursion problem. For root with different cases, different actions should be taken, which can be known from comments for code.

Then, one thing I really should be aware is that a function cannot make change to one object if this object is "pointed" to a new one. In this case, object is not like "pointer" any more. Sorry about using the term "pointer", since I started my coding life using C. I feel comfortable when I consider object as pointer, because they seem same, from the point of "change value of it in the called function, the value of this variable is also changed in calling function.", but actually there are many differences.

HOWEVER, this opinion is changed since I test the following code:

    public void printTree(TreeNode root){
    root = root.right;
    }
I passed root(1), with left(2) and right child (3), into this method in main function, and the result shows that in main function, value of root is NOT affected.
After some tests, I realize that value of root is changed only when the code inside pritnTree is "root.val = 8".

So the conclusion we may make is if object's attributes or contents are changed, the change will be reflected in calling function, if it gets "pointed" to another object, i.e. the address stored in this object is changed, then this change is not reflected.
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        //TreeNode rightMostNode = root;
        flatten1(root);
    }
   public TreeNode flatten1(TreeNode root) {
        if(root == null) return null;
        // if(root.left!=null){  
        TreeNode rightMostNode = flatten1(root.left);
        // }

        if(root.right != null && root.left !=null){
            TreeNode tmpNode = root.right;
            root.right = root.left;
            rightMostNode.right = tmpNode;
            root.left =null;
        }
       
        if(root.right == null && root.left !=null){
            root.right = root.left;
            root.left =null;
        }
        if(root.right == null && root.left ==null){
            rightMostNode = root;
            return rightMostNode;
        }
       
         return flatten1(root.right);
    }
}

Container With Most Water

public class Solution {
   
public int maxArea(int[] height){
if(height == null) return 0;
int start = 0, end = height.length - 1;
int maxArea = (end - start) * Math.min(height[start],height[end]);
while(start + 1  < end){
   if(height[start] < height[end]) start ++;// You can understand this in a general way; find out the smaller one, and then replace it by its next one for try
   else end --;
int tempArea = (end - start) * Math.min(height[start],height[end]);
            maxArea = Math.max(maxArea,tempArea);
}
   return maxArea;      
    }
}

Insert Interval

For this problem, the first thing I believe is to find out where I should put the newInterval.start and newInterval.end, and based on the value of newInterval, then determine how to merge this newInterval, or just to insert it in the right place. What is tricky is that some special cases might not be considered at first, and this problem really needs us to be careful.


/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        if (intervals == null || newInterval == null) return null;
        if (newInterval.start > newInterval.end) return null;
        int insertStartIdx = findIdxBehind(intervals, newInterval.start,0);
        int insertEndIdx = findIdxBehind(intervals, newInterval.end,insertStartIdx);
       
        if(intervals.isEmpty()) {intervals.add(newInterval); return intervals;}// Inspired by the case of [], [1 3]
       
       if(insertStartIdx == intervals.size() - 1){
           intervals.add(newInterval);
           return intervals;
        }
            int mergeStart;
            int mergeEnd;

                if(intervals.get(insertStartIdx+1).start < newInterval.start){
                    mergeStart = intervals.get(insertStartIdx+1).start;
                }
                else{
                    mergeStart = newInterval.start;
                }
           
            if(insertEndIdx == intervals.size()-1){
                mergeEnd = newInterval.end;
                Interval insertInterval = new Interval(mergeStart,mergeEnd);
                removeRange(intervals, insertStartIdx+1,insertEndIdx+1);
                intervals.add(insertStartIdx + 1, insertInterval);
            }
            else{
            boolean flag = false;  
               if(intervals.get(insertEndIdx+1).start <= newInterval.end){
                   if(intervals.get(insertEndIdx+1).end > newInterval.end)
                    mergeEnd = intervals.get(insertEndIdx+1).end;
                    else mergeEnd = newInterval.end;
                }
                else{
                    flag =true;
                    mergeEnd = newInterval.end;
                }
                Interval insertInterval = new Interval(mergeStart,mergeEnd);
                if(flag){
                        removeRange(intervals,insertStartIdx + 1,insertEndIdx+1);
                }
                else
                    removeRange(intervals, insertStartIdx + 1,insertEndIdx + 2);
                if(!intervals.contains(insertInterval))intervals.add(insertStartIdx + 1, insertInterval);
            }
        // }
        return intervals;
    }
   
    public int findIdxBehind(ArrayList<Interval> intervals, int insertVal, int startIdx){// find the index at which i the intervals.get(i).end < insertVal, while intervals.get(i+1).end >= insertVal
        if (startIdx < 0) startIdx = 0;
        while(startIdx < intervals.size()){
            if (intervals.get(startIdx).start > insertVal) return --startIdx;
            else if(intervals.get(startIdx).end >= insertVal) return --startIdx;// previously, end >= insertVal
                 else startIdx ++;
        }
        return --startIdx;
    }
    public void removeRange(ArrayList<Interval> intervals, int fromIdx, int toIdx){// since ArrayList.removeRange is protected, write it myself
        while(fromIdx < toIdx && fromIdx < intervals.size()){
            intervals.remove(fromIdx);
            toIdx --;// be careful of this, previously, I wrote from ++
        }
    }
}

Substring with Concatenation of All Words

Actually, the basic idea is to check each substring of size strLen* S.length to see whether it is concatenated by each word in the list

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        if(S == null || L == null){
            return null;
        }
        int strLen = L[0].length();
        if (strLen == 0) return null;
        HashMap<String,Integer> wordsMap = new HashMap<String,Integer>();
        ArrayList<Integer> resultIdx = new ArrayList<Integer>();
        initialMap(wordsMap,L);// store the frequency of each word in the String[] L
     
        for(int i = 0;i <= S.length() - strLen * L.length;i ++){//if one substring of S is composed of each word in //L, this substring must be length of strLen* L.length, so I just need to check each substring of size strLen* //L.length
            String currentStr = S.substring(i,i+strLen * L.length);
            if(check(currentStr,wordsMap,strLen)) {
               
                resultIdx.add(i);
            }
                initialMap(wordsMap,L);
           
        }
       
        return resultIdx;
    }
   
    public void initialMap(HashMap<String, Integer> wordsMap, String[] L){
       
        wordsMap.clear();
        for(int i = 0; i < L.length; i ++) {
        if(!wordsMap.containsKey(L[i])) wordsMap.put(L[i],1);
        else {
                int val = wordsMap.get(L[i]);
                val ++;
                // wordsMap.remove(L[i]);
                wordsMap.put(L[i],val);
            }  
        }
    }
   
    public boolean check(String currentStr, HashMap<String, Integer> wordsMap, int strLen){
       
        for(int i = 0;i <= currentStr.length() - strLen;i += strLen){
            String cmpntStr = currentStr.substring(i,i+ strLen);
            if(wordsMap.containsKey(cmpntStr)){
                int val = wordsMap.get(cmpntStr);
                val--;
                if(val < 0) return false;
                wordsMap.put(cmpntStr,val);
            }
            else{
                return false;
            }
        }
        return true;
    }
   
    public boolean determineAllWordsChecked(HashMap<String,Integer> wordsMap){
        for (Integer count: wordsMap.values()){
            if(count != 0) return false;
        }
        return true;
    }
}

Reverse Linked List II

For this problem, the basic idea is to move the mth node in the linked list right behind the nth node, i.e. "8". One thing to notice is that every time one node is moved, we always pick the node after the (m-1) th node, and move it behind that node "8". Since node "8" should be moved forward, it is wrong to keep moving the mth node behind nth node, which should be not node "8" any more.

In my solution, variable preNNode might be unnecessary. The following code can be improved later.
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null|| m > n || m <= 0 || n <= 0) return null;
        if (m == n) return head;
        int preMIdx = m - 1;
        int preNIdx = n - 1;
     
        ListNode preMNode = head;
        ListNode preNNode = head;
        ListNode mNode = head;      
        ListNode nNode = head;

        if(preMIdx == 0){// In this case, m is 1
            nNode = preNNode.next;
            int i = 1;
            while(i < n - 1 && preNNode != null && nNode != null){
                preNNode = preNNode.next;
                nNode = nNode.next;
                i++;
            }
            if(preNNode == null || nNode == null){
                return null;
            }
            // ListNode insertAfterNode = nNode;
            while(head != nNode){// move the mth element behind nth, untill the next one of m-1th node is that nth one
                mNode = head.next;
                // preMNode.next = mNode.next;
                head.next = nNode.next;
                nNode.next = head;
                head = mNode;
                // insertAfterNode = insertAfterNode.next;
            }          
        }
        else{
            mNode = preMNode.next;
            int i = 1;
            while(i < m - 1 && preMNode != null && mNode != null){
                preMNode = preMNode.next;
                mNode = mNode.next;
                i ++;
            }
            if(preMNode == null || mNode == null){
                return null;
            }          
            nNode = preNNode.next;
            i = 1;
            while(i < n - 1 && preNNode != null && nNode != null){
                preNNode = preNNode.next;
                nNode = nNode.next;
                i ++;
            }
            if(preNNode == null || nNode == null){
                return null;
            }
            // ListNode insertAfterNode = nNode;
            while(preMNode.next != nNode){// move the mth element behind nth, untill the next one of m-1th node is that nth one
             
                preMNode.next = mNode.next;
                mNode.next = nNode.next;
                nNode.next = mNode;
                mNode = preMNode.next;
                // preMNode = preMNode.next;
                // insertAfterNode = insertAfterNode.next;
            }
        }
 
        return head;
    }
}