Friday, January 29, 2016

LeetCode Q25: Reverse Nodes in k-Group (Hard)

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

1. Recursive solution (my own method)

One thing make me a bit confusing of this solution in the beginning is the use of the reference of the pointer as it is in the parameter list of function reverseKNodes(ListNode* head, int k, ListNode*& start, ListNode*& end). The reason we have to use reference for points here is because, we basically hope reverseKNodes function could change the content which is the address of memory stored in these pointer. However, these pointer is not container of address, they actually the container for ListNode object. So we either should use the pointer of the pointer ListNode ** xxx here or use the reference of the pointer.

2. Iterative solution.
This solution is from discuss forum of LeetCode. Author's original post is at: 

-1 -> 1 -> 2 -> 3 -> 4 -> 5
 |    |    |    | 
pre  cur  nex  tmp

-1 -> 2 -> 1 -> 3 -> 4 -> 5
 |         |    |    | 
pre       cur  nex  tmp

-1 -> 3 -> 2 -> 1 -> 4 -> 5
 |              |    |    | 
pre            cur  nex  tmp
Above is how it works inside one group iteration(for example, k=3)
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if(head==NULL||k==1) return head;
        int num=0;
        ListNode *preheader = new ListNode(-1);
        preheader->next = head;
        ListNode *cur = preheader, *nex, *tmp, *pre = preheader;
        while(cur = cur->next) 
            num++;
        while(num>=k) {
            cur = pre->next;
            nex = cur->next;
            for(int i=1;inext;
                nex->next = pre->next;
                pre->next = nex;
                cur->next = tmp;
                nex = tmp;
            }
            pre = cur;
            num-=k;
        }
        return preheader->next;
    }
};
Thanks to ciaoliang1992, the tmp pointer is no necessary, so the more concise solution is
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if(head==NULL||k==1) return head;
        int num=0;
        ListNode *preheader = new ListNode(-1);
        preheader->next = head;
        ListNode *cur = preheader, *nex, *pre = preheader;
        while(cur = cur->next) 
            num++;
        while(num>=k) {
            cur = pre->next;
            nex = cur->next;
            for(int i=1;inext=nex->next;
                nex->next=pre->next;
                pre->next=nex;
                nex=cur->next;
            }
            pre = cur;
            num-=k;
        }
        return preheader->next;
    }
};



LeetCode Q24: Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Surprising to see the difficulty level of this question is marked as "Medium". But it could be this hard if you really try to solve it in an iterative way. Because you gonna be very careful doing many swaps in one iteration.

However, your life will get easier if you try a recursive solution which basically just takes you no more than 10 lines code such as the one in the below:


Solution 2:

LeetCode Q23: Merge k Sorted Lists (Hard)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution 1:
The initial idea is very straightforward that every time we take the node with the least number from k lists and link this node to current merged list. To speed up in every round when choosing node with smallest number, I use priority queue.

The code is in following:

Solution 2:
Divide and conque, merge 2 lists at a time. Fastest, 36ms, beat 100%

LeetCode Q22: Generate Parenthesis

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"


Thursday, January 28, 2016

LeetCode Q21: 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.

The easiest way is to use recursion.

LeetCode Q18: 4Sum

Given an array S of n integers, are there elements abc, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2)
(-2, 0, 0, 2)
Extended from 3Sum, fixed the first pointer, and for the last three pointers, solve the problem use 3Sum. 

Solution:
This problem can be downgraded to 3Sum then to 2Sum problem. We will solve the most inner loop using two pointers. For all other loops, we linearly scanning over the given array. The trick here is that in each loop, we skip over identical elements which are not seen the first time.




Wednesday, January 27, 2016

LeetCode Q16: 3Sum Cloest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).


I first come up with a wrong solution which seems to be  very reasonable and actually similar to the final correct one. The idea in this wrong solution works by using two pointers pointing to the start and end of the sorted array. In every iteration, search the best result inbetween two pointers. Adjust (increase low point or decrease high pointer) the pointers according to the best result of current iteration. Actually so far I still can not figure out why this solution is wrong. Following is the code for this wrong soluton
  • Wrong solution


In correct solution, the idea is very similar to the one I described above. But difference is that, in this solution, in i=th iteration we keep the first pointer fixed at i-th element, and start a same searching process using two pointers as I described in the wrong solution. Following is the code for this correct solution 

  • Correct solution

Tuesday, January 26, 2016

How to create virtual environment for Python

Please refer to this fantastic post.

LeetCode Q15: 3 Sum

Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

My solution:
O(n^2).

Friday, January 22, 2016

LeetCode Q11: Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.


  • Mehtod1

Most naive way, two loops .


  • Method2


  • Method3
O(n) time method, use two pointers to scan the array once.
Suppose two points are s, e. In the beginning, s at the left end, e at the right end. The goal is to maximize the area. So, in this case, we always try to move the shortest bar between s and e to left(s) or to right(e) to look for next bigger area.

Thursday, January 21, 2016

LeetCode Q4: Median of Two Sorted Arrays (Hard)

Let's consider a more general solution, specifically, a method similar to finding the k-th smallest element in an array and remove elements smaller than k in each iteration.

Assume that the number of elements in A and B are both larger than k/2, and if we compare the k/2-th smallest element in A(i.e. A[k/2-1]) and the k-th smallest element in B(i.e. B[k/2 - 1]), there are three results:
(Becasue k can be odd or even number, so we assume k is even number here for simplicy. The following is also true when k is an odd number.)
A[k/2-1] = B[k/2-1]
A[k/2-1] > B[k/2-1]
A[k/2-1] < B[k/2-1]
if A[k/2-1] < B[k/2-1], that means all the elements from A[0] to A[k/2-1](i.e. the k/2 smallest elements in A) are in the range of k smallest elements in the union of A and B. Or, in the other word, A[k/2 - 1] can never be larger than the k-th smalleset element in the union of A and B.

Why?
We can use a proof by contradiction. Since A[k/2 - 1] is larger than the k-th smallest element in the union of A and B, then we assume it is the (k+1)-th smallest one. Since it is smaller than B[k/2 - 1], then B[k/2 - 1] should be at least the (k+2)-th smallest one. So there are at most (k/2-1) elements smaller than A[k/2-1] in A, and at most (k/2 - 1) elements smaller than A[k/2-1] in B.So the total number is k/2+k/2-2, which, no matter when k is odd or even, is surly smaller than k(since A[k/2-1] is the (k+1)-th smallest element). So A[k/2-1] can never larger than the k-th smallest element in the union of A and B if A[k/2-1]Since there is such an important conclusion, we can safely drop the first k/2 element in A, which are definitaly smaller than k-th element in the union of A and B. This is also true for the A[k/2-1] > B[k/2-1] condition, which we should drop the elements in B.
When A[k/2-1] = B[k/2-1], then we have found the k-th smallest element, that is the equal element, we can call it m. There are each (k/2-1) numbers smaller than m in A and B, so m must be the k-th smallest number. So we can call a function recursively, when A[k/2-1] < B[k/2-1], we drop the elements in A, else we drop the elements in B.


We should also consider the edge case, that is, when should we stop?
1. When A or B is empty, we return B[k-1]( or A[k-1]), respectively;
2. When k is 1(when A and B are both not empty), we return the smaller one of A[0] and B[0]
3. When A[k/2-1] = B[k/2-1], we should return one of them

In the code, we check if m is larger than n to garentee that the we always know the smaller array, for coding simplicy.

LeetCode Q10: Regular Expression Matching

'.' 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

Solution:
This problem has a typical solution using Dynamic Programming. We define the state P[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. Then the state equations are:
  1. f[i][j] = f[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
  2. f[i][j] = f[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
  3. f[i][j] = f[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.
Putting these together, we will have the following code.


How to insert code to Blogger

I basically following this blog

 Yet, the easiest way is to use Github GIST https://gist.github.com/, I love it to died!