摘要: 題目描述：請(qǐng)問(wèn)下面的兩個(gè)程序各一共輸出多少個(gè)“-”？#include <stdio.h>#include <sys/types.h>#include <unistd.h>int main(void){ int i; for(i=0; i<2; i++) { fork(); printf('-'); } return 0;}#include <stdio.h>#include <sys/types.h>#include <unistd.h>int main(void){ int i; for(i=0閱讀全文

摘要: 題目描述：輸入一個(gè)正整數(shù)數(shù)組，將它們連接起來(lái)排成一個(gè)數(shù)，輸出能排出的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{32, 321}，則輸出這兩個(gè)能排成的最小數(shù)字32132。請(qǐng)給出解決問(wèn)題的算法，并證明該算法。解析：對(duì)數(shù)組進(jìn)行排序，排序規(guī)則：當(dāng)兩個(gè)數(shù)進(jìn)行比較時(shí)，現(xiàn)將他們轉(zhuǎn)壞為char數(shù)組，然后用兩個(gè)char指針挨個(gè)字符進(jìn)行比較，當(dāng)其中一個(gè)為正常字符，而另一個(gè)為‘\0’，則后者指針回溯第一個(gè)字符，直到找到第一個(gè)不相同的字符，字符大者的對(duì)應(yīng)數(shù)為大，或者當(dāng)兩者指針對(duì)應(yīng)字符皆為‘\0’時(shí)，此時(shí)證明兩個(gè)數(shù)字”相等“。具體實(shí)現(xiàn)，見(jiàn)下面參考代碼：參考代碼：#include <iostream>#includ閱讀全文

摘要: 題目描述:輸入一個(gè)字符串，打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc，則輸出由字符a、b、c所能排列出來(lái)的所有字符串a(chǎn)bc、acb、bac、bca、cab和cba。解析：遞歸法：首先看最后兩個(gè)字符b, c。 它們的全排列為b c和c b, 即以b開(kāi)頭的c的全排列和以c開(kāi)頭的b的全排列。再看三個(gè)字符a，b，c。他們的全排列（a，b，c）、（a，c，b）、（b，a，c）、（b，c，a）、（c，a，b）、（c，b，a）從而可以推斷，設(shè)一組數(shù)p = {r1, r2, r3, ... ,rn}, 全排列為perm(p)，pn = p - {rn}。因此perm(p) = r1perm(p1),閱讀全文

摘要: 題目描述：如何對(duì)n個(gè)數(shù)進(jìn)行排序，要求時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)解析：利用計(jì)數(shù)排序法，設(shè)置一大小為65536的int數(shù)組，范圍a[0]~a[65535]，并初始為0，然后遍歷n個(gè)數(shù)，假設(shè)這n個(gè)數(shù)在數(shù)組array[0...n-1]中，則i取值從0到n-1同時(shí)執(zhí)行a[array[i]]++，最后再依照順序讀數(shù)組a，遇到不為0時(shí)，將對(duì)應(yīng)的下標(biāo)讀回?cái)?shù)組array，計(jì)數(shù)是幾次就讀幾次，覆蓋原有數(shù)，這樣得出的array即為排序所求因?yàn)榭臻g復(fù)雜度大小已知，為65536，執(zhí)行循環(huán)次數(shù)約為n+65536 ，所以其空間復(fù)雜度為O(n)，空間復(fù)雜度O(1),代碼略閱讀全文

摘要: 題目描述：一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。解析：很多解法的時(shí)間復(fù)雜度都停留在O(n)，下面的解法 仍為二分查找法 只不過(guò) 對(duì)應(yīng)題目做了相應(yīng)的改進(jìn) 時(shí)間復(fù)雜度為O(log2n)1.思路：(畫(huà)圖實(shí)際上更直觀看出來(lái)思路，讀者試著自己畫(huà)出圖來(lái)對(duì)應(yīng)分析)設(shè)數(shù)組a[start]~a[end],mid = (start + end) / 2 在進(jìn)行二叉查找時(shí)，待查找數(shù)肯定會(huì)在變量mid的兩側(cè)，其中mid的取值主要有以下幾情況，第一種為a[mid] < a[start] 說(shuō)明此時(shí)mid對(duì)應(yīng)的數(shù)閱讀全文

