Reverse Linked List II LeetCode

Find the start and end node for reversing.


public ListNode reverseBetween(ListNode head, int m, int n) {
      ListNode dummy = new ListNode(-1);
      dummy.next = head;
      ListNode temp = dummy;
     
      int index = 1;
      while (index < m) {
          temp = temp.next;
          index++;
      }
      ListNode prev = temp;
      ListNode newHead = temp.next;
      while (index <= n) {
          temp = temp.next;
          index++;
      }
      ListNode end = temp.next;
      prev.next = reverse(newHead, end);
      return dummy.next;
    }
   
    private ListNode reverse(ListNode head, ListNode end) {
        if (head == null || head.next == null) return head;
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode curr = head;
        while (curr.next != end) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return prev.next;
    }

Unique Binary Search Trees II LeetCode

Recursion could simplify the code significantly.
The returning result is all the root node of each Tree.

public List<TreeNode> generateTrees(int n) {
        return generateTrees(1,n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();
       
        if (start > end) {
            result.add(null);
            return result;
        }
        for (int i=start; i<=end; i++) {
            for (TreeNode left : generateTrees(start, i-1)) {
                for (TreeNode right : generateTrees(i+1, end)) {
                    TreeNode curr = new TreeNode(i);
                    curr.left = left;
                    curr.right = right;
                    result.add(curr);
                }
            }
        }
        return result;
    }

Maximum

DP
but we only need two variables to store the maxvalue and minvalue

public int maxProduct(int[] A) {
        if (A.length == 1) return A[0];
        int maxProduct = A[0];
        int currMax = A[0];
        int currMin = A[0];
       
        for (int i=1; i<A.length; i++) {
            int temp = currMax;
            currMax = Math.max(Math.max(temp*A[i], A[i]), currMin*A[i]);
            currMin = Math.min(Math.min(currMin*A[i], A[i]), temp*A[i]);
            maxProduct = Math.max(maxProduct, currMax);
        }
        return maxProduct;
    }

Word Break LeetCode

dp
dp[j] = dp[i] && dict.contains(s.substring(j,i))

public boolean wordBreak(String s, Set<String> dict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
       
        for (int i=1; i<=s.length();i++) {
            for (int j=0; j<i; j++) {
                if (dp[j] && dict.contains(s.substring(j,i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

Construct Binary Tree from preOrder and inOrder Leetcode

Similarly, copy the solution from postOrder and inOrder.

public TreeNode buildTree(int[] preorder, int[] inorder) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(preorder == null || inorder == null) return null;
        if(preorder.length == 0 || inorder.length == 0) return null;
        return build (preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

        public TreeNode build(int[] preorder, int start1, int end1, int[] inorder, int start2,
int end2) {
        if(start1 > end1 || start2 > end2) return null;
int current = preorder[start1];
TreeNode currRoot = new TreeNode(current);
        int k = start2;
        for(; k < inorder.length; k++)
        if(inorder[k] == current) break;
        currRoot.left = build(preorder, start1+1, start1-start2+k, inorder, start2, k-1);
        currRoot.right = build(preorder, start1-start2+k+1,end1, inorder, k+1, end2);
        return currRoot;
    }

Construct Binary Tree from Inorder and PostOrder LeetCode

The last element from postOrder is the root value.

Find the last element from inOrder, Will get the length of subTrees.

public TreeNode buildTree(int[] inorder, int[] postorder) {

        if (inorder == null || postorder == null) return null;

        if (inorder.length == 0 || postorder.length == 0) return null;

        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);

}

private TreeNode buildTree(int[] inorder, int start1, int end1, int[] postorder, int start2, int end2) {

   if (start1 > end1 || start2 > end2) return null;

   int currentValue = postorder[end2];

   TreeNode currRoot = new TreeNode(currentValue);

   int k = start1;

   for (; k < inorder.length; k++) {

       if (inorder[k] == currentValue) break;

   }

   currRoot.left = buildTree(inorder, start1, k-1, postorder, start2, end2-end1+k-1);

   currRoot.right = buildTree(inorder, k+1, end1, postorder, end2-end1+k, end2-1);

   return currRoot;

}

Convert Sort List to Binary Search Tree LeetCode

The start position for fast and slow should be set carefully.

public TreeNode sortedListToBST(ListNode head) {

        if (head == null) return null;

        if (head.next == null) return new TreeNode(head.val);

        

        ListNode fast = head.next.next;

        ListNode slow = head;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;

            slow = slow.next;

        }

        ListNode parent = slow.next;

        slow.next = null;

        TreeNode root = new TreeNode(parent.val);

        root.left = sortedListToBST(head);

        root.right = sortedListToBST(parent.next);

        

        return root;

    }

Here is a better solution. (Bottom-up)

From the CleanCodeHandbook of LeetCode.
public class Solution {
    private ListNode list;
    public TreeNode sortedListToBST(ListNode head) {
        int n = 0;
        ListNode p = head;
        while (p!=null) {
            p = p.next;
            n++;
        }
        list = head;
        return sortedListToBST(0, n-1);
    }
   
    private TreeNode sortedListToBST(int start, int end) {
        if (start > end) return null;
        int mid = (start + end)/2;
        TreeNode leftChild = sortedListToBST(start, mid-1);
        TreeNode parent = new TreeNode(list.val);
        parent.left = leftChild;
        list = list.next;
        TreeNode rightChild= sortedListToBST(mid+1, end);
        parent.right = rightChild;
        return parent;
       
    }
}

ReOrder List LeetCode

Good implementing question for LinkedList.

public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode reverseHead = slow.next;
        slow.next = null;
       
        reverseHead = reverse(reverseHead);
        ListNode curr = head;
        while (reverseHead != null) {
            ListNode temp = reverseHead.next;
            reverseHead.next = curr.next;
            curr.next = reverseHead;
            curr = reverseHead.next;
            reverseHead = temp;
        }
    }
   
    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode prev = new ListNode(-1);
        prev.next = head;
        ListNode curr = head;
        while (curr.next != null) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        return prev.next;
    }

Binary Tree Zigzag Level Order Traversal LeetCode

Use two stacks to store the node for different directions.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        Stack<TreeNode> s2 = new Stack<TreeNode>();
        if (root == null) return result;
        else {
            List<Integer> curr = new ArrayList<Integer>();
            curr.add(root.val);
            result.add(curr);
            if (root.left != null)
            s1.push(root.left);
            if (root.right != null)
            s1.push(root.right);
            helper(result, s1, s2);
            return result;
        }
    }
   
    private void helper(List<List<Integer>> result, Stack<TreeNode> s1, Stack<TreeNode> s2) {
        if (s1.empty() && s2.empty()) return;
        List<Integer> tempList = new ArrayList<Integer>();
        TreeNode tempNode = null;
        if (!s1.empty()) {
            while (!s1.empty()) {
                tempNode = s1.pop();
                tempList.add(tempNode.val);
                if (tempNode.right != null) {
                    s2.push(tempNode.right);
                }
                if (tempNode.left != null) {
                    s2.push(tempNode.left);
                }
            }
        } else {
            while (!s2.empty()) {
                tempNode = s2.pop();
                tempList.add(tempNode.val);
                if (tempNode.left != null) {
                    s1.push(tempNode.left);
                }
                if (tempNode.right != null) {
                    s1.push(tempNode.right);
                }
            }
        }
        result.add(tempList);
        helper(result, s1, s2);
        return;
    }

Flatten Binary Tree to LinkedList LeetCode

Recursion

public TreeNode lastNode = null;
    public void flatten(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
       if (root == null) return;
       if (lastNode != null) {
           lastNode.left = null;
           lastNode.right = root;
       }
     
       TreeNode left = root.left;
       TreeNode right = root.right;
       lastNode = root;
       flatten(left);
       flatten(right);
    }

Path Sum II LeetCode

public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        if (root.left == null && root.right == null && sum == root.val) {
            List<Integer> curr = new ArrayList<Integer>();
            curr.add(root.val);
            result.add(curr);
            return result;
        }
        if (root.left != null) {
            List<List<Integer>> leftResults = pathSum(root.left, sum - root.val);
            for (int j=0; j<leftResults.size();j++) {
                List<Integer> curr = new ArrayList<Integer>();
                curr.add(root.val);
                curr.addAll(leftResults.get(j));
                result.add(curr);
            }
        }
        if (root.right != null) {
            List<List<Integer>> rightResults = pathSum(root.right, sum - root.val);
            for (int j=0; j<rightResults.size();j++) {
                List<Integer> curr = new ArrayList<Integer>();
                curr.add(root.val);
                curr.addAll(rightResults.get(j));
                result.add(curr);
            }
        }
        return result;
    }

Add Two Numbers LeetCode

Recursion method is quite simple.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1,l2,0);
    }
    private ListNode helper(ListNode l1, ListNode l2, int carry) {
        if (l1==null && l2==null && carry == 0) return null;
        int sum = 0;
        if (l1 != null) {
            carry += l1.val;
            l1=l1.next;
        }
        if (l2 != null) {
            carry += l2.val;
            l2=l2.next;
        }
        ListNode curr = new ListNode(carry%10);
        carry = carry/10;
        curr.next = helper(l1,l2,carry);
        return curr;
    }

