《剑指Offer》笔记（更新中）

　　这几天为了找工作开始看《剑指offer》，到现在也大概浏览一遍了，前两天看作者博客中提到九度OJ，就去看了一下，发现上面有书上的题目，就想可以自己写代码练习一下，而不仅仅是看解题思路，毕竟还是觉得写代码实在。可是现在却不想一道一道做了，知道怎么解决并且看过代码后忽然就没动力再去写了...唉...

　　不过最后还是决定写点，写一点是一点吧，记录一下自己的代码。也许我一看要写50道题就有点害怕了，毕竟最近因为找工作的事情有点闹心，没法静下心来做事情，uva也暂时停止了，反正现在搞的挺乱的...

　　好了，没用的话说也说了，说一下感受吧，浏览完这本书后留下印象最深的就是对空指针的判断，每一个涉及指针的操作都要先判断是否为NULL，以前我是从未考虑的，因为在oj上做题是不用考虑这个的，所以我几乎没这个习惯，看来以后要该改啦。收获一方面是解题思路，另一方面就是代码的鲁棒性了，给我上了很好的一堂课。的确，自己还有很多不足，还要好好努力...

@2013-09-26

　　题3：二维数组中的查找。

 1 #include <cstdio>
 2 #define MAXN 1000+10
 3 
 4 int a[MAXN][MAXN];
 5 
 6 int main()
 7 {
 8 #ifdef LOCAL
 9     freopen("in", "r", stdin);
10 #endif
11     int m, n;
12     while (scanf("%d%d", &m, &n) != EOF)
13     {
14         int target;
15         scanf("%d", &target);
16         for (int i = 0; i < m; i++)
17             for (int j = 0; j < n; j++)
18                 scanf("%d", &a[i][j]);
19         int x = 0, y = n-1;
20         bool ok = false;
21         while (x < m && y >= 0)
22         {
23             if (a[x][y] == target)
24             {
25                 ok = true;
26                 break;
27             }
28             else if (a[x][y] > target)  y--;
29             else x++;
30         }
31         if (ok)  printf("Yes
");
32         else  printf("No
");
33     }
34     return 0;
35 }

Problem 3

　　题4：替换空格。这种题拿到OJ上已经没意义了，可以直接拿来输出，要转换吗？...KISS...

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 char str[1000000];
 5 
 6 int main()
 7 {
 8 #ifdef LOCAL
 9     freopen("in", "r", stdin);
10 #endif
11     while (gets(str))
12     {
13         int len = strlen(str);
14         for (int i = 0; i < len; i++)
15         {
16             if (str[i] == ' ')  printf("%%20");
17             else  printf("%c", str[i]);
18         }
19         printf("
");
20     }
21     return 0;
22 }

Problem 4

　　题10：二进制中1的个数。这个题用到一个很有意思的结论：将一个整数减去1再和这个数进行与运算(&)，得到的结果相当于把这个数的二进制表示的最右边的1变成0。

 1 #include <cstdio>
 2 
 3 int main()
 4 {
 5 #ifdef LOCAL
 6     freopen("in", "r", stdin);
 7 #endif
 8     int T;
 9     scanf("%d", &T);
10     while (T--)
11     {
12         int n;
13         scanf("%d", &n);
14         int cnt = 0;
15         while (n)
16         {
17             cnt++;
18             n &= (n-1);
19         }
20         printf("%d
", cnt);
21     }
22     return 0;
23 }

Problem 10

　　网上有关于更优化的方法，参见这里，而这篇文章讲解的更详细一点。

　　PS：看来还是应该在看题的时候去完成代码实现，看完后在回过头写代码就没什么动力了...

　　题目26：复杂链表的复制。比正常的链表多出一个sibling指针，可以指向链表中任意一个节点或NULL。

　　题目41：和为s的两个数字 & 和为s的连续正数序列

　　给一个有序数组，找出两个数使得和为s。(jobdu 1352)

 1 #include <cstdio>
 2 #define MAXN 1000000+100
 3 
 4 int a[MAXN];
 5 
 6 int main()
 7 {
 8 #ifdef LOCAL
 9     freopen("in", "r", stdin);
10 #endif
11     int n, k;
12     while (scanf("%d%d", &n, &k) != EOF)
13     {
14         for (int i = 0; i < n; i++)  scanf("%d", &a[i]);
15         int i = 0, j = n-1;
16         bool ok = false;
17         while (1)
18         {
19             if (i >= j)  break;
20             if (a[i] + a[j] == k)  
21             {
22                 ok = true;
23                 break;
24             }
25             else if (a[i] + a[j] < k)  i++;
26             else  j--;
27         }
28         if (ok)  printf("%d %d
", a[i], a[j]);
29         else  printf("-1 -1
");
30     }
31     return 0;
32 }

View Code

　　给一个正整数s，求和为s的连续正整数序列（至少含有两个数）。(jobdu 1354)

 1 #include <cstdio>
 2 
 3 void printResult(int left, int right)
 4 {
 5     for (int i = left; i <= right; i++)
 6         printf("%d%s", i, i==right ? "
" : " ");
 7 }
 8 
 9 int main()
10 {
11 #ifdef LOCAL
12     freopen("in", "r", stdin);
13 #endif
14     int n;
15     while (scanf("%d", &n) != EOF && n >= 0)
16     {
17         int left = 1, right = 2, sum = 3;
18         int mid = n / 2;
19         bool solved = false;
20         while (left <= mid)
21         {
22             while (sum < n)
23             {
24                 right++;
25                 sum += right;
26             }
27             if (sum == n) 
28             {
29                 printResult(left, right);
30                 solved = true;
31                 sum -= left;
32                 left++;
33             }
34             else if (sum > n) 
35             {
36                 sum -= left;
37                 left++;
38             }
39         }
40         if (!solved)  printf("Pity!
");
41         printf("#
");
42     }
43     return 0;
44 }

View Code