如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本

更新時(shí)間：2021年04月12日 17:20:52 作者：自傳難寫啊

這篇文章主要介紹了如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本的方法,需要的朋友可以參考下

一 . 刷題小技巧

1，c++中的for(auto a:b)用法

for(auto a:b)中b為一個(gè)容器，效果是利用a遍歷并獲得b容器中的每一個(gè)值，但是a無法影響到b容器中的元素。

for(auto &a:b)中加了引用符號，可以對容器中的內(nèi)容進(jìn)行賦值，即可通過對a賦值來做到容器b的內(nèi)容填充。

2，c++中map的元素進(jìn)行按照值排序（默認(rèn)按照鍵排序）

為什么不能對map進(jìn)行按值排序呢？因?yàn)閟ort排序只能對線性結(jié)構(gòu)進(jìn)行排序，而map是采用紅黑樹的數(shù)據(jù)結(jié)構(gòu)。

一是通過將map轉(zhuǎn)換到序列容器，再用STL提供的sort方法得以實(shí)現(xiàn)的。

#include<bits/stdc++.h>
 using namespace std;
tyedef pair<string, int> Pair;
 //第3參數(shù)為函數(shù)名
bool my_compare(const Pair &p1, const Pair &p2){
	return p1.second < p2.second;
}
 //第3參數(shù)為重載了operator()操作符的類對象
struct MyCompare{
public:
	bool operator()(const Pair &p1, const Pair &p2) const{
		return p1.second < p2.second;
	}
};
int main(){
	map<string, int> test;
	test["Alice"] = 3;
	test["Cindy"] = 5;
	test["Bob"] = 7;
 	cout << "> sort by key" << endl;
	for(auto itr = test.begin(); itr != test.end(); ++itr){
		cout << itr->first << ": " << itr->second << endl;
	}
	cout << endl;
 	vector<Pair> vec;
 	for(auto itr = test.begin(); itr != test.end(); ++itr){
		vec.push_back(make_pair(itr->first, itr->second));
	}
 	sort(vec.begin(), vec.end(), MyCompare()); //my_compare或者M(jìn)yCompare()都可以
 	cout << "> sort by value" << endl;
	for(auto itr = vec.begin(); itr != vec.end(); ++itr){
		cout << itr->first << ": " << itr->second << endl;
	}
 	return 0;
}

二是通過將map的key和value位置替換

#include<bits/stdc++.h>
 using namespace std;
typedef pair<string, int> Pair;
 int main(){
	map<string, int> test;
	test["Alice"] = 3;
	test["Cindy"] = 5;
	test["Bob"] = 7;
 	cout << "> sort by key" << endl;
	for(auto itr = test.begin(); itr != test.end(); ++itr){
		cout << itr->first << ": " << itr->second << endl;
	}
	cout << endl;
 	map<int, string> result;
	transform(test.begin(), test.end(), inserter(result, result.begin()), [](pair<string, int> a) { return pair<int, string>(a.second, a.first); });
 	cout << "> sort by value" << endl;
	for(auto itr = result.begin(); itr != result.end(); ++itr){
		cout << itr->first << ": " << itr->second << endl;
	}
 	return 0;
}

3.pair的認(rèn)識

1，pair是將2個(gè)數(shù)據(jù)組合成一個(gè)數(shù)據(jù)，當(dāng)需要這樣的需求時(shí)就可以使用pair，如stl中的map就是將key和value放在一起來保存。另一個(gè)應(yīng)用是，當(dāng)一個(gè)函數(shù)需要返回2個(gè)數(shù)據(jù)的時(shí)候，可以選擇pair。 pair的實(shí)現(xiàn)是一個(gè)結(jié)構(gòu)體，主要的兩個(gè)成員變量是first second 因?yàn)槭鞘褂胹truct不是class，所以可以直接使用pair的成員變量。

2，

 template pair make_pair(T1 a, T2 b) { return pair(a, b); }

很明顯，我們可以使用pair的構(gòu)造函數(shù)也可以使用make_pair來生成我們需要的pair。一般make_pair都使用在需要pair做參數(shù)的位置，可以直接調(diào)用make_pair生成pair對象很方便，代碼也很清晰。另一個(gè)使用的方面就是pair可以接受隱式的類型轉(zhuǎn)換，這樣可以獲得更高的靈活度。

3，對于pair類，由于它只有兩個(gè)元素，分別名為first和second，因此直接使用普通的點(diǎn)操作符即可訪問其成員。

4，質(zhì)數(shù)判斷的方法

1，常見方法，直接通過遍歷到n的開平法進(jìn)行整除判斷，效率不高。

