这几天为了找工作开始看《剑指offer》，到现在也大概浏览一遍了，前两天看作者博客中提到九度OJ，就去看了一下，发现上面有书上的题目，就想可以自己写代码练习一下，而不仅仅是看解题思路，毕竟还是觉得写代码实在。可是现在却不想一道一道做了，知道怎么解决并且看过代码后忽然就没动力再去写了...唉...
不过最后还是决定写点，写一点是一点吧，记录一下自己的代码。也许我一看要写50道题就有点害怕了，毕竟最近因为找工作的事情有点闹心，没法静下心来做事情，uva也暂时停止了，反正现在搞的挺乱的...
好了，没用的话说也说了，说一下感受吧，浏览完这本书后留下印象最深的就是对空指针的判断，每一个涉及指针的操作都要先判断是否为NULL，以前我是从未考虑的，因为在oj上做题是不用考虑这个的，所以我几乎没这个习惯，看来以后要该改啦。收获一方面是解题思路，另一方面就是代码的鲁棒性了，给我上了很好的一堂课。的确，自己还有很多不足，还要好好努力...
@2013-09-26
题3：二维数组中的查找。
#include <cstdio>
#define MAXN 1000+10 int a[MAXN][MAXN]; int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int m, n;
while (scanf("%d%d", &m, &n) != EOF)
{
int target;
scanf("%d", &target);
for (int i = ; i < m; i++)
for (int j = ; j < n; j++)
scanf("%d", &a[i][j]);
int x = , y = n-;
bool ok = false;
while (x < m && y >= )
{
if (a[x][y] == target)
{
ok = true;
break;
}
else if (a[x][y] > target) y--;
else x++;
}
if (ok) printf("Yes\n");
else printf("No\n");
}
return ;
}
Problem 3
题4：替换空格。这种题拿到OJ上已经没意义了，可以直接拿来输出，要转换吗？...KISS...
#include <cstdio>
#include <cstring> char str[]; int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
while (gets(str))
{
int len = strlen(str);
for (int i = ; i < len; i++)
{
if (str[i] == ' ') printf("%%20");
else printf("%c", str[i]);
}
printf("\n");
}
return ;
}
Problem 4
题10：二进制中1的个数。这个题用到一个很有意思的结论：将一个整数减去1再和这个数进行与运算(&)，得到的结果相当于把这个数的二进制表示的最右边的1变成0。
#include <cstdio> int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
int cnt = ;
while (n)
{
cnt++;
n &= (n-);
}
printf("%d\n", cnt);
}
return ;
}
Problem 10
网上有关于更优化的方法，参见这里，而这篇文章讲解的更详细一点。
PS：看来还是应该在看题的时候去完成代码实现，看完后在回过头写代码就没什么动力了...
题目26：复杂链表的复制。比正常的链表多出一个sibling指针，可以指向链表中任意一个节点或NULL。
题目41：和为s的两个数字 & 和为s的连续正数序列
给一个有序数组，找出两个数使得和为s。(jobdu 1352)
#include <cstdio>
#define MAXN 1000000+100 int a[MAXN]; int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n, k;
while (scanf("%d%d", &n, &k) != EOF)
{
for (int i = ; i < n; i++) scanf("%d", &a[i]);
int i = , j = n-;
bool ok = false;
while ()
{
if (i >= j) break;
if (a[i] + a[j] == k)
{
ok = true;
break;
}
else if (a[i] + a[j] < k) i++;
else j--;
}
if (ok) printf("%d %d\n", a[i], a[j]);
else printf("-1 -1\n");
}
return ;
}
给一个正整数s，求和为s的连续正整数序列（至少含有两个数）。(jobdu 1354)
#include <cstdio> void printResult(int left, int right)
{
for (int i = left; i <= right; i++)
printf("%d%s", i, i==right ? "\n" : " ");
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n;
while (scanf("%d", &n) != EOF && n >= )
{
int left = , right = , sum = ;
int mid = n / ;
bool solved = false;
while (left <= mid)
{
while (sum < n)
{
right++;
sum += right;
}
if (sum == n)
{
printResult(left, right);
solved = true;
sum -= left;
left++;
}
else if (sum > n)
{
sum -= left;
left++;
}
}
if (!solved) printf("Pity!\n");
printf("#\n");
}
return ;
}