程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 幾個關於串的小算法題:最小K個數、連續子數組的最大和、字符串全排列求法、數組循環移位

幾個關於串的小算法題:最小K個數、連續子數組的最大和、字符串全排列求法、數組循環移位

編輯:關於C

最小K個數:

法一:

     用改裝的快速排序,分割函數不變。

     分割後返回的標號index若等於k-1或k則退出,

                                          大於k,則遞歸左側

                                          小於k,則遞歸右側

  此法復雜度為O(n),但會移動原始數據

 

法二:

      借助擁有k個節點的最大堆

      若總元素數小於等於k,則全部返回

      遍歷所有元素,依次增加到一個最大堆中,對堆的元素數保持計數

      若元素數達到n==k,則在處理下一個數據d 時,

              若d大於等於最大堆堆頂值,則直接拋棄

             否則,刪除堆頂元素,並將d加入到堆中。

      最終,堆中剩余的k個元素即為最小的k個

 

     此法復雜度O(klogk) ,但好處是無需移動原始數據,適合大數據情況

  

 

連續子數組的最大和

問題描述:輸入一個整數數組,數組中有正數也有負數,一個或連續的多個整數組成一個子數組,求所有子數組的和的最大值。

解決方案:

       主要思路:若前面字串的累加和是正的,再加上下一個數可能還會變大。後面再加上一個負數也沒事,因為後面可能會有個絕對值更大的正數,導致總體繼續增長

                         而若前面的和是已經是負的,就沒必要再累加下去了。就算後面是正數,前面的也只會扯後腿。因此拋棄

                     如:3  -2  3  -5  5 ,看了第一個元素後累加和是3,加上第二個後變成1,但再後面的3讓總體變成了4。再看到-5後總體變-1,就沒必要再累加下去了,只會拖累   前面的和。需要重新計數,是5。因此最後結果是5

int sum = INT_MIN;   // 初始sum為最小32位有符號數 
    int curSum = 0;  //當前最小和
    for(int i = 0; i < length; ++i)  //遍歷整個數組
    { 
        if(curSum <= 0)   //若當前和小於0,則說明已經下降,需要重新開始計數
            curSum = data[i];    //重新計數
        else 
            curSum += data[i];  //繼續累加,給後面機會!
         
        if(curSum > sum)  //判斷是否更大
            sum = curSum; 
    } 
  

字符串全排列求法

遞歸方案:

    按照人手動計算的思路,先固定第一個元素,後面的遞歸計算全排列。而第一個元素總共有strlen(str)種可能,可以使用循環。

    思路:

             假設序列中沒有重復元素。若有,則只要讓重復元素在循環中只進行一次即可

if(begin == end)   // 遞歸中止條件
       printf("%s\n", str); 

for(char *x = begin; x < end; x++)  //遞歸
        { 
            // 交換x和begin指向的字符 
            Swap(x, begin);   
            Permutation(str, begin + 1, end);    //遞歸後面的序列
            // 恢復x和begin指向的字符 
            Swap(x, begin);
        } 
 

 

 數組循環移位k

循環左移直觀方法:建一個k大小的緩沖區,先把0~k-1元素復制出來,把後面元素移動到前面,然後把緩沖區中的k個值移動回數組的最後

 

改進版循環左移(原地交換版):

     首先將前k個元素原地求逆,然後後面所有元素原地求逆,然後整個數組原地求逆。

     1234567循環右移3位  1234567-> 3214567-> 3217654-> 4567123

循環右移,即為求逆變換的是最後k個元素和前面的元素,然後整體求逆。

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved