刷Leecode时遗忘的C+

Luccas0320

2023-11-28

Leecode; C++

语法

1. 变量的定义及其函数

基本变量（int,float,bool,str)

查看数据类型

1 2	int a = 0; cout << "a的数据类型是：" << typeid(a).name() << endl;

C++中好像不存在自动类型提升

int i1 = 1;
double d1 = 1.3;
int i2 = i1 + i2;  //正确

其他变量(string,vector,list)

auto

1	auto it = cnt.find(fruits[left]); //这里自动推导迭代器

“auto”用于自动推导变量的类型。它允许编译器根据变量的初始化表达式来确定变量的类型，而无需显式指定类型。

字符串string

字符串删除

1	string& erase(int pos, int n = npos);` //删除从Pos开始的n个字符

空字符串`string()`

子字符串

1 2	int start = 0,end = 3; s.substr(start,end)

reverse

1 2	reverse(s.begin(),s,end()); reverse(s.begin()+i,s,end()+i+k);//i和k都是int类型

容器 vector

插入和删除

v.push_back(元素) v.pop_back(元素) v.emplace_back(元素)

v.erase(迭代器)

size大小

返回的是容器大小，但是容器最后一个变量的索引是

1	nums.size() - 1

sort排序

对于容器v

1	sort(v.begin(), v.end());

时间复杂度为O(nlogn)

初始化容器

声明一个简单int容器

vector v;

声明一个长度为5的容器

vector v(5);

声明一个长度为5，所有元素初始值为0的容器

vector v(5,0);

用已有的数组初始化容器,区间：[a,a+6)

int a[6]={5,6,2,0,9,4};
vector v(a,a+6);

用现有容器初始化一个容器

vector v1(5,0);
vector v2(v1);

用迭代器初始化容器

vector v1(5, 0);
vector v2(v1.begin(),v1.end());

把vector转unordered_set

1 2	vector<int>& nums1; unordered_set<int> nums_set(nums1.begin(), nums1.end());

遍历容器

对于字符串t，遍历并计算每个元素出现的次数

unordered_map <char,int> ori;
string t;
for (const auto &c: t) {
            ++ori[c];
        }

其中c就是字符串t中的一个个元素

1
2
3

for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
cout << *it << endl;
}

其中it是v的迭代器，*it就是容器v中的一个个元素

另一种遍历方法：

while (r < int(s.size())) {
if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }

此时r是索引

还有一种

1 2	for (auto it = mp.begin(); it != mp.end(); ++it) { ans.emplace_back(it->second);

这里的it是迭代器，而上面的c字符串t中的是一个个元素（字符）

都相当于，*it就是mp的元素了

for(int i = 0;i<nums.size();i++)
{
    nums[i]=
}

返回最后一个值

nums.back();

栈和队列

这两个都是数据类型，但本质上是以vectoe、list、deque写成的一种接口（容器适配器）

栈stack是先入后出

stack<int> st;
int a = st.top();//返回第一个元素
st.pop();
st.push(x);
st.empty();//返回是否为空

栈与队列理论1

队列是先入先出

queue<int> qu;
int a = qu.front();
int b = qu.back();
qu.push();
qu.pop();
qu.empty();

双头队列

deque que;

que.front();

que.pop_front();

que.pop_back();

que.push_back();

查找

string s;
unordered_map <char,int> ori;
int i1 = s.find('a');
//find找到字符串后返回查找的第一个字符位置，找不到返回-1
unordered_map<char,int>::iterator p = ori.find('a');
//查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();

vector<int> nums2;
nums2.find(1);//会报错 ，没有
//用这个
auto a = find(nums2.begin(),nums2.end(),it);
返回的a不是索引而是迭代器

map<int, int>m; 
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));

//查找
map<int, int>::iterator pos = m.find(3);

键值对 pair

1	pair<string, int> p2 = make_pair("Jerry", 10);

pair构成map

1 2	unordered_map<int, int> cnt map<T1, T2> mp

最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

class Solution {
public:
    unordered_map<char,int> ori,cnt;
    bool check()
    {
        for(const auto &p:ori)
        {
            if(cnt[p.first]<p.second)
            {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        int start=0,end = 0,length ,result= INT_MAX,ansl = -1;
        for(const auto &c:t)
        {
            ori[c]++;
        }
        for(end = 0;end<s.size();end++)
        {
            if(ori.find(s[end]) != ori.end())
            {
                cnt[s[end]]++;
            }
            while(check() && (start<=end))
            {
                length = end - start + 1;
                ansl = (length<result)?start:ansl;
                result = (length<result)?length:result;
                

                if( ori.find(s[start]) != ori.end() )
                {
                    cnt[s[start]]--;
                }
                
                start++;

            }
        }
        return ansl==-1?string():s.substr(ansl,result);

    }
};

链表

定义：

struct ListNode{
    int val;
    ListNode* node;
    ListNode(int x):val(x),node(NULL){};//一个构造函数
};
//两种初始化方式
//自己定义构造函数
ListNode* head = new ListNode(5);

//默认构造函数
ListNode* head = new ListNode();
head->val = 5;

2. 运算符的使用

逻辑运算符

&&和&、||和| 跟 java一样

void test07()
{
    int i1 = 0;
    double d1 = 1.3;
    bool b1 = 1;

    int a = i1 + d1;
    cout << "a的数据类型是：" << typeid(a).name() << endl;
    cout << "i1的数据类型是：" << typeid(i1).name() << endl;
    cout << "d1的数据类型是：" << typeid(d1).name() << endl;
    bool b2 = 0;
    cout << "b1 && b2：" << (b1 && b2) << endl;
    bool b3 = b2 && (i1++);
    cout << "i1的值是：" << i1 << endl;
    bool b4 = b2 & (i1++);
    cout << "i1的值是：" << i1 << endl;
}

1701225616574

三目运算符

3. 函数的定义

在函数中调用容器

1 2	int minSubArrayLen(int target, vector<int>& nums) { }

4. 结构

结构分为正常的前向引用结构，分支结构（if，switch)和循环结构

循环结构

for循环

是可以不加迭代的

一般是

for(①;②;④)
{
③
}

①初始化

②停止条件

③函数体

④迭代

①——>②——>③——>④——>②——>③——>④

可以

for(①;②;)
{
③
}

while循环语句

作用：满足循环条件，执行循环语句

语法： while(循环条件){ 循环语句 }

解释：==只要循环条件的结果为真，就执行循环语句==

算法

数组

二分法

双指针法

只要有两个指针就可以，不管是一个快指针一个慢指针，还是两个相对方向移动的指针

可以认为是把暴力解法的双层循环，外层循环为快指针，内层循环为慢指针

滑动窗口

可以认为是双指针法的变种

异或实现swap

a ^ a=0
a ^ 0=a
a ^ b=b ^ a

a ^= b;
b ^= a;
a ^= b;

1
2
3

解释

a=(a ^ b);
b=(a ^ b) ^ b=a ^ (b ^ b) = a ^ 0 = a;
a=(a ^ b) ^ a =(a ^ a) ^ b = 0 ^ b =b;

排序算法

![1712584347763](D:\Program Files (x86)\MyBlog\source_posts\刷Leecode时遗忘的C++\1712584347763.png)

https://www.acwing.com/solution/content/24716/

注意事项

1、我用 vector<vector<int>> dp(n+1,vector<int>(m+1,0));超时；尝试vector<vector<uint64_t>> dp(n+1,vector<uint64_t>(m+1,0));

不同的数据类型在内存消耗和计算速度上有所差异。

vector<vector<int>> 使用的是 int 类型，即有符号整数。有符号整数的取值范围是有限的，通常为 -2^31 到 2^31-1 之间。当在动态规划等问题中使用 int 类型来存储中间结果时，可能会出现整数溢出的情况，导致结果不正确。

而 vector<vector<uint64_t>> 使用的是 uint64_t 类型，即无符号64位整数。无符号整数的取值范围是非负的，通常为 0 到 2^64-1 之间。使用无符号整数类型可以更好地处理较大的数值，避免溢出问题，从而得到正确的结果。

由于 uint64_t 类型可以表示更大的整数范围，可能会占用更多的内存空间。这也是为什么使用 vector<vector<uint64_t>> 可能会导致更高的内存消耗。但是，如果问题需要处理较大的数值或需要较大的计数范围，选择使用 uint64_t 类型是更合适的。

因此，在你的情况下，使用 vector<vector<uint64_t>> 帮助避免了整数溢出问题，从而得到了正确的结果。但请注意，使用更大的数据类型可能会增加内存消耗和计算时间，所以在选择数据类型时需要权衡内存和速度的要求。

2、测试样例通过但是提交不通过

最后的答案MOD 10e9+7试试

语法