アルゴリズムアルゴリズム:古典leetcodeアルゴリズムの問題解

7982 ワード

雑欄:数学&コンピュータ学科の知識

索引
1. https://leetcode.com/problems/patching-array/パッチ配列
2. https://leetcode.com/problems/find-the-duplicate-number/重複要素の検出
3. https://leetcode.com/problems/majority-element-ii/主元素を探し出す(O(n))
4. https://leetcode.com/problems/lru-cache/LRU Cache(チェーンテーブル)
5. https://leetcode.com/problems/sliding-window-maximum/スライドウィンドウ-単調キュー
6. https://leetcode.com/problems/largest-rectangle-in-histogram/(単調桟、見られる)
7. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/株式最大収益(動的計画)
8. https://leetcode.com/problems/distinct-subsequences/異なるシーケンスを探す(ダイナミックプランニング)
9. https://leetcode.com/problems/h-index/H指数計算
10. https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/回転順序配列で最小要素を探す
11. https://leetcode.com/tag/depth-first-search/深度優先検索
1.Patching Arrayパッチ配列(ingを考慮)
原題の説明:https://leetcode.com/problems/patching-array/

           nums      n，      /      ，  “     ”      [1, n]      。             。

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

古典的な解法:
C＋＋バージョン:http://blog.csdn.net/murmured/article/details/50596403
Pythonバージョン:http://bookshadow.com/weblog/2016/01/27/leetcode-patching-array/
2.Find the Duplicate Number重複数を探す(亀ウサギ競走、二分法)
原題の説明:https://leetcode.com/problems/find-the-duplicate-number/
主な考え方:https://segmentfault.com/a/1190000003817671
コードの詳細:http://bookshadow.com/weblog/2015/09/28/leetcode-find-duplicate-number/
問題外記:
int値ドメイン4バイト-2147 438 648~+2 147 438 647
long int 4バイト-2 147 438 648~+2 147 438 647
long long int 8 - 9 223 372 036 854 775 808 ~ + 9 223 372 036 854 775 807
3.Majority ElementII多数投票アルゴリズム
原題の説明:https://leetcode.com/problems/find-the-duplicate-number/
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
主な考え方:モル投票法.数とn/2より大きい2つの数を見つけます.そしてどちらが条件に合っているかを判断します.
コードの詳細:http://www.cnblogs.com/ZhangYushuang/p/4627503.html
标题外记:Majority Element--もし⌊n/2⌋であれば.Moore’s Voting Algorithmアルゴリズムを用いてhttp://blog.csdn.net/booirror/article/details/42738563
4.LRU Cache(データ構造設計)
原題の説明:https://leetcode.com/problems/lru-cache/

    ： LRU Cache        ，       ：
　　　1）get(key)：  key cache ，      value ，    -1
　　　2）set(key,value):  key  cache ，   (key,value)  cache （  ，  cache  ，               cache   ）；  key cache ，   value  。

主な考え方:http://www.cnblogs.com/dolphin0520/p/3741519.html
単鎖表:O(n)

#include 
#include 
#include 
using namespace std;
 
struct Node{
    int key;
    int value;
    Node *next;
};
class LRUCache{
private:
    int count;
    int size ;
    map mp;
    Node *cacheList;
public:
    LRUCache(int capacity) {
      size = capacity;
      cacheList = NULL;
      count = 0;
    }   
    int get(int key) { }
     void set(int key, int value) { }
      void pushFront(Node *cur){   //       ,          ，O(n)、O（1）}
      }
}

 
    
   双链表：O(1) 
    
   #include 
#include 
#include 
using namespace std;
 
struct Node{
    int key;
    int value;
    Node *pre;
    Node *next;
};
class LRUCache{
private:
    int count;
    int size ;
    map mp;
    Node *cacheHead;
    Node *cacheTail;
public:
    LRUCache(int capacity) {
      size = capacity;
      cacheHead = NULL;
      cacheTail = NULL;
      count = 0;
    }
     
    int get(int key) {}
    void set(int key, int value) {}
    void pushFront(Node *cur){   //        ,          ，O(1)}
}

int main(void){
    LRUCache cache(3);
    cache.set(1,1);
}
   
    
   题外记1：最全的c++map的用法 
   题外记2：it->second表示取键值。 
    
