如何用C++制作LeetCode刷題小技巧-錯題記錄本
一 . 刷題小技巧
1，c++中的for(auto a:b)用法
for(auto a:b)中b為一個容器，效果是利用a遍歷並獲得b容器中的每一個值，但是a無法影響到b容器中的元素。
for(auto &a:b)中加瞭引用符號，可以對容器中的內容進行賦值，即可通過對a賦值來做到容器b的內容填充。
2，c++中map的元素進行按照值排序（默認按照鍵排序）
為什麼不能對map進行按值排序呢？因為sort排序隻能對線性結構進行排序，而map是采用紅黑樹的數據結構。
一是通過將map轉換到序列容器，再用STL提供的sort方法得以實現的。
#include<bits/stdc++.h>
using namespace std;
tyedef pair<string, int> Pair;
//第3參數為函數名
bool my_compare(const Pair &p1, const Pair &p2){
return p1.second < p2.second;
}
//第3參數為重載瞭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或者MyCompare()都可以
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的認識
1，pair是將2個數據組合成一個數據，當需要這樣的需求時就可以使用pair，如stl中的map就是將key和value放在一起來保存。另一個應用是，當一個函數需要返回2個數據的時候，可以選擇pair。 pair的實現是一個結構體，主要的兩個成員變量是first second 因為是使用struct不是class，所以可以直接使用pair的成員變量。
2，
template pair make_pair(T1 a, T2 b) { return pair(a, b); }
很明顯，我們可以使用pair的構造函數也可以使用make_pair來生成我們需要的pair。 一般make_pair都使用在需要pair做參數的位置，可以直接調用make_pair生成pair對象很方便，代碼也很清晰。 另一個使用的方面就是pair可以接受隱式的類型轉換，這樣可以獲得更高的靈活度。
3，對於pair類，由於它隻有兩個元素，分別名為first和second，因此直接使用普通的點操作符即可訪問其成員。
4，質數判斷的方法
1，常見方法，直接通過遍歷到n的開平法進行整除判斷，效率不高。
2，通過標志方法，設置一個bool數組，先進行初始化，奇數設置為true，偶數設置為false，隻需將前面為true表示為質數的倍數設置為flase即可，效率較上面高。
3，質數分佈的規律：大於等於5的質數一定和6的倍數相鄰。例如5和7，11和13,17和19等等；
bool isPrime( int num )
{
//兩個較小數另外處理
if(num == 2||num == 3 )
return 1;
//不在6的倍數兩側的一定不是質數
if(num % 6 != 1&&num % 6 != 5)
return 0;
int tmp = sqrt(num);
//在6的倍數兩側的也可能不是質數
for(int i = 5;i <= tmp;i += 6)
if(num %i == 0||num % (i+ 2) == 0)
return 0;
//排除所有，剩餘的是質數
return 1;
}
二 . 錯題記錄
（1），堆棧
1，1021. 刪除最外層的括號：
方法一：雙標記法：隻要考慮（）配對，用一個標記就行
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 個高頻元素：
1，我的解法：用map鍵值對的形式記錄數字出現的次數，在轉換成vector進行sort的自定義排序，最後取出前k個元素。提示：盡量可以用hask_map的時候就不用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 的第一個元素代表數組的值，第二個元素代表瞭該值出現的次數
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,醜數
題目描述：給你一個整數 n ，請你判斷 n 是否為 醜數 。如果是，返回 true ；否則，返回 false 。醜數 就是隻包含質因數 2、3 和/或 5 的正整數。
分類討論的情況
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;
}
};
總結
通過c++制作插件以後，我們就可以快速刷題和擁有錯題記錄本。內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！以上就是如何用C++制作LeetCode刷題小技巧-錯題記錄本的詳細內容，更多關於LeetCode刷題小技巧-錯題記錄本的資料請關註WalkonNet其它相關文章！,希望大傢以後多多支持WalkonNet！
推薦閱讀：
- None Found