Copy List with Random Pointer LeetCode

Using hashmap is much easier to implement the code.
O(n) time complexity and O(n) space
First, get the regular linked list and put the node pair in the hashmap
Second, set each node with correct random pointer.
public RandomListNode copyRandomList(RandomListNode head) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode p = head;
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode q = dummy;
     
        while (p!=null) {
            q.next = new RandomListNode(p.label);
            map.put(p, q.next);
            p = p.next;
            q = q.next;
        }
        p = head;
        q = dummy;
        while (p != null) {
            q.next.random = map.get(p.random);
            p = p.next;
            q = q.next;
        }
        return dummy.next;
    }

Better solution with O(n) time complexity and O(1) space.
 public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode p = head;
        //copy the node in the list
        while (p != null) {
            RandomListNode next = p.next;
            RandomListNode copy = new RandomListNode(p.label);
            p.next = copy;
            copy.next = next;
            p = next;
        }
        //Set the random pointer correctly
        p = head;
        while (p != null) {
            p.next.random = (p.random != null) ? p.random.next : null;
            p = p.next.next;
        }
        //Reset the list to the original one
        p = head;
        RandomListNode headCopy = (p!=null) ? p.next : null;
        while (p != null) {
            RandomListNode copy = p.next;
            p.next = copy.next;
            p = p.next;
            copy.next = (p != null) ? p.next : null;
        }
        return headCopy;
     
    }

Compare Version Number LeetCode

Integer.valueOf("01") can handle conversion from string to integer.

public int compareVersion(String version1, String version2) {
        String[] version1Res = version1.split("\\.");
        String[] version2Res = version2.split("\\.");
        int idx = Math.max(version1Res.length, version2Res.length);
        int i=0;
        while (i < idx) {
            int c1 = i < version1Res.length ? Integer.valueOf(version1Res[i]):0;
            int c2 = i < version2Res.length ? Integer.valueOf(version2Res[i]):0;
            if (c1>c2) {
                return 1;
            } else if (c1<c2) {
                return -1;
            }
            i++;
        }
        return 0;
    }

Majority Element

Method 1: HashMap is always a quick solution for this kind of problems.

public int majorityElement(int[] num) {

        Map<Integer,Integer> hm = new HashMap<Integer, Integer>();

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

            if (!hm.containsKey(num[i])) {

                hm.put(num[i], 1);

            } else {

                hm.put(num[i],hm.get(num[i])+1);

                if (hm.get(num[i]) > num.length/2) {

                    return num[i];

                }

            }

        }

        return num[0];

    }

Method 2: Bit Manipulation

It is similar to Single Number.

public int majorityElement(int[] num) {

        

        //Bit manipulation

        int[] countsPerBit = new int[32];

        int result = 0;

        for (int i=0; i<32; i++) {

            int count = 0;

            for (int j=0; j<num.length; j++) {

                if((num[j]>>i&1) ==1) {

                    count++;

                }

            }

            if (count > num.length/2) {

                result |= (1<<i);

            }

        }

        return result;

    }

Method 3: Moore Voting Algorithm

This is super cool.

public int majorityElement(int[] num) {

        

        //Moore voting algorithm

        int elem = 0;

        int count = 0;

        

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

            if (count == 0) {

                elem = num[i];

                count = 1;

            } else {

                if (elem == num[i]) {

                    count++;

                } else {

                    count--;

                }

            }

        }

        return elem;

    }

Evaluate Reverse Polish Notation LeetCode

Use stack to contain all the values. When we get the operators, we pop up two values for operation.

It's easy. It has lots of follow up question.


public int evalRPN(String[] tokens) {
        if (tokens==null || tokens.length == 0) return 0;
        if (tokens.length == 1) return Integer.valueOf(tokens[0]);
       
        Stack<String> stack = new Stack<String>();
        String operators = "+-*/";
       
        for (int i=0; i<tokens.length; i++) {
            if (!operators.contains(tokens[i])) {
                stack.push(tokens[i]);
            } else {
                int a = Integer.valueOf(stack.pop());
                int b = Integer.valueOf(stack.pop());
               
                switch(tokens[i]) {
                    case "+" : stack.push(String.valueOf(a+b)); break;
                    case "-" : stack.push(String.valueOf(b-a)); break;
                    case "*" : stack.push(String.valueOf(a*b)); break;
                    case "/" : stack.push(String.valueOf(b/a)); break;
                }
            }
        }
        return Integer.valueOf(stack.pop());
    }

