Monthly Archives: June 2016

Valid Perfect Square

leetcode 367. Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Input: 16
Returns: True

Example 2:

Input: 14
Returns: False

Solution. An awesome solution is from here: n is perfect square if n = 1 + 3 + 5 + …. Below is the code:

public static boolean isPerfectSquare(int num) {
    int delta = 1;
    while (num > 0) {
        num -= delta;
        delta += 2;
    }
    return num == 0;
}

Max subarray, and Max sub rectangle less than K

This is a variation of this post. Besides finding the max continuous subarray, it requires that the max value should be less or equal to K.

The solution is to store all the sum[right] for arr[0, …, right]. Then try to find the sum[left] for arr[0, …, left], which we can get max(sum[right] – sum[left]) and sum[right] – sum[left] <= k. See below description:

maxArrayK

So, when we have sumRight and k, we try to find the sumLeft, which is equal to or greater than sumRight – k. In order to achieve this, we can use TreeSet.

Below is the code for this problem. A important part of this code is that we should add 0 into TreeSet, or it won’t pass case like ({1, 0}, 2) or ({2}, 2)

public static int maxSubArrayLessThanK(int []arr, int k) {
    int ans = Integer.MIN_VALUE, sumRight = 0;
    TreeSet<Integer> ts = new TreeSet<>();
    ts.add(0);  // this is important. without this, won't pass {1, 0}
    for (int i : arr) {
        sumRight += i;
        Integer sumLeft = ts.ceiling(sumRight - k);
        if (sumLeft != null) {
           ans = Math.max(ans, sumRight - sumLeft);
        }
        ts.add(sumRight);
    }
    return ans;
}

Finally, let’s jump to the leetcode problem: Max Sum of Rectangle No Larger Than K. Since we went through this problem and previous max subarray problem, this rectangle no larger than K problem can be solved naturally:

public static int maxSubArrayRectangleLessThanK(int [][]matrix, int k) {
    int ans = Integer.MIN_VALUE, row = matrix.length, col = matrix[0].length;
    for (int left = 0; left < col; left++) {
        int[] helper = new int[row];
        for (int right = left; right < col; right++) {
            for (int i = 0; i < helper.length; i++) {
                helper[i] += matrix[i][right];
            }
            int sumRight = 0;
            TreeSet<Integer> ts = new TreeSet<>();
            ts.add(0);  // this is important. without this, won't pass {1, 0}
            for (int i : helper) {
                sumRight += i;
                Integer sumLeft = ts.ceiling(sumRight - k);
                if (sumLeft != null) {
                    ans = Math.max(ans, sumRight - sumLeft);
                }
                ts.add(sumRight);
            }   // for
        }   // for
    }
    return ans;
}

Check my code on github: MaxSubarrayLessThanK, MaxSubarrayRectangleLessThanK

Max subarray, and Max sub rectangle

Max subarray is from here: https://en.wikipedia.org/wiki/Maximum_subarray_problem

Finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

This is a classical problem which can be solved by Kadane algorithm. Below is the java solution:

public static int maxSubArray(int []arr) {
    int max = arr[0], currMax = arr[0];
    for (int i = 1; i < arr.length; i++) {
        currMax = Math.max(currMax + arr[i], arr[i]);  // compare the history continuous sum and current value
        max = Math.max(max, currMax);  // update the max
    }
    return max;
}

However, this problem can be developed to 2d problem: Given a 2D array, find the maximum sum subarray in it. For example, in the following 2D array, the maximum sum subarray is highlighted with blue rectangle and sum of this subarray is 29. (http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/)

A great solution can be found in Tushar’s tutorial. In the solution, the outer loop iterates the column(left, right). Then it calculates the 1-dimension helper array which is sum of all elements from column left to column right. Then run the Kadane’s algorithm on this helper array.

Below is my java code:

public static int maxSubArrayRectangle(int [][]arr) {
    int row = arr.length, col = arr[0].length, max = arr[0][0];
    int[] helperArr = null;
    for (int left = 0; left < col; left++) {
        helperArr = new int[col];
        for (int right = left; right < col; right++) {
            // update helper
            for (int i = 0; i < row; i++) {
                helperArr[i] += arr[i][right];
            }
            // Kodane algorithm to find the top and bottom for max continuous sequence
            int helperMax = helperArr[0], currHelperMax = helperArr[0];
            for (int i = 0; i < row; i++) {
                currHelperMax = Math.max(currHelperMax + helperArr[i], helperArr[i]);
                helperMax = Math.max(helperMax, currHelperMax);
            }
            max = Math.max(currHelperMax, max);
        }
    }
    return max;
}

Check my code on github: Max subarray, Max sub rectangle

Counting bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Solution. A great solution is from here. It uses the formula: f(x) = f(x / 2) + x % 2

