leetcode-27 Remove Element

題意: 給定一個array, 將其中和給定值相同的元素剔除

解題思路: 這題和上題的解題思路相同,都是利用兩個變數掃描array,遇到和給定值不同的就取代,即所求

c++ code:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len=nums.size();
        int pos=0;
        for(int i=0;i<len;i++)
        {
            if(nums[i]!=val)
            {
                nums[pos]=nums[i];
                pos++;
            }
        }
        return pos;   
    }
};

leetcode-26 Remove Duplicates from Sorted Array

題意: 給定一排序好的array, 將其重複元素剔除,要求空間複雜度為O(1)

解題思路: 這題題目出得很容易讓人誤會啊= =,返回的是int,其實判定的是array,但因為array是用reference 傳進來的,所以直接修改即可, 方法就是利用兩個變數,一個沿array走,如果遇到和前面不重複的,則把另一個變數加一,並做取代,因為第一個變數走的至少會和第二個變數一樣快,所以此算法成立

C++ code:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len=nums.size();
        if(len==0)
            return 0;
        int count=1;
        
        for(int i=1;i<len;i++)
        {
            if(nums[i]!=nums[i-1])
            {
                nums[count]=nums[i];
                count++;
            }
        }
        return count;
    }
};

git 指令整理

git 是一個非常流行的版本控制系統(version control system),何謂版本控制系統呢?
就是我們在程式開發時,常常會遇到一種情形,就是不知道更動這段程式碼會發生甚麼bug,有時加了一些新功能後,才發現bug跑出來,於是想回到之前的版本,這時版本控制系統就派上用場了!
以上是單人開發時的情況,多人開發時情況更複雜,常常會有檔案蓋來蓋去,不知道對方做了甚麼,這時版本控制系統就更重要了啊!

git 內部有三個結構

Working tree  ----> staged area ---> repository(內有commit)
                     git add                 git commit
為何要有staged area呢,這是因為如果沒有staged area的話,你對working tree內做的所有改變就會在你commit後,全部跑到repository內,為了更好的做到版本控制,所以才會有staged area

git 還有一個重要概念: branch
在中文裡,branch是分支的意思,在程式設計時,如果我們想實驗程式碼,又不想動到目前的程式碼,可以新增一個新的branch,指令如下: git branch  branch名稱


以下是git 的常見指令整理:

1. git clone :複製檔案
可從網路連結抓取檔案

2. git init: 在目前的位置建立一個新的repository

3. git log : 把目前repository 的所有commit 歷史都叫出來,但有時會太長,可按q跳出

4. git status: 顯示work tree 的歷史

5. git branch: 產生新的branch(但並未轉至這個branch,若須轉到這個branch,要用git checkout)

6. git checkout : 將目前檔案回到某個commit狀態 or 轉換到某個branch

7. git diff :有三種用法

(1) git diff  commit ID1 commit ID2 :比較兩個commit的不同
(2) git diff : 比較  working tree 和 staged area
(3) git diff --stage: 比較 staged area 和most recently commit

8. git merge: 合併branch和master =>可能會產生merge conflict=>需手動處理

merge conflict: 大家動到同一個檔案 電腦不知道誰的才是對的

reference:
1. udacity
2. git help
3. https://git-scm.com/docs/git-merge

leetcode-25 Reverse Nodes in k-Group

題意: 其實是上一題(k=2)的延伸版,就是給定一個linked list, 每k個元素要反轉,若不足k個則不用,空間複雜度須為O(1)

解題思路:想法簡單,實現起來不容易,訣竅就是每數到k個元素時反轉,反轉利用三個指標,分別記錄連續三個元素,之後依此類推,須注意邊界條件處理,以免發生null pointer exception

