网站图片搜索技术哪里可以做,2022年国际新闻,怎样做农产品交易平台网站,沧州做网站优化哪家公司便宜文章目录 第5章 线性数据结构1.向量 vector2.队列 queue(1)队列的特点、应用(2)基本操作(3)例题例题1#xff1a;约瑟夫问题2 #xff08;难度#xff1a;中等#xff09; (4)习题习题1#xff1a;排队打饭 #xff08;难度#xff1a;中等#xff09; 3.栈 stack(1)栈… 文章目录 第5章 线性数据结构1.向量 vector2.队列 queue(1)队列的特点、应用(2)基本操作(3)例题例题1约瑟夫问题2 难度中等 (4)习题习题1排队打饭 难度中等 3.栈 stack(1)栈的特点、应用(2)基本操作(3)例题例题1编排字符串 难度简单例题2括号匹配 难度中等例题3计算表达式 难度困难 (4)习题习题1堆栈的使用 难度简单习题2模拟出入栈游戏 难度中等习题3简单计算器 难度困难 第6章 递归与分治1.递归(1)原理①函数②递归 (2)例题例题1n的阶乘 难度入门例题2汉诺塔Ⅲ 难度简单【分治法-递归】 2.分治(1)原理(2)例题例题1跳台阶 难度简单)例题2不连续1的子串难度中等例题32的幂次方难度困难 (3)习题习题1Fibonacci 难度入门习题2二叉树 难度简单【递归】习题3骨牌铺地砖 难度简单 【动态规划】习题4矩阵幂 难度中等 【矩阵计算】习题5全排列 难度困难【递归回溯法 - DFS】 第5章 线性数据结构
1.当定义的数组特别大达到1千万时不能定义在函数内部会崩溃。栈比较小但快。 要定义在全局位置数据段中。 【局部大数组会崩溃全局大数组不会崩溃】
2.标准模板库STL 1.向量 vector
vector是动态数组长度可改变。 vectorint vec;//创建空向量长度为0 普通静态数组长度是固定不变的。int arr[100];//创建长度为100的静态数组
1.头文件
#include vector
using namespace std;2.声明向量
vectorint vec;//长度为03.赋初值
vectorint vec2 {1,2,3};4.申请一定空间的向量所有元素初值默认为0
vectorint vec3(10000);※5.尾部插入尾部扩容 push_back(元素) 。效率最高插入n个为O(n)插入1个为O(1)。
vec.push_back(1);//vec[0]1
vec.push_back(3);//vec[1]3※6.任意位置插入
vec.insert(pos,[个数,]内容);//头部插入字符串
vec.insert(vec.begin(),str);※7.尾部删除弹出尾部元素 pop_back()
vec.pop_back();※8.下标访问
vec[i] //下标n时数组越界9.长度计算
vec.size();10.两种遍历方法 ①下标遍历
for(unsigned int i 0; i vec.size(); i){printf(vec[%d] %d\n,i,vec[i]);
}②迭代器遍历
for(vectorint::iterator it vec.begin(); it ! vec.end(); it){printf(vec[] %d\n,*it);
}11.随机位置的插入insert(位置元素)
vectorint::iterator it1 vec.begin()1;//迭代器指针指向vector的第二个位置
vec.insert(it13);//在vector第二个位置插入元素312.随机位置的删除erase(位置);
vec.erase(vec.begin());//删除vector的第一个位置的元素13.vector的实现原理 (1)vector的组成、申请空间(堆上) vector是类类型包括size容量、capacity内存大小、ptr首地址 首地址存放在栈上但vector申请的内存空间在堆区上堆区比栈区大因此vector可申请空间比静态数组在栈上申请的空间可以大很多。【静态数组 - 栈 - 小空间。 vector - 堆- 大空间】
(2)vector的扩容机制 2.队列 queue
(1)队列的特点、应用
1.队列的特点 队列queue是受限制的线性表 先进先出FIFO 队尾入队队头出队。
2.队列应用 广度优先遍历 BFS (2)基本操作
0.头文件
#include queue
using namespace std;queueint myQueue;1.队尾入队 .push(变量名)
for(int i 0;i 5;i){myQueue.push(i);
}2.队头出队 .pop() 3.判空 .empty() 4.队首元素 .front() 5.队尾元素 .back()
#include iostream
#include queue
using namespace std;int main() {//队列初始化queueint myQueue;//判空if(myQueue.empty()){cout myQueue is empty! endl;}//队尾入队for(int i 0 ; i 10; i){myQueue.push(i);//打印队首、队尾cout 队首: myQueue.front() 队尾: myQueue.back() endl;}cout --------------- endl;//队首出队for(int i 0 ; i 9; i){myQueue.pop();//打印队首、队尾cout 队首: myQueue.front() 队尾: myQueue.back() endl;}return 0;
}(3)例题
例题1约瑟夫问题2 难度中等
提交网址http://bailian.openjudge.cn/practice/3254 思路队头元素插入队尾然后队头元素出队以此实现循环队列
#include iostream
#include queue
using namespace std;int main() {queueint myQueue;int n,p,m;while(cin n p m){if(n0 p0 m0) break;//初始化队列for(int i 1; i n; i){myQueue.push(i);}//将编号为p旋转到队头for(int i 1; i p; i) { //将1到p-1号元素从队头调整到队尾myQueue.push(myQueue.front()); //队头元素插入队尾myQueue.pop(); //队头出队}//开始计数过程while(!myQueue.empty()){//将m-1个元素从队头调整到队尾for(int i 1; i m; i){myQueue.push(myQueue.front());myQueue.pop();}//打印并移除第m个元素cout myQueue.front();if(myQueue.size() 1) cout ,;myQueue.pop();}cout endl;}return 0;
}(4)习题
习题1排队打饭 难度中等
提交网址https://www.acwing.com/problem/content/description/5063/ 几个注意事项 ①可能前面有连续几个没打上饭的得用int记录而不是bool ②有些数值超过了int的表示范围将数组由int类型改为long long
#include iostream
using namespace std;int main() {int n;long long a[100010],t[100010],b[100010],res[100010]; //a[i]为到达时刻,t[i]为打饭耗时,b[i]为最大等待时长,res[i]为打饭时刻或-1cin n;for(int i 1; i n; i){cin a[i] t[i] b[i];}res[1] a[1]; //第一位同学到达后立即开始打饭cout res[1] ;int count 0; //count记录前面有连续多少位同学没有打上饭for(int i 2; i n; i){if(a[i]b[i] res[i-1-count]t[i-1-count]){ //上一位开始打饭时间打饭耗时超过了该同学最大等待时间,则放弃打饭cout -1 ;count;}else{res[i] max(res[i-1-count]t[i-1-count],a[i]); //max(最早可以打饭时刻,该同学到达时间)cout res[i] ;count 0;}}cout endl;return 0;
}3.栈 stack
(1)栈的特点、应用
1.栈的特点 栈也是操作受限的线性表只能一端进出。 后进先出 栈禁止操作的一端称为盲端。允许元素插入和删除的一端称为栈顶。
2.栈的应用 ①深度优先遍历 DFS逆序输出 ②表达式解析、表达式求值 ③递归 ④括号匹配 (2)基本操作
0.头文件
#include stack
using namespace std;1.初始化
stacktypename myStack//定义2.方法 .push()压栈将元素加入栈中 .pop()弹栈 .top()获取栈顶内容 .size()栈大小 .empty()判断栈是否为空
#include iostream
#include stack
using namespace std;int main() {//栈初始化stackint myStack;//栈判空if(myStack.empty()){cout myStack is empty! endl;}//入栈(压栈)for(int i 0; i 10 ; i){myStack.push(i);cout top is myStack.top() endl;}cout --------------- endl;//出栈(弹栈)for(int i 0 ; i 9; i){myStack.pop();cout top is myStack.top() endl;}return 0;
}(3)例题
例题1编排字符串 难度简单
提交网址https://www.acwing.com/problem/content/3578/
思路准备一个临时栈用于演示弹栈
#include iostream
#include stack
#include string
using namespace std;int main() {string str;stackstring myStack,tempStack;int m;cin m;for(int i 0; i m; i){cin str;myStack.push(str);tempStack myStack;for(int i 1; !tempStack.empty(); i){if(i 4) break; //最多输出4个字符串cout i tempStack.top() ;tempStack.pop();}cout endl;}return 0;
}例题2括号匹配 难度中等
提交网址https://www.acwing.com/problem/content/3696/ 思路栈实现。遇到右括号都是同一种思路写好一个else if后面都是复制了
#include iostream
#include string
#include stack
using namespace std;int main() {stackchar myStack;string str;cin str;for(int i 0; i str.size(); i){//1.遇到左括号,入栈if(str[i] || str[i] ( || str[i] [ || str[i] {){myStack.push(str[i]);}//2.遇到右尖括号else if(str[i] ){if(myStack.empty() || myStack.top()!){cout no endl;return 0;}else{ //栈顶就是左尖括号,匹配myStack.pop();}}//3.遇到右小括号else if(str[i] )){if(myStack.empty() || myStack.top()!(){cout no endl;return 0;}else{ //栈顶就是左小括号,匹配myStack.pop();}}//4.遇到右中括号else if(str[i] ]){if(myStack.empty() || myStack.top()![){cout no endl;return 0;}else{ //栈顶就是左中括号,匹配myStack.pop();}}//5.遇到右大括号else if(str[i] }){if(myStack.empty() || myStack.top()!{){cout no endl;return 0;}else{ //栈顶就是左大括号,匹配myStack.pop();}}}if(myStack.empty()) cout yes endl;else cout no endl;return 0;
}例题3计算表达式 难度困难
提交网址http://t.cn/AiKKJjJ5
#include stdio.h
#include string
#include stack
#include map
using namespace std;
int main() {char str[1000] { 0 };mapchar, int priority {{\0,0},{,1},{-,1},{*,2},{/,2}};while (scanf(%s, str) ! EOF) {string numStr ;stackchar opStack;stackdouble numStack;for (int i 0; ; i) {if (str[i] 0 str[i] 9) {numStr.push_back(str[i]);}else {double num stod(numStr);numStr ;numStack.push(num);// 什么时候弹栈 栈非空 新op的优先级 不高于 栈顶的优先级// 循环弹栈和计算while (!opStack.empty() priority[str[i]] priority[opStack.top()]) {double rhs numStack.top();numStack.pop();double lhs numStack.top();numStack.pop();char curOp opStack.top();opStack.pop();if (curOp ) {numStack.push(lhs rhs);}else if (curOp -) {numStack.push(lhs - rhs);}else if (curOp *) {numStack.push(lhs * rhs);}else if (curOp /) {numStack.push(lhs / rhs);}}// 栈为空 或者 新op的优先级高于栈顶if (str[i] \0) {printf(%d\n, (int)numStack.top());break;}else {opStack.push(str[i]);}}}}return 0;
}(4)习题
习题1堆栈的使用 难度简单
提交网址http://t.cn/AiKKM6F6
#include iostream
#include stack
using namespace std;int main() {int n;while(cin n){stackint myStack;char c;int a;for(int i 0; i n; i){cin c;if(c A){if(myStack.empty()) cout E endl;else cout myStack.top() endl;}else if(c P){cin a;myStack.push(a);}else if(c O){if(!myStack.empty()) myStack.pop();}}}return 0;
}习题2模拟出入栈游戏 难度中等
提交网址https://www.acwing.com/problem/content/3681/ 注意栈的初始化放在while循环里。放在外面可能会因为上一轮未清空受脏数据影响
#include iostream
#include stack
#include string
using namespace std;int main() {string str1 abcdefghijklmnopqrstuvwxyz,str2;while(cin str2){stackchar stk;int k 0;for(int i 0 ; i str1.size(); i){stk.push(str1[i]);while(stk.size() k str2.size() stk.top() str2[k]){//核心while循环:stk.pop(); //比较栈顶元素和字符串str2中当前位置的字符是否相等k;}}if(stk.empty()) cout yes endl;else cout no endl;}return 0;
}习题3简单计算器 难度困难
提交网址http://t.cn/AiKoGS94 第6章 递归与分治
1.递归
(1)原理
1.什么是递归 函数在函数体内调用自身函数的行为叫做递归 在函数定义中调用本函数叫做递归 2.递归的原理 ①代码段PC走到被调函数的入口 ②栈区栈帧压入栈内 逐过程、逐语句 3.如何使用递归 ①递归一定要有递归出口 ②每次递归变量条件向着递归出口靠近 4.递归与分治的关系 分治是一种思想分而治之递归是一种实现方法函数调用自己。 分治思想可用递归来实现也可以用其他方法来实现。递归作为一种方法不止可以用于实现递归思想也可以用来实现其他思想。 但总的来说一般都用递归方法来实现分治的思想。故两者本不是同一纬度的概念但是经常放在一起谈论。
常见的分治求斐波那契数列、快速排序 常见的递归求n的阶乘 5.2023旧版本内容 从函数到递归
①大问题→小问题等价条件 ②确定最小问题即递归出口
①函数
C语言编写的代码以函数定义为单位。
call把PC移到被调函数 ret把PC移回主调函数 ②递归
递归关注的两个点 ①大问题转化为小问题规模n→规模n-1 ②最小问题递归出口 (2)例题
例题1n的阶乘 难度入门
提交网址https://www.nowcoder.com/share/jump/2891302591709206218373 C
#include iostream
using namespace std;long long factorial(int n){if(n 0 || n 1) return n;else{return n * factorial(n-1);}
}int main(){int n;cin n;cout factorial(n);return 0;
}C语言
#include cstdiolong long int Factorial(int n){if(n 0){return 1;}else{return n*Factorial(n-1);}
}int main(){int n;while(scanf(%d,n) ! EOF){printf(%lld,Factorial(n));}return 0;
}例题2汉诺塔Ⅲ 难度简单【分治法-递归】 思路 ①n-1片为整体先由第一柱搬到第三柱最大片由第一柱搬到第二柱[Hanoi(n-1) 1] ②n-1片从第三柱搬回第一柱最大片由第二柱搬到第三柱 [Hanoi(n-1) 1] ③n-1片由第一柱搬到第三柱完成。[Hanoi(n-1)]
#include iostream
using namespace std;long long Hanoi(int n){ //搬运n片共需要Hanoi(n)步if(n 1){return 2; }else{return 3 * Hanoi(n-1) 2; }
}int main() {int n;while(cin n){cout Hanoi(n) endl;}return 0;
}2.分治
(1)原理
1.名称解释 分治法分而治之 (divide-and-conquer method) 2.分治法的两个要素 ①大问题转化为相似的小问题直至转化为最小问题 ②最小问题的解决方案 3.分治法的代码模板 ①分解大问题拆成小问题 ②治理找到等价条件解决递归出口(最小问题) ③合并 (2)例题
例题1跳台阶 难度简单)
提交网址https://www.acwing.com/problem/content/823/ 思路因为每次只能走1级或2级台阶所以走n级台阶只会是从n-1或n-2级台阶上去的。根据加法原理这两种方案的数量可以相加得到走n级台阶的方案。同样的走n-1级的方案可以拆分为走n-2级和走n-3级方案之和。 #include iostream
using namespace std;int f(int n){if(n 1){return 1;}else if(n 2){return 2;}else{return f(n-1) f(n-2);}
}int main() {int n; //n级台阶while(cin n){cout f(n) endl;}return 0;
}测试可得 f(1)1f(2)2f(3)3f(4)5f(5)8f(6)13f(7)21 … 可知跳台阶问题是斐波那契数列问题的变形即后一个值是前两个值之和。 优化分析 但是由栈帧示意图我们发现很多f(n)会重复计算多次。当n很大时该算法的效率会很低。我们自然而然地想到如何避免重复计算从而提高函数的效率。
优化:用数组存储已经计算过的结果例题2不连续1的子串难度中等
提交网址https://www.acwing.com/problem/content/3709/ 24炉灰老师分解为小问题并给出最小问题的解决方案(递归出口)
#include iostream
using namespace std;int f0(int n); // 函数声明写在前面,
int f1(int n); // 则这两个函数就可以交叉调用int f0(int n){ // 末尾为0if(n 1){return 1;}else{return f0(n-1) f1(n-1);};
}int f1(int n){ // 末尾为1if(n 1){return 1;}else{return f0(n-1);}
}int main() {int n;while(cin n){cout f0(n)f1(n) endl;}return 0;
}例题32的幂次方难度困难
提交网址https://www.acwing.com/problem/content/3486/ 分析由大问题分解为小问题用分治法 将n转化为2的指数形式 24炉灰老师
#include stdio.h
#include string
#include vector
using namespace std;
string Get2sExponet(int n) {if (n 0) {return 0;}vectorint exp;for (int i 15; i 0; --i) {if ((n (1 i)) ! 0) {exp.push_back(i);}}// n 2^(exp[0]) 2^(exp[1]) ... 2^(exp[size-1])string res ;for (int i 0; i exp.size(); i) {if (i ! 0) {res ;}if (exp[i] 1) {res 2;}else {res 2( Get2sExponet(exp[i]) );}}return res;
}
int main() {int n;while (scanf(%d, n) ! EOF) {printf(%s\n, Get2sExponet(n).c_str());}return 0;
}(3)习题
习题1Fibonacci 难度入门
提交网址http://t.cn/Ai0K3tU5 解法1斐波那契数列递归实现 C语言版本
#include cstdioint Fibonacci(int n ){if(n 0 || n 1){return n;}else{return Fibonacci(n-1) Fibonacci(n-2);}
}int main(){int n;while(scanf(%d,n) ! EOF){printf(%d\n,Fibonacci(n));}return 0;
}C版本
#include iostream
using namespace std;int Fibonacci(int n){if(n 0 || n 1){return n;}else{return Fibonacci(n-1) Fibonacci(n-2);}
}int main(){int n;while(cin n){cout Fibonacci(n);}return 0;
}解法2斐波那契数列非递归实现循环实现
#include cstdioint fib(int n){int n1 1;int n2 1;int ret 0;if (n1 || n2){return 1;}for (int i 3; i n; i){ //通过循环计算n3时ret n1 n2;n1 n2;n2 ret;}return ret;
}int main(){int n 0;scanf(%d, n);int ret fib(n);printf(%d\n,ret);return 0;
}解法3斐波那契数列非递归实现动态规划实现
#include cstdioint dp[91];int Fibonacci(int n){dp[1] 1;dp[2] 2;for(int i 3 ; i n; i){ //3-ndp[i] dp[i-1] dp[i-2];}return dp[n];
}int main(){int n;while(scanf(%d,n) ! EOF){printf(%d\n,Fibonacci(n));}return 0;
}习题2二叉树 难度简单【递归】
提交网址http://t.cn/Ai0Ke6I0
C版本根结点 左子树 右子树 如图编号为m的结点左孩子编号为2m右孩子编号为2m1
#include iostream
using namespace std;int binarytree(int m,int n){if(m n){return 0;}else{ //如图,编号为m的结点,左孩子编号为2m右孩子编号为2m1return 1 binarytree(2*m,n) binarytree(2*m1,n); //根结点 左子树 右子树}
}int main(){int m,n; //m为父结点编号,n为总结点数while(cin m n){if(m0 n0) break;cout binarytree(m,n) endl;}return 0;
}C语言版本
#include cstdioint binaryTree(int m,int n){if(mn){return 0;}else{return binaryTree(2*m,n) binaryTree(2*m1,n) 1;}
}int main(){int m,n;while(scanf(%d %d,m,n) ! EOF){if(m0 n0){break;}printf(%d\n,binaryTree(m,n));}
}习题3骨牌铺地砖 难度简单 【动态规划】
提交网址https://www.acwing.com/problem/content/3690/ 思路
用递归会超时改用动态规划数组保存计算结果避免重复计算
#include iostream
using namespace std;int dp[10010];long long Fibonacci(int n){dp[0] 0;dp[1] 1;dp[2] 2;for(int i 3; i n; i){dp[i] (dp[i-1] dp[i-2]) % 999983;}return dp[n];
}int main() {int n;cin n;cout Fibonacci(n);return 0;
}习题4矩阵幂 难度中等 【矩阵计算】
提交网址https://www.acwing.com/problem/content/3690/ 学会计算 矩阵C A×B 核心代码
for(int i 0; i n; i){for(int j 0; j n; j){for(int k 0; k n; k){ //矩阵C 矩阵A × 矩阵B:C[i][j] A[i][k]*B[k][j]; //C[i][j] A的第i行×B的第j列所有对应元素}}
}答案
#include iostream
#include cstring
using namespace std;
const int N 11;
int A[N][N],B[N][N],C[N][N];int main() {int n,m; //n为矩阵的阶,m为矩阵的幂cin n m;memset(A,0,sizeof(A));//输入矩阵Afor(int i 0; i n; i){for(int j 0; j n; j){cin A[i][j];}}//计算m次幂//(1)若m为1,输出原矩阵if(m 1){for(int i 0; i n; i){for(int j 0; j n; j){cout A[i][j] ;}cout endl;}return 0;}//(2)若m1,计算 矩阵 C A×Bmemcpy(B,A,sizeof(A));while(--m){memset(C,0,sizeof(C));for(int i 0; i n; i){for(int j 0; j n; j){for(int k 0; k n; k){ //矩阵C 矩阵A × 矩阵B:C[i][j] A[i][k]*B[k][j]; //C[i][j] A的第i行×B的第j列所有对应元素}}}memcpy(B,C,sizeof(C)); //这次的幂次运算结果C赋值给B}//输出矩阵Cfor(int i 0; i n; i){for(int j 0; j n; j){cout C[i][j] ;}cout endl;}return 0;
}习题5全排列 难度困难【递归回溯法 - DFS】
提交网址https://www.acwing.com/problem/content/3690/ 来自一位网友的答案
#includebits/stdc.h
using namespace std;
void backtracking(string tmp,string s)
{if(tmp.size()s.size())couttmpendl;else{for(int i0;is.size();i){if(tmp.find(s[i])!tmp.npos) continue;backtracking(tmps[i],s);}}
}
int main()
{string s,tmp; while(cins)backtracking(tmp,s); return 0;}
