プログラマーの進級のアルゴリズムの練習:LeetCodeの特別な場
11461 ワード
テンセントクラウド+コミュニティへようこそ、テンセントの大量の技術実践干物をもっと獲得してください.
本文は落影から発表する
前言
LeetCodeのテーマは大企業の面接でよく見られるアルゴリズムの問題で、今日の目標は5つのアルゴリズムの問題を取ることです:テーマ1はチェーンテーブルの大数加算に基づいて、基本的なデータ構造の理解を考察して、また加算を処理する過程の境界処理を考察します;テーマ2は配列の出現頻度の前のkの大きい数字を求めて、思考能力を考察して、コードはとても短いです;テーマ3は2つの配列の中から数字を選択し、最大の数字を構成し、貪欲な思想を考察する.最初の3つはすべて考えを考察することに偏って、実現するコードはすべて比較的に簡単です;テーマ4、5はデータ構造の実現問題であり、大部分の人が頭を悩ませているテーマでもある.データ構造とSTLの実現が多く、時間と空間の制限があるからだ.
本文
1、Add Two Numbers II
タイトルリンクタイトル大意:
2つのチェーンテーブルを与え、ノードは0~9の数字からなり、それぞれ2つの数字を表す.2つの数字の和を求め,チェーンテーブルの形で返す.
タイトルの意味は明らかで、2つの数字を合わせて、進位の状況を考慮する必要があります.一方向のチェーンテーブルなので、遍歴して遡るのは難しいので、まずvecに数字を保存します.また,処理を容易にするためにvecの最低位にはvecの開始部分が存在する.そこで0から2つのvecを遍歴すればよいので,最後のキャリーを考慮することに注意する.
複雑度解析:時間複雑度はO(N)空間複雑度はO(N)
2.Top K Frequent Elements
タイトルリンクタイトル大意:
1つの配列と1つの数字kを与え、数字の出現頻度の前のkの数字を返す.1<=k<=n、nは配列サイズである.
テーマ解析:
テーマは2つのステップに分けられます:1、数字ごとの出現回数を統計します;2、その中からk個の回数が最も多い数字を選択する.
1つの簡単な方法:ハッシュテーブルで各数字の出現回数を統計する.各数字の出現回数と数字をpairにし、優先キューに入れる.
これにより優先キューからk個を取り出せばよい.
複雑度解析:時間複雑度はO(Nlogn)であり,主に最後の優先キューである.
その他の解法:O(NlogK)の最適化がある;まずキューを最小有限キューに変更し、pairを優先ペアに入れるたびに、現在のsizeがkより大きい場合、topをポップアップします.このように毎回の操作はO(logN)からO(logK)に変わる.
3、create-maximum-number
テーマリンクテーマ大意:2つの配列を与え、配列は0~9の10の数字しか含まれず、長さはそれぞれn、mである.2つの配列の中からk個の数を選んで、1つの長さkの数字を構成して、要求:1、配列n、mから選択した数字の相対位置は変わらない;2、最後の数字が一番大きい.最後の数字を出力します.
テーマ解析:
最後の数字が最大であることを要求すると、できるだけ数字を前に並べます.都合法の前提の下で、99は98より大きいに違いない.では、tを列挙し、tは配列nums 1からt個の数字を選択することを示し、配列nums 2の中からk−t個の数字を選択すべきである.2つの配列のすべての数字は最大の数字を構成します.2つの配列間の数字は任意の順序であるため、大きなものを選択するたびに前に置くだけです.
問題は,O(N)が配列からt個の最大の数字を毎回選択することに簡略化される.これは欲張りで解決できる:配列が現在i番目に列挙され、nums[i]=xであると仮定する.選択した数を左から右に巡回し、1つの数字t,tに遭遇すると
4、 Insert Delete GetRandom O(1) - Duplicates allowed
テーマリンクテーマ大意:1、insert(val):数値を挿入する3つの方法を含むデータ構造を実現する.2、remove(val):数値を削除します.3、getRandom:O(1)ランダムに1つの数字を返す;
テーマ解析:
数字の挿入と削除は面倒ではなく,O(1)時間に1つの数字を返す方法を考える.配列の中に置くと、ランダムに1つの位置に戻ることができます.増加は配列の最末端で増加することができる.配列の真ん中の数字を削除するときは、一番端の数字を削除する位置に置くことができます.
現在の問題は、配列内の削除する場所を迅速に見つける方法です.hashで実現することを考える.配列はvector>;firstはvalを保存し、secondは出現回数を保存する.もう一つハッシュmap,unordered_map>には対応する数字が現れる位置が格納されています.
5、 All O`one Data Structure
タイトルリンクタイトル大意:
1、Inc(Key)-Inserts a new key with value 1.Or increments an existing key by 1. Key is guaranteed to be a non-empty string. 2、Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string. 3、GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "". 4、GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".
すべてのデータ構造の時間的複雑さはO(1)であることが要求される.
テーマ解析:
複雑さを考慮しない前提の下で、素朴なやり方は遍歴して、O(N);簡単な最適化はmapで優先キューを維持し、1、2を操作してkey値を取得し、更新して再挿入する.操作3、4はキューtopを直接持つ.各操作の複雑さはO(LogN)である.
テーマ要求はO(1)であるが,必然的に木型の構造を用いることができず,テーマ特性を利用してhashや貪欲に合わせて実現すべきである.
keyの対応する値を格納するkey-hashテーブルがあると仮定します.操作1、まずkeyHashの中にkeyがあるかどうかを見て、あるなら+1、ないなら挿入する.操作2、まずkeyHashの中にkeyがあるかどうかを見て、あれば-1、なければNothing;
最値を維持するために、チェーンテーブルlistを導入し、中のすべての要素は小さいから大きいまでです.各要素はバケツで、バケツには同じkeyが入っています.操作3、listヘッダ要素の値を直接取得する.操作4、listテール要素の値を直接取得する.
また、操作1、2は、操作中にlist対応のバケツから現在のkey値を除去し、前または次のバケツに入れたり、捨てたりする必要がある.O(1)がkeyの位置を取得するために、iter−hashを用いてkeyに対応する要素の反復器を維持することができる.
まとめ
この5つのテーマが独立して完成すれば、国内の大手企業のアルゴリズム面に対応するのに十分なレベルになるだろう.アルゴリズムはよく考えて練習し、会社がアルゴリズムの問題を出すのは役に立たないと愚痴をこぼし、時間をかけて準備するのが正しい.
この文章はすでに作者がテンセントクラウド+コミュニティに発表することを授権して、更に多くの原文はクリックしてください
注目公众号「云加社区」を検索して、最初に技术の干物を手に入れて、注目した后に1024に返事してあなたに1部の技术の课程の大きい贈り物を送ります!
本文は落影から発表する
前言
LeetCodeのテーマは大企業の面接でよく見られるアルゴリズムの問題で、今日の目標は5つのアルゴリズムの問題を取ることです:テーマ1はチェーンテーブルの大数加算に基づいて、基本的なデータ構造の理解を考察して、また加算を処理する過程の境界処理を考察します;テーマ2は配列の出現頻度の前のkの大きい数字を求めて、思考能力を考察して、コードはとても短いです;テーマ3は2つの配列の中から数字を選択し、最大の数字を構成し、貪欲な思想を考察する.最初の3つはすべて考えを考察することに偏って、実現するコードはすべて比較的に簡単です;テーマ4、5はデータ構造の実現問題であり、大部分の人が頭を悩ませているテーマでもある.データ構造とSTLの実現が多く、時間と空間の制限があるからだ.
本文
1、Add Two Numbers II
タイトルリンクタイトル大意:
2つのチェーンテーブルを与え、ノードは0~9の数字からなり、それぞれ2つの数字を表す.2つの数字の和を求め,チェーンテーブルの形で返す.
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
7243 + 564 =7807
Output: 7 -> 8 -> 0 -> 7タイトルの意味は明らかで、2つの数字を合わせて、進位の状況を考慮する必要があります.一方向のチェーンテーブルなので、遍歴して遡るのは難しいので、まずvecに数字を保存します.また,処理を容易にするためにvecの最低位にはvecの開始部分が存在する.そこで0から2つのvecを遍歴すればよいので,最後のキャリーを考慮することに注意する.
複雑度解析:時間複雑度はO(N)空間複雑度はO(N)
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *ret = NULL;
vector vec1, vec2;
sum(l1, vec1);
sum(l2, vec2);
int n = vec1.size(), m = vec2.size(), flag = 0;
for (int i = 0; i < n || i < m; ++i) {
int x = 0, y = 0;
if (i < n) {
x = vec1[i];
}
if (i < m) {
y = vec2[i];
}
int s = x + y + flag;
if (s > 9) {
s -= 10;
flag = 1;
}
else {
flag = 0;
}
ListNode *tmp = new ListNode(s);
tmp->next = ret;
ret = tmp;
}
if (flag) {
ListNode *tmp = new ListNode(1);
tmp->next = ret;
ret = tmp;
}
return ret;
}
void sum(ListNode* list, vector &vec) {
if (list->next) {
sum(list->next, vec);
}
vec.push_back(list->val);
}
}; 2.Top K Frequent Elements
タイトルリンクタイトル大意:
1つの配列と1つの数字kを与え、数字の出現頻度の前のkの数字を返す.1<=k<=n、nは配列サイズである.
example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].テーマ解析:
テーマは2つのステップに分けられます:1、数字ごとの出現回数を統計します;2、その中からk個の回数が最も多い数字を選択する.
1つの簡単な方法:ハッシュテーブルで各数字の出現回数を統計する.各数字の出現回数と数字をpairにし、優先キューに入れる.
これにより優先キューからk個を取り出せばよい.
複雑度解析:時間複雑度はO(Nlogn)であり,主に最後の優先キューである.
その他の解法:O(NlogK)の最適化がある;まずキューを最小有限キューに変更し、pairを優先ペアに入れるたびに、現在のsizeがkより大きい場合、topをポップアップします.このように毎回の操作はO(logN)からO(logK)に変わる.
class Solution {
public:
vector topKFrequent(vector& nums, int k) {
unordered_map numsHash;
for (int i = 0; i < nums.size(); ++i) {
++numsHash[nums[i]];
}
priority_queue> q;
for (int i = 0; i < nums.size(); ++i) {
if(numsHash[nums[i]]) {
q.push(make_pair(numsHash[nums[i]], nums[i]));
numsHash[nums[i]] = 0;
}
}
vector ret;
for (int i = 0; i < k; ++i) {
ret.push_back(q.top().second);
q.pop();
}
return ret;
}
}leetcode; 3、create-maximum-number
テーマリンクテーマ大意:2つの配列を与え、配列は0~9の10の数字しか含まれず、長さはそれぞれn、mである.2つの配列の中からk個の数を選んで、1つの長さkの数字を構成して、要求:1、配列n、mから選択した数字の相対位置は変わらない;2、最後の数字が一番大きい.最後の数字を出力します.
Example 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]
Example 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]テーマ解析:
最後の数字が最大であることを要求すると、できるだけ数字を前に並べます.都合法の前提の下で、99は98より大きいに違いない.では、tを列挙し、tは配列nums 1からt個の数字を選択することを示し、配列nums 2の中からk−t個の数字を選択すべきである.2つの配列のすべての数字は最大の数字を構成します.2つの配列間の数字は任意の順序であるため、大きなものを選択するたびに前に置くだけです.
問題は,O(N)が配列からt個の最大の数字を毎回選択することに簡略化される.これは欲張りで解決できる:配列が現在i番目に列挙され、nums[i]=xであると仮定する.選択した数を左から右に巡回し、1つの数字t,tに遭遇すると
class Solution {
public:
vector maxNumber(vector& nums1, vector& nums2, int k) {
int n = (int)nums1.size(), m = (int)nums2.size();
vector ret(k, 0);
for (int i = max(0, k - m); i <= k && i <= n; ++i) {
vector tmp1 = maxArray(nums1, i);
vector tmp2 = maxArray(nums2, k - i);
vector tmp = merge(tmp1, tmp2, k);
if (greater(tmp, 0, ret, 0)) {
ret = tmp;
}
}
return ret;
}
vector maxArray(vector &nums, int k) {
int n = (int)nums.size();
vector ret(k, 0);
for (int i = 0, j = 0; i < n; ++i) {
while (n - i + j > k && j > 0 && ret[j - 1] < nums[i]) {
--j;
}
if (j < k) {
ret[j++] = nums[i];
}
}
return ret;
}
vector merge(vector& nums1, vector& nums2, int k) {
vector ret(k, 0);
for (int i = 0, j = 0, r = 0; r < k; ++r) {
ret[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
}
return ret;
}
bool greater(vector &nums1, int i, vector &nums2, int j) {
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
++i;
++j;
}
return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
}
}; 4、 Insert Delete GetRandom O(1) - Duplicates allowed
テーマリンクテーマ大意:1、insert(val):数値を挿入する3つの方法を含むデータ構造を実現する.2、remove(val):数値を削除します.3、getRandom:O(1)ランダムに1つの数字を返す;
Example
1；
collection.insert(1);
1：
collection.insert(1);
2
collection.insert(2);
， 2/3 1， 1/3 2；
collection.getRandom();テーマ解析:
数字の挿入と削除は面倒ではなく,O(1)時間に1つの数字を返す方法を考える.配列の中に置くと、ランダムに1つの位置に戻ることができます.増加は配列の最末端で増加することができる.配列の真ん中の数字を削除するときは、一番端の数字を削除する位置に置くことができます.
現在の問題は、配列内の削除する場所を迅速に見つける方法です.hashで実現することを考える.配列はvector>;firstはvalを保存し、secondは出現回数を保存する.もう一つハッシュmap,unordered_map>には対応する数字が現れる位置が格納されています.
class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() {
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
bool ret = hashMap.find(val) == hashMap.end();
hashMap[val].push_back(randVec.size());
randVec.push_back(make_pair(val, hashMap[val].size() - 1));
return ret;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
bool ret = hashMap.find(val) != hashMap.end();
if (ret) {
auto last = randVec.back();
hashMap[last.first][last.second] = hashMap[val].back();
randVec[hashMap[val].back()] = last;
hashMap[val].pop_back();
if (hashMap[val].empty()) {
hashMap.erase(val);
}
randVec.pop_back();
}
return ret;
}
/** Get a random element from the collection. */
int getRandom() {
return randVec[rand() % randVec.size()].first;
}
private:
unordered_map> hashMap;
vector> randVec;
}leetcode; 5、 All O`one Data Structure
タイトルリンクタイトル大意:
1、Inc(Key)-Inserts a new key with value 1.Or increments an existing key by 1. Key is guaranteed to be a non-empty string. 2、Dec(Key) - If Key's value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string. 3、GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "". 4、GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".
すべてのデータ構造の時間的複雑さはO(1)であることが要求される.
テーマ解析:
複雑さを考慮しない前提の下で、素朴なやり方は遍歴して、O(N);簡単な最適化はmapで優先キューを維持し、1、2を操作してkey値を取得し、更新して再挿入する.操作3、4はキューtopを直接持つ.各操作の複雑さはO(LogN)である.
テーマ要求はO(1)であるが,必然的に木型の構造を用いることができず,テーマ特性を利用してhashや貪欲に合わせて実現すべきである.
keyの対応する値を格納するkey-hashテーブルがあると仮定します.操作1、まずkeyHashの中にkeyがあるかどうかを見て、あるなら+1、ないなら挿入する.操作2、まずkeyHashの中にkeyがあるかどうかを見て、あれば-1、なければNothing;
最値を維持するために、チェーンテーブルlistを導入し、中のすべての要素は小さいから大きいまでです.各要素はバケツで、バケツには同じkeyが入っています.操作3、listヘッダ要素の値を直接取得する.操作4、listテール要素の値を直接取得する.
また、操作1、2は、操作中にlist対応のバケツから現在のkey値を除去し、前または次のバケツに入れたり、捨てたりする必要がある.O(1)がkeyの位置を取得するために、iter−hashを用いてkeyに対応する要素の反復器を維持することができる.
struct Bucket {
int value;
unordered_set keys;
};
class AllOne {
public:
list buckets;
unordered_map::iterator> bucketOfKey;
/** Initialize your data structure here. */
AllOne() {
}
/** Inserts a new key with value 1. Or increments an existing key by 1. */
void inc(string key) {
if (bucketOfKey.find(key) == bucketOfKey.end()) {
bucketOfKey[key] = buckets.insert(buckets.begin(), {0, {key}});
}
auto next = bucketOfKey[key], bucket = next++;
if (next == buckets.end() || next->value > bucket->value + 1) {
next = buckets.insert(next, {bucket->value+1, {}});
}
next->keys.insert(key);
bucketOfKey[key] = next;
bucket->keys.erase(key);
if (bucket->keys.empty()) {
buckets.erase(bucket);
}
}
/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
void dec(string key) {
if (bucketOfKey.find(key) == bucketOfKey.end()) {
return ;
}
auto pre = bucketOfKey[key], bucket = pre;
if (pre != buckets.begin()) {
--pre;
}
bucketOfKey.erase(key);
if (bucket->value > 1) {
if (bucket == buckets.begin() || pre->value < bucket->value - 1) {
pre = buckets.insert(bucket, {bucket->value - 1, {}});
}
pre->keys.insert(key);
bucketOfKey[key] = pre;
}
bucket->keys.erase(key);
if (bucket->keys.empty()) {
buckets.erase(bucket);
}
}
/** Returns one of the keys with maximal value. */
string getMaxKey() {
return buckets.empty() ? "" : *(buckets.rbegin()->keys.begin());
}
/** Returns one of the keys with Minimal value. */
string getMinKey() {
return buckets.empty() ? "" : *(buckets.begin()->keys.begin());
}
}leetcode; まとめ
この5つのテーマが独立して完成すれば、国内の大手企業のアルゴリズム面に対応するのに十分なレベルになるだろう.アルゴリズムはよく考えて練習し、会社がアルゴリズムの問題を出すのは役に立たないと愚痴をこぼし、時間をかけて準備するのが正しい.
この文章はすでに作者がテンセントクラウド+コミュニティに発表することを授権して、更に多くの原文はクリックしてください
注目公众号「云加社区」を検索して、最初に技术の干物を手に入れて、注目した后に1024に返事してあなたに1部の技术の课程の大きい贈り物を送ります!