算法笔记-C++专题

记录刷题过程中遇到的重要知识点和新知识！

C++专题

小知识点

定义链表

1
2
3
4
5
6
// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

初始化

1
ListNode* head = new ListNode(5);

1
2
ListNode* head = new ListNode();
head->val = 5;

最大最小值

int maxval=INT_MIN; //最小值
int minval= INT_MAX;

数据类型转换

int转striing

1
2
int n=10;
string s =to_string(n);

string转int

1
stoi(s)
  • atoi()和stoi()

atoi()的参数是 const char ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char\类型的

而stoi()的参数是const string,不需要转化为 const char\；

  • 空指针
1
nullptr

选择子集

  • 这里介绍一种用独热编码的形式选择子集的方法，时间复杂度较高，但做法还是比较巧妙，值得学习的。
1
2
3
4
5
6
7
8
9
int start_num = 1<<n;//n位2进制编码 用来表示子集的选择情况
        for(int i=0;i<start_num;i++){
            int temp=0;
            for(int j=0;j<n;j++){
                if((i>>j)&1==1){
                    //如果当前位被选中
                    // 做接下来的事情
                }
            }

代码里可以直观的看到(n=8举例)

i 从 0000 0000 递增到 0000 0011 ——>1111 1111（共2^n次循环）

在这个过程中 j 从 0到n，也就是说 i (0000 0011) 右移 0-n次，右移完成后与最低位 0000 0001做与运算，如果为1，说明当前位置被选中，也就是num[j]当前i的轮次被选中的元素。

向上取整

  • n/size() 向上取整
1
(n + size - 1) / size; // -1 是为了避免整除情况结果1加1
  • 向下取证
1
int 类型即可

随机数

  • 随机种子
1
srand((unsigned)time(NULL));
  • 随机数
1
int index =rand()%n;
  • 均匀分布的随机浮点数
1
2
3
4
5
mt19937 gen{random_device{}()};
uniform_real_distribution<double> dis(a,b); //生成[a,b)范围的随机浮点数

//用法
double x = dis(gen), y = dis(gen);
  • 正态分布 
1
normal_distribution
  • 二项分布
1
bernoulli_distribution

判断字母 大小写转换

  • 判断是字母
1
isalpha(temp)
  • 转为小写字母
1
tolower('A')

判断是否为数字

1
isdigit(str)

判断字母大小写

1
2
islower('a')
isupper(word[1])

中位数

  • 对数组排序后 向下取整的下标就是中位数所在的下标
1
x = nums[n / 2]

取模

c++ 取模长 需要将负数加模长变为正数再去求摸

if(i>0 && ('a'-'z' +26 )%26==1 )

构建无向图

1
2
3
4
5
6
//创建无向图
        vector<vector<int>> adj(n);
        for(auto i: edges){
            adj[i[0]].push_back(i[1]);
            adj[i[1]].push_back(i[0]);
        }

STL

迭代器

  • c.begin() 返回一个迭代器，它指向容器c的第一个元素
  • c.end() 返回一个迭代器，它指向容器c的最后一个元素的下一个位置
  • c.rbegin() 返回一个逆序迭代器，它指向容器c的最后一个元素
  • c.rend() 返回一个逆序迭代器，它指向容器c的第一个元素前面的位置
  • *iter取当前迭代器的值

排序 sort()

  • 排序的规则是首先按照单词的长度升序排序，如果单词的长度相同则按照字典序降序排序。
  • 自定义sort函数，第一个参数需要排在第二个参数前面时返回true，表示不调整相关位置。
1
2
3
4
5
6
7
sort(words.begin(), words.end(), [](const string & a, const string & b) {
            if (a.size() != b.size()) {
                return a.size() < b.size();
            } else {
                return a > b;
            }
        });
  • 按绝对值排序 
1
sort(vals.begin(), vals.end(), [](int a, int b) { return abs(a) < abs(b); });//这样写可以省个函数名

反转 reverse()

vector string 等反转使用

1
2
3
reverse(nums.begin(),nums.end());//全部反转
reverse(nums.begin(),nums.begin()+k);//反转头
reverse(nums.begin()+k,nums.end());//反转尾

源码：

1
2
3
4
5
6
7
8
void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

最大值/最小值

  • max_element(requests.begin(), requests.end())

返回数组requests 中[0, end)之间的最大值的迭代器，

1
2
// *表示取迭代器的值
int maxRequest = *max_element(requests.begin(), requests.end());
  • min_element(a, a+6)

返回的值减去数组头地址即为该最大值在数组的序号，即下标。

1
2
int loc = min_element(a, a+6) - a;
int min_val = a[loc];

如果要取最大最小值，直接用*取迭代器的值就行。

1
*min_element(a, a+6)
  • 例
1
2
int minValue2 = *min_element(v.begin(), v.end());
int maxValue2 = *max_element(v.begin(), v.end());

累加accumulate()

  • 累加求和

accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值。

1
int sum = accumulate(vec.begin() , vec.end() , 0);

accumulate函数将它的一个内部变量设置为指定的初始值，然后在此初值上累加输入范围内所有元素的值。accumulate算法返回累加的结果，其返回类型就是其第三个实参的类型。

1
2
string sum = accumulate(v.begin() , v.end() , string(" "));  
// 这个函数调用的效果是：从空字符串开始，把vec里的每个元素连接成一个字符串。
  • 自定义

与sort()类似 可自定义累加规则

1
2
3
4
5
6
struct Grade  
{  
    string name;  
    int grade;  
};
int sum = accumulate(subject, subject + 3, 0, [](int a, Grade b){return a + b.grade;}); //a值是前面计算的中间结果

vector

  • vector排序：sort(nums.begin(),nums.end());

升序：sort(vec.begin(), vec.end(), less<int>());

降序：sort(vec.begin(), vec.end(), greater<int>());

  • vector数组的长度：vector.length; 或者 vector.size();

  • 初始化vector

    vector<bool> a(b.size(),false);

    vector<string> honor{"Gold Medal","Silver Medal","Bronze Medal"};

    二维数组初始化

    1
    2
    3
    vector<vector<int>> dp(a.size(),vector<int>(n,0));

    dp[0][0]=0;//可以使用 该方式赋值 访问。

    reserve

    1
    vals.reserve(cnt.size());

  • return

1
return {}; //返回空数组
1
return {1,4};//快速返回数组 相当于初始化一个数组
  • 反转 reverse()
1
reverse(num.begin(),num.end());
  • 删除 erase()
1
2
3
num.erase(num.begin()+i*2+1-i);
// 值得注意的是 删除后 数组的长度会发生变化
num.erase(num.end()-1);
  • 插入 insert()
1
2
//插入元素i到指定位置
p.insert(p.begin(),i);
  • 查找 find()
1
2
3
4
// 查找元素i是否在p中出现 (注意返回的是迭代器)
vector<int>::iterator it = find(p.begin(),p.end(),i);
if (it==p.end())
//不存在
  • 下标 distance()
1
2
//it为迭代器 计算it指向元素的下标index
int dis = distance(p.begin(), it);
  • 清空 clear()
1
ret.clear();
  • 拷贝 assign()
1
nums.assign(newArr.begin(), newArr.end());
  • 最后一个下标
1
nums.back()
  • 重新设置大小 resize()
1
sum.resize((n + size - 1) / size); // n/size 向上取整
  • 删除最后一个元素 pop_back()
1
nums.pop_back();

set和unordered_set

哈希集合

  • set和unordered_set：其中unordered_set对元素不进行排序

find(key)：查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如end() 方法返回的迭代器）。

count(key)：在容器中查找值为 key 的元素的个数。

1
2
3
4
5
unordered_set<string> cnt;
cnt.emplace("");
if (cnt.count(word.substr(0, word.size() - 1))) {
     cnt.emplace(word);
}
  • emplace() 插入
1
cnt.emplace(word);
  • insert() 插入
1
cnt.insert(root->val);
  • erase() 删除
1
2
3
4
5
6
//删除 set 容器中值为 val 的元素
size_type erase (const value_type& val);
//删除 position 迭代器指向的元素
iterator  erase (const_iterator position);
//删除 [first,last) 区间内的所有元素
iterator  erase (const_iterator first, const_iterator last);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
    //创建并初始化 set 容器
    std::set<int>myset{1,2,3,4,5};
    cout << "myset size = " << myset.size() << endl;
   
    //1) 调用第一种格式的 erase() 方法
    int num = myset.erase(2); //删除元素 2，myset={1,3,4,5}
    cout << "1、myset size = " << myset.size() << endl;
    cout << "num = " << num << endl;
    //2) 调用第二种格式的 erase() 方法
    set<int>::iterator iter = myset.erase(myset.begin()); //删除元素 1，myset={3,4,5}
    cout << "2、myset size = " << myset.size() << endl;
    cout << "iter->" << *iter << endl;
    //3) 调用第三种格式的 erase() 方法
    set<int>::iterator iter2 = myset.erase(myset.begin(), --myset.end());//删除元素 3,4，myset={5}
    cout << "3、myset size = " << myset.size() << endl;
    cout << "iter2->" << *iter2 << endl;
    return 0;
}
  • clear() 删除所有元素
