Fly me to the moon

找工作的第一场仗打得非常漂亮，能在国庆前就拿到一个不错的offer回家算是一个完美的开局了，不过接下去的10月，11月才是重头戏，希望也能完美收官吧。刚刚回到家里，打算把前两天笔试面试中碰到的一些题目记录在这里，并给出自己的实现。以后每过一阶段都会在这里总结一次碰到的题目，加以整理和进一步的思考，为后面的硬仗做好充分的准备。fighting~

快慢指针判断单链表是否有环
这题是出现在笔试题里的一道选择题，考试的时候我愣是不知道快慢指针是啥，于是猜了一个错了，回到寝室后google了一下，发现这是判断单链表是否有环的最经典的方案，对自己连这么基本的知识都不知道相当无语啊，于是赶紧实现了一下，相信这辈子也不会忘了吧

 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)//可以到达链表末尾说明无环
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)//慢指针赶上快指针说明有环
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<<"有环"<<endl;
48    else
49        cout<<"无环"<<endl;
50
51    //手工构造一个环
52    pnode tail = list;
53    while(tail->next != NULL)
54        tail = tail->next;
55    tail->next = list;
56
57    if(isCircle(list))
58        cout<<"有环"<<endl;
59    else
60        cout<<"无环"<<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}

求给定数组的连续最大和子数组
经典的动态规划，programming pearl上给了四种解法，对divide&conquer和DP的两种解法应该都是了然于心的，于是又秒杀。之后面试官要求记录最大子数组的索引，想了想，继续秒杀

 1#include <iostream>
 2#include <string>
 3using namespace std;
 4
 5int x=-1, y=-1;//x,y用来记录最大子数组的起始和结束位置
 6
 7//动态规划，求最大子数组和
 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<<"最大连续子数组和为： "<<maxsubarray(array, len)<<endl;
43    cout<<"范围： "<<"["<<x<<","<<y<<"]"<<endl;
44
45    return 0;
46}

最大子矩阵问题，给出O(N^3)的算法
事实上就是上一题的二维版本，话说也是经典题，结果愣是做了我半天没搞定，主要是下标老是被我写错。。。很郁闷，回寝室后也改了半天才总算写对，还是缺少写DP的练习啊

总结：
总的来说，题目虽然都不难，但是在面试的时候要求当场在纸上写出代码还是相当考验人的，毕竟这时候你得不到IDE的帮助，只能在自己脑子里debug，光能描述出算法的思想还是不够的，还是得多练练码代码的能力啊，平时练的时候最好是别用F5，有错直接用眼睛看，用脑子想，当然啦，真正写程序的时候还得依赖debug，但在实现一些不太复杂的算法时完全可以这么做，我相信一定有好处的。

ps:面试结束后同学告诉我很多题《编程之美》上都有，可怜我一年前就买了这本书到现在都没看过，看来国庆得花时间翻翻了啊