C++ code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        
        ListNode* ori=new ListNode(0);
        int count=0;
        if(head==NULL||k==1)
            return head;
        ListNode* e;
        ListNode* o=ori;
        while(head!=NULL)
        {
           
            count++;
            if(count==1)
            {
                e=head;
                o->next=head;
            }
            if(count==k)
            {
                
                o->next=head;
                o=e;
                head=head->next;
                ListNode* temp0=e;
                ListNode* temp=e->next;
                ListNode* temp1=temp->next;
                while(count!=1)
                {
                    temp->next=temp0;
                    temp0=temp;
                    if(count!=1)//avoid access null
                        temp=temp1;
                    if(count!=2)//avoid access null
                        temp1=temp1->next;
                    count--;
                }
                o->next=NULL;
                count--;
                continue;
            }
            head=head->next;
        }
        return ori->next;
    }
};

leetcode-24 Swap Nodes in Pairs

題意: 將linked list 中相鄰的元素做反轉(若最後一個不成對則不用反轉)

解題思路: 就照字面意思操作,可創造出原點方便操作,將原點接到第二個元素,第二個接第一個,以此類推,須注意反轉後最後一個元素一定要指向NULL,否則會TLE(太久沒寫,我都忘了QQ)

c++ code 如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* ori=new ListNode(0);
        if(head==NULL)
            return head;
        else
            if(head->next==NULL)
                return head;
            else
                ori->next=head->next;
        while(head->next!=NULL)
        {
            
            ListNode* temp=(head->next)->next;
            ListNode* temp1=head;
            (head->next)->next=head;
            head->next=NULL;
            if(temp==NULL)
                break;
            else
            {
                if(temp->next==NULL)
                    temp1->next=temp;
                else
                    temp1->next=temp->next;
                head=temp;
            }
        }
        return ori->next;
    }
};

醫學實驗設計

一般來說,在醫學實驗設計上,常見以下幾種形式:

1. randomized control trial (RCT) : 透過隨機分派受試組別(實驗組以及對照組), 給予不同介入,實驗組給予想要證明效果的介入,對照組給予安慰劑或一般治療,過一段時間後來觀察結果,在可信度上,被認為最強

2. cohort study: 將族群依某種原因做分類,而後觀察和疾病的關係
ex. 將一群人依抽菸不抽菸做分組,一段時間後,觀察兩組得肺癌比例是否不同

3. case-control study: 將族群依疾病做分組,觀察各組內是否某因子有不同的比例
ex: 將病人依是否得肺癌去做分類,再看各分組內抽菸的比例是否不同

cohort 和 control study都有相同的缺點,就是無法去除confounding factor的影響,何謂confounding factor呢, 就是有一因素A,會造成B和C, 但因為實驗未作隨機分組,導致我們以為B會導致C,其實真正的原因為A, 這樣的話, A就是confounding factor.

舉例來說, 冬天會穿厚衣服,冬天也容易一氧化炭中毒,但若我們將一氧化炭中毒和穿厚衣服做研究,可能會以為有因果關係,但實際上並沒有,如此冬天即為confounding factor

以上是小小的整理,有問題歡迎留言討論歐!

leetcode-23 Merge k Sorted Lists

題意:合併k個已排序的linkedlist

解題思路:這題我是把全部的元素丟進c++ stl 的priority queue裡,能通過測試,但時間和空間複雜度太大,但我還是先貼我過的code,待我之後再刷到這時,再更新更快做法

效率更高做法: http://bangbingsyb.blogspot.tw/2014/11/leetcode-merge-k-sorted-lists.html

C++ code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    
public:
     struct cmp 
     { 
        bool operator()(ListNode* x,ListNode*  y) 
        { 
            return x->val > y->val; 
        } 
     }; 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        int len=lists.size();
        
        for(int i=0;i<len;i++)
        {
            ListNode* par=lists[i]; 
            while(par!=NULL)
            {
                pq.push(par);
                par=par->next;
            }
        }
        ListNode* ori=new ListNode(0);
        ListNode* cur=ori;
        while(!pq.empty())
        {
            cur->next=pq.top();
            pq.pop();
            cur=cur->next;
            
        }
        cur->next=NULL;
        return ori->next;
    }
};