題目來源:
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;
}