LeetCode刷题记录(cpp)

算法 , , 评论

stringstream用法

需要include<sstream>，任何输入输出都会被转换成字符串

istringstream类用于执行C风格的串流的输入操作

ostringstream类用于执行C风格的串流的输出操作

stringstream类同时支持C风格的串流的输入输出操作

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
// 例子1: 基本用法
int main()
{
    string s;
    stringstream ss;
    int n = 11, m = 88;
    // 将11放入流中
    ss << n;
    // 从流中提取数据到s中，自动类型转换，无需关心类型问题
    ss >> s;
    // 11
    cout << s << endl;
    s += "23";
    // 1123
    cout << s << endl;
    // 清空，以便下一次使用
    ss.clear();
    ss.str("");
    ss << s;
    ss >> n;
    // 1123
    cout << n << endl;
    return 0;
}


// 例2：按空格分隔字符串
int main(int argc, char const *argv[])
{
    stringstream ss("1 2 3");
    string s;
    while (ss >> s)
    {
        cout << s << endl;
    }
    return 0;
}

// 例3：按分隔符分隔字符串
const vector<string> split(const string &str, const char &delimiter)
{
    vector<string> result;
    stringstream ss(str); // 等于ss.str(str);
    string tok;
    while (getline(ss, tok, delimiter)) // 从ss流中按delimiter为分隔符读取数据存储到tok中，直到流结束
    {
        result.push_back(tok);
    }
    return result;
}

默认值

string类型的默认值是""

int类型的默认值是0

substr函数用法

string s("123");
string a = s.substr(0,5);// 获得字符串s中从第0位开始的长度为5的字符串，若 pos+n>s.length()，只会截取到末尾

string.length()或者size()与变量作比较的bug

string.length()是unsigned型的不能与负数作比较，否则在机器数的表示上俩者都会以unsigned的编码形式比较，那就大概率结果就不对了,所以建议平时编程养成好习惯，类型不一样的数据比较或运算时一定要留一个心眼，不能直接拿来就比。用的时候可以在前面写上强转

链表题技巧

  • 多用定义变量，不容易被逻辑绕晕，比如修改指针前先用first、second、third先保存下来
  • head有可能发生改动时，先增加一个假head，返回的时候返回head->next，避免修改头结点导致多出一堆逻辑

二叉树题技巧

  • 先考虑递归（前中后序遍历）还是迭代（层序遍历）
  • 递归要先考虑函数是否有返回值，比如说判断是否是平衡二叉树，当前递归函数中要根据左右子树的返回值做判断，所以递归函数要返回值
  • 然后考虑是前，还是中，还是后。如果要先处理左右子树那就是后，特别地，回溯也是后，参考https://programmercarl.com/0236.二叉树的最近公共祖先.html
  • 最后再考虑递归终止条件，一般是root==nullptr就返回，也有特殊情况，比如叶子节点就返回
  • 层序遍历一般用队列。如果要一层一层的访问，在出队的时候要先记录当前层的节点数，根据节点数出队

数字和字符串互转

数字转字符串：to_string(number)

字符串转数字：stoi(intStr) , stol(longStr), stof(floatStr), stod(doubleStr)

数组初始化

初始化一个n*n的二维数组，用0填充

vector<vector<int>>v(n,vector<int>(n,0));

或者

v.resize(n);
for(int k=0;k<n;k++){
  v[k].resize(n);
}

或者用memset

int v[n][n];
memset(v,0,sizeof(int)*n*n);

DFS和BFS适用条件

dfs适合找解的存在和所有解，bfs适合找最优解。例如dfs可以解决可达性，bfs可以解决无权图最短路径（有权使用dijkstra）。dfs需要回溯时要注意，以N皇后和解数独为例，如果当前位置的合法性依赖之前放置的位置，那么回溯时要将位置清除（N皇后），如果当前位置的合法性不依赖之前的位置，而是依赖别的辅助空间，那么回溯时只需要清除辅助空间，放置的位置可以不清除（解数独）

图的连通性

考虑dfs和并查集

自定义排序

// sort函数第三个参数是lambda表达式，[x] 表示捕获外部的变量x
sort(arr.begin(),arr.end(),[x](const int& a,const int& b){
       return abs(a-x)==abs(b-x)?a<b:abs(a-x)<abs(b-x);
});