Triangle LeetCode

Bottom-up!
 public int minimumTotal(List<List<Integer>> triangle) {
        for(int i = triangle.size() - 2; i >= 0; i--){
            for(int j = 0; j < triangle.get(i).size(); j++){
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }

Valid Sudoku LeetCode

public boolean isValidSudoku(char[][] board) {

   

   //check the column

   for (int i=0; i<board[0].length; i++) {

       boolean[] dupCheck  = new boolean[256];

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

           if (board[j][i] != '.') {

               if (dupCheck[board[j][i]] == true) return false;

               else dupCheck[board[j][i]] = true;

           }

       }

   }

   

   //check the row

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

       boolean[] dupCheck = new boolean[256];

       for (int j=0; j<board[0].length; j++) {

           if (board[i][j] != '.') {

              if (dupCheck[board[i][j]] == true) return false;

               else dupCheck[board[i][j]] = true;

           }

       }

   }

   

   //check the subBox

   for (int i=0; i <board.length/3; i++) {

       for (int j=0; j <board[0].length/3; j++) {

           boolean[] dupCheck = new boolean[256];

           for (int m=i*3; m<i*3+3; m++) {

               for (int n=j*3; n<j*3+3; n++) {

                   if (board[m][n] != '.') {

                       if (dupCheck[board[m][n]] == true) return false;

                       else dupCheck[board[m][n]] = true;

                   }

               }

           }

       }

   }

   

   return true;

}

