Gina's blog
为你，千千万万遍
算法复习（C++）
2024.05.28
2024.05.30
算法
2.4k words 12 min

不很硬核，算心血来潮的时候记录一下算法

一、指针复习

image-20240528144526263

主要是二维数组的实参函数定义与调用,在CCF第33次测试的第三题化学方程式配平使用，计算矩阵高斯消元时写递归函数，需要传二维参数。先放递归代码（有部分样例没有通过，猜测是在计算的时候没有优化出错，大概在这一行，先放着，有时间看吧

1
2
float tmp =  (*((float *)num + i*hor + lie))/( *((float *)num + hang*hor + lie));    
 *((float *)num + i*hor + j) -= tmp*  (*((float *)num + hang*hor + j)) ;

递归：

image-20240528144526263

++
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
49
50
51
52
53
54
55
56
57
58
int gaos(float ** num,int hor,int p,int lie,int hang)
{
    if(hang >= p) return 0;
    if(lie >= hor) return 0;
    bool flag = 0;
    for (int i = hang ; i < p ; i ++)
    {
        if(*((float *)num + i*hor + lie) != 0)
        {

            flag = 1;
            break;
        }
    }
    if(flag == 0)   return gaos((float **)num,hor,p,lie + 1,hang + 1);
    else
    {
        if(*((float *)num + hang*hor + lie)==0)
        {
            for(int i = hang + 1 ; i < p; i ++) //1
            {
                if(*((float *)num + i*hor + lie) != 0)
                {
                    for (int j = lie ; j < hor ; j ++)
                    {

                        int tmp = *((float *)num + i*hor+ j);
                        *((float *)num + i*hor+ j) = *((float *)num + hang*hor+ j);
                        *((float *)num + hang*hor + j) = tmp;

                    }
                }
            }
        }

        for (int i = hang + 1 ; i < p ; i ++)
        {

            if(*((float *)num + i*hor + lie)!=0)
            {
                float tmp =  (*((float *)num + i*hor + lie))/( *((float *)num + hang*hor + lie));
                for (int j = lie ; j < hor ; j ++)
                {
                    *((float *)num + i*hor + j) -= tmp*  (*((float *)num + hang*hor + j)) ;

                }

            }


        }

        return gaos((float **)num,hor,p,lie + 1,hang + 1);

    }


}

第一次亲手写这么长的递归代码，但其实大部分代码在处理元素，递归的难度不大。

二、链表

定义

1
2
3
4
5
6
7
8
class node
{
public:
	int data;    //存储数据
	int times = 0;
	node *next;  //指向下一个node的地址

};

声明

1
node *head = new node;  // 创建头节点

遍历

1
2
3
4
5
6
7
8
9
10
for(p = head; p != NULL; p = p->next)
{
    if(p->data == val)
    {
        p->times += 1;
        exists = true;
        break;
    }
    else if(p -> next == NULL) break;
}

遍历中删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(node *p = head -> next ; p != NULL ; p = p->next)
{
   //cout << p->data << " " << p->times << endl;
    if(( p -> next != NULL))
    {
      if(p->next ->times < k){
        if(p -> next -> next == NULL)
        {
            p -> next = NULL;
        }
        else
        {
            p -> next = p -> next -> next;
        }
      }
    }
    else if(p -> next == NULL ) break;

}

这里需要注意如果写成

1
if ((p->next ->times < k) &&( p -> next != NULL))

不可以，一直记错了以为if判断语句汇编里，多个逻辑与是从后往前判断，其实是从前往后判断，如果先写检测下个节点次数是否小于k 就可能出现下个节点为空故而死循环呜呜呜。

所以要写成

1
if (( p -> next != NULL) &&(p->next ->times < k))

或者多拆几个循环嵌套（我知道这样做确实丑陋但是就不用特地记if的判断顺序了

整体实现

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class node{
public:
    int val = 0;
    node *next;
    node *last;
};


