【算法狂想曲】第一次实战做题进度(一)

2020-04-05   125 次阅读


题目网站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.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议