leetcode-30 Substring with Concatenation of All Words

題意: 給定一個string s, 另外給定許多同樣長度的words, 求出所有s中的位置,其後的連續序列會包含所有words(中間不能有其他字符)

解題思路: 這題很難, 我的解法效率也不算太高,但還是先貼,我的解法是這樣,先用map求出同樣的word出現幾次,再利用KMP,求出所有word的出現點,之後一個位置一個位置的掃描,即可得解

class Solution {
public:
    int index[100000];
    int pre[100000];
    int check[10000];
    vector<int>ans;
    vector<int> findSubstring(string s, vector<string>& words) {
        memset(check,0,sizeof(check));
        int len=s.size();
        int num=words.size();
        int len1=words[0].size();
        map <string,int> re;
        for(int i=0;i<num;i++)
        {
           
            if(re[words[i]]==0)
                re[words[i]]=i+1;
            check[re[words[i]]]++;
            strStr(s,words[i],re[words[i]]);
            //cout<<re[words[i]]<<" "<<check[re[words[i]]]<<endl;
        }
        len=len-num*len1+1;
        
        for(int i=0;i<len;i++)
        {
            //cout<<index[i]<<endl;
            int arr[10000];
            int count=0;
            memset(arr,0,sizeof(arr));
            for(int j=0;j<num;j++)
            {
                //cout<<index[i+j*len1]<<endl; 
                if((arr[index[i+j*len1]]<check[index[i+j*len1]])&&index[i+j*len1])
                    count++;
                 arr[index[i+j*len1]]++;
            }
            if(count==num)
                ans.push_back(i);
        }
        return ans;
    }
   
    void strStr(string haystack, string needle,int k) {
          int target=haystack.size();
          int target1=needle.size();
          if(target1==0)
              return; 
          int q=-1;
          pre[0]=-1;
          for(int i=1;i<target1;i++)
          {
              while(needle[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(needle[i]==needle[q+1])
                  q++;
              pre[i]=q;
          }
          q=-1;
          for(int i=0;i<target;i++)
          {
              while(haystack[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(haystack[i]==needle[q+1])
              {
                  q++;
                  if(q==target1-1)
                       index[i-target1+1]=k;
              }
          }
    }
};

leetcode-29 Divide Two Integers

題意: 實現除法,但不能使用乘法,除法或mod

解題思路: 這題應該是為了模擬某些平台,不能使用上述指令的情況,所以利用bit manipulation來實現二進位除法, 演算法如下=>
x/y, 把y做left shift,到超過x為止,將左移的量減一,而後加到答案裡,再把x減去y左移減一的量,以此類推

ps. 須注意 加減號比左右移符號更優先,故該使用括號的時候就要用XD
可參考: MSDN

C++  code:

class Solution {
public:
    int divide(int dividend, int divisor) {
        long long ans=0;
        long long ok=1;
        long long m=(long long)dividend;
        long long n=(long long)divisor;
        if(m<0)
        {
            ok=~ok+1;
            m=~m+1;
        }
        if(n<0)
        {
            ok=~ok+1;
            n=~n+1;
        }
        
        while(m>=n)
        {
            long long t=0;
            long long c=n;
            
            while(m>=c)
            {
                t++;
                c=c<<1;
            }
            t--;
            ans=ans+((long long)1<<t);
            m=m-(n<<t);
        }
        
        if(ok==-1)
            ans=~ans+1;
        if(ans>INT_MAX||ans<INT_MIN)
            return INT_MAX;
        else
            return ans;
    }
};

leetcode-28 Implement strStr()

題意: 做字符串比對,輸出第一個符合的位置

解法: 這題就是問KMP實現了,原理可看筆者先前文章

C++ code:

class Solution {
public:
    int index[100000];
    int pre[100000];
    int strStr(string haystack, string needle) {
          int target=haystack.size();
          int target1=needle.size();
          if(target1==0)
              return 0; 
          int q=-1;
          pre[0]=-1;
          for(int i=1;i<target1;i++)
          {
              while(needle[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(needle[i]==needle[q+1])
                  q++;
              pre[i]=q;
          }
          q=-1;
          for(int i=0;i<target;i++)
          {
              while(haystack[i]!=needle[q+1]&&q>-1)
                  q=pre[q];
              if(haystack[i]==needle[q+1])
              {
                  q++;
                  if(q==target1-1)
                      return i-target1+1;
              }
          }
          return -1;  
    }
};

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

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