2015年8月30日星期日

Lintcode: Reverse Linked List

Reverse a linked list.
Have you met this question in a real interview? 
Yes
Example
For linked list 1->2->3, the reversed linked list is 3->2->1
Challenge
Reverse it in-place and in one-pass
Tags Expand 
Linked List

Initial Solution:
Use three pointers and draw sketch:
Don't forget to add Null to head and reverse next and cur pointer after while loop
Time: O(n)
Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition of ListNode
 * 
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 * 
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The new head of reversed linked list.
     */
    ListNode *reverse(ListNode *head) {
        // write your code here
        
        ListNode *prev = head;
        if(!head) return NULL;
        ListNode *cur = prev->next;
        if(!cur) return head;
        head->next = NULL;
        ListNode *next = cur->next;
        while(next){
            cur->next = prev;
            prev = cur;
            cur = next;
            next = next->next;
        }
        cur->next = prev;
        return cur;
    }
};
Solution 1: Exchange adjacent nodes
Two pointers solution: Set prev node as null is a convenient way to set head->next =NULL
Time: O(n)
Space: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition of ListNode
 * 
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 * 
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The new head of reversed linked list.
     */
    ListNode *reverse(ListNode *head) {
        // write your code here
       ListNode* prev = NULL;
       ListNode* cur = head;
       while(cur){
           ListNode* temp = cur->next;
           cur->next = prev;
           prev = cur;
           cur = temp;
       }
       return prev;
    }
};

Solution 2: Recursion
Recursive nested layers: O(n)
Time: O(n)
space:O(1) ----without stack space

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition of ListNode
 * 
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 * 
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list
     * @return: The new head of reversed linked list.
     */
    ListNode *reverse(ListNode *head) {
        // write your code here
       if(head == NULL) return head;
       if(head->next == NULL) return head;
       //keep tracking head of the reversed linkedlist
       ListNode *newHead = reverse(head -> next); 
       head->next->next = head;
       head->next = NULL;
       
       return newHead;
    }
};


Lintcode second:
Three pointers solution:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The new head of reversed linked list.
     */
    ListNode *reverse(ListNode *head) {
        // write your code here
        ListNode* prev, *cur, *next;
        prev = NULL;
        cur = head;
        if(!head) return NULL;
        next = cur->next;
        while(next){
            cur->next = prev;
            prev = cur;
            cur = next;
            next = next->next;
        }
        cur->next = prev;
        return cur;
    }
};

two pointers solution:



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The new head of reversed linked list.
     */
    ListNode *reverse(ListNode *head) {
        // write your code here
        ListNode *prev, *cur;
        prev = NULL;
        cur = head;
        if(!head) return head;
        while(cur){
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

发帖者 时间： 没有评论:

Lintcode: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2->null and x = 3,
return 1->2->2->4->3->5->null.
Have you met this question in a real interview? 
Yes
Example
Tags Expand 
Two Pointers Linked List


Set two dummy head nodes, put nodes into two head by value
Note: Line 40: Don't forget to set the next of last node is NULL
http://www.cnblogs.com/springfor/p/3862392.html
Time: O(n)
Space: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    ListNode *partition(ListNode *head, int x) {
        // write your code here
        ListNode* head1 = new ListNode(0);
        ListNode* head2 = new ListNode(0);
        ListNode* p1 = head1;
        ListNode* p2 = head2;
        
        ListNode* cur = head;
        while(cur != NULL){
            if(cur->val < x){
                p1->next = cur;
                p1 = p1->next;
                cur = cur->next;
            }
            else{
                p2->next = cur;
                p2 = p2->next;
                cur = cur->next;
            }
        }
        p2->next = NULL;
        p1->next = head2 ->next;
        return head1->next;
    }
};

Lintcode second :


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    ListNode *partition(ListNode *head, int x) {
        // write your code here
        ListNode *p1, *p2, *p3, *p4;
        p1 = new ListNode(0);
        p2 = new ListNode(0);
        p3 = p1;
        p4 = p2;
        while(head){
            if(head->val < x) {
                p1->next = head;
                p1 = p1->next;
            }
            else {
                p2->next = head;
                p2 = p2->next;
            }
            head = head->next;   
        }
        
        p1->next = p4->next;
        head = p3->next;
        p2->next = NULL; //Set the end node points to NULL
        return head;
    }
};
发帖者 时间： 没有评论:

2015年8月27日星期四

Android Resources

SQL:

Android SQL Database tutorial:
https://www.youtube.com/watch?v=cp2rL3sAFmI

How to read database file in Android with Eclipse
http://jingyan.baidu.com/article/6b97984d9b1bed1ca3b0bf4a.html

SQL tutorial
http://www.w3school.com.cn/sql/

