中文字幕无码久久人妻,国产真人无码作爱免

相關(guān)推薦

經(jīng)典算法面試題及答案

1. 時針分針重合幾次

經(jīng)典算法面試題及答案

表面上有60個小格，每小格代表一分鐘，時針每分鐘走1/12小格，分針每分鐘走1小格，從第一次重合到第二次重合分針比時針多走一圈即60小格，所以

60/（1-1/12）=720/11每隔720/11分才重合一次（而并不是每小時重合一次）1440里有22個720/11，如果說算上0點和24點，那也是重合23次而已，但我覺得0點應(yīng)該算到前一天的24點頭上，所以每一天循環(huán)下來重合22次啊

2. 找出字符串的最長不重復(fù)子串，輸出長度建一個256個單元的數(shù)組，每一個單元代表一個字符，數(shù)組中保存上次該字符上次出現(xiàn)的位置；依次讀入字符串，同時維護(hù)數(shù)組的值；如果遇到?jīng)_突了，就返回沖突字符中保存的位置，繼續(xù)第二步。也可以用hashmap保存已經(jīng)出現(xiàn)的字符和字符的位置

3. 說是有一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前十個詞。先用哈希，統(tǒng)計每個詞出現(xiàn)的次數(shù)，然后在用在N個數(shù)中找出前K大個數(shù)的方法找出出現(xiàn)次數(shù)最多的前10個詞。

4. 如題3，但是車次文件特別大，沒有辦法一次讀入內(nèi)存。

1) 直接排序，寫文件時，同時寫入字符串及其出現(xiàn)次數(shù)。

2) 可以用哈希，比如先根據(jù)字符串的第一個字符將字符串換分為多個區(qū)域，每個區(qū)域的字符串寫到一個文件內(nèi)，然后再用哈希+堆統(tǒng)計每個區(qū)域內(nèi)前10個頻率最高的字符串，最后求出所有字符串中前10個頻率最高的字符串。

5. 有一個整數(shù)n，將n分解成若干個整數(shù)之和，問如何分解能使這些數(shù)的乘積最大，輸出這個乘積m。例如：n=12

（1）分解為1+1+1+…+1，12個1, m=1*1*1……*1=1

（2）分解為2+2+…+2，6個2， m=64

（3）分解為3+3+3+3，4個3， m=81

（4）大于等于4時分解時只能分解為2和3，且2最多兩個

f(n) = 3*f(n-3) n>4

f(4) = 2*2

f(3) = 3

f(2) = 2分解為4+4+4，3個4， m=64

6. 求數(shù)組n中出現(xiàn)次數(shù)超過一半的數(shù)

把數(shù)組分成[n/2]組，則至少有一組包含重復(fù)的數(shù)，因為如果無重復(fù)數(shù)，則最多只有出現(xiàn)次數(shù)等于一半的數(shù)。算法如下：

k<-n;

while k>3 do

把數(shù)組分成[k/2]組;

for i=1 to [k/2] do

if 組內(nèi)2個數(shù)相同，則任取一個數(shù)留下;

else 2個數(shù)同時扔掉;

k<-剩下的數(shù)

if k=3

then 任取2個數(shù)進(jìn)行比較;

if 兩個數(shù)不同，則2個數(shù)都扔掉

else 任取一個數(shù)

if k=2 or 1 then 任取一數(shù)

7. A文件中最多有n個正整數(shù)，而且每個數(shù)均小于n，n <=10的七次方。不會出現(xiàn)重復(fù)的數(shù)。

要求對A文件中的數(shù)進(jìn)行排序，可用內(nèi)存為1M，磁盤可用空間足夠。不要把任何問題都往很復(fù)雜的算法上靠，最直接最簡單的解決問題才是工程師應(yīng)有的素質(zhì)，題目給的很有分寸：n個數(shù)，都小于n，兩兩不同，1M=10^6byte=10^7bit的內(nèi)存，n <10^7

思路：

把1M內(nèi)存看作是一個長度為10^7的位數(shù)組，每一位都初始化為0從頭掃描n個數(shù)，如果碰到i，就把位數(shù)組的第i個位置置為1，1M內(nèi)存有點少，（1M = 8M bits), 可以代表8M整數(shù)，現(xiàn)在n <=10的七次方，你可以讀2遍文件，就可以完成排序了。第一次排n <8M得數(shù)，第2遍排 8M <n <10的七次方的數(shù)。

8. 有10億個雜亂無章的數(shù)，怎樣最快地求出其中前1000大的數(shù)。

1) 建一個1000個數(shù)的堆，復(fù)雜度為N*(log1000)=10N

2) 1.用每一個BIT標(biāo)識一個整數(shù)的存在與否，這樣一個字節(jié)可以標(biāo)識8個整數(shù)的存在與否，對于所有32位的整數(shù)，需要512Mb，所以開辟一個512Mb的字符數(shù)組A，初始全0

2.依次讀取每個數(shù)n，將A[n>>3]設(shè)置為A[n>>3]|(1<<n%8)，相當(dāng)于將每個數(shù)的對應(yīng)位設(shè)置為1

3.在A中，從大到小讀取1000個值為1的數(shù)，就是最大的1000個數(shù)了。

這樣讀文件就只需要1遍，在不考慮內(nèi)存開銷的情況下，應(yīng)該是速度最快的方法了。

9. 一棵樹節(jié)點1, 2, 3, ... , n. 怎樣實現(xiàn)：

先進(jìn)行O(n)預(yù)處理，然后任給兩個節(jié)點，用O(1)判斷它們的父子關(guān)系

dfs一遍，記錄每個結(jié)點的開始訪問時間Si和結(jié)束訪問時間Ei對于兩個節(jié)點i,j，若區(qū)間[Si,Ei]包含[Sj,Ej]，則i是j的祖先。給每個節(jié)點哈夫曼編碼也行，但只適合一般的二叉樹，而實際問題未必是Binary的，所以編碼有局限性

10. 給定一個二叉樹，求其中N（N>=2）個節(jié)點的最近公共祖先節(jié)點。每個節(jié)點只有左右孩子指針，沒有父指針。后序遞歸給每個節(jié)點打分，每個節(jié)點的分?jǐn)?shù)=左分?jǐn)?shù)+右分?jǐn)?shù)+k，如果某孩子是給定節(jié)點則+1最深的得分為N的節(jié)點就是所求吧，細(xì)節(jié)上應(yīng)該不用遞歸結(jié)束就可以得到這個節(jié)點

11. 如何打印如下的螺旋隊列：

21 22 。。。。

20 7 8 9 10

19 6 1 2 11

18 5 4 3 12

17 16 15 14 13

#include <stdio.h>

#define max(a,b) ((a)<(b)?(b):(a))

#define abs(a) ((a)>0?(a):-(a))

int foo(int x, int y)

{int t = max(abs(x), abs(y));

int u = t + t;

int v = u - 1;

v = v * v + u;

if (x == -t)

v += u + t - y;

else if (y == -t)

v += 3 * u + x - t;

else if (y == t )

v += t - x;

else

v += y - t;

return v;

}int main()

{int x, y;

for (y=-2;y<=2;y++)

{ for (x=-2;x<=2;x++)

printf("%5d", foo(x, y));

printf("\n");

}return 0;

}第 0 層規(guī)定為中間的那個 1，第 1 層為 2 到 9，第 2 層為 10 到 25，……好像看出一點名堂來了？注意到 1、9、25、……不就是平方數(shù)嗎？而且是連續(xù)奇數(shù)（1、3、5、……）的平方數(shù)。這些數(shù)還跟層數(shù)相關(guān)，推算一下就可以知道第 t 層之內(nèi)一共有 (2t-1)^2 個數(shù)，因而第 t 層會從 [(2t-1)^2] + 1 開始繼續(xù)往外螺旋。給定坐標(biāo) (x,y)，如何知道該點處于第幾層？so easy，層數(shù) t = max(|x|,|y|)。

知道了層數(shù)，接下來就好辦多了，這時我們就知道所求的那點一定在第 t 層這個圈上，順著往下數(shù)就是了。要注意的就是螺旋隊列數(shù)值增長方向和坐標(biāo)軸正方向并不一定相同。我們可以分成四種情況——上、下、左、右——或者——東、南、西、北，分別處于四條邊上來分析。

東|右：x == t，隊列增長方向和 y 軸一致，正東方向（y = 0）數(shù)值為 (2t-1)^2 + t，所以 v = (2t-1)^2 + t + y

南|下：y == t，隊列增長方向和 x 軸相反，正南方向（x ＝ 0）數(shù)值為 (2t-1)^2 + 3t，所以 v ＝ (2t-1)^2 + 3t - x

西|左：x == -t，隊列增長方向和 y 軸相反，正西方向（y ＝ 0）數(shù)值為 (2t-1)^2 + 5t，所以 v = (2t-1)^2 + 5t - y

北|上：y == -t，隊列增長方向和 x 軸一致，正北方向（x ＝ 0）數(shù)值為 (2t-1)^2 + 7t，所以 v ＝ (2t-1)^2 + 7t + x

12. 一個整數(shù)，知道位數(shù)，如何判斷它是否能被3整除，不可以使用除法和模運算

首先 3x=2^n+1時僅當(dāng) n 為奇數(shù)才可能因為2^n = 3x + (-1)^n;所以該問題就轉(zhuǎn)化為了

找到最后一個為1的位a，看看向前的一個1（b）和這個位的距離，如果為偶數(shù)的距離則不能整除，如果是奇數(shù)，去除b之后的位繼續(xù)判斷

