題目來源:
http://zhedahht.blog.163.com/blog/static/25411174200951262930831/ 題目：從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這5張牌是不是連續(xù)的。2-10為數(shù)字本身，A為1，J為11，Q為12，K為13，而大小王可以看成任意數(shù)字。思路一:
我們需要把撲克牌的背景抽象成計算機語言。不難想象，我們可以把5
張牌看成由5
個數(shù)字組成的數(shù)組。大小王是特殊的數(shù)字，我們不妨把它們都當成0
，這樣和其他撲克牌代表的數(shù)字就不重復(fù)了。
接下來我們來分析怎樣判斷5個數(shù)字是不是連續(xù)的。最直觀的是，我們把數(shù)組排序。但值得注意的是，由于0可以當成任意數(shù)字，我們可以用0去補滿數(shù)組中的空缺。也就是排序之后的數(shù)組不是連續(xù)的，即相鄰的兩個數(shù)字相隔若干個數(shù)字，但如果我們有足夠的0可以補滿這兩個數(shù)字的空缺，這個數(shù)組實際上還是連續(xù)的。舉個例子，數(shù)組排序之后為{0，1，3，4，5}。在1和3之間空缺了一個2，剛好我們有一個0，也就是我們可以它當成2去填補這個空缺。
于是我們需要做三件事情：把數(shù)組排序，統(tǒng)計數(shù)組中0的個數(shù)，統(tǒng)計排序之后的數(shù)組相鄰數(shù)字之間的空缺總數(shù)。如果空缺的總數(shù)小于或者等于0的個數(shù)，那么這個數(shù)組就是連續(xù)的；反之則不連續(xù)。最后，我們還需要注意的是，如果數(shù)組中的非0數(shù)字重復(fù)出現(xiàn)，則該數(shù)組不是連續(xù)的。換成撲克牌的描述方式，就是如果一副牌里含有對子，則不可能是順子。
更好的思路二:
1）確認5張牌中除了0，其余數(shù)字沒有重復(fù)的（可以用表統(tǒng)計的方法）;
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指向的內(nèi)存。只要不訪問非法的內(nèi)存，程序就不會出錯。
題目（七）：運行下列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. 調(diào)用B的構(gòu)造函數(shù)時，先會調(diào)用B的基類及A的構(gòu)造函數(shù)。然后在A的構(gòu)造函數(shù)里調(diào)用Print。由于此時實例的類型B的部分還沒有構(gòu)造好，本質(zhì)上它只是A的一個實例，他的虛函數(shù)表指針指向的是類型A的虛函數(shù)表。因此此時調(diào)用的Print是A::Print，而不是B::Print。接著調(diào)用類型B的構(gòu)造函數(shù)，并調(diào)用Print。此時已經(jīng)開始構(gòu)造B，因此此時調(diào)用的Print是B::Print。
同樣是調(diào)用虛擬函數(shù)Print，我們發(fā)現(xiàn)在類型A的構(gòu)造函數(shù)中，調(diào)用的是A::Print，在B的構(gòu)造函數(shù)中，調(diào)用的是B::Print。因此虛函數(shù)在構(gòu)造函數(shù)中，已經(jīng)失去了虛函數(shù)的動態(tài)綁定特性。
題目來源:
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/
題目：寫一個函數(shù)，求兩個整數(shù)的之和，要求在函數(shù)體內(nèi)不得使用＋、－、×、÷。
分析：這又是一道考察發(fā)散思維的很有意思的題目。當我們習以為常的東西被限制使用的時候，如何突破常規(guī)去思考，就是解決這個問題的關(guān)鍵所在。
看到的這個題目，我的第一反應(yīng)是傻眼了，四則運算都不能用，那還能用什么啊？可是問題總是要解決的，只能打開思路去思考各種可能性。首先我們可以分析人們是如何做十進制的加法的，比如是如何得出5+17=22這個結(jié)果的。實際上，我們可以分成三步的：第一步只做各位相加不進位，此時相加的結(jié)果是12（個位數(shù)5和7相加不要進位是2，十位數(shù)0和1相加結(jié)果是1）；第二步做進位，5+7中有進位，進位的值是10；第三步把前面兩個結(jié)果加起來，12+10的結(jié)果是22，剛好5+17=22。
前面我們就在想，求兩數(shù)之和四則運算都不能用，那還能用什么啊？對呀，還能用什么呢？對數(shù)字做運算，除了四則運算之外，也就只剩下位運算了。位運算是針對二進制的，我們也就以二進制再來分析一下前面的三步走策略對二進制是不是也管用。
5的二進制是101，17的二進制10001。還是試著把計算分成三步：第一步各位相加但不計進位，得到的結(jié)果是10100（最后一位兩個數(shù)都是1，相加的結(jié)果是二進制的10。這一步不計進位，因此結(jié)果仍然是0）；第二步記下進位。在這個例子中只在最后一位相加時產(chǎn)生一個進位，結(jié)果是二進制的10；第三步把前兩步的結(jié)果相加，得到的結(jié)果是10110，正好是22。由此可見三步走的策略對二進制也是管用的。
接下來我們試著把二進制上的加法用位運算來替代。第一步不考慮進位，對每一位相加。0加0與 1加1的結(jié)果都0，0加1與1加0的結(jié)果都是1。我們可以注意到，這和異或的結(jié)果是一樣的。對異或而言，0和0、1和1異或的結(jié)果是0，而0和1、1和0的異或結(jié)果是1。接著考慮第二步進位，對0加0、0加1、1加0而言，都不會產(chǎn)生進位，只有1加1時，會向前產(chǎn)生一個進位。此時我們可以想象成是兩個數(shù)先做位與運算，然后再向左移動一位。只有兩個數(shù)都是1的時候，位與得到的結(jié)果是1，其余都是0。第三步把前兩個步驟的結(jié)果相加。如果我們定義一個函數(shù)AddWithoutArithmetic，第三步就相當于輸入前兩步驟的結(jié)果來遞歸調(diào)用自己。
#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/
題目：輸入一個正數(shù)n，輸出所有和為n連續(xù)正數(shù)序列。
例如輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3個連續(xù)序列1-5、4-6和7-8。
分析：這是網(wǎng)易的一道面試題。
這道題和本面試題系列的第10題有些類似。我們用兩個數(shù)small和big分別表示序列的最小值和最大值。首先把small初始化為1，big初始化為2。如果從small到big的序列的和大于n的話，我們向右移動small，相當于從序列中去掉較小的數(shù)字。如果從small到big的序列的和小于n的話，我們向右移動big，相當于向序列中添加big的下一個數(shù)字。一直到small等于(1+n)/2，因為序列至少要有兩個數(shù)字。
基于這個思路，我們可以寫出如下代碼：
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級。求總共有多少總跳法，并分析算法的時間復(fù)雜度。
分析：這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個這道題作為面試題或者筆試題。
首先我們考慮最簡單的情況。如果只有1級臺階，那顯然只有一種跳法。如果有2級臺階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級；另外一種就是一次跳2級。
現(xiàn)在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數(shù)，記為f(n)。當n>2時，第一次跳的時候就有兩種不同的選擇：一是第一次只跳1級，此時跳法數(shù)目等于后面剩下的n-1級臺階的跳法數(shù)目，即為f(n-1)；另外一種選擇是第一次跳2級，此時跳法數(shù)目等于后面剩下的n-2級臺階的跳法數(shù)目，即為f(n-2)。因此n級臺階時的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。
我們把上面的分析用一個公式總結(jié)如下：
/ 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/題目：有一個復(fù)雜鏈表，其結(jié)點除了有一個
m_pNext指針指向下一個結(jié)點外，還有一個m_pSibling指向鏈表中的任一結(jié)點或者NULL。其結(jié)點的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題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。
例如輸入：
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;
}