Fmars Blog: Leetcode_num

Showing posts with label Leetcode_num_bit. Show all posts

[Leetcode Solution] Divide Two Integers

[Leetcode Solution] Next Permutation

Analysis

Let's consider a simpler situation. Given n integers [1..n] and a permutation generated by these n integers. How to find the next permutation.

It seems easy right. If we treat the permutation as a integer number, our purpose is to increase value of this number to the nearest one by reorder the integers.

Say the permutation is like this [a(1),a(2),...,a(n)]. if i<j and a(i) < a(j). If we swap ai and aj the value of permutation will increase. In order to get the nearest bigger number, we would like to increase a bit in least significant bit by swap it with a bit at more least significant direction. So the solution is find the first a(i) that there is an a(j) that a(i) < a(j) and i<j. After that we swap the value of a(i) and a(j) then resort the integers from a(i+1) to a(n) in order to change it to the smallest one.

Now consider the given scenario. There are different integers in the permutation and duplicates.

First we can just treat different integers as the sequence of 1 .. n because they share the same order. Only order makes a difference rather then the value.
Second if duplicates exist, we will only update the part which finds the first a(i).

Note

Code

[Leetcode Solution] Longest Valid Parentheses

GOOD PROBLEM

Analysis

Very similar to problems like 'Best Time to Buy and Sell Stock' and 'Largest Rectangle in Histogram' which can be easily solved in O(n*n) but has a tricky O(n) solution by two pointers scan or stack.
As the same of 'Largest Rectangle in Histogram' this problem use a stack to maintain the previous state and calculate the current state in constant time which eventually leads to a O(n) time solution.

Use a stack to store the previous information. Iterate the input string.

If string[i] == '(', push it back to the stack and store the position of '('
If string[i] == ')' then pop the last element in the stack and calculate the length of the substring formed by these ')' and '(' based on the position information stored before.

The tricky is, if a test case exists like this
"( ) ( )"
the above solution will get two parentheses pairs whose length is 2 for each but cannot sum up them together.

So the solution is adding another pointer 'start' which used to store the start position of a entire valid paired sub string. Because we know that the sub string will become invalid if the number of ')' is larger then '(' when we iterate from left to right. So as long as the number of ')' is not larger then '(', the sub string is still valid and it could be formed as a entire paired sub string.

Thus we will only reset the 'start' pointer when stack is empty and the current char is ')'.
When we calculate the length of sub string, if the stack is empty, we should use the 'start' as the start position rather then the position information stored in the stack.

Note

Code

[Leetcode Solution] Trapping Rain Water

Analysis

The volume of water can be trapped above one point depends on the highest integers in its bi-directions.
Use three passes. First find out the left side highest integer of each node, second find out the right side. Last compute the volume of water trapped at each node

Note

Code

[Leetcode Solution] Pow(x, n)

Analysis

Using f[x]=f[x-1]*x could exceed the time limits because the range of x is the integer
Using f[x]=f[x/2]*f[x/2] would be fine.

Note

When x is negative, f(x)=1/f(-x). The only thing should be notice is that -INT_MIN==-INT_MIN. This case should be treated separately

Code

[Leetcode Solution] Permutation Sequence

Analysis

At first think about the search, it should be kind of slow. And actually it exceeds the time limits
The problem is only need to get the k-th element, so we can directly calculate what the k-th element is, rather then enumerate all the elements. The idea is like carry.
If we have n integers [1..n], and the number of permutation starting from each integer is (n-1)!, thus we can calculate the first number of required permutation according to k/(n-1).
Then we can update the k, and do this procedure recursively

Note

Dealing with something like carry, or divide the region, given the each region's size S, and the k-th number, ask which region this number located in. Make the k start from 0 and then use k/S to get it

Code

[Leetcode Solution] Plus One

Analysis

Start from the least significant digit to find the first p that Digits[p] != 9
Plus one to this digit and change the digits from the least significant one to 0 until this digit
If all the digits are 9, then assign the first as 1, change all others as 0, and add one digit 0 at the end

Note

Code

UPDATED AT 2ND PASS

[Leetcode Solution] Maximal Rectangle

Analysis

Take advantage of this problem about how to solve the 1-dimensional problem
Now let's take a look at how to transform this problem to the 1-dimensional one, and then use O(n) algorithm to solve it (n is the number of nodes in the rectangle)

For each column in the matrix, we can treat it as a max rectangle in histogram problem
Let say the second column in the matrix above, we can do such a transformation: each integer in the histogram is the number of consecutive '1' started from each element in this column, then it is

Then the whole 2D matrix can be transformed into several 1D problems. And this procedure can be done in O(n) taking advantage of that we can know the number of consecutive '1' in one place instantly if we know the number of consecutive '1' in the adjacent right place

After the transformation in O(n), we will execute the max rectangle in histogram algorithm several times which equals to the number of columns. Then return the max one.

Note

Code

[Leetcode Solution] Largest Rectangle in Histogram

Analysis

The O(n*n) algorithm is obvious

for each rectangle with the high of i-th element, using two indices move to left and right separately to find the region in which every integer is bigger then i-th element. Then the size of rectangle equals to height of i-th element times the distance between two indices
Based on this idea, O(n*n)is obvious. Iterate all the integer as the height integer, and find the formed rectangle size.

The O(n) algorithm is tricky however the behind idea is the same. The procedure that iterate all the integer and find out the rectangle formed by this integer is still needed. However for different integers, this find out procedure has a lot of common sub problems. So we can take advantage of this to do the O(n) algorithm.

Use a stack to store the integers
If the current integer is smaller then the element at the top of the stack, then push it into the stack
If the current integer is bigger then the element at the top of the stack, calculation needs to be done

The idea is the same
Because the current integer is bigger then the top of stack, thus the rectangle formed by the top of stack cannot contain the current integer but contains the integer before current integer.
Because the second to last integer in the stack is smaller then the integer at the top of stack, so the rectangle formed by the integer of top of stack cannot contain the second to last integer. However it contains the integer after the second to last integers.
At this time, the rectangle formed by the integer at the top of stack can be calculate

Push back a integer 0 at the end of the vector to enforce all the rectangle is calculated.

Note

Code

[Leetcode Solution] Single Nubmer 2

Analysis

Using XOR method is no more work
Count the number of bit occurring at each position to each number in binary form
The single number will contain one bit iff the number of bit occurring at that bit cannot divided by 3

My Blog List

Analysis

Note

Code

GOOD PROBLEM

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis

Note

Code

Analysis