首页
music
关于
推荐
我的B站主页
GitHub主页
Codeforces
Search
1
《美丽数学》读书笔记
49 阅读
2
2023年10月11日创世之初
30 阅读
3
C语言基础
28 阅读
4
冒泡排序
24 阅读
5
排序算法
17 阅读
大事件
读书记录
C语言
SQL
C++
函数
算法
Python
数据结构
登录
Search
标签搜索
C语言
SQL
函数
Mellow-sky
累计撰写
23
篇文章
累计收到
1
条评论
首页
栏目
大事件
读书记录
C语言
SQL
C++
函数
算法
Python
数据结构
页面
music
关于
推荐
我的B站主页
GitHub主页
Codeforces
搜索到
9
篇与
的结果
2024-09-28
素数筛法(埃氏筛法、线性筛法)
素数筛法:用于筛选出素数核心思想:用一个数筛选其余的数普通筛法:时间复杂度为O(nlogn)#include <iostream> #define N 100 bool vis[N] = { false };// 0到N-1的元素都没有被标记 int primes[N]; // 存放素数 int tot; //普通筛法 int main() { vis[0] = vis[1] = true; // 0和1不是素数 for (int i = 2; i < N; i++) { if (!vis[i]) { primes[++tot] = i; // 找到一个素数,存放到primes中 } for (int j = 2 * i; j < N; j += i) { vis[j] = true; // 将i的倍数都标记为已被筛掉 } } for (int i = 1; i < tot; i++) { std::cout << primes[i] << " "; } std::cout << std::endl; return 0; }继续优化的话可以 只用质数去筛 ,这也就是埃氏筛法:时间复杂度为:O(nloglogn)int main() { vis[0] = vis[1] = true; // 0和1不是素数 for (int i = 2; i < N; i++) { if (!vis[i]) { primes[++tot] = i; // 找到一个素数,存放到primes中 for (int j = i * i; j < N; j += i) { vis[j] = true; // 将i的倍数都标记为已被筛掉 } } } for (int i = 1; i < tot; i++) { std::cout << primes[i] << " "; } std::cout << std::endl; return 0; }继续优化 线性筛 : 每个数都被其最小的质因数筛掉 时间复杂度为O(n)int main() { vis[0] = vis[1] = true; for (int i = 2; i <= N; i++) { if (!vis[i]) { primes[++tot] = i; } for (int j = 1; i * primes[j] < N; j++) { vis[i * primes[j]] = true; if (i % primes[j] == 0) { break; } } } for (int i = 1; i < tot; i++) { std::cout << primes[i]<< " "; } std::cout << std::endl; return 0; }
2024年09月28日
1 阅读
0 评论
0 点赞
2024-07-03
二叉树的建立与遍历
二叉树是一种非线性数据结构. 二叉树 由节点构成,每个节点包含节点值和指向左节点和右节点的指针.常用术语: 根节点(root node):位于二叉树顶层的节点,没有父节点。叶节点(leaf node):没有子节点的节点,其两个指针均指向 None 。边(edge):连接两个节点的线段,即节点引用(指针)。节点所在的层(level):从顶至底递增,根节点所在层为 1 。节点的度(degree):节点的子节点的数量。在二叉树中,度的取值范围是 0、1、2 。二叉树的高度(height):从根节点到最远叶节点所经过的边的数量。节点的深度(depth):从根节点到该节点所经过的边的数量。节点的高度(height):从距离该节点最远的叶节点到该节点所经过的边的数量。二叉树的遍历 分为层序遍历,前序遍历,中序遍历,后序遍历.层序遍历本质为BFS,即广度优先搜索.层序遍历顾名思义,为一层层的从上往下,从左到右遍历.前序遍历,中序遍历,后序遍历本质为DFS,即深度优先搜索.访问时机如图: 代码示例:#include<vector> #include<queue> #include<iostream> struct tree{ int value; tree *left; tree *right; tree(int x) : value(x), left(nullptr), right(nullptr){} }; std::vector<int> vec; //层序遍历 std::vector<int> levelorder(tree *root){ std::queue<tree *> q; q.push(root); std::vector<int> vec; while(!q.empty()){ tree *node = q.front(); q.pop(); vec.push_back(node->value); if(node->left != nullptr){ q.push(node->left); } if(node->right != nullptr){ q.push(node->right); } } return vec; } //前序遍历 void preorder(tree *root){ if(root == nullptr){ return; } vec.push_back(root->value); preorder(root->left); preorder(root->right); } //中序遍历 void inorder(tree *root){ if(root == nullptr){ return; } inorder(root->left); vec.push_back(root->value); inorder(root->right); } //后序遍历 void postorder(tree *root){ if(root == nullptr){ return; } postorder(root->left); postorder(root->right); vec.push_back(root->value); } int main(){ tree *t0 = new tree(1); tree *t1 = new tree(2); tree *t2 = new tree(3); tree *t3 = new tree(4); tree *t4 = new tree(5); t0->left = t1; t0->right = t2; t1->left = t3; t1->right = t4; preorder(t0); for(auto &i : vec){ std::cout << i << " "; } std::cout << std::endl; vec.clear(); inorder(t0); for(auto &i : vec){ std::cout << i << " "; } std::cout << std::endl; vec.clear(); postorder(t0); for(auto &i : vec){ std::cout << i << " "; } std::cout << std::endl; vec.clear(); return 0; }使用数组表示二叉树: 用数组表示时,观察可知节点下标为 i 时,父节点下标为 (i - 1) / 2 左节点下标为 2 i + 1 ,右节点下标为 2 i + 2 依此规律我们可以使用数组表示出二叉树#include<vector> #include<iostream> std::vector<int> vec; int parent(int i){ return (i - 1) / 2; } int left(int i){ return 2 * i + 1; } int right(int i){ return 2 * i + 2; } void pretree(std::vector<int> &tree, int i){ if(i < 0 || i >= tree.size()){ return; } vec.push_back(tree[i]); pretree(tree, left(i)); pretree(tree, right(i)); } void intree(std::vector<int> &tree, int i){ if(i < 0 || i >= tree.size()){ return; } intree(tree, left(i)); vec.push_back(tree[i]); intree(tree, right(i)); } void posttree(std::vector<int> &tree, int i){ if(i < 0 || i >= tree.size()){ return; } posttree(tree, left(i)); posttree(tree, right(i)); vec.push_back(tree[i]); } int main(){ std::vector<int> tree(10); for(int i = 0; i < 10; i++){ std::cin >> tree[i]; } pretree(tree, 0); for(auto &i : vec){ std::cout << i << " "; } std::cout << std::endl; vec.clear(); intree(tree, 0); for(auto &i : vec){ std::cout << i << " "; } std::cout << std::endl; vec.clear(); posttree(tree, 0); for(auto &i : vec){ std::cout << i << " "; } std::cout << std::endl; vec.clear(); return 0; }参考文章
2024年07月03日
6 阅读
0 评论
0 点赞
2024-07-01
链表
链表是一种逻辑结构上的线性表,物理结构上的非线性表链表由许多节点组成,每个节点有对应的值和指向下一个节点的指针第一个节点称为首节点,最后一个节点称为尾节点,尾节点的指向为空.特点:查找某一节点都是由头开始遍历查找,增加节点的效率比顺序表快,删除节点的效率比顺序表快,查找节点的效率比顺序表慢代码示例:#include<iostream> using namespace std; //创建链表结构体,数据成员有值和指向下一节点的指针 struct list{ int value; list *next; list(int x){ value = x; next = nullptr; } }; //在n节点后插入p节点 void insert(list *n, list *p){ p->next = n->next; n->next = p; } //删除n节点的下一个节点 void remove(list *n){ if(n->next == nullptr){ return; } list *p = n->next; list *n1 = p->next; n->next = n1; delete p; } //访问索引index的节点 list *access(list *head, int index){ for(int i = 0; i < index; i++){ if(head == nullptr){ return nullptr; } head = head->next; } return head; } //查找值为target的节点,输出索引 int find(list *head, int target){ int index = 0; while(head != nullptr){ if(head->value == target){ return index; } head = head->next; index++; } return -1; } int main(){ //创建节点 list *n1 = new list(1); list *n2 = new list(2); list *n3 = new list(3); //连接节点 n1->next = n2; n2->next = n3; //测试函数 list *p = new list(10); insert(n1, p); remove(n2); list *p1 = access(n1, 1); cout << find(n1, 10) << endl; return 0; }
2024年07月01日
10 阅读
0 评论
0 点赞
2024-06-04
C++实现顺序表
顺序表,一种线性表,因此顺序表是线性的.因为顺序表在物理结构与逻辑结构都是连续的.意味着在内存中是连续存储的,形如数组的内存存储方式,我将用数组实现顺序表.实现顺序表的主要功能为:增删查改.顺序表是一种简单的数据结构,原理与实现并不难主要维护下标size,内存空间capacity的大小即可Seqlist.h头文件声明#pragma once #include<iostream> #include<cstdlib> #include<cassert> using namespace std; // 顺序表结构定义 typedef int SLDataType; class SeqList { public: SLDataType* arr; int size; int capacity; }; typedef SeqList SL; //检查顺序表容量是否合理 void checkSLCaoacity(SL* ps); //顺序表初始化 void SLInit(SL* ps); //顺序表的销毁 void SLDestroy(SL* ps); //顺序表的插入操作 //头插尾插 void SLPushFront(SL* ps,SLDataType x); void SLPushBack(SL* ps, SLDataType x); //头删尾删 void SLPopFront(SL* ps); void SLPopBack(SL* ps); //选择插入 void SLInsert(SL* ps,int i, SLDataType x); //选择删除 void SLDelete(SL* ps, SLDataType x); //顺序表的查找操作 void SLFind(SL* ps, SLDataType x); //顺序表的修改操作 void SLUpdate(SL* ps, int i, SLDataType x); //输出所以元素 void SLPrint(SL* ps);Seqlist.cpp原文件中存方法#include"SeqList.h" void SLInit(SL* ps) { ps->arr = NULL; ps->size=ps->capacity=0; } void SLDestroy(SL* ps) { if (ps->arr) { delete[] ps->arr; } ps->arr = NULL; ps->size = ps->capacity = 0; } void checkSLCaoacity(SL* ps) { //先判断空间够不够 if (ps->size == ps->capacity) { int newCapacity = (ps->capacity == 0) ? sizeof(SLDataType) : 2 * ps->capacity; SLDataType* temp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType)); if (!temp) { perror("realloc failed"); exit(1); } ps->arr = temp; //delete(temp); ps->capacity = newCapacity; } } //头插尾插 void SLPushFront(SL* ps, SLDataType x) { assert(ps);//传其他类型指针会导致崩溃,给爷爬 checkSLCaoacity(ps); //插入 for (int i = ps->size; i > 0; i--) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ps->size++; } void SLPushBack(SL* ps, SLDataType x) { assert(ps); checkSLCaoacity(ps); ps->arr[ps->size++] = x; } //头删尾删 void SLPopFront(SL* ps) { assert(ps); if (ps->size == 0) { return; } for (int i = 0; i < (ps->size--) - 1; i++) { ps->arr[i + 1] = ps->arr[i]; } } void SLPopBack(SL* ps) { assert(ps); if (ps->size == 0) { return; } ps->size--; } //选择插入 void SLInsert(SL* ps, int i, SLDataType x) { assert(ps); checkSLCaoacity(ps); //1 2 3 4 5 size //0 1 2 3 4 for (int j = ps->size; j >i; j--) { ps->arr[j] = ps->arr[j - 1]; } ps->arr[i] = x; ps->size++; } //选择删除 void SLDelete(SL* ps, SLDataType x) { assert(ps); if (ps->size == 0) { return; } for (int j = 0; j < ps->size; j++) { if (ps->arr[j] == x) { for (int k = j; k < ps->size - 1; k++) { ps->arr[k] = ps->arr[k + 1]; } ps->size--; return; } } cout << "没有找到要删除的元素" << '\n'; } //顺序表的查找操作 void SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i <= ps->size - 1; i++) { if (ps->arr[i] == x) { cout << "找到了第" << i + 1 << "个元素\n"; cout << "值为:" << ps->arr[i] << '\n'; return; } } cout << "没有找到要查找的元素" << '\n'; } //顺序表的修改操作 void SLUpdate(SL* ps, int i, SLDataType x) { assert(ps); checkSLCaoacity(ps); if (i <= 0 || i > ps->size - 1) { cout << "索引越界" << '\n'; return; } ps->arr[i - 1] = x; } //输出所有元素 void SLPrint(SL* ps) { assert(ps); checkSLCaoacity(ps); for (int i = 0; i < ps->size; i++) { cout << ps->arr[i] << " "; } cout << '\n'; }test.cpp源文件中用于测试实现的功能#include"SeqList.h" void test01() { SL s; SLInit(&s);//初始化 //增删查改 //使用for循环插入100个元素 for (int i = 1; i <= 100; i++) { if(i&1) SLPushFront(&s, i); else SLPushBack(&s, i); } //输出所有元素 SLPrint(&s); //查找元素 SLFind(&s, 55); SLFind(&s, 999); //删除元素 SLDelete(&s, 100); SLDelete(&s, 404); SLPrint(&s); //修改元素 SLUpdate(&s, 55, 969696); SLPrint(&s); SLDestroy(&s);//销毁 } int main() { test01(); return 0; }
2024年06月04日
10 阅读
0 评论
0 点赞
2024-05-07
二分法
二分查找本质上是按照某一性质每次一分为二查找左右边界 普通的二分查找 题目 题目解释:在一组有序无重复数组中查找某一个数,如果能查找到输出这个数是第几个数,否则输出-1. 我们可以使用二分法进行查找,即将数组一分为二,从中间的数进行判断是否大于或小于我们要查找的数,因为数组是有序递增的,所以如果中间数大于查找的数我们便查找左部分的数否则查找右部分的数。 代码示例:#include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int l = 1, r = n;//因为数组大小为n所以左右边界为(1,n) int x; cin >> x;//输入要查找的数 while (l < r)//设置跳出循环的条件,即当l=r时退出循环 { int mid = (l + r) >> 1;//(l+r)/2,对中间数进行向下取整 if (a[mid] >= x)r = mid; //如果查询的数小于等于中间数,查询左部分,将右边界向左移 else l = mid + 1; //如果查询的数大于中间数,查询右部分,将左边界向右移,因为数组mid对应的数不对所以再右移一位 } //l下标对应的即是最后的查找 if (a[l] == x) cout << l << '\n'; else cout << -1 << '\n'; return 0; }二分查找左右边界 二分查找左边界 二分查找右边界 题目解释:左右边界意思是最左或最右,或者最小或最大。 如一组数12333445,查找3的左边界,答案为3.查找3的右边界,答案为5二分查找左边界 左边界代码://二分查找左边界 #include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int y; cin >> y; while (y--) { int x; cin >> x; int l = 1, r = n; while (l < r) { int mid = (l + r) >> 1; if (a[mid] >= x)r = mid; else l = mid + 1; } if (a[l] == x)cout << l << ' '; else cout << -1 << ' '; } return 0; }可以看到查找左边界和普通二分查找原理相同,稍有的不同只是因为题目的需求不同,实际上普通二分查找是查找左右边界的特例,只不过是因为数组中的数是否重复而不同 下面给出右边界代码:#include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int y; cin >> y; while (y--) { int x; cin >> x; int l = 1, r = n; while (l < r) { int mid = (l + r + 1) >> 1;//1.注意, 如果 l=r-1 && nums[mid] <= target 此时l不能变化,进入死循环因此 mid更新应该改变 ,即 +1 if (a[mid] <= x)l = mid;//2.注意 else r = mid - 1;//注意 } if (a[l] == x)cout << l << ' '; else cout << -1 << ' '; } return 0; }注意代码中的注意,为与左边界不同的地方 1.如果 l=r-1 && nums[mid] <= target 此时l不能变化,进入死循环,因此 mid更新应该改变 ,即 +12.l不能+1,如果r=l+1,可能存在mid =r =l +1让循环进入死循环3.r-1是因为当前mid对应的数不为查找的数查找最小值用左边界,查找最大值用右边界左右边界的不同可以简单记忆为:左加右减二分答案-以伐木工为例 伐木工 咋一看与二分无关,如果直接暴力容易超时,因此使用二分法。 具体思路为写一个check函数判断当前高度以上的数相加是否符合所需的木材 此时的左右边界设置为0与最高高度的树,因为我们需要求的是伐木的高度,因此我们使用的二分法是求右边界,边界范围只与给出树的最高高度有关,再高就不礼貌了。 代码示例#include<iostream> #include<vector> using namespace std; using ll = long long; bool check(ll mid, ll n, ll m, vector<ll>& a) { ll num = 0;//num求a中mid高度以上的树的和 for (ll i = 1; i <= n; i++) { if (a[i] > mid)num += (a[i] - mid); if (num >= m)return true;//如果相加的木材长度大于或等于需要的木材长度,返回true,继续增加高度 } return false; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n, m; cin >> n >> m; vector<ll>a(n + 1); for (ll i = 1; i <= n; i++)cin >> a[i]; ll l = 0;//左边界 //找出最高的树作为右边边界 ll r = a[0]; for (ll i = 1; i <= n; i++) r = max(r, a[i]); //二分查找右边界 while (l < r) { ll mid = (l + r + 1) >> 1; if (check(mid, n, m, a)) l = mid; else r = mid - 1; } cout << l << '\n'; return 0; }洛谷-进击的奶牛 题解 本题查找相邻两头牛 最大 的最近距离,因此使用 右边界 选择好使用哪种二分后想想该怎么具体实现。我们想要对首先我们需要对输入的数组进行排序,然后取 l 为 1 , r 为一个很大的值即可。 check 函数中我们需要定义一个 num 对间隔距离进行求和,当 num>=mid 时对牛牛数量进行加 1 并且让 num为0 ,重新计数,直到牛牛的数量 >= 输入的奶牛的数量 c 。 示例代码//洛谷 进击的奶牛 #include<iostream> #include<vector> #include<algorithm> using namespace std; const int N=0x3f3f3f3f; using ll = long long; ll n, c; vector<ll>a(1); bool check(ll mid){ ll num = 0; ll nn = 1; for(ll i = 2; i <= n; i++){ num += a[i] - a[i - 1]; if(num >= mid) { nn++; num = 0; } if(nn >= c) return true; } return false; } int main() { std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> c; a.resize(n + 1); for(ll i = 1;i <= n; i++) cin >> a[i]; sort(a.begin(), a.end()); ll l = 0,r = N; while(l < r){ ll mid = (l + r + 1) >> 1; if(check(mid)) l = mid; else r = mid - 1; } cout << l <<'\n'; return 0; }
2024年05月07日
10 阅读
0 评论
0 点赞
1
2