Apple – CodeBySteven

Leetcode 102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

Analysis:

Use queue.

Time complexity: O(n)

Space complexity: O(n)

Code is below:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List> levelOrder(TreeNode root) {
        // O(n) BFS
        
        List<List> result = new ArrayList<>();
        
        if (root == null) {
            return result;
        }
        
        Queue queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            ArrayList level = new ArrayList<>();
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                // poll the head
                TreeNode head = queue.poll();
                level.add(head.val);
                
                // add the left subnode
                if (head.left != null) {
                    queue.offer(head.left);
                }
                
                // add the right subnode
                if (head.right != null) {
                    queue.offer(head.right);
                }
            }
            result.add(level);
        }
        return result;
    }
}

Leetcode 235 & 236. Lowest Common Ancestor of a Binary (Search) Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Analysis:

Check for the properties of the BST. If root.val > both p.val and q.val, we know the lca is in the left side, then goto the left subtree. If root.val < both p.val & q.val, then go to right subtree. Otherwise, return root.

Time complexity: O(logn)

Space complexity: O(1)

Code is below:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // O(logn)
        
        if (root == null || p == null || q == null) {
            return null;
        }
        
        if (root.val > p.val && root.val > q.val) {
            // left sub tree
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            // right sub tree
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
}

Followup:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Analysis:

No properties similar to BST. We can use divide and conquer. Divide the tree to be the left and right. If left & right not null, return root. If left not null, return left, otherwise return right.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // O(n)
        
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // divide: get the left and right lca
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // conquer: check for the left and right
        // If left and right both exits, then return root
        if (left != null && right != null) {
            return root;
        }
        
        if (left != null) {
            return left;
        }
        
        if (right != null) {
            return right;
        }
        
        return null;
    }
}

Leetcode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Analysis:

Make a dummy node, compare the two values in the two lists. If one is smaller, add it to the head. Update the head to next.

Note: the two lists may not be the same length. After all iteration, we need to check the lefts and add them to the result.

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // O(n)
        
        if (l1 == null) {
            return l2;
        }
        
        if (l2 == null) {
            return l1;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            
            cur = cur.next;
        }
        
        // Check if there're lefts
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        
        return dummy.next;
    }
}

Leetcode 92 & 206. Reverse Linked List I & II

Reverse a singly linked list.

click to show more hints.

Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?

Analysis:

For iteration, we need to have a prev and next node for temporal save.

For recursive,

Assume that the rest of the list had already been reversed, now how do I reverse the front part? Let’s assume the list is: n₁ → … → n_k-1 → n_k → n_k+1 → … → n_m → Ø

Assume from node n_k+1 to n_m had been reversed and you are at node n_k.

n₁ → … → n_k-1 → n_k → n_k+1 ← … ← n_m

We want n_k+1’s next node to point to n_k.

So, n_k.next.next = n_k

Time complexity: O(n)

Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        // O(n)
        
        if (head == null || head.next == null) {
            return null;
        }
        
        // iteration
        ListNode current = head;
        ListNode prev = null;
        ListNode next;
        
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
        
        // recursive
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        
        return p;
    }
}

Followup:
Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Analysis:
Go through the list and find the position before m. Then start from m, reverse the n-m nodes like reverse linked list.

Time complexity: O(n)
Space complexity: O(1)

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // O(n)
        
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        dummy.next = head;
        
        // Find the position before the reverse start
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }
        
        // Reverse the n - m nodes
        ListNode cur = prev.next;
        for (int i = 0; i < n - m; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        
        return dummy.next;
    }
}

Leetcode 237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4after calling your function.

Analysis:

Very intuitive method.

Code is below:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        // O(1)
        
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Leetcode 48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Analysis:

Use some math magic?

Time complexity: O(n ^ 2)

Space complexity: O(1)

Code is below:

public class Solution {
    public void rotate(int[][] matrix) {
        // O(n^2)
        
        if (matrix == null || matrix.length == 0 ||
            matrix[0] == null || matrix[0].length == 0) {
                return;
            }
            
        int len = matrix.length;
            
        for (int i = 0; i < len / 2; i++) {
            for (int j = 0; j < (len + 1) / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len - j - 1][i];
                matrix[len - j - 1][i] = matrix[len - i - 1][len -j - 1];
                matrix[len - i - 1][len -j - 1] = matrix[j][len - i - 1];
                matrix[j][len - i - 1] = temp;
            }
        }
        
    }
}