Intersection of Two LinkedList LeetCode (Important)

1. Find the length of each list
2. Scan from the same length of the short list in the longer list.

It should be O(n) time and O(1) space.
It is not easy for me :(

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
       
        //Get the length 0f List A
        int indexA = 0;
        ListNode tempA = headA;
        while (tempA != null) {
            tempA = tempA.next;
            indexA++;
        }
       
        //Get the length of List B
        int indexB = 0;
        ListNode tempB = headB;
        while (tempB != null) {
            tempB = tempB.next;
            indexB++;
        }
       
        //Two pointers
       
        ListNode longNode = (indexA > indexB) ? headA : headB;
        ListNode shortNode = (longNode == headA) ? headB : headA;
        int diff = Math.abs(indexA - indexB);
        while (diff > 0) {
            longNode = longNode.next;
            diff--;
        }
       
        while (longNode != null) {
            if (longNode.val == shortNode.val) {
                return longNode;
            }
            longNode = longNode.next;
            shortNode = shortNode.next;
        }
        return null;
    }

Search 2D Matrix LeetCode (Important)

Very good question.
It can come with lots of follow up.

Step Wise method. I prefer this method. Easy to implement and very good for a quick solution during the interview.

public boolean searchMatrix(int[][] matrix, int target) {
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        int row = 0;
        int col = matrix[0].length-1;
        if (matrix[0][0] > target || matrix[rowLen-1][colLen-1] < target) return false;
     
        while (row < rowLen && col >= 0) {
            if (matrix[row][col] > target) {
                col--;
            } else if (matrix[row][col] < target) {
                row++;
            } else {
                return true;
            }
        }
        return false;
    }

Binary Search on row and column.
public boolean searchMatrix(int[][] matrix, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int row = searchRow(matrix, 0, matrix.length, target);
        int result = Arrays.binarySearch(matrix[row], target);
        return result >= 0 ? true : false;
    }
 
    private int searchRow(int[][] matrix, int start, int end, int target) {
        int mid = (start + end)/2;
        if (start == mid) {
            return mid;
        }
        if (matrix[mid][0] <= target) {
            return searchRow(matrix, mid, end, target);
        } else {
            return searchRow(matrix, start, mid, target);
        }
    }

