C語言練習（5月17日更新）

題目來源：

算法面試：精選微軟經典的算法面試100題（第1-20題） 釋出時間：2010-10-11 18:56 算法面試：精選微軟經典的算法面試100題 引言： 給你10分鐘時間，根據上排給出十個數，在其下排填出對應的十個數 要求下排每個數都是先前上排那十個數在下排出現的次數。 上排的十個數如下： 【0，1，2，3，4，5，6，7，8，9】 舉一個例子， 數值:0,1,2,3,4,5,6,7,8,9 配置設定:6,2,1,0,0,0,1,0,0,0 0在下排出現了6次，1在下排出現了2次， 2在下排出現了1次，3在下排出現了0次.... 以此類推.. 算法面試：精選微軟等公司經典的算法面試100題 第1-20題 如下： --------------- -------------- 1.把二進制查找樹轉變成排序的雙向連結清單 題目： 輸入一棵二進制查找樹，将該二進制查找樹轉換成一個排序的雙向連結清單。 要求不能建立任何新的結點，隻調整指針的指向。 10 / / 6 14 / / / / 4 8 12 16 轉換成雙向連結清單 4=6=8=10=12=14=16。 首先我們定義的二進制查找樹 節點的資料結構如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 2.設計包含min函數的棧。 定義棧的資料結構，要求添加一個min函數，能夠得到棧的最小元素。 要求函數min、push以及pop的時間複雜度都是O(1)。 3.求子數組的最大和 題目： 輸入一個整形數組，數組裡有正數也有負數。 數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。 求所有子數組的和的最大值。要求時間複雜度為O(n)。 例如輸入的數組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數組為3, 10, -4, 7, 2， 是以輸出為該子數組的和18。 4.在二進制樹中找出和為某一值的所有路徑 題目：輸入一個整數和一棵二進制樹。 從樹的根結點開始往下通路一直到葉結點所經過的所有結點形成一條路徑。 列印出和與輸入整數相等的所有路徑。 例如 輸入整數22和如下二進制樹 10 / / 5 12 / / 4 7 則列印出兩條路徑：10, 12和10, 5, 7。 二進制樹節點的資料結構定義為： 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個整數，輸出其中最小的k個。 例如輸入1，2，3，4，5，6，7和8這8個數字，則最小的4個數字為1，2，3和4。 第6題 騰訊面試題： 給你10分鐘時間，根據上排給出十個數，在其下排填出對應的十個數 要求下排每個數都是先前上排那十個數在下排出現的次數。 上排的十個數如下： 【0，1，2，3，4，5，6，7，8，9】 初看此題，貌似很難，10分鐘過去了，可能有的人，題目都還沒看懂。 舉一個例子， 數值: 0,1,2,3,4,5,6,7,8,9 配置設定: 6,2,1,0,0,0,1,0,0,0 0在下排出現了6次，1在下排出現了2次， 2在下排出現了1次，3在下排出現了0次.... 以此類推.. 昨天，花了一個下午，用c++實作了此題。(*^__^*) 第7題 微軟亞院之程式設計判斷倆個連結清單是否相交 給出倆個單向連結清單的頭指針，比如h1，h2，判斷這倆個連結清單是否相交。 為了簡化問題，我們假設倆個連結清單均不帶環。 問題擴充： 1.如果連結清單可能有環列? 2.如果需要求出倆個連結清單相交的第一個節點列? 第8題 此貼選一些 比較怪的題，，由于其中題目本身與算法關系不大，僅考考思維。特此并作一題。 1.有兩個房間，一間房裡有三盞燈，另一間房有控制着三盞燈的三個開關，這兩個房間是 分割開的，從一間裡不能看到另一間的情況。 現在要求受訓者分别進這兩房間一次，然後判斷出這三盞燈分别是由哪個開關控制的。 有什麼辦法呢？ 2.你讓一些人為你工作了七天，你要用一根金條作為報酬。金條被分成七小塊，每天給出一塊。如果你隻能将金條切割兩次，你怎樣分給這些勞工? 3.★連結表和數組之間的差別是什麼? 　　★做一個連結表，你為什麼要選擇這樣的方法? 　　★選擇一種算法來整理出一個連結表。你為什麼要選擇這種方法?現在用O(n)時間來做。 　　★說說各種股票分類算法的優點和缺點。 　　★用一種算法來颠倒一個連結表的順序。現在在不用遞歸式的情況下做一遍。 　　★用一種算法在一個循環的連結表裡插入一個節點，但不得穿越連結表。 　　★用一種算法整理一個數組。你為什麼選擇這種方法? 　　★用一種算法使通用字元串相比對。 　　★颠倒一個字元串。優化速度。優化空間。 　　★颠倒一個句子中的詞的順序，比如将我叫克麗絲轉換為克麗絲叫我，實作速度最快，移動最少。 　　★找到一個子字元串。優化速度。優化空間。 　　★比較兩個字元串，用O(n)時間和恒量空間。 　　★假設你有一個用1001個整數組成的數組，這些整數是任意排列的，但是你知道所有的整數都在1到1000(包括1000)之間。此外，除一個數字出現兩次外，其他所有數字隻出現一次。假設你隻能對這個數組做一次處理，用一種算法找出重複的那個數字。如果你在運算中使用了輔助的存儲方式，那麼你能找到不用這種方式的算法嗎? 　　★不用乘法或加法增加8倍。現在用同樣的方法增加7倍。 第9題 判斷整數序列是不是二進制查找樹的後序周遊結果 題目：輸入一個整數數組，判斷該數組是不是某二進制查找樹的後序周遊的結果。 如果是傳回true，否則傳回false。 例如輸入5、7、6、9、11、10、8，由于這一整數序列是如下樹的後序周遊結果： 8 / / 6 10 / / / / 5 7 9 11 是以傳回true。 如果輸入7、4、6、5，沒有哪棵樹的後序周遊的結果是這個序列，是以傳回false。 第10題 翻轉句子中單詞的順序。 題目：輸入一個英文句子，翻轉句子中單詞的順序，但單詞内字元的順序不變。句子中單詞以空格符隔開。 為簡單起見，标點符号和普通字母一樣處理。 例如輸入I am a student.，則輸出student. a am I。 第11題 求二叉樹中節點的最大距離... 如果我們把二叉樹看成一個圖， 父子節點之間的連線看成是雙向的， 我們姑且定義"距離"為兩節點之間邊的個數。 寫一個程式， 求一棵二叉樹中相距最遠的兩個節點之間的距離。 第12題 題目：求1+2++n， 要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句（A?B:C）。 第13題： 題目：輸入一個單向連結清單，輸出該連結清單中倒數第k個結點。連結清單的倒數第0個結點為連結清單的尾指針。 連結清單結點定義如下： struct ListNode { int m_nKey; ListNode* m_pNext; }; 第14題： 題目：輸入一個已經按升序排序過的數組和一個數字， 在數組中查找兩個數，使得它們的和正好是輸入的那個數字。 要求時間複雜度是O(n)。如果有多對數字的和等于輸入的數字，輸出任意一對即可。 例如輸入數組1、2、4、7、11、15和數字15。由于4+11=15，是以輸出4和11。 第15題： 題目：輸入一顆二進制查找樹，将該樹轉換為它的鏡像， 即在轉換後的二進制查找樹中，左子樹的結點都大于右子樹的結點。 用遞歸和循環兩種方法完成樹的鏡像轉換。 例如輸入： 8 / / 6 10 // // 5 7 9 11 輸出： 8 / / 10 6 // // 11 9 7 5 定義二進制查找樹的結點為： 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題： 題目（微軟）： 輸入一顆二進制樹，從上往下按層列印樹的每個結點，同一層中按照從左往右的順序列印。 例如輸入 8 / / 6 10 / / / / 5 7 9 11 輸出8 6 10 5 7 9 11。 第17題： 題目：在一個字元串中找到第一個隻出現一次的字元。如輸入abaccdeff，則輸出b。 分析：這道題是2006年google的一道筆試題。 第18題： 題目：n個數字（0,1,,n-1）形成一個圓圈，從數字0開始， 每次從這個圓圈中删除第m個數字（第一個為目前數字本身，第二個為目前數字的下一個數字）。 當一個數字删除後，從被删除數字的下一個繼續删除第m個數字。 求出在這個圓圈中剩下的最後一個數字。 July：我想，這個題目，不少人已經 見識過了。 第19題： 題目：定義Fibonacci數列如下： / 0 n=0 f(n)= 1 n=1 / f(n-1)+f(n-2) n=2 輸入n，用最快的方法求該數列的第n項。 分析：在很多C語言教科書中講到遞歸函數的時候，都會用Fibonacci作為例子。 是以很多程式員對這道題的遞歸解法非常熟悉，但....呵呵，你知道的。。 第20題： 題目：輸入一個表示整數的字元串，把該字元串轉換成整數并輸出。 例如輸入字元串"345"，則輸出整數345。 文章更新位址： http://topic.csdn.net/u/20101011/16/2befbfd9-f3e4-41c5-bb31-814e9615832e.html

引言中的題目(與第6題相同)

int main()
{
    int above[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    int i;
    int j;
    int temp;
    int sum;
    int right;

    int below[10] = {[0] = 0};
    printf("數值:[");
    for (i = 0, sum = 0; i < 10; i++)
    {
        printf("%d ", above[i]);
    }
    printf("\b]\n");
    while(1)
    {
        right = 10;
        for (i = 0; i < 10; i++)
        {
            for (j = 0,temp = 0; j < 10; j++)
            {
                if (below[j] == above[i])
                {
                    temp++;
                }
            }
            if(below[i] != temp)
            {
                below[i] = temp;
                right--;
            }
        }
        if(right == 10)
        {
            break;
        }

    }
    printf("配置設定:[");
    for (i = 0, sum = 0; i < 10; i++)
    {
        sum += below[i];
        printf("%d ", below[i]);
    }
    printf("\b]\n");
    return 0;
}

           

結果：