二分技巧

标准二分查找

int search(vector<int>& nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right)
    {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;
}

二分查找第一个满足XXX的位置

int left = 0, right = nums.size()- 1, ans = -1;
// <= 可以判断区间长度为1时，即left==right时是否有解；若二分条件必须在区间大于等于2的情况下判断，则去掉=，参考leetcode162
while (left <= right)
{
    int middle = left + (right - left) / 2;
    if (满足XXX)
    {
        ans = middle;
        right = middle - 1;
    }
    else
    {
        left = middle + 1;
    }
}
return ans;

二分查找最后一个满足XXX的位置

int left = 0, right = nums.size()- 1, ans = -1;
// <= 可以判断区间长度为1时，即left==right时是否有解；若二分条件必须在区间大于等于2的情况下判断，则去掉=，参考leetcode162
while (left <= right)
{
    int middle = left + (right - left) / 2;
    if (满足XXX)
    {
        ans = middle;
        left = middle + 1;
    }
    else
    {
        right = middle - 1;
    }
}
return ans;

STL的二分查找

lower_bound(begin,end,num): 从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的迭代器，不存在则返回end。通过返回的迭代器减去begin可以得到数字的下标。

upper_bound(begin,end,num): 从数组的begin位置到end-1位置二分查找第一个大于num 数字，找到返回该数字的迭代器，不存在则返回end。通过返回的迭代器减去begin可以得到数字的下标。

// 用在vector上
vector<int> nums1{1,10,4,4,2,7};
sort(nums1.begin(),nums1.end());
int pos1 = lower_bound(nums1.begin(),nums1.end(),9)-nums1.begin();

// 用在数组上
int nums2[6] = {1, 10, 4, 4, 2, 7};
sort(nums2,nums2+6);
int pos2 = lower_bound(nums2,nums2+6,9)-nums2;

// 返回vector中最靠近5的第一个小于或等于5的数
vector<int> nums1{1,10,4,4,2,7};
sort(nums1.rbegin(),nums1.rend());
int pos3 = lower_bound(nums1.begin(), nums1.end(), 5,greater<int>())-nums1.begin();

优先队列

// 升序序列
priority_queue<int, vector<int>, greater<int>>q;
// 降序序列(默认，等同于priority_queue<int>)
priority_queue<int, vector<int>, less<int>>q;
 
// 自定义类型排序
struct student
{
    student(int age){
        this->age = age;
    }
    int age;
};
struct cmp{
    bool operator() (student& s1,student& s2){
        return s1.age<s2.age;
    }
};
int main(int argc, char const *argv[])
{
  vector<int> ages{3,4,1,2};
  priority_queue<student,vector<student>,cmp>a;
  for(int age:ages){
    student s(age);
    q.push(s);
  }
  while(q.size()>0){
      student head = q.top();q.pop();
      cout<<head.age<<endl;
  }
}

位运算符技巧

按位与运算符（&）

参加运算的两个数据，按二进制位进行“与”运算

运算规则：0&0=0；0&1=0；1&0=0；1&1=1；

即：两位同时为1，结果才为1，否则为0

例如：3&5 即 0000 0011 & 0000 0101 = 0000 0001 因此，3&5=1

”与运算“的特殊用途

  • 清零。如果想将一个单元清零，即全部二进制位归0，只要与一个各位都为0的数值相与，结果为0
  • 取一个数的指定二进制位。如果想取某个数的后四位，那么可以计算 该数&0000 1111

按位或运算符（|）

参加运算的两个数据，按二进制位进行“或”运算

运算规则：0|0=0；0|1=1；1|0=1；1|1=1；

即：参加运算的两个数据只要有一个位1，其值为1

例如：3|5 即 0000 0011 | 0000 0101 = 0000 0111， 因此，3|5的值为7

“或运算”特殊用途

  • 常用来对一个数的某些位置置为1。如果想对某个数的后四位置为1，那么可以计算 该数 | 0000 1111

异或运算符（^）

参加运算的两个数据，按二进制位进行“异或”运算