Length of Last Word LeetCode

public int lengthOfLastWord(String s) {
        if (s== null || s.length()==0) return 0;
        int end = s.length()-1;
        while (end >=0 && s.charAt(end) == ' ') {
            end--;
        }
        int start = end;
        while (start >=0 && s.charAt(start) != ' ') {
            start--;
        }
        return end-start;
    }

    public int lengthOfLastWord(String s) {
        if (s==null ||s.length()==0) return 0;
        int end = s.length()-1;
        //Scan from the last character and skip all the whitespace
        while (end>=0 && Character.isWhitespace(s.charAt(end))) {
            end--;
        }
       
        //Already scan all the string return 0
        int start = end;
        while (start>=0 && !Character.isWhitespace(s.charAt(start))) {
            start--;
        }
        return end - start;
    }

Plus One LeetCode

Try to add 1 for the lowest digit and return.

There is a corner condition like 999.

So if all the digits are 0, we will create a new integer array to store the result.

public int[] plusOne(int[] digits) {

        int index = digits.length-1;

        while (index >= 0) {

            if (digits[index] != 9) {

                digits[index]++;

                return digits;

            } else {

                digits[index--] = 0;

            }

        }

        int[] result = new int[digits.length+1];

        result[0] = 1;

        for (int i=1; i<result.length; i++) {

            result[i]=0;

        }

        return result;

    }

LeetCode CountAndSay

public String countAndSay(int n) {
        if (n==0) return "";
        if (n==1) return "1";
        String lastResult = countAndSay(n-1);
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<lastResult.length();) {
            char currChar = lastResult.charAt(i);
            int count = 0;
           
            while(i<lastResult.length() && currChar == lastResult.charAt(i)) {
                count++;
                i++;
            }
            sb.append(count).append(currChar);
        }
        return sb.toString();
    }