quick sort

quick sort 中文譯為快速排序演算法,在comparison sort 中算是最快的演算法,其平均複雜度可以到$O(nlog\ n)$,其原理為利用分治法(divide and conquer), 假設現有一數列等待我們來排序,我們可在數列中選擇任一數字做為支點(pivot),將比支點小的數分成一堆,比支點大的數分成一堆,再遞迴處理,假設每次都可以把數列平分,則其複雜度算式可寫為 $T(n)=2*T(\frac{n}{2})+O(n)$,其中$O(n)$為分類所需的時間,如此一來,複雜度為$O(nlog\ n)$,然而事情總是不這麼美好QQ,如果不小心pivot沒有選好,則可能每次分群,都有一群沒有任何數,如此一來,$T(n)=T(n-1)+O(n)$,其複雜度退化到$O(n^2)$,實在太慢了@@, 於是聰明的電腦科學家為了避免這個問題,於是引進了隨機選支點的方法,如此一來,平均複雜度可以達到$O(nlog\ n)$, oh YA!!!




至於如何用pivot來分群呢,就是一個小技巧了XD,其原理為將隨機選中的pivot和最左邊或最右邊的數互換,接著利用兩個變數作為指標,其中一個變數表示其左邊的數都小於pivot,另一個變數表示目前確認到哪一個數,若確認到的數比pivot小,則將那個數和第一個變數指到的數互換,如此一直移動第二個變數,最後再將pivot和第一個指標指到的數互換,大功告成!!!
參考資料:
1. MIT ocw
2. coursera
3. introduction to algorithms

KMP 演算法

花了好幾個小時,總算對萬惡的(?)KMP演算法有點眉目,就讓在下來分享一下吧!
KMP演算法全名為Knuth-Morris-Pratt algorithm,其中knuth為鼎鼎大名的Donald Knuth !


KMP演算法主要分為兩部分,第一部份為對字串預處理,第二部分為實際比對,先來分享預處理的部分


預處理的原理如下,將所欲處理的字串,對其從頭開始的所有字串求出其最大前綴與後綴相等的長度(在此我稱呼他為字串函數),舉例來說,字串  AAABBA,其值會是012001,讀者可以自己試看看,然而這個演算法的精隨就在如何快速地做預處理,原理如下:利用邊界的概念,逐次推進,何謂邊界的概念呢,邊界即為目前處理到的前綴的最後一個位置,若邊界的下一個位置和後綴的下一個位置相等,則後綴下一個位置的字串函數的值即為後綴最後一位的字串函數值加一;若不相等呢?則利用目前以處理的字串,利用字串函數往前推進,因為所選取的前綴和後綴相同,差別只是在下一位的字符,所以只需要再做比對一個字符,直到出現邊界的下一個位置和前綴的下一個位置相等為止 =>這樣的複雜度和字串長度成正比

圖解:

字串可看成
SDS =>其中S代表相同字串,若皆不相同則為空字串,D表任意字串

每輪多比對新的字符
SDSN=>其中N為新字符,故我們須比較S+N是否會和S+D的第一個字符相同,若相同,則把前後綴都加一,若不同.由於S和S相同,故只需要對S取前後綴相同,在做同樣判定即可,以此類推



了解了預處理的概念後,實作KMP的方法有兩個版本
1.
我們可以先將所欲求的pattern(簡寫為P),和所與比對的字串(簡寫為T),將其相加,並在中間插入任意符號(不會出現在P和T中的符號),然後對新得到的字串做預處理,接著進行第二部分,實際比對,可發現若字串函數的值和pattern長度相等,則表示match,如此即所求
其複雜度為$O(P+T)$

2.
先對P做預處理,再把T和P做比對,其複雜度也為$O(P+T)$

c++ 程式碼如下

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)
                      cout<<i-target1+1<<endl;
              }
          }
          return 0;  
    }
};

PS. 小魯的參考資料:
1. coursera
2. Introduction to algorithms
           

大唐雙龍傳讀後感

香港一代武俠小說黃易最近過世了,剛好小弟最近讀完了大唐雙龍傳,就讓我來分享一下讀書心得吧XD


留白以防雷




















正文開始:
故事是設定在隋末唐出的時候,劇中的場景非常考據,出現許多歷史人物,且內部對戰役以及人物設定大部分都符合史實,故算是一部歷史小說吧,不過個人覺得作者為了配合歷史,中間許多主角群們的表現不太自然,譬如最為人詬病的是寇仲如此有野心的人,竟然會輕易地將天下讓給李世民(謎之音:那你之前的努力是都在搞笑嗎),以及徐子陵好像都和女角色互動不多,卻讓眾多女角竟然都愛上他,也許這也是另一種主角威能?!不過上述的皆瑕不掩瑜,這部小說的角色和場景非常多,結構宏大,但基本上每個角色黃易都有處理到,去向也都交代得還算清楚,值得一題的是,作者許多慣用語都會一直出現,比如說虎體劇震,虎軀亦微震,感覺震了好多次= =,不過總體來說,是一部值得一讀的小說,體現出黃易處理大型結構的功力,真的讚!!!

日劇-砂之塔心得

好像還沒有寫過日劇心得文呢,來試著寫寫看好了,想寫的是日劇砂之塔,日本官方網站如下:
http://www.tbs.co.jp/sunanotou/


之前提到學習日文可以試看看吧看到的所有日文名詞都唸出來,這裡就是練習的好機會,其中砂＝すな、塔＝とう,這樣又學了兩個日文單字了XD


留白以求防雷~












正文開始:
這篇日劇主要是探討親子互動,家庭的意義的日劇,雖說劇情到後面好像有點偏掉?出現了一堆很難解釋的劇情,不過整體走向能然令人思考何謂家庭,天下愛自己孩子的媽媽非常多,但愛自己的孩子並不一定代表就是好媽媽,劇中主角家庭的哥哥長期受到學校霸凌,但後母完全沒發現,反倒是生母發現的,但生母以前為了保護還是嬰兒的哥哥,過度防衛的殺死了跟蹤狂,被判刑,因為害怕旁人把哥哥視為殺人犯的小孩,於是選擇和主角家庭的爸爸離婚,中間經過無數的轉折,生母在出獄後不甘心,想搶回哥哥,但最後還是放棄,因為哥哥選擇了後母,社會上旁人的眼光很可怕啊,歧視的眼神能摧毀小孩! 這部片其實最大亮點我想還是松島菜菜子的演技吧,每個眼神,每個動作,優雅的氣息,都完全表現出符合劇中人物的氣息,果然是日劇女王!整體來說,我推薦這部日劇,算是近期的好片吧

從日本看台灣醫療

先貼上NHK新聞連結
http://www3.nhk.or.jp/news/html/20170407/k10010939781000.html

新聞大意如下:日本二十幾歲的醫師一周平均工時(男:57.3, 女:53.5),而六十幾歲醫師平均工時差不多一周四十個小時,日本怕醫師過勞,正在檢討勞動制度

小弟從FB上看到這則新聞,心理顫動了一下,台灣醫學界多年來不斷的努力,才成功推動住院醫師一周88小時(聽說最近改成80小時?),曾當過實習醫師的我,對長時間勞動的體會非常深刻,猶記得以前曾經連續三十二小時不睡,只為處理病人的事,其實對病人不是好事!

會念書的都知道,真正高手都是不熬夜的,因為熬夜唸書精神不集中,反而不如睡飽後好好念,效率更高,不過也許台灣健保只求服務到每位民眾,對品質不太要求吧?!所以常常讓醫師過勞,很多年輕醫師因為過勞失去工作能力甚至喪失性命,希望政府能夠改善這個問題,唯有健康的醫師才是全民之福啊!

2017 google code jam 資格賽

這是我第三次參加GCJ,比起前兩次進步超多的> <,寫出了完整三題,最終排名在三千左右,雖然資格賽排名沒甚麼用,但我還是心裡暗爽了一下XD


以下,就由小弟來分享一下解題心得吧


先附上題目連結: https://code.google.com/codejam/contest/3264486/dashboard


一. 翻餅問題: 這題算是考古題吧! 蠻有名的題目,不過有簡化過,以前的題目翻餅數不固定,不過這次翻餅數固定,可以用貪心法求解,解題思路如下,因為翻的順序不影響餅的狀態,所以可以先從最左邊開始考慮,若最左邊為unhappy,則從最左邊開始翻,並更新從最左邊開始K塊餅的狀態,之後,若遇到happy則跳過,unhappy則連翻K塊餅,最後在確認邊界,即可得知答案,這樣算是比較粗略的作法,複雜度為O(n*k),還有更快的作法,稱為尺取法,不過這題不需要,有需要請自行google

code如下:

#include<cstdio>
#include<iostream>
#include<string>
#pragma warning(disable : 4996)
using namespace std;