1
2
//清空 myset 容器
myset.clear();

map和unordered_map

哈希表

map是有序的，红黑树实现。

unordered_map是无序的，内部实现了一个哈希表。

map int 初始值 0；

  • 插入 insert()：
1
order_list.insert(pair<char, int>(score[i], i));

也可以通过键值对赋值：

1
2
unordered_map<int,int> map;
map[nums[i]]=i;

  • 删除 erase()

  • 统计 count()：

注意count()的参数是map的key

1
2
3
4
//判断 order_list 中是否出现过 x
order_list.count(x)

index_set.count(list2[i]) > 0 //表示该元素出现过
  • 遍历：

方法一：

1
2
3
4
5
6
7
unordered_map<string, int> cnt;
// & 引用
for (auto & [key,val] : cnt) {
          if (key.substr(0, prefix.size()) == prefix) {
              res += val;
          }
}
1
2
3
for (auto &[x, _] : map) {
   vals.push_back(x);
}

方法二：

1
2
3
4
5
std::map<int, TaskInfo*>::iterator iter;
for (iter=maps.begin(); iter!=maps.end(); iter++)
   {
       printf("%d, %s", iter->first, iter->second);
	}
  • 示例
1
2
3
4
5
6
7
unordered_map<int,int> map;
       for(int i=0;i<nums.size();i++){
           if(map.count(target-nums[i])>0)
               return {map[target-nums[i]],i};
           else 
               map[nums[i]]=i;
       }