int main(){

    node *head = new node;
    cout << head <<endl;
    node *p = head;
    node *tail;
    cout << p << endl;
    for (int i = 0 ; i < 10 ; i ++)
    {
       head -> val += 1;
       node * next_node = new node;
       next_node->next = NULL;
       next_node->last = p;
       p ->next = next_node;
       p = p->next;
       p -> val = i;
       tail = next_node;
    }
    cout <<endl;
    p = tail;
    cout << p << endl;
    while(p != head)
    {
        cout << p ->val << " ";
        p = p->last;
        if(p == head) break;
    }
    cout << endl << "双向链表完成";
    cout << "中间删除一个元素，删除4好嘞" <<endl;
    p = head;
    node *need_delete;
    while(p != NULL){

        if(p-> val == 4 && p != head)
        {
            cout <<"p  :" << p << endl;
            cout << "(p -> last) -> next :" << (p -> last) -> next  << endl;
            cout << " p -> next" <<  p -> next << endl;
            cout << "(p -> next) -> last" << (p -> next) -> last << endl;
            cout << " p -> last" <<  p -> last << endl;
            (p -> last) -> next = p -> next;
            (p -> next) -> last = p -> last;
             cout <<"p" << p << endl;
            cout << "(p -> last) -> next :" << (p -> last) -> next  << endl;
            cout << " p -> next" <<  p -> next << endl;
            cout << "(p -> next) -> last" << (p -> next) -> last << endl;
            cout << " p -> last" <<  p -> last << endl;
            cout << "已经删除";
            need_delete = p;
            p = p-> next;
            delete(need_delete);
            break;
        }
        else p = p->next;
        if(p ->next == NULL ) break;

    }

   p = head;
    while(p  != NULL)
    {
        p = p->next;
        cout << p ->val << " ";
        if(p -> next == NULL) break;
    }
   p = tail;
    while(p != head)
    {
        cout << p ->val << " ";
        p = p->last;
        if(p == head) break;
    }
   
}

包括双向链表，删除元素。前后序遍历之类。

image-20240529213706906

三、素因数寻找

参考了csdn的代码，这个方式好牛逼，而且步骤也简单，经常也会遇到素数题，记一下，真的牛。

1
2
3
4
5
6
7
8
9
while(sum > 1)
      {
          if(sum % val == 0)
          {
              sum /= val;
              // val从2开始，就是素因数，真的牛
          }
          else val += 1;
      }

四、优化（前缀和

刷到31次ccf之后，遇到简单的坐标变换，只需要根据题目描述，很快就可以把代码写出来。但是在提交的时候发现数据过大的时候，会超时，但是整个代码只有两层循环，自己做了很多尝试，累计变化最后结算，变量移来移去，运行时间超了50%

CSDN看见了优化代码，时间复杂度从o(n2)到O(n)了。

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

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int type;
        double value;
        cin >> type >> value;
        if (type == 1) {
            k[i] = k[i - 1] * value;
            xita[i] = xita[i - 1];
        } else {
            k[i] = k[i - 1];
            xita[i] = xita[i - 1] + value;
        }
    }

    for (int i = 0; i < m; ++i) {
        int l, r;
        double x, y;
        cin >> l >> r >> x >> y;

        double sum_xita = xita[r] - xita[l - 1];
        double pro_k = k[r] / k[l - 1];

        cout << fixed << setprecision(3) << (x * cos(sum_xita) - y * sin(sum_xita)) * pro_k << " "
             << (x * sin(sum_xita) + y * cos(sum_xita)) * pro_k << endl;
    }

    return 0;
}

其思想是不对原本变量进行保留，输入操作的时候就直接记录操作前缀和变化，由于查询时会输入起点与终点，于是前缀和相减、除就可以获得变化。这样每次查询就可以直接输出结果，时间复杂度降低。

我自己时间大概是3s ,这个同样样例数据只需要500ms。真的牛，Mark一下。

STL

STL-vector

库

1
#include <vector>

初始化

1
vector<int> a;

常用函数

