亲宝软件园·资讯

展开

LeetCode刷题小技巧-错题记录本 怎样用C++制作LeetCode刷题小技巧-错题记录本

自传难写啊 人气:0
想了解怎样用C++制作LeetCode刷题小技巧-错题记录本的相关内容吗,自传难写啊在本文为您仔细讲解LeetCode刷题小技巧-错题记录本的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点: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;

    }

};

加载全部内容

相关教程
猜你喜欢
用户评论