public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix==null || matrix.length==0 || matrix[0].length==0) return false;
        //Search the col
        int l=0;
        int r=matrix.length-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (matrix[mid][0] == target) return true;
            if (matrix[mid][0] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        int row = r;
        if (row < 0) return false;
        //Search the row
        l=0;
        r=matrix[0].length-1;
        while (l<=r) {
            int mid = (l+r)/2;
            if (matrix[row][mid] == target) return true;
            if (matrix[row][mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }

Sort Colors LeetCode

Two passes are easy to understand. Count and put all the numbers in.

public void sortColors(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (A == null || A.length == 0) return;
         int[] helper = new int[3];
         for (int i=0; i<A.length; i++) {
             helper[A[i]] ++;
         }
       
         int index = 0;
         for (int j=0; j<3; j++) {
             while (helper[j]-- > 0) {
                 A[index++] = j;
             }
         }
    }

OK. Let's make it better.
ONE Pass.
index0 and index1 are two pointer for the current location of 0 and 1.

public void sortColors(int[] A) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       if (A==null||A.length==0) return;
       int ind0 = 0;
       int ind1 = 0;
       for (int i=0; i<A.length; i++) {
           if (A[i] == 0) {
               A[i] = 2;
               A[ind1++] = 1;
               A[ind0++] = 0;
           } else if (A[i] == 1) {
               A[i] = 2;
               A[ind1++] = 1;
           }
       }
    }

Find Minimum in Rotated Sorted Array II LeetCode

Always separate the array for three conditions.
Put equal condition individually.


 public int findMin(int[] num) {
        int l = 0;
        int r = num.length - 1;
        int min = num[0];
       
        while (l < r) {
            int m = (l+r)/2;
            if (num[l] < num[m]) {
                min = Math.min(num[l], min);
                l = m + 1;
            } else if (num[l] > num[m]) {
                min = Math.min(num[m], min);
                r = m - 1;
            } else {
                min = Math.min(num[m], min);
                l++;
            }
        }
        min = Math.min(num[r], min);
        min = Math.min(num[l], min);
        return min;
    }

Search in Rotated Sorted Array LeetCode II

Only One situation need to be done.
When A[L] == A[mid].

public boolean search(int[] A, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
         int L = 0;
       int R = A.length-1;
   
       while (L<=R) {
           int mid = (L+R)/2;
           if (A[mid] == target) return true;
       
           // Example: 4 5 6 7 8 9 1 2 3
           if (A[L] < A[mid]) {
               if (A[L]<=target && target < A[mid]) {
                   R = mid - 1;
               } else {
                   L = mid + 1;
               }
           }
           // Example: 8 9 1 2 3 4 5 6 7
           else if (A[L] > A[mid]) {
               if (A[mid] < target && target <= A[R]) {
                   L = mid + 1;
               } else {
                   R = mid - 1;
               }
           } else {
               L++;
           }
       }
       return false;
    }

Find Minimum in Rotate Array LeetCode

Search in Rotated sorted Array

中间值大于起始值，且起始值大于终止值

    public int findMin(int[] num) {
        int l = 0;
        int r = num.length - 1;
        int min = num[0];
        
        while (l < r) {
            int m = (l+r)/2;
            if (num[l] < num[m]) {
                min = Math.min(num[l], min);
                l = m + 1;
            } else if (num[l] > num[m]) {
                min = Math.min(num[m], min);
                r = m - 1;
            } else {
                min = Math.min(num[m], min);
                l++;
            }
        }
        min = Math.min(num[r], min);
        min = Math.min(num[l], min);
        return min;

    }

Better solution:

public int findMin(int[] num) {
        int l = 0;
        int r = num.length - 1;
        
        while (l < r) {
            int m = (l+r)/2;
//中间值大于起始值，且起始值大于终止值
            if (num[m] >= num[l] && num[l] > num[r]) {
                l = m + 1;
            } else {
                r = m;
            }
            
        }
        return num[l];

    }

Search in Rotated Sorted Array LeetCode

Binary search.
Two different cases:
3 4 5 6 7 8 9 1 2
8 9 1 2 3 4 5 6 7

Here is the solution:

public int search(int[] A, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
       int L = 0;
       int R = A.length-1;
     
       while (L<=R) {
           int mid = (L+R)/2;
           if (A[mid] == target) return mid;
         
           // Example: 4 5 6 7 8 9 1 2 3
           if (A[L] <= A[mid]) {
               if (A[L]<=target && target < A[mid]) {
                   R = mid - 1;
               } else {
                   L = mid + 1;
               }
           }
           // Example: 8 9 1 2 3 4 5 6 7
           else {
               if (A[mid] < target && target <= A[R]) {
                   L = mid + 1;
               } else {
                   R = mid - 1;
               }
           }
       }
       return -1;
    }

Container with most water LeetCode

Two pointer. Same idea with TwoSum.

public int maxArea(int[] height) {
        int start = 0;
        int end = height.length - 1;
       
        int maxArea = 0;
        while (start < end) {
            maxArea = Math.max(maxArea, (end - start) * Math.min(height[start], height[end]));
            if (height[start] > height[end]) {
                end--;
            } else {
                start++;
            }
        }
        return maxArea;
    }

Clone Graph LeetCode

• A queue is used to do breath first traversal.
• a map is used to store the visited nodes. It is the map between original node and copied node.

It would be helpful if you draw a diagram and visualize the problem.

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
         if(node == null)
            return null;

        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map =
                                   new HashMap<UndirectedGraphNode,UndirectedGraphNode>();

        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);

        queue.add(node);
        map.put(node, newNode);
       
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.pop();
            List<UndirectedGraphNode> currNeighbors = curr.neighbors;
           
            for (UndirectedGraphNode ngn : currNeighbors) {
                if (!map.containsKey(ngn)) {
                    UndirectedGraphNode copy = new UndirectedGraphNode(ngn.label);
                    map.put(ngn, copy); //updating the mapping
                    map.get(curr).neighbors.add(copy); //updating the curr neighbors
                    queue.add(ngn); //updating the queue
                } else {
                    map.get(curr).neighbors.add(map.get(ngn)); //adding the node from clone graph to the curr's neighbor
                }
            }
        }
        return newNode;
    }

