代码编织梦想

算法刷题(一)

以下题部分来自于AcWing,蓝桥杯等地。

二分

机器人跳跃问题

image-20230328211333153

输入样例1:

5
3 4 3 2 4

输出样例1:

4

输入样例2:

3
4 4 4

输出样例2:

4

输入样例3:

3
1 6 4

输出样例3:

3
#include <bits/stdc++.h>
using namespace std;
int n; 
const int N=100010;
int a[N];
bool check(int e)
{
    for(int i=0;i<n;i++)
    {
        e=e*2-a[i];
        if(e>=1e5) return true;
        if(e<0) return false;
    }
    return true;
}

int main()
{  
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int l=0,r=1e5;
    while(l<r)
    {
        int mid=l+(r-l)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}

带分数

资源限制

内存限制:256.0MB

C/C++时间限制:1.0s

Java时间限制:3.0s

Python时间限制:5.0s

100 可以表示为带分数的形式:100 = 3 + 69258 / 714

还可以表示为:100 = 82 + 3546 / 197

注意特征:带分数中,数字1~9分别出现且只出现一次(不包含0)。

类似这样的带分数,100 有 11 种表示法。

题目要求:
  从标准输入读入一个正整数N (N<1000*1000)
  程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
  注意:不要求输出每个表示,只统计有多少表示法!

例如:
  用户输入:

100

程序输出:

11

用户输入:

105

程序输出:

6

资源约定:

峰值内存消耗 < 64M
CPU消耗 < 3000ms

#include <bits/stdc++.h>
using namespace std;

const int N=20;
int ans=0;
int n;
bool st[N],backup[N];

bool check(int a,int c)
{	
	int b=n*c-a*c;
	if(!a||!b||!c)
		return false;
	memcpy(backup,st,sizeof st);
	while(b)
	{
		int x=b%10; //娶个位数
		b/=10;//删掉个位数
		if(!x||backup[x])
			return false;
		backup[x]=true;
	}
	for(int i=1;i<=9;i++)
	{
		if(!backup[i])
			return false;
	}
	return true;
}

void dfsc(int u,int a,int c)
{
	if(u==n) return;
	if(check(a,c))
		ans++;
	for(int i=1;i<=9;i++)
	{
		if(!st[i])
		{
			st[i]=true;
			dfsc(u+1,a,c*10+i);
			st[i]=false;
		}	
	}	
}
void dfsa(int u,int a)
{
	if(a>=n) return;
	dfsc(u,a,0);
	for(int i=1;i<=9;i++)
	{
		if(!st[i])
		{
			st[i]=true;
			dfsa(u+1,a*10+i);
			st[i]=false;
		}
	}
}
int main()
{
	cin>>n;
	dfsa(0,0);
	cout <<ans<<endl;
	return 0;
}

递归

递归求斐波那契数列

image-20230328213002498

输入样例:

4

输出样例:

3
#include <bits/stdc++.h>
using namespace std;

int f(int n)
{
    if(n==1||n==2)
    {
        return 1;
    }
    if(n>2)
    {
        return f(n-1)+f(n-2);
    }
}

int main()
{
    int n;
    cin>>n;
    cout<<f(n)<<endl;
    return 0;
}

递归实现组合型枚举

image-20230328213349917

输入样例:

5 3

输出样例:

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
#include <bits/stdc++.h>
using namespace std;

const int N=30;

int m,n;
int st[N];//位置
 
void dfs(int x,int y )
{
    if(x==m+1)
    {
        for(int i=1;i<=m;i++)
        {
            cout<<st[i]<<" ";
        }
        puts(" ");
        return;
    }
    for(int i=y;i<=n;i++)
    {
        st[x]=i;
        dfs(x+1,i+1);
        st[x]=0;
    }
}
 
 
int main()
{
    cin>>n>>m;
    dfs(1,1);
    return 0;
}

递归实现排列型枚举

image-20230328213536820

输入样例:

3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include <bits/stdc++.h>
using namespace std;

const int N=10;
int n;
bool s[N];
int st[N]; //记录每个位置当前的状态 ,0没考虑,1选,2不选 
void dfs(int u)
{
	if(u>n)
	{
		for(int i=1;i<=n;i++)
		{
			printf("%d ",st[i]);
		
		}	
		puts("");
		return ;
	}
	for(int i=1;i<=n;i++)
		{
			if(!s[i])
			{
				st[u]=i;
				s[i]=true;
				dfs(u+1);
				
				st[u]=0;
				s[i]=false;
			}
		}
}
int main()
{
	scanf("%d",&n);
	dfs(1);
	return 0;
}

翻硬币

资源限制

内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写字母,不是零)。

