Our blog, keeping you up-to-date on our latest news.

 

[Leetcode]Contains Duplicate III

June 28, 2015 at 10:36 pm | Algorithms | No comment

 

Overview

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Thoughts

the thought process is to exam the numbers within k distances, and see if there is aa number having a difference smaller than t. The most intuitive solution is to have two loops, the first loop to go through all numbers in the array, and the inside loop check every number within k difference, to see if it is a almost duplicate number.

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums==null || nums.length<=1 || k<=0 || t<0)
            return false;
        for(int i = 1; i<nums.length; i++){
            for(int j = Math.max(0, i-k); j<i; j++){
                if(Math.abs(nums[i]-nums[j])<=t)
                    return true;
            }
        }
        return false;
    }
}

but obviously, this solution is not quite good from time efficiency perspecitive. The time complexity is O(n*k), the worst case is O(n^2). So to optimize this, we should ask one question: do we really need to exam all items within k distances?

the answer is of course not, we can maintain an binary search tree, to identify the numbers with smallest difference. and the search of the time complexity will be reduced from O(n) to O(lg).

Solution

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 
        if(nums==null || nums.length<=1 || k<=0 || t<0)
            return false;
 
        TreeSet<Integer> window = new TreeSet<Integer>();
 
        for(int i = 0; i<nums.length; i++){
 
            Integer floor = window.floor(nums[i]);
            Integer ceiling = window.ceiling(nums[i]);
            if(floor != null && new Long(nums[i])- new Long(floor)<= new Long(t))
                return true;
            if(ceiling != null && new Long(ceiling)- new Long(nums[i])<= new Long(t))
                return true;
            if(window.size()==k)
                window.remove(nums[i-k]);
            window.add(nums[i]);
        }
        return false;
    }
}

Notes

1. I choose the treeset, which is using treemap to hold all the elements. And the treemap is an implemenation of black-red tree.
2. we have to be very careful about the edge condwitions. especially when the Integer number is extremely large, and the difference might be exceed the maxium value of an Integer.

 

[Leetcode]Single Number II

January 29, 2015 at 6:41 am | Algorithms | No comment

 

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

[Thoughts]

This one is similar to the “Single Number”, and the idea is the same too, try to make the numbers appear three times to zero, and then leave the single one as our result.
One way is to look into each integer in a bit way. then each number is 32 bits. if the number appears three times, that means each bit for this number appears three times as well. then if we add each bit accordingly, and then use math mod(“%”) operation, all numbers appear three times will be 0.
And this way is very common, it could apply to element appear twice, three times, four times etc.

Solution

public class Solution {
    public int singleNumber(int[] A) {
 
        int result = 0;
 
        for(int i = 0; i< 32; i++){
            int count = 0;
            for(int j=0; j<A.length; j++){
                //add up all number's 'ith' bits.
                count+=((A[j]>>i)&1);
            }
            result|=((count%3)<<i);
        }
        return result;
    }
}
 

[Leetcode]Single Number

January 29, 2015 at 5:51 am | Algorithms | No comment

 

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

[Thoughts]

So this is a good example of algorithm that uses bit-wise operation.

As each number appears twice except for one, so if we can make all pairs disappear, then the remaining one will be  the single one. And the bit-wise operator XOR is just the operator we needed, as it has this nature:

x ^ 0 == x
x ^ x == 0

[Solution]

public class Solution {
    public int singleNumber(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        int result = A[0];
        for(int i = 1; i<A.length; i++)
            result^=A[i];
        return result;
    }
}
 

Java Bit Manipulation Guide

January 25, 2015 at 5:03 am | Algorithms | No comment

 

Overview

I found that in some algorithms it has a lot of bit manipulation. Some of you may not have ever done manipulation, and some of you may not know how to do it in Java. This is a short guide to help you. I found this guide from rice university and here is the original URL: http://sys.cs.rice.edu/course/comp314/10/p2/javabits.html

Shift Happens

Some of the most basic operations on bits is shifting in the form of a shift left and a shift right. In Java, the operators are << and >>. Here is what they do:

/* 00000001 << 1 = 00000010 */
1 << 1 == 2 
 
/* 00000001 << 3 = 00001000 */
1 << 3 == 8
 
/* 11111111 11111111 11111111 11110000 >> 4 = 11111111 11111111 11111111 11111111 */
0xFFFFFFF0 >> 4 == 0xFFFFFFFF 
 
/* 00001111 11111111 11111111 11111111 >> 4 = 00000000 11111111 11111111 11111111 */
0x0FFFFFFF >> 4 == 0x00FFFFFF

Note that the right shift operator is signed. Java, as with many languages, uses the most significant bit as a “sign” bit. A negative number’s most significant bit is always ‘1’ in Java. A signed shift-right will shift in the value of the sign. So, a binary number that begins with ‘1’ will shift in ‘1’s. A binary number that begins with ‘0’ will shift in ‘0’s. Java does bitwise operators on integers, so be aware!

You can use a third shift operator called the “unsigned shift right” operator: >>> for always shifting in a “0” regardless of the sign.

/* 10000000 00000000 00000000 00000000 >>> 1 = 01000000 00000000 00000000 00000000 */
0x80000000 >>> 1 == 0x40000000
 
/* 10000000 00000000 00000000 00000000 >> 1 = 11000000 00000000 00000000 00000000 */
0x80000000 >> 1  == 0xC0000000

One of the uses for in creating quick powers of 2. Shifting “1” by 1 is 2, by 2 is 4, by 4 is 8, etc.. Similarly, a quick shift right will divide a number by two.

This is also useful for creating masks. A bitmask is used for isolating or altering a specific part of  a binary number. This is described in detail in the next section. For now, assume that we want to create the bitmask 00001000. Then the code is just

int bitmask = 1 << 3;

You can create more complicated bit masks using binary arithmetic operators which are also described in the next section.

Binary “BitWise” Operations

Here are four common bit operators in Java.

  • ~ – The unary complement
  • & – Bitwise and
  • ^ – Bitwise exclusive or
  • | – Bitwise inclusive or

Here are some examples of their use (just showing the binary for simplicity):

1010 & 0101 == 0000
1100 & 0110 == 0100
 
1010 | 0101 == 1111
1100 | 0110 == 1110
 
~1111 == 0000
~0011 == 1100
 
1010 ^ 0101 == 1111
1100 ^ 0110 == 1010

You can “set” a bit in a number by “or”-ing with another number with that bit (and only that bit) set to 1.

10000001 | 00100000 = 10100001 /* turned on bit 5 */
10000001 | 1 << 5 = 10100001 /* did the same thing
00000000 | 1 << 2 | 1 << 5 = 00100100

There are other methods for setting bits that do not require branching. I do not describe those here, although you might look at this document.

You can turn off a bit by anding with a binary number of all 1’s, except for the bit to be set.

01010101 & ~(1<<2) == 01010101 & 11111011 == 01010001

A Word About Bit Order

Assuming that the most-significant-bit is on the left,

10010110
^      ^
|      |------- bit 0
|
|-------------- bit 7

Notice that the value of bit 0 is 2^0, bit 1 is 2^1, …, bit 7 is 2^7.

Using ParseInt

A very convenient way to work with binary numbers in your code is to use the Integer.parseInt() command. Integer.parseInt("101",2) creates an integer with the binary value of 101 (decimal 5). This means that you can even do a for loop with binary in this manner:

/* loops from 5 up to and including 15 */
for (int b = Integer.parseInt("0101",2); b <= Integer.parseInt("1111",2); b++) {
	/* do stuff here */
}

 

Reading and writing bits

Some useful advice: build yourself a class that knows how to read and write bits to a stream rather than the usual Java input and output streams that know all about reading and writing bytes.  You’ll find it helpful to separate out the operations of “give me the next N bits” and “advance the cursor by M bits.”  For example, this would allow you to read enough data to cover the longest possible Huffman code. Once you discover the true length of the Huffman code you just read, then you advance the cursor by only that many bits.  A class like that also lets you try to compartmentalize the uglier aspects of bit manipulation into a fairly small chunk of code.

Likewise, if you’re going for speed, then you’ll find table lookups to be exceptionally powerful.  Imagine you’ve got one Huffman code that’s simply “0” while all the other codes are exactly three bits long and start with “1”.  That means you need a table with eight entries (2^3 = 8).  Your table might then say:

char code[8];
int codelen[8];
 
code[0] = 'a'; codelen[0] = 1;
code[1] = 'a'; codelen[1] = 1;
code[2] = 'a'; codelen[2] = 1;
code[3] = 'a'; codelen[3] = 1;
code[4] = 'b'; codelen[4] = 3;
code[5] = 'c'; codelen[5] = 3;
code[6] = 'd'; codelen[6] = 3;
code[7] = 'e'; codelen[7] = 3;

With two array lookups, you now know the token and how many bits to advance to find the next one.  This is going to be far, far cheaper than some kind of for loop over all possible tokens, at the expense of a little more RAM usage.

 

[LeetCode] Regular Expression Matching, Solution

January 17, 2015 at 10:10 pm | Algorithms | No comment

 

Implement regular expression matching with support for ‘.’ and ‘*’.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.
 
The matching should cover the entire input string (not partial).
 
The function prototype should be:
bool isMatch(const char *s, const char *p)
 
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true

[Thoughts]

String match, and it is a typical DP problem.

create a two dimension table dp[s.length()+1][p.length()+1]

so dp[i][j] means whether string [0, i-1] matches pattern [0, j-1]
and dp[i+1][j+1] means whether string [0, i] matches pattern [0, j]

to initialize, dp[0][0] should be true, which means empty string matches empty string.
and dp[i][0] should be always false, when string is not empty, but the pattern is empty.
and dp[0][j] depends on whether there are ‘*’, because * could match empty string, for example ‘a*’ could match an empty string

to get the value dp[i+1][j+1]:
1. the simplest way, if s[i]==p[j]|| p[j]==’.’, that means we need to check whether s[0, i-1] matches p[0, j-1]
dp[i+1][j+1] = dp[i][j]

2. the complicated way, if(p[j]==’*’), that means we need to check the wildcard
the wildcard may take effective from 0 time to many times
if the wild card plays 0 time, then it matches an empty string with the previous character.
in this scenario, dp[i+1][j+1] = dp[i+1][j-1]

if the wild card plays once, then dp[i+1][j+1] = dp[i][j-1] && (s[i]==p[j-1] || p[j-1] == ‘.’)

if the wild card plays many times, the dp[i+1][j+1] = dp[i][j+1] && (s[i]==p[j-1] || p[j-1] == ‘.’)

3. the other scenarios, the default value “false” will be populated for the rest.

[Solution]

public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        //it actually is not necessary, as the default value is false for primitive boolean
        for(int i =0; i<s.length(); i++){
            dp[i+1][0] = false;
        }
        for(int j =0; j<p.length(); j++){
            if(j-1>=0 && p.charAt(j) == '*')
                dp[0][j+1]=dp[0][j-1];   
            else    
                //it actually is not necessary, as the default value is false for primitive boolean
                dp[0][j+1] = false;
        }
        for(int i =0; i<s.length(); i++){
            for(int j = 0; j< p.length(); j++){
                if(p.charAt(j) == s.charAt(i)||p.charAt(j) == '.'){
                    dp[i+1][j+1] = dp[i][j];   
                }
                else if(p.charAt(j) == '*' && j-1>=0){
                    if(p.charAt(j-1)==s.charAt(i) || p.charAt(j-1) == '.' )
                        // dp[i][j+1] means the * matches many times
                        // dp[i][j-1] means the * matches once
                        dp[i+1][j+1] = dp[i][j+1] || dp[i][j-1];
                    //the * matches 0
                    dp[i+1][j+1] = dp[i+1][j+1]||dp[i+1][j-1];;
                }
 
            }
        }
 
        return dp[s.length()][p.length()];
 
    }
}