13. seq=[a,b,...,z,aa,ab,...,az,ba,bb...,bz,...za,zb,...,zz,aaa...],求[a-z]+(從a到z任意字符組成的字符串)s在seq的位置，即排在第幾

本質(zhì)就是26進(jìn)制。

大家都知道，看一個數(shù)是否能被2整除只需要看它的個位能否被2整除即可。可是你想過為什么嗎？這是因為10能被2整除，因此一個數(shù)10a+b能被2整除當(dāng)且僅當(dāng)b能被2整除。大家也知道，看一個數(shù)能否被3整除只需要看各位數(shù)之和是否能被3整除。這又是為什么呢？答案或多或少有些類似：因為10^n-1總能被3整除。2345可以寫成2*(999+1) + 3*(99+1) + 4*(9+1) + 5，展開就是2*999+3*99+4*9 + 2+3+4+5。前面帶了數(shù)字9的項肯定都能被3整除了，于是要看2345能否被3整除就只需要看2+3+4+5能否被3整除了。當(dāng)然，這種技巧只能在10進(jìn)制下使用，不過類似的結(jié)論可以推廣到任意進(jìn)制。

注意到36是4的整數(shù)倍，而ZZZ...ZZ除以7總是得555...55。也就是說，判斷一個36進(jìn)制數(shù)能否被4整除只需要看它的個位，而一個36進(jìn)制數(shù)能被7整除當(dāng)且僅當(dāng)各位數(shù)之和能被7整除。如果一個數(shù)同時能被4和7整除，那么這個數(shù)就一定能被28整除。于是問題轉(zhuǎn)化為，有多少個連續(xù)句子滿足各位數(shù)字和是7的倍數(shù)，同時最后一個數(shù)是4的倍數(shù)。這樣，我們得到了一個O(n)的算法：用P[i]表示前若干個句子除以7的余數(shù)為i有多少種情況，掃描整篇文章并不斷更新P數(shù)組。當(dāng)某句話的最后一個字能被4整除時，假設(shè)以這句話結(jié)尾的前綴和除以7余x，則將此時P[x]的值累加到最后的輸出結(jié)果中（兩個前綴的數(shù)字和除以7余數(shù)相同，則較長的前綴多出來的部分一定整除7）。

上述算法是我出這道題的本意，但比賽后我見到了其它各種各樣新奇的算法。比如有人注意到36^n mod 28總是等于8，利用這個性質(zhì)也可以構(gòu)造出類似的線性算法來。還有人用動態(tài)規(guī)劃（或者說遞推）完美地解決了這個問題。我們用f[i,j]表示以句子i結(jié)束，除以28余數(shù)為j的文本片段有多少個；處理下一句話時我們需要對每一個不同的j進(jìn)行一次掃描，把f[i-1,j]加進(jìn)對應(yīng)的f[i,j']中。最后輸出所有的f[i,0]的總和即可。這個動態(tài)規(guī)劃可以用滾動數(shù)組，因此它的空間同前面的算法一樣也是常數(shù)的。

如果你完全不知道我在說什么，你可以看看和進(jìn)位制、同余相關(guān)的文章。另外，我之前還曾出過一道很類似的題(VOJ1090)，你可以對比著看一看。

有一個整數(shù)n,寫一個函數(shù)f(n),返回0到n之間出現(xiàn)的"1"的個數(shù)。比如f(13)=6,現(xiàn)在f(1)=1,問有哪些n能滿足f(n)=n？

例如：f(13)=6, 因為1,2,3,4,5,6,7,8,9,10,11,12,13.數(shù)數(shù)1的個數(shù)，正好是6.

public class Test {

public int n = 2;

public int count = 0;

public void BigestNumber(int num) {

for (int i = 1; i <= num; i++) {

int m = 0;

int j = i;

while (j > 0) {

m = j % 10;

if (m == 1)

count++;

if (j > 0)

j = j / 10;

} }System.out.println("f(" + num + ")=" + count);

}public static void main(String args[]) {

Test t = new Test();

long begin = System.currentTimeMillis();

t.BigestNumber(10000000);

long end = System.currentTimeMillis();

System.out.println("總時間" + (end-begin)/1000 + "秒");

} }結(jié)果：

f(10000000)=7000001

總時間5秒

1、將一整數(shù)逆序后放入一數(shù)組中（要求遞歸實現(xiàn)）

void convert(int *result, int n) {

if(n>=10)

convert(result+1, n/10);

*result = n%10;

}int main(int argc, char* argv[]) {

int n = 123456789, result[20]={};

convert(result, n);

printf("%d:", n);

for(int i=0; i<9; i++)

printf("%d", result);

}2、求高于平均分的學(xué)生學(xué)號及成績（學(xué)號和成績?nèi)斯ぽ斎耄?/p>