摘要: 題目描述：輸入一個(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。分析：來(lái)源于互聯(lián)網(wǎng) 以下僅給出思路解法一：兩個(gè)for循環(huán)解決，復(fù)雜度O(n2)解法二：因?yàn)檎麛?shù)序列有序，可以設(shè)立兩個(gè)游標(biāo)satrt,end，通過(guò)判區(qū)間[start,end]的和是否為n來(lái)得到這個(gè)序列。如果區(qū)間和大于n,start往前移動(dòng)，如果小于n,end往前移動(dòng)，等于就輸出這個(gè)區(qū)間。時(shí)間復(fù)雜度是0(n).解法三：假設(shè)start + (start + 1) + ... +end = n 是一個(gè)答案，則根據(jù)求和公式就是 (start +閱讀全文

摘要: 源于網(wǎng)絡(luò)1.如何判斷單鏈表里面是否有環(huán)？設(shè)置兩個(gè)指針(fast, slow)，初始值都指向頭，slow每次前進(jìn)一步，fast每次前進(jìn)二步，如果鏈表存在環(huán)，則fast必定先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)，兩個(gè)指針必定相遇。(當(dāng)然，fast先行頭到尾部為NULL，則為無(wú)環(huán)鏈表)程序如下：bool IsExitsLoop(slist *head){ slist *slow = head, *fast = head; while ( fast && fast->next ) { slow = slow->next; fast = fast->next->ne...閱讀全文

摘要: 題目：給你n個(gè)數(shù)，其中有且僅有一個(gè)數(shù)出現(xiàn)了奇數(shù)次，其余的數(shù)都出現(xiàn)了偶數(shù)次。用線性時(shí)間常數(shù)空間找出出現(xiàn)了奇數(shù)次的那一個(gè)數(shù)。給你n個(gè)數(shù)，其中有且僅有兩個(gè)數(shù)出現(xiàn)了奇數(shù)次，其余的數(shù)都出現(xiàn)了偶數(shù)次。用線性時(shí)間常數(shù)空間找出出現(xiàn)了奇數(shù)次的那兩個(gè)數(shù)。答案：從頭到尾異或一遍，最后得到的那個(gè)數(shù)就是出現(xiàn)了奇數(shù)次的數(shù)。這是因?yàn)楫惢蛴幸粋€(gè)神奇的性質(zhì)：兩次異或同一個(gè)數(shù)，結(jié)果不變。再考慮到異或運(yùn)算滿足交換律，先異或和后異或都是一樣的，因此這個(gè)算法顯然正確。從頭到尾異或一遍，你就得到了需要求的兩個(gè)數(shù)異或后的值。這兩個(gè)數(shù)顯然不相等，異或出來(lái)的結(jié)果不為0。我們可以據(jù)此找出兩個(gè)數(shù)的二進(jìn)制表達(dá)中不同的一位(即找出所有結(jié)果的二進(jìn)制形式閱讀全文

摘要: 算法設(shè)計(jì)：后續(xù)遍歷此二叉樹(shù)，將兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)分別放入兩個(gè)鏈表中，然后順序?qū)Ρ?，找出最后一個(gè)相同的節(jié)點(diǎn)，既是最低共同節(jié)點(diǎn)C偽碼實(shí)現(xiàn)：List *h,*h1,*h2;bool find1=false,find2=false;void postVisit(BTNode *root){ if(root!=null) { add(root,h); //將root結(jié)點(diǎn)加入以h為表頭的鏈表中 postVisit(root->lchild); if(root->lchild!=NULL)...閱讀全文

摘要: 代碼編寫(xiě)完成函數(shù)： int maxnumstr(char *inputstr, char *outputstr) 函數(shù)功能：找出inputstr中的最長(zhǎng)連續(xù)數(shù)字串存儲(chǔ)到outputstr里并返回長(zhǎng)度，如調(diào)用maxnumstr('123abc1234a', outputstr)后返回4且outputstr中為'1234'。代碼實(shí)現(xiàn)：（未驗(yàn)證正確性）int maxnumstr(char *inputstr, char *outputstr){ int i,j,count,max=-1; char *p,*pmax; for(i=0;inputstr[i]!=閱讀全文

摘要: 算法設(shè)計(jì)某大型項(xiàng)目由n個(gè)組件N1, N2……Nn構(gòu)成，每個(gè)組件都可以獨(dú)立編譯，但是某些組件的編譯依賴(lài)于其它組件（即某些組件只能在其它組件編譯完成后才能編譯），設(shè)計(jì)算法給出統(tǒng)計(jì)過(guò)程。思路：拓?fù)渑判蛩惴ㄕZ(yǔ)言偽代碼：(1)初始化棧S(2)找出所有可執(zhí)行的組件w，w進(jìn)棧(3)while(棧S非空) v=棧頂元素出棧; if（v未被編譯） 編譯v，并且輸出v； foreach（更新與v相關(guān)的組件依賴(lài)參數(shù)） if(x=組件可被編譯) x進(jìn)棧；C偽碼：void compileModel...閱讀全文

摘要: 2、二重哥德巴赫猜想每個(gè)不小于6的偶數(shù)都可以表示為兩個(gè)素?cái)?shù)之和編寫(xiě)一個(gè)函數(shù)，輸出6-100000內(nèi)所有偶數(shù)可以表示為哪兩個(gè)素?cái)?shù)之和，如果一個(gè)偶素有多種表示方式，輸出任意一種即可。代碼實(shí)現(xiàn)（僅供參考）：int ispri(int num){ for(int k=2;k<=num/2;k++) { if(!num%k) return 0; } return 1;}void judge(int number){ for(int j=1;j<number;j++) { if(ispri(j)) { ...閱讀全文

摘要: 1.問(wèn)題描述有一個(gè)單入口，單出口的有向無(wú)環(huán)圖。給出一個(gè)算法，在已有結(jié)點(diǎn)之間插入若干結(jié)點(diǎn)，使得從入口結(jié)點(diǎn)到出口結(jié)點(diǎn)經(jīng)過(guò)的任意路徑長(zhǎng)度一致，詳細(xì)描述你的算法思路，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。2.算法思路首先深度遍歷，計(jì)算出入口到出口的最長(zhǎng)路徑，然后重新深度遍歷，遍歷到出口節(jié)點(diǎn)之前計(jì)算此路徑長(zhǎng)度，如果計(jì)算出小于最長(zhǎng)路徑則插入節(jié)點(diǎn)，使這個(gè)路徑等于最長(zhǎng)路徑。3.算法實(shí)現(xiàn)：(僅供參考)struct Edge{ VPoint *dest; Edge *next;}struct VPoint{ int id; int weight; Edge *adj;}int longe...閱讀全文

摘要: 算法設(shè)計(jì)給定一個(gè)數(shù)字編碼N，大多數(shù)情況下可以找到一個(gè)數(shù)字編碼M，其位數(shù)與編碼N相等(編碼可以從0開(kāi)始)，各位數(shù)字之和與編碼N中各位數(shù)字之和相等，并且M是數(shù)值大于N的所有碼中最小的一個(gè)，也可能要找的編碼M不存在。如給定編碼N=134,則編碼M=143;給定編碼N=020,則編碼M=101，形式化表述為f(N)=M,如果M不存在，則f(N)=-1。現(xiàn)在給定一個(gè)起始編碼N， N的數(shù)字位數(shù)最大不超過(guò)1000，N 的數(shù)值最大不超過(guò)10^500，要求給出序列S(N)，其中S(0)=N，S(1)=f(N)，S(2)=f(S(1))，S(3)=f(S(2))...，當(dāng)S(i+1)<0時(shí)序列結(jié)束，但小于0閱讀全文

摘要: 算法題目：求一個(gè)全排列函數(shù)：如p([1,2,3])輸出：[123],[132],[213],[231],[321],[323].思路：采用字典序的排序的方法代碼實(shí)現(xiàn)：void swap(char *a,char *b){ char temp; temp=*a; *a=*b; *b=temp;}void reverse(char *dic ,int start,int end){ int i=start,j=end; for(;i<=j;i++,j--) swap(dic[i],dic[j]);}void perm (char *...閱讀全文

摘要: 題目算法設(shè)計(jì)一個(gè)一維數(shù)軸上有不同的線段，求重復(fù)最長(zhǎng)的兩個(gè)線段。例： a： 1~3b: 2~7c： 2~8最長(zhǎng)重復(fù)是b和c算法設(shè)計(jì)（偽代碼 僅供參考）typedef struct{ char id; int start; //如果無(wú)序 可以先按照start從小到大排序 int end;}Span;char reid1,reid2;void maxspan(Span *sp,int size) //線段有序{ int i,j,maxspan=-1; char id1,id2,tempmin; for(i=0;i<si...閱讀全文