题目网站acwing，为了准备某比赛而做的题，感谢大佬推荐
92.递归实现指数型枚举
思路
很简单的回溯
AC代码
#include<iostream>
#include<vector>
using namespace std;
void perm(vector<int> result,int current,int n);
int main()
{
vector<int> result;
int N;
std::cin>>N;
perm(result,1,N+1);
}
void perm(vector<int> result,int current,int n)
{
for(int i=0;i<result.size();i++)
std::cout<<result[i]<<" ";
std::cout<<std::endl;
for(int i=current;i<n;i++)
{
result.push_back(i);
perm(result,i+1,n);
result.pop_back();
}
}
717.简单斐波那契
思路
题如其名，简单的斐波那契
AC代码
#include<iostream>
using namespace std;
int main()
{
int num=0;
std::cin>>num;
int N[47]={0};
N[0]=0;
N[1]=1;
for(int i=0;i<num;i++)
{
if(i==0||i==1)
std::cout<<N[i]<<" ";
else
{
N[i]=N[i-1]+N[i-2];
std::cout<<N[i]<<" ";
}
}
return 0;
}
93.递归实现组合型枚举
思路
同样可以用回溯轻松解决，但是刷LeetCode刷多了下意识用vector，结果超时了，于是改用普通int数组，轻松AC
超时代码
#include<iostream>
#include<vector>
using namespace std;
void perm(vector<int> result,int current,int N,int k);
int main()
{
int N,k;
std::cin>>N>>k;
if(!k)
return 0;
vector<int> result;
perm(result,1,N+1,k);
return 0;
}
void perm(vector<int> result,int current,int N,int k)
{
if(result.size()==k)
{
for(int i=0;i<result.size();i++)
std::cout<<result[i]<<" ";
std::cout<<std::endl;
return;
}
for(int i=current;i<N;i++)
{
result.push_back(i);
perm(result,i+1,N,k);
result.pop_back();
}
}
AC代码(不用vector，改用普通int数组)
#include<iostream>
using namespace std;
void perm(int num[1000],int current,int N,int k);
int main()
{
int num[1000];
int N,k;
std::cin>>N>>k;
if(!k)
return 0;
perm(num,1,N+1,k);
return 0;
}
void perm(int num[1000],int current,int N,int k)
{
if(num[0]==k) //如果当前数组中储存数据数等于预期数，输出
{
for(int i=1;i<=num[0];i++)
std::cout<<num[i]<<" ";
std::cout<<std::endl;
return;
}
for(int i=current;i<N;i++)
{
num[++num[0]]=i;
perm(num,i+1,N,k);
num[0]--;
}
}
1209.带分数
思路
一开始看到这题我是迷茫的，心想着暴力，裸回溯肯定超时啥的，后面没有思路了看大佬的题解直接傻了，竟然真的是暴力，而且还是各种暴力
行吧
大致的思路是将1~9个数进行全排列
然后当全排列完成后从全排列中分出三个数，然后判断结果
可以说是非常简单粗暴了
感谢大佬 Daniel丶y的题解让我明白了这道题的思路
AC代码
#include<iostream>
#include<string>
using namespace std;
int total=0; //用于统计总数
int all[10]; //用于存储全排列状态
bool used[10]; //标记数是否被使用
int target=0; //储存目标数
int transform(int from,int to);
void dfs(int current);
int main()
{
//std::cout<<"开始"<<std::endl;
std::cin>>target;
dfs(0);
std::cout<<"total:"<<total<<std::endl;
return 0;
}
//转换函数，将一个整数数组中的一段内容转化为数字
int transform(int from,int to)
{
int result=0;
for(int i=from;i<=to;i++)
{
result*=10;
result+=all[i];
}
return result;
}
//搜索函数，包含全排列功能以及
void dfs(int current)
{
//假如u为9，说明全排列已经完成，可以进行分解操作
if(current==9)
{
for(int i=0;i<7;i++)
{
for(int j=i+1;j<8;j++)
{
//将整数数组分割为3个数a,b,c
int a=transform(0,i);
int b=transform(i+1,j);
int c=transform(j+1,8);
//std::cout<<"a:"<<a<<" b:"<<b<<" c:"<<c<<std::endl;
//倘若满足条件，将总数进行加一操作
if(a*c+b==target*c)
total++;
}
}
return;
}
//全排列操作
for(int i=1;i<=9;i++)
{
if(!used[i])
{
used[i]=true;
all[current]=i;
dfs(current+1);
used[i]=false; //还原
}
}
}
累计用时361ms
94.递归实现排列型枚举
思路
做完带分数那题后，仔细一想这个全排列似乎是从小到大的顺序，于是想起来前面还有这一题，因此就现学现用，果然轻松AC
AC代码
#include<iostream>
using namespace std;
void perm(int current);
int num[1000]; //存储全排列内容
bool used[1000]; //标志着一个数是否被使用
int N;
int main()
{
std::cin>>N;
perm(0);
return 0;
}
void perm(int current)
{
if(current==N) //如果current等于N，说明全排列完成，可以输出
{
for(int i=0;i<N;i++)
std::cout<<num[i]<<" ";
std::cout<<std::endl;
}
for(int i=1;i<=N;i++)
{
if(!used[i])
{
used[i]=true;
num[current]=i;
perm(current+1);
used[i]=false;
}
}
}
1208.翻硬币
思路
这题看起来很难，其实还是相对容易的，因为题目中提到一个很关键的条件：
数据保证一定有解
这样意味着不存在什么死锁无限循环的状态，那样就可以从开头遍历到结尾
AC代码
#include<iostream>
#include<string>
using namespace std;
string remain,target; //储存初始状态和目标状态
int step=0; //记录步数
int main()
{
int indexA=0; //遍历变量
std::cin>>remain>>target;
int L=remain.length();
while(indexA<L-1) //从头遍历到倒数第二个字符
{
//std::cout<<remain<<" "<<target<<std::endl;
int add = '*'+'o';
//如果匹配到不同的字符，就将其与其往后一个硬币进行反转
if(remain[indexA]!=target[indexA])
{
remain[indexA]=add-remain[indexA];
remain[indexA+1]=add-remain[indexA+1];
step++; //记录步数
}
else indexA++;
//std::cout<<remain<<" "<<target<<std::endl;
}
std::cout<<step<<std::endl;
return 0;
}
789.数的范围
思路
因为前提是排序数组，因此思路其实很好想，但是我忘了这个叫什么方法了，好像是有关前缀的？就是从头扫描到尾，开两个足够大的数组用于储存开头与结尾（用结构体其实也行）
第一次扫描到某个数的时候（检查该数的开头数组为0，**这里要解释一下，因为第一个数出现的起始位置一定为0，因此位置都按+1来计算），将该位置添加到开头数组中，并将前一个index添加到先前元素的结尾数组中
从头到尾扫描即可
AC代码
#include<iostream>
using namespace std;
int a[100000]; //开头数组
int b[100000]; //结尾数组
int N,K; //储存数据个数与查询个数
int main()
{
std::cin>>N>>K;
int indexA=1; //遍历索引，从1开始（原因在思路里有提及）
int save=0; //用于保存每次输入的值
while(indexA<=N)
{
int pre=save; //用于保存先前的数
std::cin>>save;
if(a[save]==0) //倘若该数第一次出现，设置当前数的开头与之前的数的结尾
{
a[save]=indexA;
b[pre]=indexA-1;
}
indexA++;
}
b[save]=N; //注意因为本人代码缺陷这里要把最后一个数的结束位置加上
while(K>0)
{
std::cin>>save; //查询
if(a[save]!=0) //如果一个数连开头都没有，那就不需要考虑了
std::cout<<a[save]-1<<" "<<b[save]-1<<std::endl;
else std::cout<<"-1 -1"<<std::endl;
K--;
}
return 0;
}
790.数的三次方根
思路
看到题目一头雾水（常态），于是直接进了题解，想不到二分还能这样用（可能本来就是这样用，因为这题标榜模板题），于是看了之后大体了解了思路
数据范围-10000<=n<=10000
于是设置上界与下界为10000和-10000
每次求出上界与下界的和除以2的值，然后让该值进行立方运算，如果结果小于预期结果，则将上界设为(上界+下界）/2，反之如果大于则将下界设为(上界+下界）/2
一直运算下去直到上界与下界的误差小于1e-7
最后结果用stdio的格式化输出即可
AC代码
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
double rest; //储存目标数
std::cin>>rest;
double result; //储存最终结果
double low=-10000; //储存下界
double high=10000; //储存上界
double mid; //储存二分的中间值
while(high-low>1e-7)
{
mid=(high+low)/2; //计算二分的中间值
//std::cout<<"mid:"<<mid<<std::endl;
result=mid*mid*mid; //计算该中间值的立方
//相应操作
if(result<rest)
low=mid;
else if(result>rest)
high=mid;
else break;
}
//printf进行格式化输出
printf("%1.6lf",mid);
return 0;
}
因为题目太多了就先放到这里
Q.E.D.
Comments | 0 条评论