0        1        2        3        4        5        6        7        8

0        1       10      11       110     101    110   111      1000

0        1        1        2        2        2        2        3        1

We know 7 move right 1 bit, then it can reach 3. So we can calculate 7 by 3. The only difference is that we need to know the new bit is 0 or 1.

Check my code on github.

Intersection of Two Linked Lists

leetcode 160.

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

Solution. I got the cool but trick solution from here. O(n) time, O(1) space.

Define a and b Node to travel through 2 lists. The point is to let both a and b travel complete 2 lists.

a travels: a1 -> a2 -> c1 -> c2 -> c3 -> b1 -> b2 -> b3 -> c1

b travels: b1 -> b2 -> b3 -> c1 -> c2 -> c3 -> a1 -> a2 -> c1

If order to let a, b travel, below code is presented:

def getIntersectionNode(self, headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a != None else headB
        b = b.next if b != None else headA
    return a

Check my code on github: link

Count Numbers with Unique Digits

leetcode 357.

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Solution. This problem is a combination problem.

When n == 0, return 1. I got this answer from the test case.

When n == 1, _ can put 10 digit in the only position. [0, … , 10]. Answer is 10.

When n == 2, _ _ first digit has 9 choices [1, …, 9], second one has 9 choices excluding the already chosen one. So totally 9 * 9 = 81. answer should be 10 + 81 = 91

When n == 3, _ _ _ total choice is 9 * 9 * 8 = 684. answer is 10 + 81 + 648 = 739

When n == 4, _ _ _ _ total choice is 9 * 9 * 8 * 7.

…

When n == 10, _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

When n == 11,  _ _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 0 = 0

Others are always 0.

Below is my code:

public static int countNumbersWithUniqueDigits(int n) {
    if (n == 0) {
        return 1;
    }
    int ans = 10, base = 9;
    for (int i = 2; i <= n && i <= 10; i++) {
        base = base * (9 - i + 2);
        ans += base;
    }
    return ans;
}

Here is my code on github: link

Data Stream as Disjoint Intervals

From https://leetcode.com/problems/data-stream-as-disjoint-intervals/

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

This is a good one. The solution from here. Use TreeMap and put start as key, (start, end) as value in TreeMap. Basically, ; there will be 3 conditions when adding a new value: add 4 to (5, 6), (8, 9); add 6 to (5, 5); add 4 to (5, 5):

add_middle              add_left              add_right

Besides, there are 2 exceptions: add 6 to (5, 7); add 6 to (6, 6):

exception1       exception2

Check my code on github: link

Lambda study summary

Below code is a basic way to self-define a lambda. Basically, it requires:
1. a interface with only one function
2. a method which has the interface as parameter, and in the method, it will call the function in that interface implementation.

public static void simpleWay() {
    Math add = new Math() {
        @Override
        public int operate(int a, int b) {
            return a + b;
        }
    };
    Math sub = new Math() {
        public int operate(int a, int b) {
            return a - b;
        }
    };
    System.out.println(MathOperation(1, 2, add));
    System.out.println(MathOperation(1, 2, sub));
}

public static void lambdaWay() {
    Math add = (int a, int b) -> a + b;
    Math sub = (int a, int b) -> a - b;
    System.out.println(MathOperation(1, 2, add));
    System.out.println(MathOperation(1, 2, sub));
}

/**
 * MathOperation and Math are the core for defining lambda expression.
 * An operation interface and a function which uses interface.do() to return something.
 */

public static int MathOperation (int a, int b, Math math) {
    return math.operate(a, b);
}

interface Math {
    public int operate(int a, int b);
}

After that, below are some useful lambda expression in Java 8.

public static void forEachCase() {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.forEach(i -> System.out.println(i));
}

public static void removeIf() {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.removeIf(i -> i == 2); // if only has one element, doesn't has to be (Integer i) -> i == 2 ....  Could be i -> i == 2
    System.out.println(list);
}

public static void replaceAll() {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.replaceAll(i -> -i);
    System.out.println(list);
}

public static void sortCase1() {
    List<Integer> list = new ArrayList<>();
    list.add(3);
    list.add(2);
    list.add(1);
    list.add(4);
    Collections.sort(list, (i1, i2) -> i1 - i2);
    System.out.println(list);
}

public static void sortCase2() {
    List<Integer> list = new ArrayList<>();
    list.add(3);
    list.add(2);
    list.add(1);
    list.add(4);
    list.sort((i1, i2) -> i1 - i2);
    System.out.println(list);
}

public static void threadCase() {
    Runnable r1 = () -> {
        try {
            for (int i = 0; i < 10; i++) {
                System.out.println(i);
                Thread.sleep(1000);
            }
        } catch (Exception e) {}
    };
    new Thread(r1).start();
}