Leetcode 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Analysis:

To get the products of all others, we can have an array of the same length. Then go through the array, get all products for all lefts. Then Go from the back and multiply all values on the right.

Note: we need to set up the first value res[0] to be 1 initially.

Time complexity: O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        // O(n) O(1)
        
        if (nums == null || nums.length == 0) {
            return nums;
        }
        
        int[] res = new int[nums.length];
        int left = 1;
        int right = 1;
        
        res[0] = 1;
        
        // Get the product of all lefts
        for (int i = 1; i < nums.length; i++) {             left = left * nums[i - 1];             res[i] = left;         }                  // Go from the back, get the product of all rights         for (int i = nums.length - 2; i >= 0; i--) {
            right = right * nums[i + 1];
            res[i] = right * res[i];
        }
        
        return res;
    }
}

Leetcode 191. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

Analysis:

We need to check each bit of the integer. To do that, we have a mask and let mask start from 1, which is $0000000000000000000000000000000 1, then use a logical AND between the number and the mask. If the result is not 0, then that means the digit is 1. Then we shift the mask to left by one.$

Time complexity: O(1)

Space complexity: O(1)

Code is below:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        // O(1)
        
        int count = 0;
        int mask = 1;
        
        // Have a mask from 1, 0000 0000 0000 0000 0000 0000 0000 0001
        // Use logial AND to check it
        // Shift the mask left by 1
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                count++;
            }
            mask <<= 1;
        }
        
        return count;
    }
}

Leetcode. 165. Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37

Analysis:

We can split the string to be a string array and then compare them separately. During comparison, it may happen that the two arrays are not the same size. Then we need to go through the longest one and add 0 if one is less than the longest size.

Note: here split function using on . we can not use . directly, but use \\.

Time complexity: O(n)
Space complexity: O(n)

Code is below:

public class Solution {
    public int compareVersion(String version1, String version2) {
        // O(n) O(n)
        
        if (version1 == null || version2 == null) {
            return 0;
        }
        
        if (version1.equals(version2)) {
            return 0;
        }
        
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        
        int maxLen = Math.max(v1.length, v2.length);
        
        for (int i = 0; i < maxLen; i++) {
            int num1 = i < v1.length ? Integer.parseInt(v1[i]) : 0;
            int num2 = i < v2.length ? Integer.parseInt(v2[i]) : 0;
            
            if (num1 < num2) {                 return -1;             }                          if (num1 > num2) {
                return 1;
            }
        }
        
        return 0;
    }
}

Leetcode 151 & 186. Reverse Words in a String I& II

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Analysis:

Use extra place. To split the whole string and get a string array, then go from the back and put them in a new string.

Time complexity : O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public String reverseWords(String s) {
        // O(n) O(n)
        
        if (s == null || s.length() == 0) {
            return "";
        }
        
        s = s.trim();
        String[] str = s.split(" ");
        StringBuilder sb = new StringBuilder();
        
        for (int i = str.length - 1; i >= 0; i--) {
            if (!str[i].equals("")) {
                sb.append(str[i]).append(" ");
            }
        }
        
        return sb.toString().trim();
    }
}

Followup:
Could you do it in-place without allocating extra space?

Analysis:
Use str.toCharArray() to change it to char array. Then reverse the whole array. Scan the array, if find a ‘ ‘, then reverse it from beginning. Update the start.

Time complexity : O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public void reverseWords(char[] s) {
        // O(n) O(1)
        
        if (s == null || s.length == 0) {
            return;
        }
        
        // reverse the whole array
        reverse(s, 0, s.length - 1);
        
        //reverse part of the words
        for (int i = 0, start = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
    }
    
    public void reverse(char[] s, int start, int end) {
        while (start < end) {
            char c = s[start];
            s[start] = s[end];
            s[end] = c;
            start++;
            end--;
        }
    }
}