1. Toy模板网首页
  2. > Toy博客

【刷题笔记4】

8月前 作者：My heart will go ~~ 分类：Toy博客 阅读(21) 违法举报

这篇具有很好参考价值的文章主要介绍了【刷题笔记4】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划题目汇总

斐波那契数列：1，1，2，3，5，8，13……
递归一把解决三类问题：1.数据定义是按照递归的（斐波那契数列）。2.问题解法是按递归算法实现的。 3.数据形式是按照递归形式定义的。
递归的一般形式：

void rec(形参列表)
{
	if(test) return;  //边界条件
    //！！！注意！！！  递归一定要有边界条件！！！否则就会死循环！！！
    rec(实参列表)     //递归调用
    语句序列2         //递归返回段(回溯)
}
  1. 有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。例：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
    输入一个int型整数表示第n个月
    输出对应的兔子总数
#include <iostream>
using namespace std;
int total(int n);
int total(int n)
{
    if(n==1||n==2)//这个叫边界条件
    return 1;
    else
    return total(n-1)+total(n-2);//递归调用
}
int main() {
    //斐波那契数列
    int n,num;
    cin>>n;
    num=total(n);
    cout<<num;
}
  1. 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？ 注意：如果有7个苹果和3个盘子，（5，1，1）和（1，5，1）被视为是同一种分法。

解题思路：
假设有m个苹果和n个盘子，我们可以将问题分为两种情况： 1. 盘子中至少有一个盘子为空：这种情况下，我们可以将m个苹果放在n-1个盘子中，即将问题转化为将m个苹果放在n-1个盘子中的分法。所以，这种情况下的分法数为f(m, n-1)。 2. 盘子中所有盘子都有苹果：这种情况下，我们可以将每个盘子中放入一个苹果，然后将剩余的m-n个苹果放在n个盘子中，即将问题转化为将m-n个苹果放在n个盘子中的分法。所以，这种情况下的分法数为f(m-n, n)。 综上所述，将m个苹果放在n个盘子中的分法数为f(m, n) = f(m, n-1) + f(m-n, n)。
边界条件： - 当m=0时，表示没有苹果需要放入盘子中，所以只有一种分法，即所有盘子都为空。 - 当n=0时，表示没有盘子可以放苹果，所以没有分法。 根据上述递推关系和边界条件，可以使用递归或动态规划的方法来求解。

#include <iostream>
using namespace std;

int fn(int m,int n)
{
    if(n<1) return 0;
    if(m<0) return 0;
    if(m==0) return 1;
    return fn(m-n,n)+fn(m,n-1);//没有空盘子+有1个空盘子
}

int main() {
    int m,n;
    cin>>m>>n;
    cout<<fn(m,n);
}
  1. n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
#include <iostream>
using namespace std;
int digui(int x,int y)
{
    if(x==1||y==1)//只有一行或者一列的时候，就有x+y种方法
    return x+y;    //否则就往上或者往下走一步。
    return digui(x-1,y)+digui(x,y-1);

	//if(x==0)
	//return 1;
	//if(y==0)
	//return 1;
    //return x+y;    //否则就往上或者往下走一步。
    //return digui(x-1,y)+digui(x,y-1);




	//if(m<0||n<0)
    //return 0;
    //else if(n==1&&m==0)
    //return 1;
    //else if(m==1&&n==0)
    //return 1;
    //else  
    //return(digui(m-1, n)+digui(m,n-1));
}

int main() {
    int m,n;
    cin>>n>>m;
    cout<<digui(m,n);

}

最长递增子序列问题：

【刷题笔记4】,笔记,笔记,算法,c++
4.

class Solution {
  public:
    int LIS(vector<int>& arr) {
        if (arr.empty())
            return 0;
        int N = arr.size();
        vector<int>dp(N, 1);
        int maxLen = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = max(dp[i], dp[j] + 1); //长度加1
                }
            }
            maxLen = max(maxLen, dp[i]);//更新最大长度
        }
        return maxLen;
    }
 
};

【刷题笔记4】,笔记,笔记,算法,c++

  1. BFS（广度优先搜索算法）
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int Map[5][5];  //定义地图大小
int dir[4][2]= {1,0,-1,0,0,-1,0,1};  //定义方向
int n,m,ans;
struct node
{
    int x,y,step;

} now,nextt;  //保存走步
int BFS(int x,int y)
{
    queue<node>q;
    int xx,yy,zz;
    Map[x][y]=2;  //走过初始点
    now.x=x;
    now.y=y;
    now.step=0;
    q.push(now);  //从当前点开始
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(int i=0; i<4; i++)  //遍历四个方向
        {
            xx=now.x+dir[i][0];
            yy=now.y+dir[i][1];  //走一步
            if(xx>=0&&xx<5&&yy>=0&&yy<5&&Map[xx][yy]!=1&&Map[xx][yy]!=2)  //可以走
            {
                nextt.x=xx;
                nextt.y=yy;
                nextt.step=now.step+1;  //步数加一
                Map[now.x][now.y]=2;   //走过一个点
                if(Map[xx][yy]==3)  //到达终点
                    return nextt.step;
                q.push(nextt);

            }
            for(int i=0; i<5; i++){      //打印地图
                for(int j=0; j<5; j++)
                    cout << Map[i][j];
                cout << endl;
            }
            cout << endl;
        }
    }
    return -1;   //走不过去
}

int main()
{

    for(int i=0; i<5; i++)     //输入地图
        for(int j=0; j<5; j++)
            cin >> Map[i][j];
    Map[4][4]=3;  //定义终点
    ans=BFS(0,0);
    cout << ans<< endl;
    return 0;

}

自己重构的走迷宫的代码：

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n,m;
int zuiyou;
vector<vector<int>>maze;  //定义地图大小
struct point{
    int x,y;
};
int fangxiang[4][2]={{-1,0},{1,0},{0,-1},{0,1}};  //定义上下左右
vector<vector<int> >path(5,vector<int>(5));//记录每次的方向,0,1,2,3对应上下左右
vector<vector<int>>fan;

struct node{
    int x,y,z;
}now, nextt;;

void bfs(int x,int y)
{   
    // vector<vector<int>> path(n, vector<int>(m));
    maze[x][y]=2;
    queue <node> q;
    now.x=x;
    now.y=y;
    now.z=0;
    q.push(now);
    
    while(!q.empty())
    {   
        now=q.front();
        maze[now.x][now.y]=2;
        q.pop();
        for( int i=0;i<4;i++)
        {
            int xx=now.x+fangxiang[i][0];
            int yy=now.y+fangxiang[i][1];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&maze[xx][yy]==3)
            {   
                path[xx][yy]=i;
                if(maze[xx][yy]==3)
                    zuiyou=now.z+1;
            }

            if(xx>=0&&xx<n&&yy>=0&&yy<m&&maze[xx][yy]==0)
            {   
                nextt.x=xx;
                nextt.y=yy;
                nextt.z=now.z+1;
                q.push(nextt);
                path[xx][yy]=i;
            }
        }
    }

    int ii=n-1,jj=m-1;
    fan.push_back({ii,jj});

    while(ii!=0||jj!=0)
    {   
        int num=path[ii][jj];
        ii=ii-fangxiang[num][0];   
        jj=jj-fangxiang[num][1];   
        fan.push_back({ii,jj});
    }
    reverse(fan.begin(),fan.end());
}


int main()
{   
    cin>>n>>m;
    maze=vector<vector<int>>(n,vector<int>(m));  //定义地图大小    
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>maze[i][j];
        }
    }
    maze[4][4]=3;
    bfs(0, 0);
    cout<<zuiyou<<endl;;
    cout<<endl;
    for(auto t:fan)
    {
        cout<<t[0]<<","<<t[1];
        cout<<endl;
    }


}

一个非常简单好用的方法，解决称砝码问题：
现有n种砝码，重量互不相等，分别为 m1,m2,m3…mn ；每种砝码对应的数量为 x1,x2,x3…xn 。现在要用这些砝码去称物体的重量(放在同一侧)，问能称出多少种不同的重量。

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int>a;
    vector<int>b;
    for(int i=0;i<n;i++)
    {   
        int aa;
        cin>>aa;
        a.push_back(aa);
    }

    for(int i=0;i<n;i++)
    {   
        int aa;
        cin>>aa;
        b.push_back(aa);
    }

    set<int>s,tmp;
    s.insert(0);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<b[i];j++)
        {
            tmp=s;
            for(set<int>::iterator it=s.begin();it!=s.end();it++)
            tmp.insert(a[i]+*it);
            s=tmp;
        }

    }
    cout<<s.size();
}

【刷题笔记4】,笔记,笔记,算法,c++

  1. DFS（深度优先搜索算法）：一般用于查找图中的路径、连通性检测、拓扑排序等。
    深度优先搜索使用栈（Stack）数据结构来保存需要探索的节点。每次访问一个节点时，将其标记为已访问，并将其未访问的邻居节点压入栈中。然后从栈中弹出一个节点，继续访问该节点的未访问邻居节点，直到栈为空。

如果需要找到最短路径，可以考虑使用其他算法，如广度优先搜索（BFS）或 Dijkstra 算法。一般最小步数、最短距离、最小操作次数等问题采用BFS。


//DFS
#include <deque>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int N,M;
vector<vector<int>> maze;
vector<vector<int>> path_best;
vector<vector<int>> path_temp;//临时的辅助路径

void bestpath(int i,int j){
    //如果进来，走过就不走了
    maze[i][j]=1;
    
    //存进去
    path_temp.push_back({i,j});

    //判断出去的条件
    if(i==N-1&&j==M-1){
        if(path_temp.size()<path_best.size() || path_best.empty()){
            path_best = path_temp;
            return;
        }
    }

    //开始走 上、下、左、右
    if(i-1>=0 && maze[i-1][j]==0){
        bestpath(i-1,j);
    }
    if(i+1< N && maze[i+1][j]==0){
        bestpath(i+1,j);
    }
    if(j-1>=0 && maze[i][j-1]==0){
        bestpath(i,j-1);
    }
    if(j+1<M && maze[i][j+1]==0){
        bestpath(i,j+1);
    }

    //如果没进循环，标记回去
    maze[i][j]=0;
    path_temp.pop_back();//删除最后一个元素
}

int main() {
    while (cin >> N >> M) { // 注意 while 处理多个 case
        //赋值
        maze = vector<vector<int>>(N,vector<int>(M,0));
        //清空
        path_best.clear();
        path_temp.clear();
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                cin>>maze[i][j];
            }
        }

        //递归回溯
        bestpath(0,0);

        //输出
        for(auto itor:path_best){
            cout<<"("<<itor[0]<<","<<itor[1]<<")"<<endl;
        }
    }
    return 0;
}
  1. 回溯

三步走：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

【刷题笔记4】,笔记,笔记,算法,c++

例：从输入数据里取出特定个数的数据的组合。

#include <iostream>
#include <vector>
using namespace std;
vector<int>path;
vector<vector<int>>res;

void dfs(vector<int>& v1,int k,int step,int index)
{
    if(step==k)
    {
        res.push_back(path);
        return;
    }
    
    for(int i=index;i<v1.size();i++)
    {
        path.push_back(v1[i]);
        step++;
        dfs(v1,k,step,i+1);
        step--;
        path.pop_back();
    }
}

int main() {
    vector<int>v1;
    int k;
    while(cin>>k)
    v1.push_back(k);
    v1.pop_back();
    int step=0;
    int index=0;
    dfs(v1,k,step,index);
    cout<<res.size()<<endl;
    for(auto t:res)
    {
        for(int i=0;i<t.size();i++)
        {
            cout<<t[i]<<" ";
        }
        cout<<endl;
    }
}

练习：全排列文章来源地址https://www.toymoban.com/news/detail-812414.html

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
vector<int>path;
vector<vector<int>>res;
vector<int>jilu;

void dfs(vector<int>& v1,int num,int step,int index,vector<int>& jilu)
{
    if(step==num)
    {
        res.push_back(path);
        return;
    }
    for(int i=0;i<v1.size();i++)
    {
        if( find (jilu.begin(),jilu.end(), i)==jilu.end() )
        {
            path.push_back(v1[i]);
            jilu.push_back(i);
            step++;
            dfs(v1,num,step,i+1,jilu);
            step--;
            path.pop_back();
            jilu.pop_back();
        }
        
    }
}

int main() {
    vector<int>v1;
    int k;
    while(cin>>k)
    v1.push_back(k);
    int num=v1.size();
    int step=0;
    int shi=0;
    dfs(v1,num,step,shi,jilu);
    cout<<res.size()<<endl;

    for(auto t:res)
    {
        for(auto tt:t)
        {
            cout<<tt<<" ";
        }
        cout<<endl;
    }
}

到了这里，关于【刷题笔记4】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 力扣刷题笔记

    诸神缄默不语-个人CSDN博文目录 我以前刷过一波力扣，然后全忘了……从0开始的力扣复活赛！ 以前刷题用的是Java，现在Java几乎忘光了，所以现在是Python 3 + Java双语选手。 以下题目按照力扣官方顺序排列。 449. 序列化和反序列化二叉搜索树 1281. 整数的各位积和之差 1749. 任意

    2024年02月14日
    浏览(30)
  • 【刷题笔记4】

    【刷题笔记4】

    斐波那契数列：1，1，2，3，5，8，13…… 递归一把解决三类问题：1.数据定义是按照递归的（斐波那契数列）。2.问题解法是按递归算法实现的。 3.数据形式是按照递归形式定义的。 递归的一般形式： 有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月

    2024年01月21日
    浏览(21)
  • Verilog刷题笔记14

    Verilog刷题笔记14

    题目： One drawback of the ripple carry adder (See previous exercise) is that the delay for an adder to compute the carry out (from the carry-in, in the worst case) is fairly slow, and the second-stage adder cannot begin computing its carry-out until the first-stage adder has finished. This makes the adder slow. One improvement is a carry-select adder, sh

    2024年01月18日
    浏览(20)
  • Verilog刷题笔记16

    Verilog刷题笔记16

    题目： Since digital circuits are composed of logic gates connected with wires, any circuit can be expressed as some combination of modules and assign statements. However, sometimes this is not the most convenient way to describe the circuit. Procedures (of which always blocks are one example) provide an alternative syntax for describing circuits. For syn

    2024年01月18日
    浏览(24)
  • Verilog刷题笔记17

    Verilog刷题笔记17

    题目： For hardware synthesis, there are two types of always blocks that are relevant: Combinational: always @(*) Clocked: always @(posedge clk) Clocked always blocks create a blob of combinational logic just like combinational always blocks, but also creates a set of flip-flops (or “registers”) at the output of the blob of combinational logic. Instea

    2024年01月21日
    浏览(24)

  • 搜索 (C++刷题笔记)

    力扣 DFS 标记当前搜索位置已被搜索（标记当前位置的mark数组为1） 按照四个方向扩展四个新位置newx,newy 若新位置不在地图范围内，则忽略 如果新位置未曾到达mark[new][newy]，且是陆地，继续DFS该位置 BFS 设置搜索队列Q，标记mark[x][y]=1,并将待搜索位置(x,y)进入队列 只要队列不

    2024年02月03日
    浏览(18)
  • LeetCode刷题笔记

    LeetCode刷题笔记

    目录  LeetCode1.两数之和 思路： 代码：    LeetCode2.两数相加 思路： 代码：     LeetCode1171.链表删除和为0的连续节点  思路： 代码： 暴力： 最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。 当我们使用遍历整个数组的方式寻找 target - x 时，需

    2024年02月09日
    浏览(24)
  • 刷题笔记4

    刷题笔记4

    斐波那契数列：1，1，2，3，5，8，13…… 递归一把解决三类问题：1.数据定义是按照递归的（斐波那契数列）。2.问题解法是按递归算法实现的。 3.数据形式是按照递归形式定义的。 递归的一般形式： 有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月

    2024年01月18日
    浏览(22)
  • html刷题笔记

    html刷题笔记

    1 em = 12 pt = 16 px = 100% source元素 为 audio、video、picture元素指定多个媒体文件 margin是用来隔开元素与元素的间距；padding是用来隔开元素与内容的间隔 。 margin用于布局分开元素使元素与元素互不相干；padding用于元素与内容之间的间隔，让内容（文字）与（包裹）元素之间有一段

    2024年02月04日
    浏览(25)

  • 【算法】刷题路线(系统+全面)

    本系列基于当前各大公司对大公司的考察情况，给大家规划一条可行的算法刷题路线，大概会规划 200 道自认为有用的题，并且争取让初学者，能够刷起来更加丝滑，而且每个阶段都会进行相对应的说明。 当然，无论是面试还是笔试，你也完全可以按照这个路线来，应付大公

    2024年02月16日
    浏览(26)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包