double find(int total, int n) {

int number, score, average;

scanf("%d", &number);

if(number != 0) {

scanf("%d", &score);

average = find(total+score, n+1);

if(score >= average)

printf("%d:%d\n", number, score);

return average;

} else {

printf("Average=%d\n", total/n);

return total/n;

} }int main(int argc, char* argv[]) {

find(0, 0);

}3、遞歸實現(xiàn)回文判斷（如：abcdedbca就是回文，判斷一個面試者對遞歸理解的簡單程序）

int find(char *str, int n) {

if(n<=1) return 1;

else if(str[0]==str[n-1]) return find(str+1, n-2);

else return 0;

}int main(int argc, char* argv[]) {

char *str = "abcdedcba";

printf("%s: %s\n", str, find(str, strlen(str)) ? "Yes" : "No");

}4、組合問題（從M個不同字符中任取N個字符的所有組合）

void find(char *source, char *result, int n) {

if(n==1) {

while(*source)

printf("%s%c\n", result, *source++);

} else {

int i, j;

for(i=0; source != 0; i++);

for(j=0; result[j] != 0; j++);

for(; i>=n; i--) {

result[j] = *source++;

result[j+1] = '\0';

find(source, result, n-1);

} } }int main(int argc, char* argv[]) {

int const n = 3;

char *source = "ABCDE", result[n+1] = {0};

if(n>0 && strlen(source)>0 && n<=strlen(source))

find(source, result, 3);

}5、分解成質(zhì)因數(shù)(如435234=251*17*17*3*2，據(jù)說是華為筆試題)

void prim(int m, int n) {

if(m>n) {

while(m%n != 0) n++;

m /= n;

prim(m, n);

printf("%d*", n);

} }int main(int argc, char* argv[]) {

int n = 435234;

printf("%d=", n);

prim(n, 2);

}6、尋找迷宮的一條出路，o：通路； X：障礙。（大家經(jīng)常談到的一個小算法題）

#define MAX_SIZE 8

int H[4] = {0, 1, 0, -1};

int V[4] = {-1, 0, 1, 0};

char Maze[MAX_SIZE][MAX_SIZE] = {{'X','X','X','X','X','X','X','X'},

{'o','o','o','o','o','X','X','X'},

{'X','o','X','X','o','o','o','X'},

{'X','o','X','X','o','X','X','o'},

{'X','o','X','X','X','X','X','X'},

{'X','o','X','X','o','o','o','X'},

{'X','o','o','o','o','X','o','o'},

{'X','X','X','X','X','X','X','X'}};