Remove duplicate from sorted list LeetCode

Check whether the duplicate is existing or not.
If so, prev.next = curr.next. If not, prev.next = curr;

 public ListNode deleteDuplicates(ListNode head) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if (head == null) return null;
        ListNode dummy = new ListNode(-1);
        dummy.next =head;
        ListNode prev = dummy;
        ListNode curr = head;
       
        while (null != curr) {
            while (curr.next != null && prev.next.val == curr.next.val) {
                curr = curr.next;
            }
           
            if (prev.next == curr) {
                prev = curr;
            } else {
                prev.next = curr.next;
            }
            curr = curr.next;
        }
        return dummy.next;

    }

Gas Station LeetCode

Use two variables to get the index.
diff is checking whether the entire loop has enough gas for the cost.
remain is trying to find the best start location. If it is negative which means we could not start at any previously point. So we count it again from the next point.

public int canCompleteCircuit(int[] gas, int[] cost) {
        int index = -1;
        int diff = 0;
        int remain = 0;
       
        for (int i=0; i<gas.length; i++) {
            diff += gas[i] - cost[i];
            remain += gas[i] - cost[i];
            if (remain < 0) {
                index = i;
                remain = 0;
            }
        }
        return diff >= 0 ? index + 1: -1;
    }

Partition List LeetCode

Create two listnodes for each list.

 public ListNode partition(ListNode head, int x) {
        ListNode root = new ListNode(-1);
        ListNode pivot = new ListNode(x);
       
        ListNode before = root;
        ListNode after = pivot;
       
        ListNode curr = head;
       
        while (curr != null) {
            ListNode next = curr.next;
            if (curr.val < x) {
                before.next = curr;
                before = curr;
            } else {
                after.next = curr;
                after = curr;
                after.next = null;
            }
            curr = next;
        }
        before.next = pivot.next;
        return root.next;
    }

LeetCode Reverse Words in a String

After splitting, there may be some " " string in the string array.
For example "a    b", the splitting result is "a", " ", "b".

public String reverseWords(String s) {
        if (s==null ||s.length()==0) return "";
   
    //split to words by space
    String[] arr = s.trim().split(" ");
    StringBuilder sb = new StringBuilder();
    for (int i=arr.length-1; i >=0; i--) {
       if (!"".equals(arr[i])) {
    sb.append(arr[i]).append(" ");
       }
    }
    return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
    }


Also there is a alternative solution for two passes and O(1) space.
The condition is there no spaces at the beginning and the tail. Every word is separated by single space.

Algorithm.
Reverse entire sentence.
Reverse every word.

LeetCode Gray Code

第n位的格雷码由两部分构成，一部分是n-1位格雷码，再加上 1<<(n-1)和n-1位格雷码的逆序的和
public List<Integer> grayCode(int n) {
        if (n==0) {
            List<Integer> result = new ArrayList<Integer>();
            result.add(0);
            return result;
        }
       
        List<Integer> prevList = grayCode(n-1);
        int highestBit = 1 << (n-1);
        List<Integer> result = new ArrayList<Integer>(prevList);
        for (int i=prevList.size() - 1; i>=0; i--) {
            result.add(highestBit + prevList.get(i));
        }
        return result;
    }

LeetCode SubSetsII

Add one variable to add duplicate number in the lists.

public List<List<Integer>> subsetsWithDup(int[] num) {

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        result.add(new ArrayList<Integer>());

        Arrays.sort(num);

        

        int startIndex = 0;

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

            int size = result.size();

            for (int j = startIndex; j < size; j++) {

                List<Integer> sub = new ArrayList<Integer>();

                sub.addAll(result.get(j));

                sub.add(num[i]);

                result.add(sub);

            }

            if (i<num.length-1 && num[i+1] == num[i]) {

                startIndex = size;

            } else {

                startIndex = 0;

            }

        }

        return result;

    }