Shared Preference:
http://developer.android.com/guide/topics/data/data-storage.html#pref
http://developer.android.com/training/basics/data-storage/shared-preferences.html
http://www.cnblogs.com/linjiqin/archive/2011/05/26/2059133.html
ListView:

Android official tutorial for List View, the key part is filling an adaptor view with data
http://developer.android.com/guide/topics/ui/declaring-layout.html#AdapterViews

Android ListView tutorial with array adaptor:
https://www.youtube.com/watch?v=eAPFgC9URqc

Use simple Adaptor to create ListView where each element contains several lines with Hashmap:
http://blog.csdn.net/hellogv/article/details/4542668

A detailed, complete ListView app development
http://www.vogella.com/tutorials/AndroidListView/article.html

Intent:

Official guidance: just introduce explicit and implicit intent
http://developer.android.com/guide/components/intents-filters.html

Transmit object between activities：Intent.putExtras(Bundle extras)
http://blog.csdn.net/withiter/article/details/16946659
http://blog.csdn.net/android_tutor/article/details/5740845
http://zhouhongyu1989.blog.51cto.com/2931598/1407257

Note: for databasehelper, don't need to pass databasehelper object between activities. Just create a new databasehelper and use the database directly

Sensor:
motion sensor values reading:
https://www.youtube.com/watch?v=MwH0z1HIxog

Handler:
Official Definition:
http://developer.android.com/reference/android/os/Handler.html
introduction：
http://www.codeceo.com/article/android-handler-message.html
http://mobile.51cto.com/aprogram-442833.htm
Examples:
http://www.jb51.net/article/43360.htm

bundle can pass object, handler can pass bundle, so handler can pass object:
Can see the pedometer project where I use handler to pass location object.
Handler uses message to transmit bundle, bundle uses serial or parallel way to transmit object.
In my pedometer project, I created a handler to update an address textview whenever GPS location changes.
http://www.lxway.com/8184952.htm

Bundle: transmit string , int...etc directly or any object serial or parallel
pass object serially or parallel
http://www.jcodecraeer.com/a/anzhuokaifa/androidkaifa/2012/1211/694.html
Note: In pedometer project, I try to pass a Location variable serially, but failed. While I succeed when passing it parallel. Interesting. There are still some differences between these two ways!


System time:
SystemClock:
http://developer.android.com/reference/android/os/SystemClock.html
Calendar:
http://developer.android.com/reference/java/util/GregorianCalendar.html

GPS:
Official tutorial:
https://developer.android.com/training/location/display-address.html
Get Current Location with Geocoding:
In android studio, there is a debug hint for locationManager.requestLocationUpdates(), ignore that.
Don't do any modification!!
http://javapapers.com/android/android-get-address-with-street-name-city-for-location-with-geocoding/ 
Good tutorial for just Geolocation:
http://javapapers.com/android/get-current-location-in-android/
https://www.youtube.com/watch?v=7-n6p6RxSS8
http://www.androidhive.info/2015/02/android-location-api-using-google-play-services/

Common projects:
Timer:
http://examples.javacodegeeks.com/android/core/os/handler/android-timer-example/

Step counts algorithm:
http://blog.bawa.com/2013/11/create-your-own-simple-pedometer.html
http://motzcod.es/post/82515321689/part-1-my-stepcounter-android-step-sensors

Common Step when finishing app
Creating signed APK in Android Studio
Change App icon
Change Background Picture
Change APK version


Google map
how to configure project when using map
Store location in a list then draw polyline in map
http://stackoverflow.com/questions/17038258/update-polyline-according-to-the-user-moving-android-googlemaps-v2
Polyline official tutorial
https://developers.google.com/maps/documentation/android-api/shapes
How to display path of updated locations:
1. add new location to polyoptions; 2. clear google map; 3. draw new polyoptions to polyline
http://www.pubnub.com/blog/displaying-android-location-live-updating-map-google-maps/

Fragment:
TextViews don't appear when fragment is full screen ---- declare TextView after the fragment
http://stackoverflow.com/questions/26550722/put-two-textviews-above-fragment-that-contains-a-google-maps
How to display android mapfragment view in specified shape or background
TIP: to change the size of fragment, just do it in xml file
Some solution says to use fragment.getView().getRootView().setBackgroundResource(), however, don't work for me.
http://stackoverflow.com/questions/20278693/how-to-display-android-mapfragment-view-rounded-shape


Weird problems when developing:
1. R cannot be resolved
     a. change the minSDK version;
     b. update the SDK
     c. add packages into build.gradle like compile 'com.google.android.gms:play-services:7.8.0'
2. Google map doesn't display, API KEY authentication problem



发帖者 时间： 没有评论:

Lintcode: Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
Have you met this question in a real interview? 
Yes
Example
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Tags Expand 
Linked List

Solution 1:
Keep comparing current value and next node value:
If equal: link current node to the next next node and delete next node;
If not equal: jump to next node

Time: O(n)
Space: O(1)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    ListNode *deleteDuplicates(ListNode *head) {
        // write your code here
       if(head == NULL) return NULL;
       ListNode *cur = head;
       while(cur->next != NULL){
           if(cur->next->val == cur->val) {
               ListNode *temp = cur->next;
               cur->next = cur->next->next;
               delete temp;
           }
           else cur = cur->next;
       }
       return head;      
    }
};

Solution 2: two pointers
left pointer is at the start of repetition while right pinter is at the end.
Note: the right pointer may point to NULL and don't forget to delete node
Time: O(n)
Space: O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    ListNode *deleteDuplicates(ListNode *head) {
        // write your code here
       if(head == NULL) return NULL;
       ListNode *left, *right;
       left = head;
       right = left->next;
       while(right!= NULL){
           while(left->val == right->val){
               //if(right->next != NULL){
                    ListNode *temp = right;
                    right = right->next;
                    delete temp;
                    if(right == NULL){
                        left->next = right;
                        return head;
                    }
                    else if(left->val != right->val){
                        left->next = right;
                        break;
                    }
           }
           left = left->next;
           right = right->next;
       }
       return head;
    }
};


Lintcode second:
O(n) two pointers


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    ListNode *deleteDuplicates(ListNode *head) {
        // write your code here
        ListNode *start, *end;
        start = end = head;
        
        while(start){
            //end is located at the point that is equal to start
            while(end && end->next && end->next->val == start->val){
                end = end->next;
            }
            if(start != end) start->next = end->next;
            start = start->next;
            end = start;
        }
        return head;
    }
};
发帖者 时间： 没有评论:

2015年8月26日星期三

Lintcode: Merge Two Sorted Lists

Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.
Have you met this question in a real interview? 
Yes
Example
Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null.
Tags Expand 
Linked List


My solution:
Create a new linkedlist with a dummy node:
Compare elements from two lists, only add the smaller one into my linkedlist until either one is null.
Note: Take notice of linking nodes with the next pointer.
Time: O(m+n)
Space: O(m+n)
Analysis: It's not necessary to create new Node, just link the existing nodes into one linkedlist is enough.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // write your code here
        ListNode *result = new ListNode(0);
        ListNode *cur = result;
        ListNode *left, *right;
        left = l1;
        right = l2;
        while(left!=NULL && right!=NULL){
            if(left->val < right->val) {
                cur->next = new ListNode(left->val);
                cur = cur->next;
                left = left->next;
            }
            else{
                cur->next = new ListNode(right->val);
                cur = cur->next;
                right = right->next;
            }
        }
        while(left!=NULL){
            cur->next = new ListNode(left->val);
            left = left->next;
            cur = cur->next;
        }
        while(right!=NULL){
            cur->next = new ListNode(right->val);
            right = right->next;
            cur = cur->next;
        }
        return result->next;
    }
};

Common solution:
Good version to reference:
http://shibaili.blogspot.com/2013/04/day-12-21-merge-two-sorted-lists.html
Note: Dummy node is important when the head pointer is unsure.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // write your code here
        ListNode *head = new ListNode(0);
        ListNode *cur = head;
        while(true){
            if(l1 == NULL){
                cur->next = l2;
                break;
            }
            if(l2 == NULL){
                cur->next = l1;
                break;
            }
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        return head->next;
    }
};

Lintcode second:
O(n) dummy node


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // write your code here
        
        ListNode *head = new ListNode(0);
        ListNode *orghead = head;
        while(l1 && l2){
            if(l1->val < l2->val){
                head->next = l1;
                l1 = l1->next;
            }else{
                head->next = l2;
                l2 = l2->next;
            }
            head = head->next; //don't forget...
        }
        if(l1) head->next = l1;
        if(l2) head->next = l2;
        return orghead->next;
    }
};
发帖者 时间： 没有评论:

Lintcode: Remove Nth Node From End of List


Given a linked list, remove the nth node from the end of list and return its head.
Have you met this question in a real interview? 
Yes
Example
Given linked list: 1->2->3->4->5->null, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5->null.
Note
The minimum number of nodes in list is n.
Challenge
O(n) time
Tags Expand 
Two Pointers Linked List


Note: consider special case that when the nth node from the end is head;
Both ways have the same complexity:
Time: O(n)
Space: O(1)