advance()函数

advance() 函数用于将迭代器前进（或者后退）指定长度的距离，其语法格式如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class InputIterator, class Distance>
    void advance (InputIterator& it, Distance n);
    
举例：
				list<int> lst(nums.begin(), nums.end());
        for (int i = 0;i<this->back.size();i++)
            {
                // 使用list的迭代器
                auto it = lst.begin();
                // 选择随机数
                int j = rand()%(lst.size());
                cout<<j;
                // 将迭代器向后移动j位
                advance(it,j);
            }

string

  • 干货
1
2
3
4
5
6
7
8
9
int string::find(char);     // 字符串中找第一个字符的索引
string string::substr(int); // 从当前索引开始的子串
position=s.find("b",n);     //从字符串s 下标n开始，查找字符串b ,返回b 在s 中的下标
没找到的话返回string::npos
position = s.find("jkff");
position != string::npos
返回子串出现在母串中的首次出现的位置，和最后一次出现的位置:
position = s.find_first_of(char);
position = s.find_last_of(char);
  • 初始化
1
2
string sgood="abs";
string sgood_rev(sgood.rbegin(), sgood.rend());
  • 反转
1
2
3
4
reverse(ans.begin(), ans.end());
或者
string sgood="abs";
string sgood_rev(sgood.rbegin(), sgood.rend());
  • 截取字符串
  • substr(开始位置，数量)