void FindPath(int X, int Y) {

if(X == MAX_SIZE || Y == MAX_SIZE) {

for(int i = 0; i < MAX_SIZE; i++)

for(int j = 0; j < MAX_SIZE; j++)

printf("%c%c", Maze[j], j < MAX_SIZE-1 ? ' ' : '\n');

}else for(int k = 0; k < 4; k++)

if(X >= 0 && Y >= 0 && Y < MAX_SIZE && X < MAX_SIZE && 'o' == Maze[X][Y]) {

Maze[X][Y] = ' ';

FindPath(X+V[k], Y+H[k]);

Maze[X][Y] ='o';

} }int main(int argc, char* argv[]) {

FindPath(1,0);

}7、隨機(jī)分配座位，共50個學(xué)生，使學(xué)號相鄰的同學(xué)座位不能相鄰(早些時候用C#寫的，沒有用C改寫）。

static void Main(string[] args)

{ int Tmp = 0, Count = 50;

int[] Seats = new int[Count];

bool[] Students = new bool[Count];

System.Random RandStudent=new System.Random();

Students[Seats[0]=RandStudent.Next(0,Count)]=true;

for(int i = 1; i < Count; ) {

Tmp=(int)RandStudent.Next(0,Count);

if((!Students[Tmp])&&(Seats[i-1]-Tmp!=1) && (Seats[i-1] - Tmp) != -1) {

Seats[i++] = Tmp;

Students[Tmp] = true;

} } foreach(int Student in Seats)

http://emrowgh.comnsole.Write(Student + " ");

http://emrowgh.comnsole.Read();

}8、求網(wǎng)格中的黑點分布�，F(xiàn)有6*7的網(wǎng)格，在某些格子中有黑點，已知各行與各列中有黑點的點數(shù)之和，請在這張網(wǎng)格中畫出黑點的位置。（這是一網(wǎng)友提出的題目，說是他筆試時遇到算法題）

#define ROWS 6

#define COLS 7

int iPointsR[ROWS] = {2, 0, 4, 3, 4, 0}; // 各行黑點數(shù)和的情況

int iPointsC[COLS] = {4, 1, 2, 2, 1, 2, 1}; // 各列黑點數(shù)和的情況

int iCount, iFound;

int iSumR[ROWS], iSumC[COLS], Grid[ROWS][COLS];

int Set(int iRowNo) {

if(iRowNo == ROWS) {

for(int iColNo=0; iColNo < COLS && iSumC[iColNo]==iPointsC[iColNo]; iColNo++)

if(iColNo == COLS-1) {

printf("\nNo.%d:\n", ++iCount);

for(int i=0; i < ROWS; i++)

for(int j=0; j < COLS; j++)

printf("%d%c", Grid[j], (j+1) % COLS ? ' ' : '\n');

iFound = 1; // iFound = 1，有解

} } else {

for(int iColNo=0; iColNo < COLS; iColNo++) {

if(iPointsR[iRowNo] == 0) {

Set(iRowNo + 1);

} else if(Grid[iRowNo][iColNo]==0) {

Grid[iRowNo][iColNo] = 1;

iSumR[iRowNo]++; iSumC[iColNo]++; if(iSumR[iRowNo]<iPointsR[iRowNo] && iSumC[iColNo]<=iPointsC[iColNo])

Set(iRowNo);

else if(iSumR[iRowNo]==iPointsR[iRowNo] && iRowNo < ROWS)

Set(iRowNo + 1);

Grid[iRowNo][iColNo] = 0;

iSumR[iRowNo]--;

iSumC[iColNo]--;

} } }return iFound; // 用于判斷是否有解

}int main(int argc, char* argv[]) {

if(!Set(0))

printf("Failure!");

}9、有4種面值的郵票很多枚，這4種郵票面值分別1, 4, 12, 21，現(xiàn)從多張中最多任取5張進(jìn)行組合，求取出這些郵票的最大連續(xù)組合值。（據(jù)說是華為2003年校園招聘筆試題）

#define N 5

#define M 5

int k, Found, Flag[N];

int Stamp[M] = {0, 1, 4, 12, 21};

// 在剩余張數(shù)n中組合出面值和Value

int Combine(int n, int Value) {

if(n >= 0 && Value == 0) {

Found = 1;

int Sum = 0;

for(int i=0; i<N && Flag != 0; i++) {

Sum += Stamp[Flag];

printf("%d ", Stamp[Flag]);

} printf("\tSum=%d\n\n", Sum);

}else for(int i=1; i<M && !Found && n>0; i++)

if(Value-Stamp >= 0) {

Flag[k++] = i;

Combine(n-1, Value-Stamp);

Flag[--k] = 0;

} return Found;

}int main(int argc, char* argv[]) {

for(int i=1; Combine(N, i); i++, Found=0);

}10、大整數(shù)數(shù)相乘的問題。（這是2002年在一考研班上遇到的算法題）

void Multiple(char A[], char B[], char C[]) {

int TMP, In=0, LenA=-1, LenB=-1;

while(A[++LenA] != '\0');

while(B[++LenB] != '\0');

int Index, Start = LenA + LenB - 1;

for(int i=LenB-1; i>=0; i--) {

Index = Start--;

if(B != '0') {

for(int In=0, j=LenA-1; j>=0; j--) {

TMP = (C[Index]-'0') + (A[j]-'0') * (B - '0') + In;

C[Index--] = TMP % 10 + '0';

In = TMP / 10;

} C[Index] = In + '0';

} } }int main(int argc, char* argv[]) {

char A[] = "21839244444444448880088888889";

char B[] = "38888888888899999999999999988";

char C[sizeof(A) + sizeof(B) - 1];

for(int k=0; k<sizeof(C); k++)

C[k] = '0';

C[sizeof(C)-1] = '\0';

Multiple(A, B, C);

for(int i=0; C != '\0'; i++)

printf("%c", C);

}11、求最大連續(xù)遞增數(shù)字串（如“ads3sl456789DF3456ld345AA”中的“456789”）

int GetSubString(char *strSource, char *strResult) {

int iTmp=0, iHead=0, iMax=0;

for(int Index=0, iLen=0; strSource[Index]; Index++) {

if(strSource[Index] >= '0' && strSource[Index] <= '9' &&

strSource[Index-1] > '0' && strSource[Index] == strSource[Index-1]+1) {

iLen++; // 連續(xù)數(shù)字的長度增1

} else { // 出現(xiàn)字符或不連續(xù)數(shù)字

if(iLen > iMax) {

iMax = iLen; iHead = iTmp;

} // 該字符是數(shù)字，但數(shù)字不連續(xù)

if(strSource[Index] >= '0' && strSource[Index] <= '9') {

iTmp = Index;

iLen = 1;

} } } for(iTmp=0 ; iTmp < iMax; iTmp++) // 將原字符串中最長的連續(xù)數(shù)字串賦值給結(jié)果串

strResult[iTmp] = strSource[iHead++];

strResult[iTmp]='\0';

return iMax; // 返回連續(xù)數(shù)字的最大長度

}int main(int argc, char* argv[]) {

char strSource[]="ads3sl456789DF3456ld345AA", char strResult[sizeof(strSource)];

printf("Len=%d, strResult=%s \nstrSource=%s\n",

GetSubString(strSource, strResult), strResult, strSource);

}12、四個工人，四個任務(wù)，每個人做不同的任務(wù)需要的時間不同，求任務(wù)分配的最優(yōu)方案。（2015年5月29日全國計算機(jī)軟件資格水平考試——軟件設(shè)計師的算法題）。

#include "stdafx.h"

#define N 4

int Cost[N][N] = { {2, 12, 5, 32}, // 行號：任務(wù)序號，列號：工人序號

{8, 15, 7, 11}, // 每行元素值表示這個任務(wù)由不同工人完成所需要的時間

{24, 18, 9, 6},

{21, 1, 8, 28}};

int MinCost=1000;

int Task[N], TempTask[N], Worker[N];

void Assign(int k, int cost) {

if(k == N) {

MinCost = cost;

for(int i=0; i<N; i++)

TempTask = Task;

} else {

for(int i=0; i<N; i++) {

if(Worker==0 && cost+Cost[k] < MinCost) { // 為提高效率而進(jìn)行剪枝

Worker = 1; Task[k] = i;

Assign(k+1, cost+Cost[k]);

Worker = 0; Task[k] = 0;

} } } }int main(int argc, char* argv[]) {

Assign(0, 0);

printf("最佳方案總費用=%d\n", MinCost);

for(int i=0; i<N; i++)

printf("\t任務(wù)%d由工人%d來做：%d\n", i, TempTask, Cost[TempTask]);

}13、八皇后問題，輸出了所有情況，不過有些結(jié)果只是旋轉(zhuǎn)了90度而已。（回溯算法的典型例題，是數(shù)據(jù)結(jié)構(gòu)書上算法的具體實現(xiàn)，大家都親自動手寫過這個程序嗎？）

#define N 8

int Board[N][N];

int Valid(int i, int j) { // 判斷下棋位置是否有效

int k = 1;

for(k=1; i>=k && j>=k;k++)

if(Board[i-k][j-k]) return 0;

for(k=1; i>=k;k++)

if(Board[i-k][j]) return 0;

for(k=1; i>=k && j+k<N;k++)

if(Board[i-k][j+k]) return 0;

return 1;

}void Trial(int i, int n) { // 尋找合適下棋位置

if(i == n) {

for(int k=0; k<n; k++) {

for(int m=0; m<n; m++)

printf("%d ", Board[k][m]);

printf("\n");

} printf("\n");

} else {

for(int j=0; j<n; j++) {

Board[j] = 1;

if(Valid(i,j))

Trial(i+1, n);

Board[j] = 0;

} } }int main(int argc, char* argv[]) {

Trial(0, N);

}14、實現(xiàn)strstr功能，即在父串中尋找子串首次出現(xiàn)的位置。（筆試中常讓面試者實現(xiàn)標(biāo)準(zhǔn)庫中的一些函數(shù)）

char * strstring(char *ParentString, char *SubString) {

char *pSubString, *pPareString;

for(char *pTmp=ParentString; *pTmp; pTmp++) {

pSubString = SubString;

pPareString = pTmp;

while(*pSubString == *pPareString && *pSubString != '\0') {

pSubString++;

pPareString++;

} if(*pSubString == '\0') return pTmp;

} return NULL;

}int main(int argc, char* argv[]) {

char *ParentString = "happy birthday to you!";

char *SubString = "birthday";

printf("%s",strstring(ParentString, SubString));

}15、現(xiàn)在小明一家過一座橋，過橋的時候是黑夜，所以必須有燈。現(xiàn)在小明過橋要1分，小明的弟弟要3分，小明的爸爸要6分，小明的媽媽要8分，小明的爺爺要12分。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點燃后30分就會熄滅。問小明一家如何過橋時間最短？（原本是個小小智力題，據(jù)說是外企的面試題，在這里用程序來求解）

#include "stdafx.h"

#define N 5

#define SIZE 64

// 將人員編號：小明-0，弟弟-1，爸爸-2，媽媽-3，爺爺-4

// 每個人的當(dāng)前位置：0--在橋左邊， 1--在橋右邊

int Position[N];

// 過橋臨時方案的數(shù)組下標(biāo)；臨時方案；最小時間方案；

int Index, TmpScheme[SIZE], Scheme[SIZE];

// 最小過橋時間總和，初始值100；每個人過橋所需要的時間

int MinTime=100, Time[N]={1, 3, 6, 8, 12};

// 尋找最佳過橋方案。Remnant:未過橋人數(shù); CurTime:當(dāng)前已用時間;

// Direction:過橋方向,1--向右,0--向左

void Find(int Remnant, int CurTime, int Direction) {

if(Remnant == 0) { // 所有人已經(jīng)過橋，更新最少時間及方案

MinTime=CurTime;

for(int i=0; i<SIZE && TmpScheme>=0; i++)

Scheme = TmpScheme;

} else if(Direction == 1) { // 過橋方向向右，從橋左側(cè)選出兩人過橋

for(int i=0; i<N; i++)

if(Position == 0 && CurTime + Time < MinTime) {

TmpScheme[Index++] = i;

Position = 1;

for(int j=0; j<N; j++) {

int TmpMax = (Time > Time[j] ? Time : Time[j]);

if(Position[j] == 0 && CurTime + TmpMax < MinTime) {

TmpScheme[Index++] = j;

Position[j] = 1;

Find(Remnant - 2, CurTime + TmpMax, !Direction);

Position[j] = 0;

TmpScheme[--Index] = -1;

} } Position = 0;

TmpScheme[--Index] = -1;

} } else { // 過橋方向向左，從橋右側(cè)選出一個人回來送燈

for(int j=0; j<N; j++) {

if(Position[j] == 1 && CurTime+Time[j] < MinTime) {

TmpScheme[Index++] = j;

Position[j] = 0;

Find(Remnant+1, CurTime+Time[j], !Direction);

Position[j] = 1;

TmpScheme[--Index] = -1;

} } } }int main(int argc, char* argv[]) {

for(int i=0; i<SIZE; i++) // 初始方案內(nèi)容為負(fù)值，避免和人員標(biāo)號沖突

Scheme = TmpScheme = -1;

Find(N, 0, 1); // 查找最佳方案

printf("MinTime=%d:", MinTime); // 輸出最佳方案

for(int i=0; i<SIZE && Scheme>=0; i+=3)

printf(" %d-%d %d", Scheme, Scheme[i+1], Scheme[i+2]);

printf("\b\b ");

算法面試：精選微軟經(jīng)典的算法2015-11-01 15:24 | #2樓

1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表

題目：

輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。

要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。

/ /

6 14

/ / / /

4 8 12 16

轉(zhuǎn)換成雙向鏈表

4=6=8=10=12=14=16。

首先我們定義的二元查找樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：

struct BSTreeNode

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

2.設(shè)計包含min函數(shù)的棧。

定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。

要求函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。

3.求子數(shù)組的最大和

題目：

輸入一個整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。

數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。

求所有子數(shù)組的和的最大值。要求時間復(fù)雜度為O(n)。

例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，

因此輸出為該子數(shù)組的和18。

4.在二元樹中找出和為某一值的所有路徑

題目：輸入一個整數(shù)和一棵二元樹。

從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。

打印出和與輸入整數(shù)相等的所有路徑。

例如輸入整數(shù)22和如下二元樹

/ /

5 12

/ /

4 7

則打印出兩條路徑：10, 12和10, 5, 7。

二元樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義為：

struct BinaryTreeNode // a node in the binary tree

{

int m_nValue; // value of node

BinaryTreeNode *m_pLeft; // left child of node

BinaryTreeNode *m_pRight; // right child of node

};

5.查找最小的k個元素

題目：輸入n個整數(shù)，輸出其中最小的k個。

例如輸入1，2，3，4，5，6，7和8這8個數(shù)字，則最小的4個數(shù)字為1，2，3和4。

第6題

騰訊面試題：

給你10分鐘時間，根據(jù)上排給出十個數(shù)，在其下排填出對應(yīng)的十個數(shù) 要求下排每個數(shù)都是先前上排那十個數(shù)在下排出現(xiàn)的次數(shù)。

上排的十個數(shù)如下：

【0，1，2，3，4，5，6，7，8，9】

初看此題，貌似很難，10分鐘過去了，可能有的人，題目都還沒看懂。

舉一個例子，

數(shù)值: 0,1,2,3,4,5,6,7,8,9

分配: 6,2,1,0,0,0,1,0,0,0

0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次，

2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次....

以此類推..

昨天，花了一個下午，用c++實現(xiàn)了此題。(*^__^*)

第7題

微軟亞院之編程判斷倆個鏈表是否相交給出倆個單向鏈表的頭指針，比如h1，h2，判斷這倆個鏈表是否相交。為了簡化問題，我們假設(shè)倆個鏈表均不帶環(huán)。

問題擴(kuò)展：

1.如果鏈表可能有環(huán)列?

2.如果需要求出倆個鏈表相交的第一個節(jié)點列?

第8題

此貼選一些比較怪的題，，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。

1.有兩個房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個開關(guān)，這兩個房間是分割開的，從一間里不能看到另一間的情況�，F(xiàn)在要求受訓(xùn)者分別進(jìn)這兩房間一次，然后判斷出這三盞燈分別是由哪個開關(guān)控制的。有什么辦法呢？

2.你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。如果你只能將金條切割兩次，你怎樣分給這些工人?

3.★鏈接表和數(shù)組之間的區(qū)別是什么?

★做一個鏈接表，你為什么要選擇這樣的方法?

★選擇一種算法來整理出一個鏈接表。你為什么要選擇這種方法?現(xiàn)在用O(n)時間來做。

★說說各種股票分類算法的優(yōu)點和缺點。

★用一種算法來顛倒一個鏈接表的順序�，F(xiàn)在在不用遞歸式的情況下做一遍。

★用一種算法在一個循環(huán)的鏈接表里插入一個節(jié)點，但不得穿越鏈接表。

★用一種算法整理一個數(shù)組。你為什么選擇這種方法?

★用一種算法使通用字符串相匹配。

★顛倒一個字符串。優(yōu)化速度。優(yōu)化空間。

★顛倒一個句子中的詞的順序，比如將“我叫克麗絲”轉(zhuǎn)換為“克麗絲叫我”，實現(xiàn)速度最快，移動最少。

★找到一個子字符串。優(yōu)化速度。優(yōu)化空間。

★比較兩個字符串，用O(n)時間和恒量空間。

★假設(shè)你有一個用1001個整數(shù)組成的數(shù)組，這些整數(shù)是任意排列的，但是你知道所有的整數(shù)都在1到1000(包括1000)之間。此外，除一個數(shù)字出現(xiàn)兩次外，其他所有數(shù)字只出現(xiàn)一次。假設(shè)你只能對這個數(shù)組做一次處理，用一種算法找出重復(fù)的那個數(shù)字。如果你在運算中使用了輔助的存儲方式，那么你能找到不用這種方式的算法嗎?

★不用乘法或加法增加8倍�，F(xiàn)在用同樣的方法增加7倍。

第9題

判斷整數(shù)序列是不是二元查找樹的后序遍歷結(jié)果

題目：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。

如果是返回true，否則返回false。

例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：

/ /

6 10

/ / / /

5 7 9 11

因此返回true。

如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回false。

第10題

翻轉(zhuǎn)句子中單詞的順序。

題目：輸入一個英文句子，翻轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符的順序不變。句子中單詞以空格符隔開。

為簡單起見，標(biāo)點符號和普通字母一樣處理。

例如輸入“I am a student.”，則輸出“student. a am I”。

第11題

求二叉樹中節(jié)點的最大距離...如果我們把二叉樹看成一個圖，父子節(jié)點之間的連線看成是雙向的，我們姑且定義"距離"為兩節(jié)點之間邊的個數(shù)。寫一個程序，

求一棵二叉樹中相距最遠(yuǎn)的兩個節(jié)點之間的距離。

第12題

題目：求1+2+…+n，

要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語句（A?B:C）。

第13題：

題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。鏈表結(jié)點定義如下：

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

第14題：

題目：輸入一個已經(jīng)按升序排序過的數(shù)組和一個數(shù)字，在數(shù)組中查找兩個數(shù)，使得它們的和正好是輸入的那個數(shù)字。要求時間復(fù)雜度是O(n)。如果有多對數(shù)字的和等于輸入的數(shù)字，輸出任意一對即可。例如輸入數(shù)組1、2、4、7、11、15和數(shù)字15。由于4+11=15，因此輸出4和11。

第15題：

題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。

例如輸入：

/ /

6 10

// //

5 7 9 11

輸出：

/ /

10 6

// //

11 9 7 5

定義二元查找樹的結(jié)點為：

struct BSTreeNode // a node in the binary search tree (BST)

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

第16題：

題目（微軟）：

輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點，同一層中按照從左往右的順序打印。

例如輸入

/ /

6 10

/ / / /

5 7 9 11

輸出8 6 10 5 7 9 11。

第17題：

題目：在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。

分析：這道題是2015年google的一道筆試題。

第18題：

題目：n個數(shù)字（0,1,…,n-1）形成一個圓圈，從數(shù)字0開始，

每次從這個圓圈中刪除第m個數(shù)字（第一個為當(dāng)前數(shù)字本身，第二個為當(dāng)前數(shù)字的下一個數(shù)字）。當(dāng)一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第m個數(shù)字。求出在這個圓圈中剩下的最后一個數(shù)字。

July：我想，這個題目，不少人已經(jīng) 見識過了。

第19題：

題目：定義Fibonacci數(shù)列如下：

/ 0 n=0

f(n)= 1 n=1

/ f(n-1)+f(n-2) n=2

輸入n，用最快的方法求該數(shù)列的第n項。

分析：在很多C語言教科書中講到遞歸函數(shù)的時候，都會用Fibonacci作為例子。因此很多程序員對這道題的遞歸解法非常熟悉，但....呵呵，你知道的。。

第20題：

題目：輸入一個表示整數(shù)的字符串，把該字符串轉(zhuǎn)換成整數(shù)并輸出。

例如輸入字符串"345"，則輸出整數(shù)345。

【經(jīng)典算法面試題及答案】相關(guān)文章：