LeetCode 112. Path Sum

Problem:

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solution:

Remember root to leaf.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (sum - root.val == 0 && root.left == null && root.right == null) return true;
        return (hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val));
    }
}

LeetCode 14. Longest Common Prefix

Problem:

Write a function to find the longest common prefix string amongst an array of strings.

Solution:

Careful when strs has no Strings at all.

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        String longest = "";
        int index = 0;
        if (strs.length == 0) return longest;
        while(index < strs[0].length()) {
            longest += strs[0].charAt(index++);
            for (int i = 1; i < strs.length; i++) {
                if (index > strs[i].length() || strs[i].charAt(index-1) != longest.charAt(index-1)) {
                    return longest.substring(0, index-1);
                }
            }
        }
        return longest;
    }
}

LeetCode 4. Median of Two Sorted Arrays

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution:

Copied from here. I’m such an idiot.

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        if ( total % 2 == 1 ){ //median in the middle number of two arrays
            return (double) findKth( nums1, 0, nums1.length-1, nums2, 0, nums2.length-1,total/2+1 );
        }else{ // median is the average of two middle numbers
            int part1 =  findKth( nums1,0,nums1.length-1,nums2,0,nums2.length-1, total/2);
            int part2 =  findKth( nums1,0,nums1.length-1,nums2,0,nums2.length-1,total/2 + 1);
            return (double) (part1+part2)/2;
        }
    }

    /****
     * Helper function to find the kth element of sub-ranges of two arrays
     */
    private int findKth ( int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k ){
        if (start1 > end1) { //no elements in first array
            return nums2[start2 + k - 1];
        } else if (start2 > end2) { // no elements in second array
            return nums1[start1 + k - 1];
        } else if (k == 1) { // result must be at the head of arrays
            return nums1[start1] < nums2[start2] ? nums1[start1] : nums2[start2];
        } else if (((end1 - start1 + 1) + (end2 - start2 + 1)) == k) { // result in the tails of arrays
            return nums1[end1] > nums2[end2] ? nums1[end1] : nums2[end2];
        }

        // Idetnify the parts of array can be possibly cuts
        int cut1 = (end1 - start1 + 1) < k / 2 ? (end1 - start1 + 1) : k / 2;
        int cut2 = (end2 - start2 + 1) < k / 2 ? (end2 - start2 + 1) : k / 2;

        if (nums1[start1 + cut1 - 1] == nums2[start2 + cut2 - 1] && k == (cut1 + cut2)) {
            //result is the cutting element
            return nums1[start1 + cut1 - 1];
        } else if (nums1[start1 + cut1 - 1] == nums2[start2 + cut2 - 1] && (k + 1) == cut1 + cut2) {
            //reust is the next of cutting element
            int next1 = (start1 + cut1) < nums1.length ? nums1[start1 + cut1] : Integer.MAX_VALUE;
            int next2 = (start2 + cut2) < nums2.length ? nums2[start2 + cut2] : Integer.MAX_VALUE;
            return next1 <= next2 ? next1 : next2;
        } else if (nums1[start1 + cut1 - 1] <= nums2[start2 + cut2 - 1]) {
            //cut first part of the first array
            return findKth(nums1, start1 + cut1, end1, nums2, start2, (cut1 + cut2) >= k ? (start2 + cut2 - 1) : end2, k - cut1);
        } else { //if ( nums1[start1+cut1-1] > nums2[start2+cut2-1]){
            //cut first part of the second array
            return findKth(nums1, start1, (cut1 + cut2) >= k ? (start1 + cut1 - 1) : end1, nums2, start2 + cut2, end2, k - cut2);
        }
    }
}

LeetCode 93. Restore IP Addresses

Problem:

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

Use recursion. Mind the cases like “010010”, no ip can be “0.10.01.0”.

public class Solution {
    ArrayList<String> result = new ArrayList<String>();
    public List<String> restoreIpAddresses(String s) {
        getIP(s, "", 3);
        return result;
    }
    
    private void getIP(String source, String current, int left) {
        if (left == 0) {
            if (source.length() < 1 || source.length() > 3) return;
            if (source.length() > 1 && source.charAt(0) == '0') return;
            int ip = Integer.parseInt(source);
            if (ip >= 0 && ip <= 255) {
                result.add(current + source);
            }
        }
        else {
            for (int i = 1; i < 4; i++) {
                int end = i < source.length() ? i : source.length();
                if (end == 0) return;
                String cut = source.substring(0, end);
                if (cut.length() > 1 && cut.charAt(0) == '0') return;
                int ip = Integer.parseInt(cut);
                if (ip >= 0 && ip <= 255) {
                    getIP(source.substring(end), current + ip + ".", left - 1);
                }
            }
        }
    }
}