<way 1>
Get the length of linked lists.
Then use two pointers to delete the len - n node

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: The head of linked list.
     */
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // write your code here
        int len = 0;
        ListNode * temp = head;
        while(temp){
            temp = temp -> next;
            len++;
        }
        ListNode *p;
        ListNode *q;
        p=head;
        q=p;
        int times = len - n;
        while(times > 0){
            q = p;
            p = p -> next;
            times--;
        }
        if(len == n){
            q = p->next;
            delete head;
            return q;
        }
        temp = p -> next;
        delete p;
        q->next = temp;
        return head;
    }
};


<way 2> common two pointers solution
Set two pointers n nodes far away from each other. Move the front one forward until null, then the back one is located at the node we wanna delete.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: The head of linked list.
     */
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // write your code here
        ListNode *slow;
        ListNode *fast;
        slow = head;
        fast = head;
        for(int i = 0; i < n; i++){
            fast = fast -> next;   
        }
        ListNode *prev = slow;
        //special case, when the element to be deleted is head
        if(!fast){
            slow = slow -> next;
            delete head;
            return slow;
        }
        while(fast){
            prev = slow;
            slow = slow -> next;
            fast = fast -> next;
        }
        ListNode *temp = slow -> next;
        delete slow;
        prev -> next = temp;
        return head;
    }
};

Lintcode second:
two pointers, O(n), remember when delete head,return new head.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: The head of linked list.
     */
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // write your code here
        ListNode *p1, *p2;
        p1 = p2 = head;
        for(int i = 0; i < n; i++){
            p2 = p2->next;
        }
        ListNode *prev;
        while(p2){
            p2 = p2->next;
            prev = p1;
            p1 = p1->next;
        }
        if(p1 == head) {
            ListNode *res = p1->next;
            delete head;
            return res;
        }
        prev->next = p1->next;
        delete p1;
        return head;
    }
};
发帖者 时间： 没有评论:

2015年8月25日星期二

Lintcode: next permutation

Given a list of integers, which denote a permutation.
Find the next permutation in ascending order.
Have you met this question in a real interview? 
Yes
Example
For [1,3,2,3], the next permutation is [1,3,3,2]
For [4,3,2,1], the next permutation is [1,2,3,4]
Note
The list may contains duplicate integers.
Tags Expand 
LintCode Copyright Permutation


Reference:
http://blog.csdn.net/m6830098/article/details/17291259
http://algorithm.yuanbin.me/zh-cn/exhaustive_search/next_permutation.html

Pure mathematical problem, key is to understand Lexicographical algorithm
Time: O(n) + O(n) + O(n) = O(n)
Space: O(1)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An array of integers that's next permuation
     */
    vector<int> nextPermutation(vector<int> &nums) {
        // write your code here
        int left;
        if(nums.size()<2) return nums;
        for(int i = nums.size() - 2; i >= 0; i--){
            if(nums[i] < nums[i + 1]) {
                left = i;
                break;
            }
            if(i == 0){
                reverse(nums, 0, nums.size() - 1);
                return nums;
            }
        }
        int right = 0;
        for(int i = nums.size() - 1; i > left; i--){
            if(nums[i] > nums[left]) {
                right = i;
                break;
            }
        }
        swap(nums, left, right);
        reverse(nums, left + 1, nums.size() - 1);
        return nums;
    }
private:
    void swap(vector<int>& nums, int left, int right){
        if(left == right) return;
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right]= temp;
    }
    void reverse(vector<int>& nums, int start, int end){
        for(int i = start, j = end; i < j; i++, j--){
            swap(nums, i, j);
        }
    }
};


Lintcode second:
O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An array of integers that's next permuation
     */
    vector<int> nextPermutation(vector<int> &nums) {
        // write your code here
        //find the first nums[k] < nums[k + 1]
        //int k = nums.size() - 1; //if cannot find , k = -1
        if(nums.size() <= 1) return nums;
        int k = nums.size() - 2;
        for(; k >= 0; k--){
            if(nums[k] < nums[k + 1]) break;
        }
        //find nums[l] from right to left that is larger than k, 
        int j = nums.size() - 1;
        for(; k > -1 && j > k; j--){
            if(nums[j] > nums[k]) {
                swap(nums, k, j);
                break;
            }
        }
        //reorder from k + 1 to nums.end
        reorder(k + 1, nums);
        return nums;
    }
    void swap(vector<int> &nums, int k, int j){
        int temp = nums[k];
        nums[k] = nums[j];
        nums[j] = temp;
    }
    void reorder(int start, vector<int> &nums){
        int end = nums.size() - 1;
        while(start < end){
            swap(nums, start, end);
            start++;
            end--;
        }
        
    }
};
全排列
http://blog.csdn.net/m6830098/article/details/17320819
发帖者 时间： 没有评论:
订阅： 博文 (Atom)