1
2
3
4
5
6
7
8
a.push_back(3);//在最后插入3
a.insert(a.begin(),3);//在a.begin()开始插入3
a.size();//返回大小(元素个数)
a.pop_back();//删除最后一个元素
a.empty();//判断是否为空
a.clear();//清空
a.resize(20,3);//改成一共20个元素，每个都是3（已经指定的不会修改
a.swap(b);//b也是向量    a和b内容完全交换

便捷方法

1
2
3
4
5
#include <algorithm>
sort(a.begin(),a.end());//从小到大排序
reverse(a.begin(), a.end());//颠倒
auto it = find(a.begin(),a.end(),6);
return distance(a.begin(),it);//找元素返回位置

传参

1
2
int print_vec(const vector<int> & a){   }
print_vec(a);

测试代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include<algorithm>
using namespace std;

int print_vec(const vector<int> & a)
{
    cout << a[0];
    return 1;
}
int print_vec_all(const vector<int> &a)
{
     for (int i = 0 ; i < a.size();i++){
        cout << a[i] << " ";
     }
     cout << "全部打印完成" << endl;
     return 1;
}

int main(){

   vector<int> a;
   a.push_back(2);
   a.insert(a.begin()+ 1,3);
   print_vec(a);
   cout <<endl;
   print_vec_all(a);
   if(!a.empty())
   {
          a.clear();
          if(a.empty())
          cout << "已经清空" << endl;
   }
   for(int i = 0; i <= 10 ; i ++)
   {
       a.insert(a.begin() + i,i);
   }
    print_vec_all(a);
    a.clear();
    a.insert(a.begin(),5,520);
    cout << "向量a后面插入5个数值，都是520"<< endl;
    print_vec_all(a);
    a.resize(20,1);
    cout << "a的元素个数设置为20个，都是1 [已经存在的不会改动]"<< endl;
    print_vec_all(a);
    vector<int> b;
    b.resize(5,0);
    a.swap(b);
    cout << "a和b完全交换" <<endl;
    print_vec_all(a);
    print_vec_all(b);
    a = b; //直接赋值
    print_vec_all(b);
       for(int i = 0; i <= 10 ; i ++)
   {
       a.insert(a.begin() + i,10-i);
   }
    print_vec_all(a);
    sort(a.begin(),a.end());//默认从小到大
    print_vec_all(a);
    reverse(a.begin(),a.end());
    print_vec_all(a); //倒置
    auto it = find(a.begin(), a.end(), 6);
    cout <<distance(a.begin(), it);
}

STL-stack

感觉栈的东西好少和vector比起来

1
2
3
4
5
6
7
#include <stack>
stack<int> a;
a.push();//压栈
a.pop();//弹栈
a.empty();
a.top();//栈顶
print_satck(a);//函数调用

打印只能搞个新的挨个输出

1
2
3
4
5
6
7
8
9
int print_stack(const stack<int> &a){
    stack<int>tmp = a;
    while(!tmp.empty())
    {
        cout << tmp.top() <<" ";
        tmp.pop();
    }
    cout << endl;
}

STL-queue

1
2
3
4
5
6
7
8
9
#include <queue>
queue<int> q;
q.push();//压入队列
q.pop();//弹出队列
q.front();//返回队列第一个元素
q.back();//返回队列最后一个元素
q.empty();
q.size();//队列大小
//函数调用和传参和栈一样

排序算法

1
2
3
#include <algorithm>
sort(a.begin(),a.end()); //结构体排序自己写比较函数作为第三个参数
stable_sort(arr,arr+10); //排序后相同元素相对顺序不变

数组滑动

1
2
3
4
5
6
7
8
9
10
11
12
//  1 2 3 4            2 3 4 1   左滑p个
void slip(int *a,int n,int p){
    int tmp[n];
    for(int i = 0 ; i < n ; i ++)
    {
        tmp[i] = a[i];
    }
    for (int i = 0; i < n; ++i) {
        a[i] = tmp[(i + p) % n];
    }

}
C++ 算法
算法记录
Carvana ImageMasking Challenge [基于UNET的kaggle图像遮蔽挑战]
© 2020 Gina
Powered by hexo | Theme is blank
Title - Artist
0:00