LeetCode 142. Linked List Cycle II

Problem:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

Solution:

Such a mind game… use a slow tracker and a fast tracker, when slow and fast points to the same node, the start node is where head and slow reach after running the same distance.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode slow = head, fast = head.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while (slow.next != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

LeetCode 268. Missing Number

Problem:

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Solution:

O(n) time, O(1) space

public class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        for (int i = 1; i <= nums.length; i++) sum += i;
        for (int i = 0; i < nums.length; i++) sum -= nums[i];
        return sum;
    }
}

LeetCode 303. Range Sum Query – Immutable

Problem:

Given an integer array nums, find the sum of the elements between indices i and j (ij), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

Solution:

new to C, took a while.

struct NumArray {
    int* myNums;
    int* sums;
};

/** Initialize your data structure here. */
struct NumArray* NumArrayCreate(int* nums, int numsSize) {
    struct NumArray* numArray = malloc(sizeof(struct NumArray));
    numArray->myNums = nums;
    numArray->sums = malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        numArray->sums[i] = 0;
        for (int j = 0; j <= i; j++) {
            numArray->sums[i] += numArray->myNums[j];
        }
    }
    return numArray;
}

int sumRange(struct NumArray* numArray, int i, int j) {
    return numArray->sums[j] - numArray->sums[i] + numArray->myNums[i];
}

/** Deallocates memory previously allocated for the data structure. */
void NumArrayFree(struct NumArray* numArray) {
    free(numArray);
}

LeetCode 289. Game of Life

Problem:

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state.

Follow up:

  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Solution:

boring

public class Solution {
    int[][] myBoard, newBoard;
    public void gameOfLife(int[][] board) {
        myBoard = board;
        newBoard = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                update(i, j);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = newBoard[i][j];
            }
        }
    }
    
    private void update(int i, int j) {
        int live = countNeighbors(i, j);
        if (myBoard[i][j] > 0) {
            if (live < 2) newBoard[i][j] = 0;
            else if (live < 4) newBoard[i][j] = 1;
            else newBoard[i][j] = 0;
        }
        else if (live == 3) newBoard[i][j] = 1;
    }
    
    private int countNeighbors(int i, int j) {
        int count = 0;
        if (i - 1 >= 0) {
            if (myBoard[i-1][j] > 0) count++;
            if (j - 1 >= 0) {
                if (myBoard[i-1][j-1] > 0) count++;
            }
            if (j + 1 < myBoard[0].length) {
                if (myBoard[i-1][j+1] > 0) count++;
            }
        }
        if (i + 1 < myBoard.length) {
            if (myBoard[i+1][j] > 0) count++;
            if (j - 1 >= 0) {
                if (myBoard[i+1][j-1] > 0) count++;
            }
            if (j + 1 < myBoard[0].length) {
                if (myBoard[i+1][j+1] > 0) count++;
            }
        }
        if (j - 1 >= 0) {
            if (myBoard[i][j-1] > 0) count++;
        }
        if (j + 1 < myBoard[0].length) {
            if (myBoard[i][j+1] > 0) count++;
        }
        return count;
    }
}

LeetCode 154. Find Minimum in Rotated Sorted Array II

Problem:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution:

At first I did not see the array may contain duplicates, which really bugged me.

public class Solution {
    int[] myNums;
    public int findMin(int[] nums) {
        myNums = nums;
        if (nums.length < 10) {
            // avoid trivial cases
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < min) min = nums[i];
            }
            return min;
        }
        return getMin(0, nums.length - 1);
    }
    
    private int getMin(int start, int end) {
        int mid = (start + end) / 2;
        int left = start + (end - start) / 4;
        int right = end - (end - start) / 4;
        if (start > myNums.length - 1) return myNums[myNums.length - 1];
        if (end < 0) return myNums[0];
        if (end - start < 1) return myNums[start];
        if (myNums[left] <= myNums[mid] && myNums[mid] <= myNums[right]) {
            int opt1 = getMin(start, left - 1);
            int opt2 = getMin(right + 1, end);
            return Math.min(opt1, opt2);
        }
        else if (myNums[left] > myNums[mid]) {
            return getMin(left+1, mid);
        }
        else if (myNums[mid] > myNums[right]) {
            return getMin(mid+1, right);
        }
        return 0;
    }
}