寫CODE，會想到騎車也在想.....

2015年8月27日星期四

LEET code-- Linked List Cycle II

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

這題很奸詐阿
沒寫過當場要想出來我覺得太難了
硬幹不好
要先利用再 linked list cycle I的觀念找出是哪一點(meeting)有發現循環
利用meeting指標跟temp指標來找出head在哪
因為兩個會同時到達cycle head
解釋如下

head: list head
E: the head of the cycle
X: the meeting point of the fast and slow pointer in the Linked list cycle I
H: distance from head to cycle entry E (head到E的長度) D: distance from E to X (E到X的長度) L: cycle length (cycle的長度) _____ / \ head_____H______E \ \ / X_____/ 因為fast and slow會同時到達X點
對slow而言他走了 H+D這麼長才到X點
對fast而言他走了 2(H+D)的長度才跟slow碰面
但是!!!
fast 可能已經走了好幾圈了，可能已經繞了n圈
所以他而外多走了n*L這些距離
所以會變成 H+D+n*L=2(H+D)
H = (n-1)*L + (L-D)
你會發現 H的長度會跟L-D的距離一樣
所以我們可以利用X的指標，讓他跟另外一個從head開始走的指標一起比較
兩個同時都往下走，因為走的距離一樣，當發現兩個指到同一個東西的時候就會剛好是E

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode * hasCycle(struct ListNode *head) {
    if(head==NULL)return NULL;
    struct ListNode * fast=head;
    struct ListNode * slow=head;
    
    while(fast && fast->next && fast->next->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast == slow)return slow;
    }
    if(fast->next == NULL || fast->next->next==NULL)return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * meeting=NULL;
    struct ListNode * temp=head;
    meeting = hasCycle(head);
    if(meeting == NULL)return NULL;
    
    while(temp && temp->next){
        if(temp == meeting)return temp;
        meeting=meeting->next;
        temp=temp->next;
    }
}

2015年8月24日星期一

LEET code--single number ||

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

難

下面是解釋
------------

The key to solve this problem is the count of 1s of each bit of all numbers.
Take one bit number for example: nums = [1, 1, 1, 0, 0, 0, ..., x] . All numbers are 0 or 1.
We know that every number appears three times except for just one number. So, if the count of 1s in nums is 0, 3, 6, ..., 3 * n, then the single number is 0. And if the count of 1s in nums is 1, 4, 7, ..., 3*n+1, then the single number is 1.
So, for an array " nums " that contains only 0 or 1, the code to find the single number are:

count = 0
for num in nums:
    count = (count + num) % 3
return count

To make "count" less than 3, mod "count" with 3 in every loop.
Below is the procedure for finding the single number in [1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]:

Table 1:
++=======++===+===+===+===+===+===+===+===+===+===+===+===+===+====++
|| num   ||   | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0  ||
++-------++---+---+---+---+---+---+---+---+---+---+---+---+---+----++
|| count || 0 | 1 | 1 | 2 | 0 | 0 | 1 | 1 | 2 | 2 | 0 | 0 | 1 | 1* ||
++=======++===+===+===+===+===+===+===+===+===+===+===+===+===+====++

So the single number is 1.
We can write the calculate table for expression "count' = (count + num) % 3":

Table 2:
++=======+=====+========++
|| count | num | count' ||
++-------+-----+--------++
||   0   |  0  |   0    ||
++-------+-----+--------++
||   1   |  0  |   1    ||
++-------+-----+--------++
||   2   |  0  |   2    ||
++-------+-----+--------++
||   0   |  1  |   1    ||
++-------+-----+--------++
||   1   |  1  |   2    ||
++-------+-----+--------++
||   2   |  1  |   0    ||
++-------+-----+--------++

To extend this algorithm to 32bits number. We need to rewrite these code to bit operation expressions.
And the key is rewriting the expression " count' = (count + num) % 3 " to bit operation expressions.
Write binary numbers of " count " and " count' " in "Table 2". And split their bits into two column:

Table 3:
++=======+============+=====+============+========++
||       |    count   | num |   count'   |        ||
|| count |    (bin)   |     |   (bin)    | count' ||
|| (dec) ++=====+=====+=====+=====+=====++ (dec)  ||
||       || b1  | b0  | num | b1' | b0' ||        ||
++-------++-----+-----+-----+-----+-----++--------++
||   0   ||  0  |  0  |  0  |  0  |  0  ||   0    ||
++-------++-----+-----+-----+-----+-----++--------++
||   1   ||  0  |  1  |  0  |  0  |  1  ||   1    ||
++-------++-----+-----+-----+-----+-----++--------++
||   2   ||  1  |  0  |  0  |  1  |  0  ||   2    ||
++-------++-----+-----+-----+-----+-----++--------++
||   0   ||  0  |  0  |  1  |  0  |  1  ||   1    ||
++-------++-----+-----+-----+-----+-----++--------++
||   1   ||  0  |  1  |  1  |  1  |  0  ||   2    ||
++-------++-----+-----+-----+-----+-----++--------++
||   2   ||  1  |  0  |  1  |  0  |  0  ||   0    ||
++=======++===========+=====+===========++========++

Here comes the hardest part of this solution.
"Table 3" is a truth table, we need to use it to find the formulas to calculate " b0' " and " b1' ":

b0' = f(b1, b0, num)
b1' = g(b1, b0, num)

With observations, guesses, experiments and even some luck. Finally I got two simple and elegant formulas:

b0' = (b0 ^ num) & (~b1)
b1' = (b1 ^ num) & (~b0')

or

int nb0 = (~b1 & b0 & ~num) | (~b1 & ~b0 & num);
int nb1 = (b1 & ~b0 & ~num) | (~b1 & b0 & num) ;

The AC code:

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def singleNumber(self, nums):
        b1, b0 = 0, 0
        for num in nums:
            b0 = (b0 ^ num) & (~b1)
            b1 = (b1 ^ num) & (~b0)
        return b0

-----------

2015年8月17日星期一

LEET code --linked list cycle

Given a linked list, determine if it has a cycle in it.

我這方法不好因為順序被我打亂了

好方法是分兩個pointer
一個走比較慢一個走比較快
如果快的會走到NULL 那就沒回圈
如果快地碰到曼的就代表有迴圈

為了增加處理速度可以增加走的速度

bool hasCycle(struct ListNode *head) {
    if(head==NULL)return false;
    struct ListNode* current=head;
    struct ListNode* previous=NULL;
    while(current!=NULL && current->next!=head){
        struct ListNode* next = current->next;
        current->next=previous;
        previous= current;
        current=next;
    }
    return (current==NULL) ? false:true;
}

---------------------------------------------
改版之後
用快慢pointer來指

bool hasCycle(struct ListNode *head) {
    if(head==NULL)return false;
    struct ListNode * fast=head;
    struct ListNode * slow=head;
    
    while(fast && fast->next && fast->next->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast == slow)return true;
    }
    if(fast->next == NULL || fast->next->next==NULL)return false;
    
}

LEET code--Add Digits

Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

int addDigits(int num) {
    while(num>=10){
        int temp=0;
        while(num!=0){
            temp+=num%10;
            num/=10;
        }
        num=temp;
    }
    return num;
}

2015年8月15日星期六

S型脊椎側彎矯正紀錄

從小從C型到高中之後變成S型但是很剛好的都不會痛

S型是上20度下20度
所以算是輕微的，之前看西醫，醫生都說反正2X歲了，都定型了，不要惡化就好
就再也沒理他

直到今年7月因為手受傷去中醫復健，那邊醫生突然冒出來一句"你是不是脊椎側彎"
我回"反正都2X了也沒救了"
醫生"那是不會治的人，少部分會，我推薦你去看XXX，但是要自費，因為他健保難掛"

就這句話，衝了拉

------------------------------------------
從新竹到要那邊1個小時

我第一次掛自費，號碼就27號了
4點到那邊，只看到25號...

等到快5點，從終於有床位

醫生會問你要看什麼的，脊椎側彎就要你去照全身X光

照完之後，醫生還很納悶怎麼知道找他來做矯正，我就把故事跟他講
醫生覺得大概是學弟吧

醫生看X光發現我的S型轉的角度很奇怪，是麻煩的，但是事可以治好的!!

OS: 人生有救了?

醫生說他治很多個S型了，我不是第一個

----------------------------------------
第一次治療，因為有X光，所以護士會幫你用健保的，而不是自費(不然$$$$$$$$$$)

所以第一次才220
----------------------------------------
第二次自療自費要640 (哭哭這時候才知道健保的好
治療內容主要就是他會要你做一堆奇怪的動作，每個星期都要去，還好我還是學生

---------------------------------------
醫生一直說我是假的脊椎側彎完全不知道位什麼......

2015年8月12日星期三

LEET code --Search for a Range

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

直觀就是直接找一次就好
一開始寫玩都不會對
搞半天

*returnSize 要給2

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int *ans = (int *)malloc(sizeof(int) * *returnSize);
    ans[0]=-1;
    ans[1]=-1;
    if(numsSize == 0)return ans;
    if(target < nums[0] || target > nums[numsSize-1])return ans;
    for(int i=0;i<numsSize;i++){
        if(target == nums[i]){
            if(ans[0]==-1){
                ans[0]=i;
                ans[1]=i;
            }
            else ans[1]=i;
        }
        if(target<nums[i])break;
    }
    return ans;
}

如果要更快可以改用binary search
因為都排序好了
會兩倍快

LEET code --Merge Two Sorted Lists

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.

就兩個排序過的list 重新再組合
一開始有想過是不是可以用recursive
但是懶得去想

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1==NULL)return l2;
    if(l2==NULL)return l1;
    struct ListNode* l1temp = l1;
    struct ListNode* l2temp = l2;
    
    while(l1temp != NULL && l2temp != NULL){
        if( l1temp->val >=l2temp->val){
            while(l2temp->next!=NULL){
                if( l2temp->next->val > l1temp->val){
                    break;
                }else{
                    l2temp=l2temp->next;
                }
            }
            struct ListNode* temp2=l2temp->next;
            l2temp->next = l1temp;
            l2temp = temp2;
      
        }else{
            while(l1temp->next!=NULL){
                if( l1temp->next->val > l2temp->val){
                    break;
                }else{
                    l1temp=l1temp->next;
                }
            }
            struct ListNode* temp=l1temp->next;
            l1temp->next = l2temp;
            l1temp=temp;
        }
    }
    return (l1->val >= l2->val)? l2:l1;
    
}

------------------------
recursive version
每次都跟自己比較
比較小的就去recursive 找下一個可以比對方大的數字
這樣每次recursive 都會return最小值

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;
    if (l1->val <= l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

訂閱：文章 (Atom)

2015年8月27日 星期四

Linked List Cycle II

2015年8月24日 星期一

2015年8月17日 星期一