1
s.substr(left, right-left);//从left(包括)截取长度为right-left个字符 不包括右边界
1
word.substr(0, word.size())

从indexa开始截断：

1
string a1 = a.substr(indexa,a.size()-indexa);
  • 查找字符串find()

查找字符串a是否包含子串b,不是用strA.find(strB) > 0 而是 strA.find(strB) != string:npos。

其中string:npos是个特殊值，说明查找没有匹配。

1
(s + s).find(goal) != string::npos
  • 查找字符第一次出现的位置
1
int pos1 = str_log1.find_first_of(" ");
  • 拼接字符串
1
2
string code;
code.append(MORSE[c - 'a']);
1
code +="aaa";
  • 生成连续字符
1
string(cnt, 'a')

array

初始化

1
2
3
4
std::array<int, 5> arr = {1, 2, 3, 4, 5};
std::array<double, 100> data {}; //初始化为0.0

values.fill(3.1415926); //通过调用数组对象的成员函数 fill()，可以将所有元素设成给定值。
  • 空格分割字符串，使用stringstream
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(){
    //用于存放分割后的字符串 
    vector<string> res;
    //待分割的字符串，含有很多空格 
    string word="   Hello, I want   to learn C++!   ";
    //暂存从word中读取的字符串 
    string result;
    //将字符串读到input中 
    stringstream input(word);
    //依次输出到result中，并存入res中 
    while(input>>result)
        res.push_back(result);
    //输出res 
    for(int i=0;i<res.size();i++){
        cout<<res[i]<<endl;
    }
    return 0;
}
  • 字符串遍历

for (char ch: s)

1
2
3
4
5
unordered_map<char, int> c;
for (char ch: s) {
       ++c[ch];
     }

  • isalnum(char c ) 判断是否是字母或数字
  • isalpha() 判断是否是字母
  • isdigit() 判断是否是数字
  • tolower() 转小写 ；touper() 转大写
1
a = tolower(a);
1
2
3
4
5
string ans;
for(char c : s){
      ans += tolower(c);
   }
return ans;

优先队列 priority_queue

  1. 定义 priority_queue<Type, Container, Functional>

STL里面默认用的是vector

引用

1
priority_queue<pii, vector<pii>, greater<pii>> pq;
  1. 方法
1
2
3
4
pq.empty() 
pq.top()
pq.emplace()
pq.pop()

优先队列没有 insert() 方法

  • 示例
1
2
3
4
5
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy; //greater 升序 队头最小
//pair 插入，插入对应位置就行 不用make_pair()
busy.emplace(arrival[i]+load[i],2);
//当然 使用make_pair()也行
busy.emplace(make_pair(arrival[i]+load[i],*machine));

pair

配合vector使用

1
vector<pair<int, int>> arr;
  • make_pair(1,2)

stack

  • 栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
  • 所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。
  • 栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。
  • 栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
  • **SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。deque是一个双向队列，只要封住一端，只开通另一端就可以实现栈的逻辑了。
1
2
3
stack<int> dataStack;

stack<int> stack1,stack2;
  • push() 入栈
1
dataStack.push(val);
  • pop() 出栈
1
dataStack.pop()
  • top() 栈顶元素
1
dataStack.top()
  • empty() 判断是否为空栈
1
if(stack2.empty())

queue

  • STL 队列不被归类为容器，而被归类为container adapter（ 容器适配器）。
  • 队列中先进先出的数据结构，不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
1
2
queue<int> queue1;
queue<int> queue2;
  • front() 相当于stack的top(),取队首元素
1
queue1.front()

  • back() 取队尾元素

  • push() 在末尾加入一个元素

  • pop() 删除第一个元素

  • empty()

  • 插入元素用 emplace

1
queue1.emplace(1);

语法

1.判断大小写

islower('a')

isupper(word[1])

2. 异或

^运算符

  • 异或运算，相异为真，相同为假，所以 a^a = 0 ;0^a = a
  • 因为异或运算 满足交换律 a\^b^a = a\^a^b = b 所以数组经过异或运算，单独的值就剩下了