运算规则：0 ^ 0=0；0 ^ 1=1；   1 ^ 0=1；   1 ^ 1=0；

即：参加运算的两个数据，如果两个相应位值不同，则该位位1，否则为0（模2和）

“异或运算”特殊用途

  • 翻转一个数的指定位。如果将对某个数的后四位翻转， 那么可以计算 该数 ^ 0000 1111
  • 与0异或，保留原值

取反运算符（~）

参加运算的一个数据，按二进制位进行“取反”运算

运算规则：~1 = 0；~0 = 1；

即：对一个二进制数按位取反。

“取反运算”特殊用途

  • 使一个数的最低位为0，可以计算 该数 & ~1

左移运算符（<<）

将一个数据的各二进制位全部左移若干位（左边的二进制位丢弃，右边补0）

例如：a = a << 2 将a的二进制位左移2位，右补0。若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2

右移运算符（>>)

将一个数的各二进制位全部右移若干位，正数左补0，负数左补1，右边丢弃。

例如： a = a >> 2 将a 二进制位右移2位，操作数每右移一位，相当于该数除以2

>> 运算符把 expression1 的所有位向右移 expression2 指定的位数。expression1 的符号位被用来填充右移后左边空出来的位。向右移出的位被丢弃。

例如-14（1111 0010）右移两位等于-4（11111100）

无符号右移运算符（>>>)

>>> 运算符把 expression1 的各个位向右移 expression2 指定的位数。右移后左边空出的位用零来填充。移出右边的位被丢弃。

例如 -14 （11111111 11111111 11111111 11110010），向右移两位后等于1073741820（00111111 11111111 11111111 11111100）

不同长度的数据进行位运算

如果两个不同长度的数据进行位运算时，系统会将二者按右端对齐，然后进行位运算

以“与”运算为例说明如下：我们知道在C语言中long型占4个字节，int型占2个字节，如果一个long型数据与一个int型数据进行“与”运算，右端对齐后，左边不足的位依下面三种情况补足

  • 如果整形数据为正数，左边补16个0
  • 如果整形数据为负数，左边补16个1
  • 如果整形数据为无符号数，左边也补16个0

数组题技巧

考虑双指针，双向前缀和，单调队列

快排

void myquickSort(vector<int>& nums,int low,int high){
    // mid不能是下标
    int mid = nums[(low+high)/2];
    int i = low,j = high;
    do{
        while(nums[i]<mid) i++;
        while(nums[j]>mid) j--;
        if(i<=j) swap(nums[i++],nums[j--]);
    }while(i<=j);
    if(low<j) myquickSort(nums,low,j);
    if(i<high) myquickSort(nums,i,high);
}

背包问题

常见的背包问题有三种

组合排列问题

    1. 组合总和 Ⅳ
    1. 目标和
    1. 零钱兑换 II

True、False问题

    1. 单词拆分
    1. 分割等和子集

最大最小问题

    1. 一盒零
    1. 零钱兑换

组合排列问题公式

dp[i] += dp[i-num]

True、False问题公式

dp[i] = dp[i] or dp[i-num]

最大最小问题公式

dp[i] = min(dp[i],dp[i-num]+1)或者dp[i] = max(dp[i],dp[i-num]+1)

以上三组公式是解决对应问题的核心公式

背包问题分析步骤

  1. 分析是否为背包问题
  2. 是以上三种背包问题中的哪一种
  3. 是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用
  4. 如果是组合排列问题，组合问题外循环物品，内循环背包；排列相反

背包问题特征

背包问题具有的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数组，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target

背包问题遍历

  • 如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序

    for(int i=0;i<nums.size();i++){
  for(int j=target;j>=nums[i];j--){
    // dp公式
  }
}

  • 如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环，且内循环正序

    for(int i=0;i<nums.size();i++){
  for(int j=nums[i];j<=target;j++){
    // dp公式
  }
}

  • 如果是排列问题，即需要考虑元素之间的顺序，target放在外循环，nums放在内循环

    for(int i=0;i<=target;i++){
  for(int j=0;j<nums.size();j++){
    if(i>nums[j]){
      // dp公式
    }
  }
}

单调栈

通常是一维数组，要寻找任一元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了

panzun