题目来源:
http://zhedahht.blog.163.com/blog/static/25411174200951262930831/ 题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。思路一:
我们需要把扑克牌的背景抽象成计算机语言。不难想象，我们可以把5
张牌看成由5
个数字组成的数组。大小王是特殊的数字，我们不妨把它们都当成0
，这样和其他扑克牌代表的数字就不重复了。
接下来我们来分析怎样判断5个数字是不是连续的。最直观的是，我们把数组排序。但值得注意的是，由于0可以当成任意数字，我们可以用0去补满数组中的空缺。也就是排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，但如果我们有足够的0可以补满这两个数字的空缺，这个数组实际上还是连续的。举个例子，数组排序之后为{0，1，3，4，5}。在1和3之间空缺了一个2，刚好我们有一个0，也就是我们可以它当成2去填补这个空缺。
于是我们需要做三件事情：把数组排序，统计数组中0的个数，统计排序之后的数组相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。最后，我们还需要注意的是，如果数组中的非0数字重复出现，则该数组不是连续的。换成扑克牌的描述方式，就是如果一副牌里含有对子，则不可能是顺子。
更好的思路二:
1）确认5张牌中除了0，其余数字没有重复的（可以用表统计的方法）;
2) 满足这样的逻辑：（max，min分别代表5张牌中的除0以外的最大值最小值）
如果没有0，则max-min=4，则为顺子，否则不是
如果有一个0，则max-min=4或者3，则为顺子，否则不是
如果有两个0，则max-min=4或者3或者2，则为顺子，否则不是
最大值和最小值在1）中就可以获得，这样就不用排序了
题目来源:
http://zhedahht.blog.163.com/blog/static/25411174201102642136998/
题目（六）：运行下列C++代码，输出什么？
struct Point3D
{
int x;
int y;
int z;
};
int _tmain(int argc, _TCHAR* argv[])
{
Point3D* pPoint = NULL;
int offset = (int)(&(pPoint)->z);
printf("%d", offset);
return 0;
}
答案：输出8。由于在pPoint->z的前面加上了取地址符号，运行到此时的时候，会在pPoint的指针地址上加z在类型Point3D中的偏移量8。由于pPoint的地址是0，因此最终offset的值是8。
&(pPoint->z)的语意是求pPoint中变量z的地址（pPoint的地址0加z的偏移量8），并不需要访问pPoint指向的内存。只要不访问非法的内存，程序就不会出错。
题目（七）：运行下列C++代码，输出什么？
class A
{
public:
A()
{
Print();
}
virtual void Print()
{
printf("A is constructed.\n");
}
};
class B: public A
{
public:
B()
{
Print();
}
virtual void Print()
{
printf("B is constructed.\n");
}
};
int _tmain(int argc, _TCHAR* argv[])
{
A* pA = new B();
delete pA;
return 0;
}
答案：先后打印出两行:A is constructed. B is constructed. 调用B的构造函数时，先会调用B的基类及A的构造函数。然后在A的构造函数里调用Print。由于此时实例的类型B的部分还没有构造好，本质上它只是A的一个实例，他的虚函数表指针指向的是类型A的虚函数表。因此此时调用的Print是A::Print，而不是B::Print。接着调用类型B的构造函数，并调用Print。此时已经开始构造B，因此此时调用的Print是B::Print。
同样是调用虚拟函数Print，我们发现在类型A的构造函数中，调用的是A::Print，在B的构造函数中，调用的是B::Print。因此虚函数在构造函数中，已经失去了虚函数的动态绑定特性。
题目来源:
http://zhedahht.blog.163.com/blog/static/254111742010111112236313/模拟法
#include<stdio.h>
#define MAX_LEN 101
void
print_circle(int (*mtrx)[MAX_LEN], int leftup_x, int leftup_y, int rightdown_x, int rightdown_y)
{
int i, j;
if(leftup_x == rightdown_x) {
for(j=leftup_y; j<=rightdown_y; j++)
printf("%d\t", mtrx[leftup_x][j]);
return;
}
if(leftup_y == rightdown_y) {
for(i=leftup_x; i<=rightdown_x; i++)
printf("%d\t", mtrx[i][leftup_y]);
return;
}
for(i=leftup_y; i<rightdown_y; i++)
printf("%d\t", mtrx[leftup_x][i]);
for(j=leftup_x; j<rightdown_x; j++)
printf("%d\t", mtrx[j][rightdown_y]);
for(i=rightdown_y; i>leftup_y; i--)
printf("%d\t", mtrx[rightdown_x][i]);
for(j=rightdown_x; j>leftup_x; j--)
printf("%d\t", mtrx[j][leftup_y]);
}
void
solve(int (*mtrx)[MAX_LEN], int width, int length)
{
int lu_x, lu_y, rd_x, rd_y;
lu_x = lu_y = 0;
rd_x = width-1;
rd_y = length-1;
while(1) {
if(lu_x>rd_x || lu_y>rd_y)
break;
print_circle(mtrx, lu_x, lu_y, rd_x, rd_y);
++lu_x;
++lu_y;
--rd_x;
--rd_y;
}
}
int
main(int argc, char **argv)
{
int i, j, length, width, matrix[MAX_LEN][MAX_LEN];
scanf("%d %d", &width, &length);
for(i=0; i<width; i++)
for(j=0; j<length; j++)
scanf("%d", matrix[i]+j);
solve(matrix, width, length);
return 0;
}
题目来源:
http://zhedahht.blog.163.com/blog/static/254111742011125100605/
题目：写一个函数，求两个整数的之和，要求在函数体内不得使用＋、－、×、÷。
分析：这又是一道考察发散思维的很有意思的题目。当我们习以为常的东西被限制使用的时候，如何突破常规去思考，就是解决这个问题的关键所在。
看到的这个题目，我的第一反应是傻眼了，四则运算都不能用，那还能用什么啊？可是问题总是要解决的，只能打开思路去思考各种可能性。首先我们可以分析人们是如何做十进制的加法的，比如是如何得出5+17=22这个结果的。实际上，我们可以分成三步的：第一步只做各位相加不进位，此时相加的结果是12（个位数5和7相加不要进位是2，十位数0和1相加结果是1）；第二步做进位，5+7中有进位，进位的值是10；第三步把前面两个结果加起来，12+10的结果是22，刚好5+17=22。
前面我们就在想，求两数之和四则运算都不能用，那还能用什么啊？对呀，还能用什么呢？对数字做运算，除了四则运算之外，也就只剩下位运算了。位运算是针对二进制的，我们也就以二进制再来分析一下前面的三步走策略对二进制是不是也管用。
5的二进制是101，17的二进制10001。还是试着把计算分成三步：第一步各位相加但不计进位，得到的结果是10100（最后一位两个数都是1，相加的结果是二进制的10。这一步不计进位，因此结果仍然是0）；第二步记下进位。在这个例子中只在最后一位相加时产生一个进位，结果是二进制的10；第三步把前两步的结果相加，得到的结果是10110，正好是22。由此可见三步走的策略对二进制也是管用的。
接下来我们试着把二进制上的加法用位运算来替代。第一步不考虑进位，对每一位相加。0加0与 1加1的结果都0，0加1与1加0的结果都是1。我们可以注意到，这和异或的结果是一样的。对异或而言，0和0、1和1异或的结果是0，而0和1、1和0的异或结果是1。接着考虑第二步进位，对0加0、0加1、1加0而言，都不会产生进位，只有1加1时，会向前产生一个进位。此时我们可以想象成是两个数先做位与运算，然后再向左移动一位。只有两个数都是1的时候，位与得到的结果是1，其余都是0。第三步把前两个步骤的结果相加。如果我们定义一个函数AddWithoutArithmetic，第三步就相当于输入前两步骤的结果来递归调用自己。
#include<stdio.h>
int
tricky_add(int arg1, int arg2)
{
int a, b;
a = arg1 ^ arg2; /* this is the result of arg1+arg2 without carry */
b = arg1 & arg2;
b <<= 1;
if(b == 0)
return a;
else
return tricky_add(a, b);
}
int
main(int argc, char **argv)
{
int x, y;
while(scanf("%d %d", &x, &y) != EOF) {
printf("%d\n", tricky_add(x, y));
}
return 0;
}
题目来源:
http://zhedahht.blog.163.com/blog/static/25411174200732711051101/
题目：输入一个正数n，输出所有和为n连续正数序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
分析：这是网易的一道面试题。
这道题和本面试题系列的第10题有些类似。我们用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。如果从small到big的序列的和大于n的话，我们向右移动small，相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话，我们向右移动big，相当于向序列中添加big的下一个数字。一直到small等于(1+n)/2，因为序列至少要有两个数字。
基于这个思路，我们可以写出如下代码：
void PrintContinuousSequence(int small, int big);
/////////////////////////////////////////////////////////////////////////
// Find continuous sequence, whose sum is n
/////////////////////////////////////////////////////////////////////////
void FindContinuousSequence(int n)
{
if(n < 3)
return;
int small = 1;
int big = 2;
int middle = (1 + n) / 2;
int sum = small + big;
while(small < middle)
{
// we are lucky and find the sequence
if(sum == n)
PrintContinuousSequence(small, big);
// if the current sum is greater than n,
// move small forward
while(sum > n)
{
sum -= small;
small ++;
// we are lucky and find the sequence
if(sum == n)
PrintContinuousSequence(small, big);
}
// move big forward
big ++;
sum += big;
}
}
/////////////////////////////////////////////////////////////////////////
// Print continuous sequence between small and big
/////////////////////////////////////////////////////////////////////////
void PrintContinuousSequence(int small, int big)
{
for(int i = small; i <= big; ++ i)
printf("%d ", i);
printf("\n");
}
题目来源:
http://zhedahht.blog.163.com/blog/static/25411174200731844235261/
题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。
分析：这道题最近经常出现，包括MicroStrategy等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。
首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。
现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。
我们把上面的分析用一个公式总结如下：
/ 1 n=1
f(n)= 2 n=2
\ f(n-1)+(f-2) n>2
分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。
题目来源：
http://zhedahht.blog.163.com/blog/static/2541117420073471124487/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node {
char value;
struct Node *next;
};
struct Node *
list_reverse(struct Node *head)
{
struct Node *tmp, *cur, *pre = NULL;
cur = head;
while(cur) {
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
struct Node *
list_reverse_recursive(struct Node *head)
{
struct Node *rv;
if(head && head->next) {
rv = list_reverse_recursive(head->next);
head->next->next = head;
head->next = NULL;
return rv;
} else
return head;
}
void
test_print(struct Node *head)
{
while(head) {
printf("%c\t", head->value);
head = head->next;
}
printf("\n");
}
int
main(int argc, char **argv)
{
struct Node d = {'d', NULL};
struct Node c = {'c', &d};
struct Node b = {'b', &c};
struct Node a = {'a', &b};
test_print(&a);
struct Node *rev_first = list_reverse(&a);
test_print(rev_first);
struct Node *rev_second = list_reverse_recursive(rev_first);
test_print(rev_second);
return 0;
}
题目来源:
http://blog.163.com/prevBlogPerma.do?host=zhedahht&srl=25411174200731139971&mode=prev
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
/*
* #define INT_MAX 2147483647
* #define INT_MIN (-INT_MAX-1)
*/
enum Status {
Success,
Fail
};
enum Status ret;
int negative;
int
Str2Int(const char *input)
{
long long num = 0;
negative = 0;
ret = Fail;
if(input == NULL)
return num;
const char *ptr = input;
if(*ptr=='+' || *ptr=='-') {
if(*ptr == '-')
negative = 1;
++ptr;
}
while(*ptr) {
if(!(*ptr>='0' && *ptr<='9'))
return num;
if((!negative && num>INT_MAX) || (negative && (-num)<INT_MIN))
return num;
num = num*10 + (*ptr-'0');
++ptr;
}
ret = Success;
return num;
}
#define MAX_LEN 101
int
main(int argc, char **argv)
{
int result;
char value[MAX_LEN];
while(scanf("%s", value) != EOF) {
result = Str2Int(value);
if(ret == Success)
printf("%d\n", negative ? (-result) : result);
else
printf("Invalid\n");
}
return 0;
}
题目来源：
http://zhedahht.blog.163.com/blog/static/254111742010819104710337/题目：有一个复杂链表，其结点除了有一个
m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node {
char value;
struct Node *next;
struct Node *random;
};
void test_print(struct Node *);
struct Node *
list_copy_with_random_pointer(struct Node *head)
{
struct Node *tmp, *ptr, *ret;
ptr = head;
while(ptr != NULL) {
tmp = (struct Node *)malloc(sizeof(struct Node));
tmp->value = (ptr->value)-32; /* from lowercase to uppercase, just for testing */
tmp->next = ptr->next;
tmp->random = NULL;
ptr->next = tmp;
ptr = ptr->next->next;
}
ptr = head;
while(ptr != NULL) {
ptr->next->random = ptr->random==NULL ? NULL : ptr->random->next;
ptr = ptr->next->next;
}
ptr = head;
ret = (head==NULL ? NULL : (head->next));
while(ptr != NULL) {
tmp = ptr->next;
ptr->next = ptr->next->next;
tmp->next = ptr->next==NULL ? NULL : ptr->next->next;
ptr = ptr->next;
}
return ret;
}
void
test_print(struct Node *head)
{
while(head != NULL) {
printf("%c: [%c, %c]\n", head->value, head->next==NULL?'-':head->next->value, head->random==NULL?'-':head->random->value);
head = head->next;
}
}
int
main(int argc, char **argv)
{
struct Node d = {'d', NULL, NULL};
struct Node c = {'c', &d, NULL};
struct Node b = {'b', &c, NULL};
struct Node a = {'a', &b, NULL};
a.random = &c;
d.random = &b;
test_print(&a);
struct Node *copy = list_copy_with_random_pointer(&a);
printf("\n\n");
test_print(&a);
printf("\n\n");
test_print(copy);
return 0;
}
题目来源：
http://blog.163.com/prevBlogPerma.do?host=zhedahht&srl=2541117420072159363370&mode=prev题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/ \
6 10
/\ /\
5 7 9 11
输出：
8
/ \
10 6
/\ /\
11 9 7 5
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node {
int value;
struct Node *left;
struct Node *right;
};
void
bst_preorder(struct Node *root)
{
if(root == NULL)
return;
printf("%d\t", root->value);
bst_preorder(root->left);
bst_preorder(root->right);
}
void
bst_mirror_recursive(struct Node *root) /* easy */
{
if(root == NULL)
return;
struct Node *ptr = root->left;
root->left = root->right;
root->right = ptr;
bst_mirror_recursive(root->left);
bst_mirror_recursive(root->right);
}
/* STACK : naive */
#define STACK_SIZE 101
struct Stack {
void *data[STACK_SIZE];
int top;
};
void
stack_pop(struct Stack *stack)
{
if((stack->top) >= 0)
--(stack->top);
}
void *
stack_top(struct Stack *stack)
{
if((stack->top) >= 0)
return stack->data[stack->top];
return NULL;
}
void
stack_push(struct Stack *stack, void *entity)
{
stack->data[++(stack->top)] = entity;
}
int
stack_isempty(struct Stack *stack)
{
return (stack->top) < 0;
}
void
bst_mirror_nonrecursive(struct Node *root, struct Stack *aux_stack) /* stack used : good method */
{
stack_push(aux_stack, root);
while(!stack_isempty(aux_stack)) {
struct Node *node = (struct Node *)stack_top(aux_stack);
struct Node *ptr = node->left;
node->left = node->right;
node->right = ptr;
stack_pop(aux_stack);
if(node->left)
stack_push(aux_stack, node->left);
if(node->right)
stack_push(aux_stack, node->right);
}
}
int
main(int argc, char **argv)
{
struct Node a = {5, NULL, NULL};
struct Node b = {7, NULL, NULL};
struct Node c = {9, NULL, NULL};
struct Node d = {11, NULL, NULL};
struct Node e = {6, &a, &b};
struct Node f = {10, &c, &d};
struct Node g = {8, &e, &f};
bst_preorder(&g);
printf("\n");
bst_mirror_recursive(&g);
bst_preorder(&g);
printf("\n");
bst_mirror_recursive(&g);
bst_preorder(&g);
printf("\n");
struct Stack aux = {{0}, -1};
bst_mirror_nonrecursive(&g, &aux);
bst_preorder(&g);
printf("\n");
return 0;
}