1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int reduce = 0;
        for (int num : nums) {
            reduce =  reduce ^ num;
        }
        return reduce;
    }
}

3.引用 &

用 char &c 可以修改原变量的内容

1
2
3
for(char &c : s){
    c =  tolower(c);
}
  • 实例

使用vector<int>& ans可以修改原变量的内容，因此可以使用void返回值。

例题：589. N 叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//递归的思想实现
class Solution {
public:
    void get_val(Node* root,vector<int>& ans){
        if(root==nullptr){
            return ;
        }
        ans.push_back(root->val);
        //遍历孩子节点
        for(auto child : root->children){
             get_val(child,ans);
        }  
    }
    vector<int> preorder(Node* root) {
        vector<int> ans;
        get_val(root,ans);
        return ans;
    }
};

4.把数字字符串转换成int输出

  • atoi()的参数是 const char ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char 类型的,

  • stoi()的参数是const string*,不需要转化为 const char*

1
2
string date = "2019-01-09"
int year = stoi(date.substr(0, 4));

5.数字范围

位运算要加括号if((num & MASK2) == MASK1)

  • int
1
INT_MAX

6.位运算

  • 异或
1
a^b // 相同为0 不同为1
  • 左移乘2
1
2
3
step <<= 1; //步长 * 2
n >>= 1;  //总数 / 2
u << 1 | 1; //✖️2➕1
  • 如何循环int的每一位
1
2
3
4
5
6
7
int n=10;
for(int i=0;n>>i;i++){
	//这里 n>>i 为0时 for循环结束
	//m这里表示n的第i位
	int m = (n>>i)&1; //与1做与运算 可以取出最低位
	
}
  • 移位

看一道例题：

  1. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {

        //思路：
        //依次从n的尾部遍历,直到其前全为0
        //1.将n与1做与操作,取到尾部的数字: n & 1
        //2.将与完1后的结果的尾,左移到前面对应位置： (n & 1) << (31 - i)
        //3.将上述结果赋值给res,每次res都需要与上一次res做或操作才能保留每次拉到前面的数
        //4.每次需要将n做逻辑右移,尾部去掉,前面补零的操作

        int res = 0;

        for (int i = 0; i < 32; i++) {
            //取得每次颠倒的结果
            res = res | ((n & 1) << (31 - i));
            
            //n逻辑右移
            n = n >> 1;
            
            //若全剩下0则直接可以返回
            if (n == 0){
                break;
            }
        }

        return res;

    }
};
  • 快速生成掩码
1
2
static const int MASK1 = 1 << 7;	//2^7 1000 0000
static const int MASK2 = (1 << 7) + (1 << 6); //2^7+2^6	1100 0000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binaryGap(int n) {
        //右移
        int max_dis=0;
        int last=-1;
        for(int i=0;n;i++){
            //取最低位
            if(n&1 ){
                if(last!=-1)
                    max_dis=max(max_dis,i-last);
                last =i;
            }
            n>>=1;
        }
    return max_dis;
    }

7.is_sorted() 判断排序规则

  1. is_sorted()
1
2
3
4
//判断 [first, last) 区域内的数据是否符合 std::less<T> 排序规则，即是否为升序序列
bool is_sorted (ForwardIterator first, ForwardIterator last);
//判断 [first, last) 区域内的数据是否符合 comp 排序规则  
bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);
1
2
is_sorted(nums.begin(), nums.end()) //升序
is_sorted(nums.rbegin(), nums.rend()) //降序
  1. is_sorted_until()

和 is_sorted() 函数相比，is_sorted_until() 函数不仅能检测出某个序列是否有序，还会返回一个正向迭代器，该迭代器指向的是当前序列中第一个破坏有序状态的元素。

1
2
//排序规则为默认的升序排序
ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);

8.统计1的个数

  • __builtin_popcount()

是一个gcc内建的函数，内部实现是用查表实现的。

1
int a=__builtin_popcount(n);

也可以用lowbit 统计最低位1的个数。