2，通過標(biāo)志方法，設(shè)置一個(gè)bool數(shù)組，先進(jìn)行初始化，奇數(shù)設(shè)置為true，偶數(shù)設(shè)置為false，只需將前面為true表示為質(zhì)數(shù)的倍數(shù)設(shè)置為flase即可，效率較上面高。

3，質(zhì)數(shù)分布的規(guī)律：大于等于5的質(zhì)數(shù)一定和6的倍數(shù)相鄰。例如5和7，11和13,17和19等等；

bool isPrime( int num )
{
    //兩個(gè)較小數(shù)另外處理
    if(num == 2||num == 3 )
        return 1;
    //不在6的倍數(shù)兩側(cè)的一定不是質(zhì)數(shù)
    if(num % 6 != 1&&num % 6 != 5)
        return 0;
    int tmp = sqrt(num);
    //在6的倍數(shù)兩側(cè)的也可能不是質(zhì)數(shù)
    for(int i = 5;i <= tmp;i += 6)
        if(num %i == 0||num % (i+ 2) == 0)
            return 0;
    //排除所有，剩余的是質(zhì)數(shù)
    return 1;
 }

二 . 錯(cuò)題記錄

（1），堆棧

1，1021. 刪除最外層的括號：

方法一：雙標(biāo)記法：只要考慮（）配對，用一個(gè)標(biāo)記就行

class Solution {
public:
	string removeOuterParentheses(string S) {
		string res = "";
        int a[S.length()+1];
        int flag=0;
        for(int i=0;i<S.length();i++)
        {
            if(S[i]=='(')
            {
                flag++;
                a[i]=flag;
            }
            else{
                flag--;
                a[i]=flag;
            }
        }
        for(int i=0;i<S.length();i++)
        {
            if(S[i]=='('&&a[i]==1)
            {
            }
            else if(S[i]==')'&&a[i]==0)
            {
 
            }
            else res.push_back(S[i]);
        }
		return res;
	}
};

方法二：棧：只要考慮到'(',')'是否為最外面的符號就行

 class Solution {
public:
	string removeOuterParentheses(string S) {
		string res = "";
		stack<char> a;
         for(auto b:S)
        {
            if(b=='(')
            {
                if(!a.empty())
                    res.push_back('(');// 表示非外部
                a.push('(');
             }
            else{
                if(a.size()!=1){// 表示非外部
                    res.push_back(')');
                }
                a.pop();
            }
        }
		return res;
	}
};

2，347. 前 K 個(gè)高頻元素：

1，我的解法：用map鍵值對的形式記錄數(shù)字出現(xiàn)的次數(shù)，在轉(zhuǎn)換成vector進(jìn)行sort的自定義排序，最后取出前k個(gè)元素。提示：盡量可以用hask_map的時(shí)候就不用map.

 typedef pair<int,int> Pair;
  
 bool my_compare(const Pair &p1, const Pair &p2){
        return p1.second > p2.second;
}
class Solution {
public:
     vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int>mymap;
        vector<Pair> v;
        vector<int> res;
        for(auto i:nums)
        {
            mymap[i]+=1;
        }
        for(auto itr = mymap.begin(); itr != mymap.end(); ++itr)
		v.push_back(make_pair(itr->first, itr->second));
  
 		sort(v.begin(),v.end(),my_compare);
  		for(int i=0;i<k;i++)
        {
           res.push_back(v[i].first);
        }
        return res;
    }
};

2，官方答案：有些寫法看不懂

class Solution {
public:
    static bool cmp(pair<int, int>& m, pair<int, int>& n) {
        return m.second > n.second;
    }
     vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> occurrences;
        for (auto& v : nums) {
            occurrences[v]++;
        }
         // pair 的第一個(gè)元素代表數(shù)組的值，第二個(gè)元素代表了該值出現(xiàn)的次數(shù)
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
        for (auto& [num, count] : occurrences) {
            if (q.size() == k) {
                if (q.top().second < count) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }
        vector<int> ret;
        while (!q.empty()) {
            ret.emplace_back(q.top().first);
            q.pop();
        }
        return ret;
    }
};

3,丑數(shù)

題目描述：給你一個(gè)整數(shù) n ，請你判斷 n 是否為丑數(shù) 。如果是，返回 true ；否則，返回 false 。丑數(shù) 就是只包含質(zhì)因數(shù) 2、3 和/或 5 的正整數(shù)。

分類討論的情況

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        return n == 1;
    }
};

總結(jié)

通過c++制作插件以后，我們就可以快速刷題和擁有錯(cuò)題記錄本。內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！以上就是如何用C++制作LeetCode刷題小技巧-錯(cuò)題記錄本的詳細(xì)內(nèi)容，更多關(guān)于LeetCode刷題小技巧-錯(cuò)題記錄本的資料請關(guān)注腳本之家其它相關(guān)文章！希望大家以后多多支持腳本之家！

您可能感興趣的文章: