• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 183,  comments - 10,  trackbacks - 0
            http://blog.csdn.net/v_JULY_v
            一個算法的博客

            幾個算法題目

            1.
            實現(xiàn)過程中參考了網(wǎng)上別人的博客,主要思想是利用一個輔助棧記錄 min 的索引。

             1 #include <iostream>
             2 #include <ctime>
             3 #include <cassert>
             4 using namespace std;
             5 
             6 class MinStack
             7 {
             8 private:
             9     int stack[100];
            10     int p;
            11     int minstack[100];
            12     int q;
            13 public:
            14     MinStack() : p(0), q(0) {}
            15     bool empty()
            16     {
            17         return p == 0;
            18     }
            19     bool minEmpty()
            20     {
            21         return q == 0;
            22     }
            23     void push(int i)
            24     {
            25         stack[p++= i;
            26         if (minEmpty())
            27         {
            28             minstack[q++= p - 1;
            29         }
            30         else
            31         {
            32             if (i <= stack[minTop()])
            33             {
            34                 minstack[q++= p - 1;
            35             }
            36         }
            37     }
            38     void pop()
            39     {
            40         assert(!empty());
            41         if (top() == stack[minTop()])
            42         {
            43             minPop();
            44         }
            45         --p;
            46     }
            47     int min()
            48     {
            49         assert(!empty());
            50         return stack[minTop()];
            51     }
            52     void minPop()
            53     {
            54         assert(!minEmpty());
            55         --q;
            56     }
            57     int top()
            58     {
            59         assert(!empty());
            60         return stack[p - 1];
            61     }
            62     int minTop()
            63     {
            64         assert(!minEmpty());
            65         return minstack[q - 1];
            66     }
            67 };
            68 
            69 int main()
            70 {
            71     MinStack ms;
            72     srand(time(0));
            73     for (int i = 0; i < 10++i)
            74     {
            75         int n = rand() % 100;
            76         ms.push(n);
            77     }
            78     while (!ms.empty())
            79     {
            80         cout << ms.top() << '\t' << ms.min() << endl;
            81         ms.pop();
            82     }
            83     return 0;
            84 }

             


            2.
             1 /*
             2  *
             3  *先統(tǒng)計所有查詢的次數(shù),所有查詢有 300 萬個,255 * 300 * 10000B = 765 MB,可以存入內(nèi)存。這里使用 STL 中的 map。所得時間復雜度為 O(NlogM),N 為所有的查詢,包括重復的,M 為不重復的查詢。更好的方法是用散列。
             4  *
             5  *然后遍歷 map,維護一個大小為 10 的集合,在遍歷 map 時,比較當前查詢的出現(xiàn)次數(shù)與集合中出現(xiàn)次數(shù)最小的查詢的出現(xiàn)此時比較,如果大于,將當前查詢替換到集合中。
             6  *這里的集合還是用的 map,時間復雜度為 O(MlogK),這里 K = 10。
             7  *
             8  */
             9 
            10 #include <iostream>
            11 #include <fstream>
            12 #include <map>
            13 #include <string>
            14 using namespace std;
            15 
            16 void statistics(map<stringint>& data, const string& query)
            17 {
            18     ++data[query];
            19 }
            20 
            21 void findTopK(multimap<intstring>& topK, int k, const map<stringint>& data)
            22 {
            23     topK.clear();
            24     for (map<stringint>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
            25     {
            26         if (topK.size() < k)
            27         {
            28             topK.insert(make_pair(cit->second, cit->first));
            29         }
            30         else
            31         {
            32             if (cit->second > topK.begin()->first)
            33             {
            34                 topK.erase(topK.begin());
            35                 topK.insert(make_pair(cit->second, cit->first));
            36             }
            37         }
            38     }
            39 }
            40 
            41 int main()
            42 {
            43     ifstream fin("queryfile.txt");
            44     map<stringint> data;
            45     multimap<intstring> top10;
            46     string query;
            47     while (getline(fin, query))
            48     {
            49         statistics(data, query);
            50     }
            51     findTopK(top10, 10, data);
            52     for (multimap<intstring>::const_reverse_iterator cit = top10.rbegin(); cit != top10.rend(); ++cit)
            53     {
            54         cout << cit->second << '\t' << cit->first << endl;
            55     }
            56 
            57     return 0;
            58 }

            3.
             1 #include <iostream>
             2 #include <string>
             3 using namespace std;
             4 
             5 char solve(const string& s)
             6 {
             7     static int times[26= {0};
             8     memset(times, 0sizeof (times));
             9     for (size_t i = 0; i < s.size(); ++i)
            10     {
            11         ++times[s[i] - 'a'];
            12     }
            13     for (size_t i = 0; i < s.size(); ++i)
            14     {
            15         if (times[s[i] - 'a'== 1)
            16         {
            17             return s[i];
            18         }
            19     }
            20     return 0;
            21 }
            22 
            23 int main()
            24 {
            25     string s = "abaccdeff";
            26     cout << solve(s) << endl;
            27     return 0;
            28 }

            posted on 2011-06-25 16:44 unixfy 閱讀(93) 評論(0)  編輯 收藏 引用
            中文字幕久久精品无码| 久久精品国产亚洲网站| 久久这里只有精品首页| 久久综合久久自在自线精品自| 久久精品天天中文字幕人妻| 99久久国产主播综合精品| 久久精品视频一| 国产精品欧美久久久久天天影视| 亚洲国产精品综合久久一线| 久久66热人妻偷产精品9| 四虎亚洲国产成人久久精品| 国产精品美女久久久| 伊人久久精品无码二区麻豆| 久久久免费观成人影院| 久久精品国产99国产电影网 | 久久亚洲国产精品一区二区| 亚洲国产一成久久精品国产成人综合 | 色天使久久综合网天天| 九九久久99综合一区二区| 久久精品国产色蜜蜜麻豆| 亚洲精品乱码久久久久久蜜桃| 久久r热这里有精品视频| 久久久久人妻一区精品性色av| 香蕉久久夜色精品国产2020| 国内精品久久久久国产盗摄| 99久久99久久精品免费看蜜桃| 久久精品国产亚洲αv忘忧草 | 久久ZYZ资源站无码中文动漫| 亚洲国产香蕉人人爽成AV片久久| 久久精品国产亚洲Aⅴ香蕉| 青青草原综合久久大伊人精品| 99久久免费国产特黄| 国产亚洲综合久久系列| 久久夜色精品国产噜噜麻豆| 久久精品中文闷骚内射| 久久99国产综合精品免费| 久久国产热精品波多野结衣AV| 亚洲AV无码久久| 97久久超碰成人精品网站| 久久被窝电影亚洲爽爽爽| 久久精品国产亚洲综合色|