比如,可能情形是:* * o o * * * o o o o

如果同时翻转左边的两个硬币,则变为:o o o o * * * o o o o

现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?
我们约定:把翻动相邻的两个硬币叫做一步操作。

程序输入:

两行等长的字符串,分别表示初始状态和要达到的目标状态。每行的长度<1000

程序输出:

一个整数,表示最小操作步数

用户输入:

**********
o****o****

程序输出:

5

用户输入:

*o**o***o***
*o***o**o***

程序输出:

1

资源约定:

峰值内存消耗 < 64M
CPU消耗 < 1000ms

#include <bits/stdc++.h>
using namespace std;
const int N=110;
char st[N],en[N];
int n;
void turn(int i)
{
	if(st[i]=='o')
	{
		st[i]='*';
	}
	else
	{
		st[i]='o';
	}
}
int main()
{
	cin>>st>>en;
	n=strlen(st);
	int s=0;
	for(int i=0;i<n-1;i++)
	{
		if(st[i]!=en[i])
		{
			turn(i),turn(i+1);
			s++;
		}
	}
	cout<<s;
	return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_61355929/article/details/129825890

java 算法刷题指南_java需要刷题吗-爱代码爱编程

  目前感觉比较好的刷题方式就是按照《算法笔记》的框架进行刷题。尽量将每种题型的模板背下来,经常默写。下面给出框架。 1.基础 1.1 输入输出 CSDN:笔试面试中的输入输出 公众号:笔试面试中的输入输出 1.2

算法刷题手册让你横扫各大厂算法面试题_算法岗刷题-爱代码爱编程

大厂面试官:你的算法怎么样? 面试算法工程师的程序员们常常遇到这样的问题,无论是BAT这样的大厂,还是其他小公司,招聘工程师的时候,对算法考察的很仔细。 为什么算法这么重要呢? 1、算法能力可以辨别程序员的技术功底;2、算法能力是发掘程序员潜力的关键手段;3、算法能力能够判断程序员在面对新问题时候的分析解决能力;4、算法能力是设计一个高性能系统、性能

算法刷题路线总结与相关资料分享_刷题算法学习流程-爱代码爱编程

算法刷题路线总结与相关资料分享 前言一、算法刷题路线总结二、算法题刷题步骤三、基础数据结构知识汇总1、时间复杂度2、空间复杂度3、线性表4、栈与队列5、树 四、基础算法知识汇总1、递归2、多指针算法3、动

算法刷题笔记的总结篇-爱代码爱编程

本文为算法刷题笔记的总结篇,花了两个多月的时间,将牛客网上《剑指Offer》的66道题刷了一遍,以博客的形式整理了一遍,这66道题属于相对基础的算法题目,对于刷题练手是很好的实践,接下来会继续回到LeetCode,争取每天拿出一个小时,刷一到两道题。   本文主要对这66道题做一个总结,整体来看,这66道题,涉及到了常用的数据结构:数组、字符串、链表、树

18-爱代码爱编程

题目 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据保证整个链式结构中不存在环。 注意,函数返回结果后,链表必须 保持其原始结构 。 自定义评测: 评测系统的输入如下(你设计的程序不适用此输入):