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

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

 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)//可以到達(dá)鏈表末尾說(shuō)明無(wú)環(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)//慢指針趕上快指針說(shuō)明有環(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<<"無(wú)環(huán)"<<endl;
50
51    //手工構(gòu)造一個(gè)環(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<<"無(wú)環(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}

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

 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}

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

 1#include <iostream>
 2#include <string>
 3using namespace std;
 4
 5int x=-1, y=-1;//x,y用來(lái)記錄最大子數(shù)組的起始和結(jié)束位置
 6
 7//動(dòng)態(tài)規(guī)劃，求最大子數(shù)組和
 8int maxsubarray(int a[], int n)
 9{
10    int max = 0, temp;//temp用來(lái)記錄每次新的可能的最長(zhǎng)子數(shù)組的開(kāi)始位置
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ù)子數(shù)組和為： "<<maxsubarray(array, len)<<endl;
43    cout<<"范圍： "<<"["<<x<<","<<y<<"]"<<endl;
44
45    return 0;
46}

最大子矩陣問(wèn)題，給出O(N^3)的算法
事實(shí)上就是上一題的二維版本，話說(shuō)也是經(jīng)典題，結(jié)果愣是做了我半天沒(méi)搞定，主要是下標(biāo)老是被我寫(xiě)錯(cuò)。。。很郁悶，回寢室后也改了半天才總算寫(xiě)對(duì)，還是缺少寫(xiě)DP的練習(xí)啊

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

ps:面試結(jié)束后同學(xué)告訴我很多題《編程之美》上都有，可憐我一年前就買了這本書(shū)到現(xiàn)在都沒(méi)看過(guò)，看來(lái)國(guó)慶得花時(shí)間翻翻了啊