Jepson's Blog
0%

Posted on

string和vector都有insert和erase函数，但是参数有区别。

容器 insert erase *note
string s.insert(i, s) s.erase(i, n) string可以用迭代器也可以直接用下标，习惯直接用下标
vector a.insert(a.begin()+i, val) a.erase(a.begin()+i) vector只能用迭代器

Posted on

1.先枚举区间长度

1
2
3
4
5
6
7
8
for(int len=3;len<=n;len++){
    for(int i=0;i+len-1<n;i++){
        int j = i+len-1;
        for(int k=i+1;k<=j-1;k++){
            dp[i][j] = max(dp[i][j], a[k]*a[i]*a[j]+dp[i][k]+dp[k][j]);
        }
    }
}

这种比较好理解。

2.先枚举区间边界

1
2
3
4
5
6
7
for(int i=n-1;i>=0;i--){
    for(int j=i+1;j<=n-1;j++){
        for(int k=i+1;k<=j-1;k++){
            dp[i][j] = max(dp[i][j], a[k]*a[i]*a[j]+dp[i][k]+dp[k][j]);
        }
    }
}

这种方式在枚举左边界的时候需要逆序枚举，因为区间dp要保证所有小区间都被计算过了才能计算大区间，如果i正向枚举的话，会导致dp[k][j]没有被计算过，因为k>i，而反向枚举i即可保证所有的dp[k][j]都被计算过。

Posted on Edited on

一个基于非比较的排序算法，只能应用于整数排序，复杂度为O(dn)，d是整数最大的长度，即可以在线性时间和线性空间复杂度内完成排序，快于一切基于比较的排序算法，比如快排、归并排序等。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if(n<2) return 0;
        int ans = 0;
        //sort(nums.begin(),nums.end());

        int mx = -0x3f3f3f3f;
        // 找到最大的整数，决定排序迭代的次数
        for(int i=0;i<n;i++){
            mx = max(mx, nums[i]);
        }
        int x = 1;
        vector<int> tmp(n);

        while(mx>=x){
            // 计数器
            vector<int> cnt(10);
            // 对十进制的每一位进行计数
            for(int i=0;i<n;i++){
                int d = (nums[i]/x)%10;
                cnt[d] ++;
            }
            // 把计数器转换为索引
            for(int i=1;i<10;i++){
                cnt[i] += cnt[i-1];
            }
            // 逆序遍历，对数组进行重新排序
            for(int i=n-1;i>=0;i--){
                int d = (nums[i]/x)%10;
                tmp[cnt[d]-1] = nums[i];
                cnt[d] --;
            }
            // 更新数组
            //copy(tmp.begin(), tmp.end(), nums.begin());
            nums.swap(tmp);
            
            x *= 10;
        }

        for(int i=1;i<n;i++){
            ans = max(ans, nums[i]-nums[i-1]);
        }
        return ans;
    }
};

20211209124114

Posted on Edited on
malloc new
从堆上动态分配内存 从自由存储区动态分配内存
返回值是void*，需要强制转换 自动返回对象类型的指针
需要制定内存大小 不需要制定内存大小
分配失败返回NULL 分配失败抛出bac_alloc异常
内存不够不能重新分配 可以重新分配
不能调用构造函数和析构函数 可以调用构造函数和析构函数
不能初始化数组元素对象 可以初始化数组元素对象？

自由存储区是c++基于new操作符的一个抽象概念，其可以是堆也可以是静态存储区，主要取决于operator new的实现。

Posted on

const

const是只读类型的变量，值不能修改，只能在定义的时候赋值。

形式为const int a = 1;

常量指针和指针常量

常量指针又叫底层const，形式为const int *p = &a;

特点：不能使用该指针修改指向的值，但是可以修改指针指向的地址。

即，初始化后不可以*p=2，但是可以p=&b;

指针常量又叫顶层const，形式为int* const p = &a;

特点：能使用该指针修改指向的值，但是不可以修改指针指向的地址。

即，初始化后可以*p=2，但是不能p=&b;

还有一种叫做常指针常量的，形式为const int* const a = &b;

是常量指针和指针常量的综合，既不可以修改指针指向的地址也不可以修改指针指向的值。