   map m;
m["one"] = 1;

map::iterator p = m.begin();
p->first; //     string    "one"
p->second; //    int    1
  
題外記3:
シーケンスコンテナ用erase:iter=c.erase(iter);//反復器の無効化の削除と防止
関連性容器用erase:mp.erase(iter++);//削除された要素の反復器だけが無効ですが、戻り値はvoidです.
5.Sliding Window Maximumスライドウィンドウ最大値(単調キュー)
原題の説明:https://leetcode.com/problems/sliding-window-maximum/
主な考え方:
優先キュー:時間O(NlogK)空間O(K).Kサイズの最大スタックをメンテナンスし、Kサイズのウィンドウをメンテナンスし、新しい数を読み込むたびに、スタックのウィンドウの一番左の数を捨てて、新しい数をスタックに追加します.このようにスタックトップはこのウィンドウ内の最大の値です.
双方向キュー-時間O(N)空間O(K).
//新数が入るたびに、キューヘッダの数の下付き文字が、ウィンドウの一番左の数の下付き文字であることを発見したら、捨てる
//新しい数より小さいものはすべて捨てて、降順であることを保証する
//新数を入れる
//キューヘッダはこのウィンドウ内で一番大きい
コードの詳細:https://segmentfault.com/a/1190000003903509 
問題外記:peek()メソッドはキューのヘッダを取得するために使用されます.ただし、削除されません.
6.Largest Rectangle in Histogramヒストグラム最大面積(単調スタック)
原題の説明:https://leetcode.com/problems/largest-rectangle-in-histogram/
主な考え方:
1、height配列が昇順であることが知られている場合は、どうすればいいですか.
例えば1,2,5,7,8は(1*5)vs.(2*4)vs.(5*3)vs.(7*2)vs.(8*1)、すなわちmax(height[i]*(size-i))である.
2、スタックを使用する目的は、このような昇順シーケンスを構築し、以上の方法で解くことである.
コードの詳細:http://www.cnblogs.com/ganganloveu/p/4148303.html 
7. Best Time to Buy and Sell Stock III(DP) 
原題の説明:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
主な考え方:ダイナミックプランニング法.i日目を境に、i日目までに1回の取引が行われる最大収益preprofit[i]と、i日目以降に1回の取引が行われる最大収益postProfit[i]を計算し、最後に遍歴するとmax{preprofit[i]+postProfit[i]}(0≦i≦n−1)が最大収益となる.i日目以前とi日目以降に1回行われる最大収益求法はBest Time to Buy and Sell Stock Iと同じである.
preProfit[i] = Math.max(preProfit[i - 1], prices[i] - curMin); 
postProfit[i] = Math.max(postProfit[i + 1], curMax - prices[i]); 
maxProfit = Math.max(maxProfit, preProfit[i] + postProfit[i]); 
コードの詳細:http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html 
余談:DPアルゴリズムは多段階決定プロセス最適化問題を解決する一般的な方法である.
多段階決定プロセス(multistep decision process)とは、時間順にいくつかの相互に関連する段階に分解することができ、各段階で決定を行う必要があり、すべてのプロセスの決定は決定シーケンスである.
動的計画(dynamic programming)アルゴリズムは多段階決定過程の最適化問題を解決する一般的な方法であり,難易度が高く,技術性も強い.
8. Best Time to Buy and Sell Stock III(DP) 
原題の説明:https://leetcode.com/problems/distinct-subsequences/
コードの詳細:http://www.tuicool.com/articles/6BZRJf 
9.H-Index H因子(二分?)
原題の説明:https://leetcode.com/problems/h-index/
コードの詳細:http://www.thinksaas.cn/group/topic/395874/(Java版)
10.Find Minimum in Rotated Sorted Array(二分)
原題の説明:https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
コードの詳細:http://www.cnblogs.com/x1957/p/4028271.html class Solution {
public:
    int findMin(vector &num) {
        int size = num.size() - 1;
        int l = 0;
        int r = size;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if (num[mid] > num[size]) {
                //left
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return num[l];
    }
};
  
11. Depth-first Search 
原題リスト:https://leetcode.com/tag/depth-first-search/
DFS共通コード:http://www.cnblogs.com/PegasusWang/archive/2013/04/06/3002511.html void bfs(int v)
20 {
21     list::iterator it;
22     printf("%5d", v);
23     visited[v] = true;
24     queue t;
25     t.push(v);
26     while (!t.empty())
27     {
28         v = t.front();
29         t.pop();
30         for (it = graph[v].begin(); it != graph[v].end(); ++it)
31             if (!visited[*it])
32             {
33                 printf("%5d", *it);
34                 t.push(*it);
35                 visited[*it] = true;
36             }
37     }
38     cout << endl;
39 }
  
ありがとうジャックMao.

私が理解しているluceneの原理(初級)

[leetcode] 102. Binary Tree Level Order Traversal解題レポート