int main(void)
{
    freopen("C:\\Users\\user\\Desktop\\input.in", "r", stdin);
    freopen("C:\\Users\\user\\Desktop\\output.txt", "w", stdout);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {

        string s;
        cin >> s;
        int k;
        cin >> k;
        int ans = 0;
        int len = s.length();

        //cout<<s<<" "<<k<<" "<<len<<endl;
        for (int j = 0; j < len; j++)
        {
            //cout << s << endl;
            if (j + k >len)
            {
                for (int g = j; g < len; g++)
                {
                    if (s[g] != '+')
                    {
                        ans = -1;
                        break;
                    }
                }
            }
            else
            {
                if (s[j] == '+')
                    continue;
                else
                {
                    for (int g = j; g < j + k; g++)
                    {
                        if (s[g] == '-')
                            s[g] = '+';
                        else
                            s[g] = '-';
                    }
                    ans++;
                }
            }
            if (ans < 0)
                break;
        }
        if (ans != -1)
            cout << "Case #" << i + 1 << ": " << ans << endl;
        else
            cout << "Case #" << i + 1 << ": " << "IMPOSSIBLE" << endl;
    }

二. 小數問題: 這題其實算是簡單的數學題吧,解題技巧就是找到第一個比下一個數字還小的數,若這個數字和之前相同,則回推到第一個相同的數字,再將其減一,之後都加九,直到底為止,如此即為答案,複雜度為O(n)


ex. 13322, 其答案為12999, 可由上述演算法得知
ps. 若減一後發現為零,需捨去零.要特別注意

code如下:

#include<bits/stdc++.h>

using namespace std;

int main(void)
{
    freopen("C:\\Users\\user\\Desktop\\input.in","r",stdin);
freopen("C:\\Users\\user\\Desktop\\output.txt","w",stdout);
    int t;
    cin>>t;

    for(int i=1;i<=t;i++)
    {
        int ok=1;
        string s;
        cin>>s;
        //cout<<s<<endl;
        string ans="";
        int len=s.length();
        int same=0;;
        for(int i=0;i<len-1;i++)
        {

            if(s[i]>s[i+1])
            {
                for(int j=0;j<same;j++)
                ans=ans+s[j];
                char c=s[same]-1;
                if(same!=0||c!='0')
                ans=ans+c;
                for(int j=same+1;j<len;j++)
                ans=ans+'9';
                ok=0;
                break;
            }
        if(s[i]!=s[i+1])
            same=i+1;

        }
        if(ok)
            ans=s;
        cout<<"case #"<<i<<": "<<ans<<endl;
    }

}

三. 廁所問題:這題算是數論題,有O($log$ $n$) 的解法,公式有些複雜,不過最終答案可由n,k組成的公式決定,讀者慢慢推應可發現和$\lfloor\log _2 n\rfloor$有關,可以用狀態樹來分析,比如說如果n=6,那狀態樹就會6分成3和2,剩下繼續分,一直分到零為止,而由大到小第k個節點的值即為第k次分的點,接下來就可求解答案!

#include<bits/stdc++.h>

using namespace std;

long long logtwo(long long q)
{
    long long a=1;
    long long r=0;
    while(a<=q)
    {
        r++;
        a=a*2;
    }
    return a/2;
}

int main(void)
{
   freopen("C:\\Users\\user\\Desktop\\input.in","r",stdin);
   freopen("C:\\Users\\user\\Desktop\\output.txt","w",stdout);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        long long n,k;
        cin>>n>>k;
        //cout<<n<<" "<<k<<endl;
        long long exp=logtwo(k);
        //cout<<exp<<endl;
        long long temp=(n+1-exp)/exp;
        if((n+1-exp-exp*(temp))>=k+1-exp)
            temp++;
        cout<<"Case #"<<i<<": "<<temp/2<<" "<<(temp-1)/2<<endl;
    }
}

四. 筆者也不會,還在努力研究中

first app

小弟經過不段的努力,終於開發出人生中的第一個APP,網址如下:


https://play.google.com/store/apps/details?id=com.blogspot.codecrazer.eng1&hl=zh_TW


如果有發現任何bug, 歡迎留言,感謝各位,如果對開發APP有問題的話,也歡迎一起切磋討論


補記上架心得: 其實android 上架就是去google play developer console 註冊帳號,然後用信用卡繳25塊美金(約750塊台幣),就可終生使用,還蠻划算的! 之後就是上傳檔案,通常幾個小時就會出現在google play store, 之後就是可以每天去google play developer console 看下載數,以及如果有發現bug的話,可以上傳新版,對我來說,看下載數一直上升還蠻爽的XD