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