Fly me to the moon

找工作的第一場仗打得非常漂亮，能在國慶前就拿到一個不錯的offer回家算是一個完美的開局了，不過接下去的10月，11月才是重頭戲，希望也能完美收官吧。剛剛回到家里，打算把前兩天筆試面試中碰到的一些題目記錄在這里，并給出自己的實現。以后每過一階段都會在這里總結一次碰到的題目，加以整理和進一步的思考，為后面的硬仗做好充分的準備。fighting~

快慢指針判斷單鏈表是否有環(huán)
這題是出現在筆試題里的一道選擇題，考試的時候我愣是不知道快慢指針是啥，于是猜了一個錯了，回到寢室后google了一下，發(fā)現這是判斷單鏈表是否有環(huán)的最經典的方案，對自己連這么基本的知識都不知道相當無語啊，于是趕緊實現了一下，相信這輩子也不會忘了吧

 1#include <iostream>
 2#include <string>
 3using namespace std;
 4
 5typedef struct list_node
 6{
 7    int x;
 8    struct list_node* next;
 9}node, *pnode;
10
11bool isCircle(pnode list)
12{
13    pnode quick=list, slow=list;//快慢指針
14    while(1)
15    {
16        if(quick==NULL || slow == NULL)//可以到達鏈表末尾說明無環(huán)
17            return false;
18        quick = quick->next;
19        if(quick == NULL)
20            return false;
21        quick = quick->next;
22        slow = slow->next;
23
24        if(slow==quick)//慢指針趕上快指針說明有環(huán)
25            return true;
26    }
27}
28
29int main()
30{
31    pnode list = NULL, temp;
32
33    for(int i=1;i<=10;i++)
34    {
35        pnode pn = new node;
36        pn->x = i;
37        pn->next = list;
38        list = pn;
39    }
40    
41    temp = list;
42    for(int i=0;i<10;i++, temp=temp->next)
43        cout<<temp->x<<" ";
44    cout<<endl;
45
46    if(isCircle(list))
47        cout<<"有環(huán)"<<endl;
48    else
49        cout<<"無環(huán)"<<endl;
50
51    //手工構造一個環(huán)
52    pnode tail = list;
53    while(tail->next != NULL)
54        tail = tail->next;
55    tail->next = list;
56
57    if(isCircle(list))
58        cout<<"有環(huán)"<<endl;
59    else
60        cout<<"無環(huán)"<<endl;
61
62    for(int i=0;i<10;i++)
63    {
64        temp = list->next;
65        delete list;
66        list = temp;
67    }
68
69    return 0;
70}

原地刪除給定字符串中的指定字符
一聽到面試官說要原地算法，第一反應就是交換，于是秒殺

 1#include <iostream>
 2#include <string>
 3using namespace std;
 4
 5//原地刪除字符串中的指定字符
 6char* del_char(char *str, char del)
 7{
 8    int n = strlen(str);
 9    int i,j;
10    for(i=0;i<n;i++)
11    {
12        if(str[i]==del)
13        {
14            j=i;
15            while(str[j]==del)
16                j++;
17            swap(str[i], str[j]);
18            if(str[i]=='\0')
19                return str;
20        }
21    }
22    return str;
23}
24
25int main()
26{
27    char str[] = "banana";
28    cout<<del_char(str, 'a')<<endl;
29
30    return 0;
31}

求給定數組的連續(xù)最大和子數組
經典的動態(tài)規(guī)劃，programming pearl上給了四種解法，對divide&conquer和DP的兩種解法應該都是了然于心的，于是又秒殺。之后面試官要求記錄最大子數組的索引，想了想，繼續(xù)秒殺

 1#include <iostream>
 2#include <string>
 3using namespace std;
 4
 5int x=-1, y=-1;//x,y用來記錄最大子數組的起始和結束位置
 6
 7//動態(tài)規(guī)劃，求最大子數組和
 8int maxsubarray(int a[], int n)
 9{
10    int max = 0, temp;//temp用來記錄每次新的可能的最長子數組的開始位置
11    int maxendinghere = 0;
12    for(int i=0;i<n;i++)
13    {
14        if(maxendinghere+a[i]>=0)//特別注意這里是大于等于，不能忘記等于
15        {
16            if(maxendinghere==0)
17                temp = i;
18            maxendinghere += a[i];
19        }
20        else
21            maxendinghere = 0;
22
23        if(maxendinghere > max)
24        {
25            max = maxendinghere;
26            y = i;
27            x = temp;
28        }
29    }
30
31    return max;
32}
33
34int main()
35{
36    int array[] = {2,-3,4};
37    int len = sizeof(array)/sizeof(array[0]);
38    for(int i=0;i<len;i++)
39        cout<<array[i]<<" ";
40    cout<<endl;
41
42    cout<<"最大連續(xù)子數組和為： "<<maxsubarray(array, len)<<endl;
43    cout<<"范圍： "<<"["<<x<<","<<y<<"]"<<endl;
44
45    return 0;
46}

最大子矩陣問題，給出O(N^3)的算法
事實上就是上一題的二維版本，話說也是經典題，結果愣是做了我半天沒搞定，主要是下標老是被我寫錯。。。很郁悶，回寢室后也改了半天才總算寫對，還是缺少寫DP的練習啊

總結：
總的來說，題目雖然都不難，但是在面試的時候要求當場在紙上寫出代碼還是相當考驗人的，畢竟這時候你得不到IDE的幫助，只能在自己腦子里debug，光能描述出算法的思想還是不夠的，還是得多練練碼代碼的能力啊，平時練的時候最好是別用F5，有錯直接用眼睛看，用腦子想，當然啦，真正寫程序的時候還得依賴debug，但在實現一些不太復雜的算法時完全可以這么做，我相信一定有好處的。

ps:面試結束后同學告訴我很多題《編程之美》上都有，可憐我一年前就買了這本書到現在都沒看過，看來國慶得花時間翻翻了啊