C++刷题常见方法

2020-06-03 · 6 min read

1. 排序

排序是刷题中最常见的预处理操作，在C++中可利用sort函数实现数组、链表、向量等的优化排序。

函数简介

在C++中，sort函数的使用方法为：sort(start_pointer, end_pointer, cmp)。
参数start_pointer代表排序数据的首地址，类型为指针常量，例如用数组名代表数组数据的首地址；
参数end_pointer代表排序数据的尾地址的下一地址，类型为指针常量，例如用数组名+数组length的形式代表整个数组的末端；
end_pointer - start_pointer代表排序的元素的数量；
参数cmp代表自定义的排序方式，默认不填写时以升序进行排序。

example

talk is cheap, show the code.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool cmp(int a, int b)
{
	return a > b; // descending order
}

// bool cmp_structure(Student a, Student b) {return a.id > b.id;}

int main()
{
	int a[10] = {7,6,5,4,3,2,1};
	sort(a, a+5); // 3,4,5,6,7,2,1

	vector<int> b = {2,4,6,8,10};
	sort(b.begin(), b.end(), cmp); // 10,8,6,4,2

	return 0;
}

Leetcode实战

Leetcode 1029 两城调度
costs是一个N*2维的数组，需要以cost[i][0] - cost[i][1]进行升序排序，第一种解法如下所示：

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {

        sort(costs.begin(), costs.end(), [](auto& a, auto& b) {
            return a[0] - a[1] < b[0] - b[1];} );

        int ans = 0, n = costs.size() >> 1;
        for (int i = 0; i < n; ++i)
            ans += costs[i][0] + costs[i + n][1];

        return ans;
    }
};

第二种解法：

class Solution {
public:

    static bool cmp(vector<int> a, vector<int> b)
    // static bool cmp(auto a, auto b)
    //      False, 'auto' is not allowed in function prototype
    //  bool cmp(vector<int> a, vector<int> b)
    //      False, function has an implicit parameter
    {
        return a[0] - a[1] < b[0] - b[1];
    }
        
    int twoCitySchedCost(vector<vector<int>>& costs) {
        
        sort(costs.begin(), costs.end(), cmp);

        int ans = 0, n = costs.size() >> 1;
        for (int i = 0; i < n; ++i)
            ans += costs[i][0] + costs[i + n][1];
            
        return ans;
    }
};

二者的区别主要在于cmp函数处。
解法1直接将cmp函数的内容缩略至sort函数中，auto关键字的使用可以使程序正确地判断传递参数的类型；
解法2则需要清晰地定义cmp函数中的参数类型，此时不允许使用auto关键字是因为auto不能出现在函数的原型中。同时Leetcode解题过程中需要将cmp函数定义为static类型(静态成员函数指针和普通函数指针没区别)或置于类外(作为全局普通函数)，不能定义成常规成员函数指针是因为成员函数指针有隐含变量，例如：bool cmp(Solution* this, vector<int> a, vector<int> b)，所涉及到的this指针是普通函数所不具备的。更详细的关于成员函数指针和普通函数指针的分析可参见这篇博客。

2. 查找

vector
vector的初始化和有序状态下的二分查找可参照下例子：

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;

int main()
{
	//C++ 11
	vector<int> a = {1,2,3,4,5};
    vector<int> a1(4,3); // initialize the value of 4 elements to 3
	
	//before C++ 11
	int a[7] = {1,2,3,4,5,6,7};  
    vector<int> b(a,a+7); 

    int c = lower_bound(a, a+5, 2) - a; // 1
	int d = lower_bound(b.begin(), b.end(), 5) - b.begin(); // 4

 	return 0;
}

lower_bound()返回一个迭代器，具体指向大于等于key的第一个值的位置。
upper_bound()返回一个迭代器，具体指向大于等于key的最后一个值的位置。

3. 指数

不同于python有便捷的乘方使用方法**，C++中可使用1<<n的方式表示 $2^n$ 的数值，使用x>>n的方式表示 $\lfloor \frac{x}{2^n} \rfloor$ 。

4. 常识

查看vector长度时要用a.size()，查看数组长度可用sizeof(a)/sizeof(a[0])。
C++使用INT_MAX/LONG_MAX和INT_MAX/LONG_MIN来表示最大/最小量，Python则使用float("inf")和float("-inf")来表示。
int dp[n][n] = {0};报错是因为，C++中不可在使用变量定义数组的同时赋值，需要随后赋值。
C++中，树节点用TreeNode* root定义，空节点用nullptr表示。
C++中，true，false；Python中，True，False。
Python3刷题时，若要设置全局变量，可直接在类内函数外定义变量，例如ans = 0，然后在函数中以self.ans的形式调用。