寫CODE，會想到騎車也在想.....: 8月 2015

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;
    }
}

2015年8月10日星期一

Blogger 插入CODE

網路上還要抓套件什麼

太麻煩了

用人家寫好的比較快拉!!!
http://hilite.me/

直接幫你轉換成HTML

要用的時候直接貼到HTML就好

LEET code--Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

current 只有再future不一樣的時候才會前進
future會每次循環都向前

這樣是避免連續出現同樣數字，保留current的讓future去找誰重複
如果沒有重複就current向前

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(head==NULL)return head;
    struct ListNode *current=head;
    struct ListNode *future=head->next;
    while(current!=NULL && future!=NULL){
        if(current->val == future->val){
            current->next=future->next;
            free(future);
            future=(current !=NULL) ? current->next: NULL;
        }
        else{
            current=current->next;
            future=(current !=NULL) ? current->next: NULL;
        }
    }
    return head;
}

LEET code--Search Insert Position

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

寫到現在最簡單的一題，這居然不是正確率最高的...
第一次交出去，一次就對XD

反正如果一樣或是比目標大就直接回傳該位置
不然就是最後回傳最後的位置

-----------------

int searchInsert(int* nums, int numsSize, int target) {
    int i;
    for( i=0 ; i &lt; numsSize ; i++ )
    {
        if(target == nums[i] || nums[i]&gt;target)return i;
    }
    return numsSize;
}

LEET code --Excel Sheet Column Number

Excel Sheet Column Number

Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28

原本還在想規律什麼  還跑去EXCEL 看之後到底怎麼排出來

後來突然想到  靠  這不就26進位而已嗎

繞一大圈  直接當作26進位來做就很快了

我算了一下 26進位在int的型態下 應該不會超過7~8位數

所以預先算好這些值，之後直接查表就好了

PS: 寫玩才想起來 明明有內建的可以call pow(26, (s.length() - i))

白癡....

而且 好像也不用需要那個涵式，直接每次*26 就好啦....

---------------------------------------

int titleToNumber(char* s) {
    int num[8];
    num[0]=1;
    for(int i=1;i<8-1;i++){
        num[i]=num[i-1]*26;
    }
    int size=strlen(s);
    int ans=0;
    if(size ==1)return s[0]-'A'+1;
    for(int i=0;i<size;i++){
        ans+=(s[i]-'A'+1)*num[size-i-1];
    }
    return ans;
}

------------------------------------
int titleToNumber(char* s) {
    int len = strlen(s);
    int num = 0;
    int GAP = 'A' - 1;
    for(int i = 0; i < len; ++i)
    {
        num = num * 26 + s[i] - GAP;
    }
    return num;
}

2015年8月9日星期日

LEET code--Invert Binary Tree

Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  7     2
 / \   / \
9   6 3   1

超級簡單   指標全部互相交換就好

沒有到會有神人栽在這題

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    if(root == NULL) return;
    struct TreeNode *temp=root->left;
    root->left=root->right;
    root->right=temp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

2015年8月7日星期五

LEET code--Same Tree

Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

檢查兩個樹有沒有完全一致(結構上跟val)

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if( p==NULL && q == NULL)return true;
if( p==NULL && q!= NULL )return false;
if( p!=NULL && q==NULL)return false;
if(p->val != q->val)return false;

bool le,ri;
le=isSameTree(p->left,q->left);
ri=isSameTree(p->right, q->right);

return (le==false || ri==false)? false:true;

}

更好的寫法:

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p == NULL && q == NULL) 
    return true;
if(p != NULL && q == NULL) 
    return false;
if(p == NULL && q != NULL) 
    return false;
if(p->val != q->val)
    return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

直接用&& 改回傳只有true的方式  比較簡潔

LEET code--Delete Node in a Linked List

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

一開始只給你要刪除的node的pointer
所以要把該刪除的node內部值改成下一個的
像這樣

    p = node->next;
    if (!p) return;
    node->val = p->val;
    node->next = p->next;
    free(p);

P=上面範例的4

所以把3的內容改成4

再把4刪除

這樣3就不見了

但是更好的寫法是


如果不在乎刪除空間:

*node = *(node->next);

//直接把pointer的值改成下一個
*node是取pointer內部儲存的記憶體空間
直接改成*(node->next) 就可以把3變成4 (直接改記憶體位置)
如果要刪除空間:

struct ListNode* tofree = node->next;
*node = *(node->next);
free(tofree);

LEET code--Maximum Depth of Binary Tree

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

用recursive走一圈就知道
走到最後發現是null 就回傳0

int maxDepth(struct TreeNode* root) {
if(root==NULL)return 0;
int le=0,ri=0;
le=maxDepth(root->left);
ri=maxDepth(root->right);

return (le > ri)? le+1:ri+1;

}

2015年8月6日星期四

LEET code--Single Number

Single Number

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?

最快想試用兩個for 暴力算

但是要線性又不要求多餘空間
就很難阿

看到有人用XOR 真是天才
因為兩個依樣數字就會剛好抵銷

numsSize>1 是因為用了nums[0] 要把0給跳過
------------
int singleNumber(int* nums, int numsSize) {
while(numsSize>1){
nums[0]^=nums[--numsSize];
}
return nums[0];
}

訂閱：文章 (Atom)

2015年8月27日 星期四