【六十】【算法分析与设计】用一道题目解决dfs深度优先遍历,dfs中节点信息,dfs递归函数模板进入前维护出去前回溯,唯一解的剪枝飞升返回值true

路径之谜

题目描述

小明冒充X星球的骑士,进入了一个奇怪的城堡。

城堡里边什么都没有,只有方形石头铺成的地面。

假设城堡地面是n×n个方格。如下图所示。

1e8908abd7eb470083d000bb49a7bab3.png

按习俗,骑士要从西北角走到东南角。可以横向或纵向移动,但不能斜着音走,也不能跳跃。每走到一个新方格,就要向正北

方和正西方各射一箭。(城堡的西墙和北墙内各有12个靶子)同一个方格只允许经过一次。但不必走完所有的方格。如果只

给出靶子上箭的数目,你能推断出骑士的行走路线吗?有时是可以的,比比如上图中的例子。

本题的要求就是已知箭靶数字,求骑士的行走路径(测试)数据保证路径唯一)

输入描述

第一行一个整数N(0<N<20),表示地面有NXN个方格。

第二行N个整数,空格分开,表示北边的箭靶上的数字(自西向东)

第三行N个整数,空格分开,表示西边的箭靶上的数字(自北向南)

输出描述

输出一行若干个整数,表示骑士路径。

为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号号:0,1,2,3

比如,上图中的方块编号为:

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

输入输出样例

示例

输入

4

2 4 3 4

4 3 3 3

输出

0 4 5 1 2 3 7 11 10 9 13 14 15

运行限制

最大运行时间:5s

最大运行内存:256M

12c651f1c7234b9988867f9e74ddcf2e.png

暴力递归

1.

定义dfs(i,j)表示当前节点坐标。

假设入口位置坐标是(1,1),往下是row行,往右是col列。

定义row记录从入口到当前节点这条路径西边靶子的数量,row[1]表示西边第一个靶子上箭的数量,row[2]表示西边第二个靶子上箭的数量...以此类推。

定义col记录从入口到当前节点这条路径北边靶子的数量,col[1]表示北边第一个靶子上箭的数量,col[2]表示北边第二个靶子上箭的数量...以此类推。

定义path记录从入口到当前节点的路径信息。

定义visit记录从入口到当前节点,这条路径,当前所有位置访问情况,访问过为true,没有被访问过false。

2.

也就是当前节点的信息不止有(i,j)还有path,row,col,visit四个变量共同组成。

3.

dfs内部逻辑,进入当前节点的时候,维护当前节点的所有信息。

离开当前节点返回之前,回溯,消除当前节点维护的所有信息。

4.

夹在中间的就是计算逻辑,写代码的时候先把首位维护和回溯写掉,然后在中间加主要逻辑。

 
void dfs(int i, int j) {
    visit[i][j] = true;
    row[i]++;
    col[j]++;
    path.push_back((i - 1) * n + (j - 1));//数学推导不细说,找规律
    //添加主要逻辑
    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;
}

 

5.

06e70e01efad4a72a6044d401aaf9bae.png

对于当前节点,下一个遍历的节点位置有四个,上下左右,但是有一些位置需要剪枝。

规则是,第一,这四个位置首先不能越界,第二,这四个位置不能被访问过,被访问过表示已经是路径上的点,已经走过了。如果满足要求就可以dfs进入下一节点。

 
void dfs(int i, int j) {
    visit[i][j] = true;
    row[i]++;
    col[j]++;
    path.push_back((i - 1) * n + (j - 1));

    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
            dfs(x, y);
        }
    }

    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;
}

 

6.

思考递归出口,递归出口是当你走到出口的时候,即i==n&&j==n。

此时遍历row和col,看看靶子上箭的数量是不是和aim_row,aim_col目标值对上。

如果对上了此时path里面存放的就是我们要的路径,打印出来即可。

如果没有对上就返回,不需要再进入下一节点了。

返回前注意需要回溯,消除维护操作。

 
void dfs(int i, int j) {
    visit[i][j] = true;
    row[i]++;
    col[j]++;
    path.push_back((i - 1) * n + (j - 1));

    if (i == n && j == n) {
        int flag = 1;
        for (int i = 1; i <= n; i++) {
            if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;
        }
        if (flag == 1) {
            for (auto& x : path) cout << x << " ";
        }
                path.pop_back();
                row[i]--;
                col[j]--;
                visit[i][j] = false;
                return;
        
    }
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
            dfs(x, y);
        }
    }

    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;
}

 

代码1

7.

此时得到的代码如下,

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

int n; // 定义n表示城堡地面是n×n个方格
vector<int> path; // 用于记录骑士的行走路径
vector<int> row; // 用于记录每行射出的箭的数量
vector<int> col; // 用于记录每列射出的箭的数量
vector<vector<int>> visit; // 记录某个格子是否被访问过
int dx[4] = { 1,-1,0,0 }; // 方向数组,用于实现上下左右移动
int dy[4] = { 0,0,1,-1 };
vector<int> aim_col; // 存储每列应该射出的箭的目标数量
vector<int> aim_row; // 存储每行应该射出的箭的目标数量

// 深度优先搜索(DFS)函数,用于尝试所有可能的路径
void dfs(int i, int j) {
    visit[i][j] = true; // 标记当前格子为已访问
    row[i]++; // 当前行的箭数增加
    col[j]++; // 当前列的箭数增加
    path.push_back((i - 1) * n + (j - 1)); // 将当前格子编号加入路径

    // 如果到达东南角,并且每行每列的箭数都符合目标
    if (i == n && j == n) {
        int flag = 1;
        for (int i = 1; i <= n; i++) {
            if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;
        }
        if (flag == 1) {
            for (auto& x : path) cout << x << " "; // 如果路径有效,输出这条路径
        }
        path.pop_back();
        row[i]--;
        col[j]--;
        visit[i][j] = false;
        return;
    }

    // 尝试向四个方向移动
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
            dfs(x, y);
        }
    }

    // 回溯,撤销当前步骤的影响
    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;
}

int main() {
    cin >> n; // 读入n的大小
    aim_col.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> aim_col[i]; // 读入每列的目标箭数
    aim_row.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> aim_row[i]; // 读入每行的目标箭数

    row.resize(n + 1);
    col.resize(n + 1);
    visit = vector<vector<int>>(n + 1, vector<int>(n + 1));

    dfs(1, 1); // 从西北角开始进行深度优先搜索

    return 0;
}

运行结果如下,

09945d723f644fc8a58e3ff7d6749755.png

剪枝1:唯一解找到即返回true(飞升)

8.

大部分运行超时,说明代码整体逻辑没有问题,但是剪枝操作没有做好。

重新思考剪枝操作。

题目中测试数据保证了路径的唯一性,说明我们只要找到了最终答案,就不需要回溯,后面的操作都不需要,找到最终答案就一路飞升回到第一层递归返回。

修改dfs的返回值,不使用void返回值,而使用int或者bool,意思是如果当前找到了就返回true,没有找到就返回false。

修改完返回值还需要修改进入下一层递归的代码,不能直接是dfs,而是if(dfs(x, y)) return true;

如果返回值是true说明找到了,如果找到了什么都不用管,直接返回true。

每一层节点都接收这个信息,有没有完成工作,有没有找到路径?找到了就可以不用再工作了,直接返回。

还需要修改递归出口的逻辑,flag==1说明找到了,打印完路径后直接返回true。

 
int dfs(int i, int j) {
    visit[i][j] = true;
    row[i]++;
    col[j]++;
    path.push_back((i - 1) * n + (j - 1));

    if (i == n && j == n) {
        int flag = 1;
        for (int i = 1; i <= n; i++) {
            if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;
        }
        if (flag == 1) {
            for (auto& x : path) cout << x << " ";
            return true;
        }
            path.pop_back();
            row[i]--;
            col[j]--;
            visit[i][j] = false;
            return;
    }
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
             if(dfs(x, y)) return true;
        }
    }

    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;
    
    return false;
}

 

代码2

9.

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

int n; // 城堡地面为n×n个方格的大小
vector<int> path; // 存储骑士的行走路径
vector<int> row; // 每行射箭的次数
vector<int> col; // 每列射箭的次数
vector<vector<int>> visit; // 标记方格是否访问过
int dx[4] = { 1,-1,0,0 }; // x方向的移动:下,上,不动,不动
int dy[4] = { 0,0,1,-1 }; // y方向的移动:不动,不动,右,左
vector<int> aim_col; // 目标,每列应射箭的次数
vector<int> aim_row; // 目标,每行应射箭的次数

// 深度优先搜索(DFS)算法,i和j表示当前位置
int dfs(int i, int j) {
    visit[i][j] = true; // 标记当前方格为已访问
    row[i]++; // 当前行的射箭次数增加
    col[j]++; // 当前列的射箭次数增加
    path.push_back((i - 1) * n + (j - 1)); // 将当前方格的编号加入到路径中

    // 检查是否到达右下角,并且所有行和列的射箭次数都符合目标
    if (i == n && j == n) {
        int flag = 1; // 用于检查是否所有行和列的射箭次数都匹配
        for (int i = 1; i <= n; i++) {
            if (row[i] != aim_row[i] || col[i] != aim_col[i]) flag = 0;
        }
        if (flag == 1) {
            for (auto& x : path) cout << x << " "; // 如果匹配,输出路径
            cout << endl; // 输出换行
            return true; // 返回找到有效路径
        }
    }

    // 尝试四个可能的移动方向
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
            if (dfs(x, y)) return true; // 递归调用dfs
        }
    }

    // 回溯,撤销当前步骤
    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;

    return false; // 没有找到有效路径
}

int main() {
    cin >> n;
    aim_col.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> aim_col[i]; // 输入每列的目标射箭次数
    aim_row.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> aim_row[i]; // 输入每行的目标射箭次数

    row.resize(n + 1);
    col.resize(n + 1);
    visit = vector<vector<int>>(n + 1, vector<int>(n + 1, false)); // 初始化访问标记数组

    dfs(1, 1); // 从(1,1)开始深度优先搜索

    return 0;
}

运行结果如下,

a94fedcc6cc74cd2bcb5c4451d3fd699.png

剪枝2:靶子箭数量小于目标靶子箭数量

10.

说明这个剪枝操作微不足道,没什么用。

继续思考其他剪枝操作,我们发现如果到了一个节点,如果row,col中有一个靶子的箭数量大于目标靶子的箭数量,后面的路径都不可能是最终答案。

因为靶子上箭的数量不可能减少只能增加,所以到出口之前,如果是正确路径,靶子数量一定小于目标靶子数量。

所以如果靶子箭数量大于目标靶子箭数量,直接返回。

 
int dfs(int i, int j) {
    visit[i][j] = true;
    row[i]++;
    col[j]++;
    path.push_back((i - 1) * n + (j - 1));

    int flag1 = 1;
    for (int i = 1; i <= n; i++) {
        if (row[i] > aim_row[i] || col[i] > aim_col[i]) {
            flag1 = 0;
            break;
        }
    }
    if (flag1 == 0) {
        path.pop_back();
        row[i]--;
        col[j]--;
        visit[i][j] = false;

        return false;
    }

    if (i == n && j == n) {
        int flag = 1;
        for (int i = 1; i <= n; i++) {
            if (row[i] != aim_row[i] || col[i] != aim_col[i]) {
                flag = 0;
                break;
            }
        }
        if (flag == 1) {
            for (auto& x : path) cout << x << " ";
            return true;
        }else{
        path.pop_back();
        row[i]--;
        col[j]--;
        visit[i][j] = false;

        return false;
    }
    }

    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
            if (dfs(x, y)) return true;
        }
    }

    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;

    return false;
}

 

代码3

 
#include <iostream>
#include<bits/stdc++.h>  // 引入常用库,包含STL等
using namespace std;

// 定义全局变量
int n;  // 地图大小
vector<int> path;  // 记录路径
vector<int> row;  // 记录每行走过的次数
vector<int> col;  // 记录每列走过的次数
vector<vector<int>> visit;  // 访问标记数组
int dx[4] = { 1,-1,0,0 };  // 方向数组,表示行的移动
int dy[4] = { 0,0,1,-1 };  // 方向数组,表示列的移动
vector<int> aim_col;  // 目标列的箭数
vector<int> aim_row;  // 目标行的箭数

// 深度优先搜索函数
int dfs(int i, int j) {
    visit[i][j] = true;  // 标记当前单元格已访问
    row[i]++;  // 增加当前行的计数
    col[j]++;  // 增加当前列的计数
    path.push_back((i - 1) * n + (j - 1));  // 记录路径

    int flag1 = 1;
    // 检查所有行列是否满足条件
    for (int i = 1; i <= n; i++) {
        if (row[i] > aim_row[i] || col[i] > aim_col[i]) {
            flag1 = 0;
            break;
        }
    }
    if (flag1 == 0) {  // 如果条件不满足,则回退操作
        path.pop_back();
        row[i]--;
        col[j]--;
        visit[i][j] = false;
        return false;
    }

    // 检查是否到达最后一个方格
    if (i == n && j == n) {
        int flag = 1;
        for (int i = 1; i <= n; i++) {
            if (row[i] != aim_row[i] || col[i] != aim_col[i]) {
                flag = 0;
                break;
            }
        }
        if (flag == 1) {  // 如果满足最终条件,输出路径
            for (auto& x : path) cout << x << " ";
            return true;
        } else {  // 否则,进行回退操作
            path.pop_back();
            row[i]--;
            col[j]--;
            visit[i][j] = false;
            return false;
        }
    }

    // 遍历四个方向
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x >= 1 && x <= n && y >= 1 && y <= n && !visit[x][y]) {
            if (dfs(x, y)) return true;
        }
    }

    // 回退操作
    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;
    return false;
}

int main() {
    cin >> n;
    aim_col.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> aim_col[i];  // 输入北边靶子箭数
    aim_row.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> aim_row[i];  // 输入西边靶子箭数

    row.resize(n + 1);
    col.resize(n + 1);
    visit = vector<vector<int>>(n + 1, vector<int>(n + 1));  // 初始化访问矩阵

    dfs(1, 1);  // 从(1,1)开始搜索

    return 0;
}

72a4030d74204f56b86d822e926b7774.png

总结结论

1.

递归函数dfs,用同样的函数完成相同的逻辑问题,但是需要用其他遍历辅助判断当前位于那个节点。

vector<int> path;

vector<int> row;

vector<int> col;

vector<vector<int>> visit;

(i,j)

以上都是当前节点的信息。

2.

每一次进入dfs维护当前节点信息,每一次出去之前回溯,消除维护的信息。

 
void dfs(int i, int j) {
    visit[i][j] = true;
    row[i]++;
    col[j]++;
    path.push_back((i - 1) * n + (j - 1));//数学推导不细说,找规律
    //添加主要逻辑
    path.pop_back();
    row[i]--;
    col[j]--;
    visit[i][j] = false;
}

 

3.

如果只需要找唯一解,找到即返回,找到就不用工作,找到就飞升。

修改返回值,进入下一层逻辑,出口逻辑。

7401f170df974efcb1dc440636a9fd40.png

4.

剪枝操作提前返回,注意返回之前一定要回溯,也就是消除维护当前节点信息的操作!!!

结尾

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

 

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

 

谢谢您的支持,期待与您在下一篇文章中再次相遇!

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/569000.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】解决ubuntu20.04版本插入无线网卡没有wifi显示【无线网卡Realtek 8811cu】

ubuntu为Realtek 8811cu安装驱动&#xff0c;解决wifi连接问题 1、确认无线网卡的型号-Realtek 8810cu2、下载并配置驱动 一句话总结&#xff1a;先确定网卡的型号&#xff0c;然后根据网卡的型号区寻找对应的驱动下载&#xff0c;下载完成之后在ubuntu系统中进行编译&#xff…

3D 文件格式的江湖纷争

自从上世纪 60 年代计算机辅助设计(Computer Aided Design, CAD)发明已来,3D 图形产业繁荣发展,逐步覆盖工业制造、影视游戏、VR/AR 、3D 打印等各个领域。如果说 3D 模型是构成 XR 应用场景的基础组件,那么 3D 文件格式就是构建 XR 世界沟通语言。而伴随各种 3D 建模软件…

C++链表操作入门

数据结构基础&#xff1a;链表操作入门 数据结构基础&#xff1a;链表操作入门链表的基本概念链表的基本操作输出链表插入节点删除节点查找值 完整的链表操作示例结语 数据结构基础&#xff1a;链表操作入门 在计算机科学中&#xff0c;数据结构是组织和存储数据的方式&#x…

H264 编码标准常见术语解释

H264 编码标准 H.264编码标准&#xff0c;也被称作MPEG-4 AVC&#xff08;Advanced Video Coding&#xff09;&#xff0c;是一种被广泛使用的数字视频压缩标准&#xff0c;由国际电信联盟&#xff08;ITU-T&#xff09;和国际标准化组织&#xff08;ISO&#xff09;共同开发。…

【蓝牙协议栈】【BLE】低功耗蓝牙工作流程(角色\广播\扫描\连接等专业名词介绍)

1. 精讲蓝牙协议栈&#xff08;Bluetooth Stack&#xff09;&#xff1a;SPP/A2DP/AVRCP/HFP/PBAP/IAP2/HID/MAP/OPP/PAN/GATTC/GATTS/HOGP等协议理论 2. 欢迎大家关注和订阅&#xff0c;【精讲蓝牙协议栈】和【Android Bluetooth Stack】专栏会持续更新中.....敬请期待&#x…

谷歌搜索seo排名怎么做上去?

谷歌算法纵使千变万化&#xff0c;用户体验&#xff08;UX&#xff09;也始终是核心&#xff0c;用户体验包含很多&#xff0c;但核心就是让访问你网站的人觉得你的网站看着顺眼&#xff0c;同时轻松找到他们需要的信息或服务&#xff0c;这意味着你的网站得易于导航&#xff0…

命名空间:namespace

对于无名命名空间 &#xff1a;但是不能再次定义相同名称的变量 在同一文件中

Stable Diffusion WebUI 使用 LoRA 调整风格——详细教程

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里&#xff0c;订阅后可阅读专栏内所有文章。 大家好&#xff0c;我是水滴~~ 本教程旨在深入探讨 LoRA 模型的奥秘&#xff0c;涵盖其基本概念、独特作用以及实操指南。我们将从下载和使用LoRA的步…

Laravel 6 - 第十五章 验证器

​ 文章目录 Laravel 6 - 第一章 简介 Laravel 6 - 第二章 项目搭建 Laravel 6 - 第三章 文件夹结构 Laravel 6 - 第四章 生命周期 Laravel 6 - 第五章 控制反转和依赖注入 Laravel 6 - 第六章 服务容器 Laravel 6 - 第七章 服务提供者 Laravel 6 - 第八章 门面 Laravel 6 - …

微信小程序实时日志使用,setFilterMsg用法

实时日志 背景 为帮助小程序开发者快捷地排查小程序漏洞、定位问题&#xff0c;我们推出了实时日志功能。开发者可通过提供的接口打印日志&#xff0c;日志汇聚并实时上报到小程序后台。开发者可从We分析“性能质量->实时日志->小程序日志”进入小程序端日志查询页面&am…

【八股】计算机网络篇

网络模型 应用层【HTTP&#x1f449;报文/消息】 传输层【TCP或UDP&#x1f449;段&#x1f449;MSS】网络层【IP、寻址和路由&#x1f449;MTU】 ①IP&#xff08;Internet Protocol&#xff0c;网际协议&#xff09;主要作用是定义数据包的格式、对数据包进行路由和寻址&…

【Linux-14】进程地址空间&虚拟空间&页表——原理&知识点详解

前言 大家好吖&#xff0c;欢迎来到 YY 滴 系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过Linux的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的《Lin…

STM32的GPIO输入和输出函数详解

系列文章目录 STM32单片机系列专栏 C语言术语和结构总结专栏 文章目录 1. GPIO模式 2. GPIO输出 2.1 RCC 2.2 GPIO 3. 代码示例 3.1 RCC时钟 3.2 GPIO初始化 3.3 GPIO输出函数 3.4 推挽输出和开漏输出 4. GPIO输入 4.1 输入模式 4.2 数据读取函数 5. C语言语法 1…

2024免费最好用的苹果电脑mac虚拟机工具Parallels Desktop19中文版下载

一、软件概述 Parallels Desktop是一款专为Mac设计的虚拟机软件&#xff0c;它允许用户在Mac上同时运行Windows、Linux等多个操作系统&#xff0c;而无需额外的硬件设备。通过Parallels Desktop&#xff0c;Mac用户可以轻松地在同一台电脑上体验不同操作系统的功能和应用程序。…

Burpsuite CA证书导入浏览器、导入本地

前言 为什么要导入证书&#xff0c;因为要获得浏览器的信任、本地的信任&#xff1b;才能抓包 导入浏览器 1.从bp导出证书 然后打开火狐浏览器 打开bp,设置好代理 火狐浏览器foxyproxy开启代理 访问https://www.baidu.com 可以抓到https的包 本地导入CA证书 可能某一天你要…

AIGC实战——基于Transformer实现音乐生成

AIGC实战——基于Transformer实现音乐生成 0. 前言1. 音乐生成的挑战2. MuseNet3. 音乐数据3.1 巴赫大提琴组曲数据集3.2 解析 MIDI 文件3.3 分词3.4 创建训练数据集 4. MuseNet 模型4.1 正弦位置编码4.2 多输入/输出 5. 音乐生成 Transformer 的分析6. 多声部音乐分词6.1 网格…

牛客NC195 二叉树的直径【simple DFS C++ / Java /Go/ PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/15f977cedc5a4ffa8f03a3433d18650d 思路 最长路径有两种情况&#xff1a; 1.最长条路径经过根节点&#xff0c;那么只需要找出根节点的左右两棵子树的最大深度然后相加即可。 2.最长路径没有经过根节点&#xf…

JavaSE——常用API进阶二(8/8)-Arrays、Comparable、Comparator(Arrays类提供的的常见方法、用法示例)

目录 Arrays Arrays类提供的的常见方法 用法示例 Comparable、Comparator Comparable Comparator 本篇学习Arrays&#xff0c;不算作是重点知识&#xff0c;但是为学习后面的Lambda表达式打一个基础&#xff0c;或者说&#xff0c;作为铺垫。 Arrays 用来操作数组的一个…

初见-响应式编程-002

&#x1f917; ApiHug {Postman|Swagger|Api...} 快↑ 准√ 省↓ GitHub - apihug/apihug.com: All abou the Apihug apihug.com: 有爱&#xff0c;有温度&#xff0c;有质量&#xff0c;有信任ApiHug - API design Copilot - IntelliJ IDEs Plugin | Marketplace #Reacti…

lnmp架构

目录 环境 步骤 下载nginx源码包&#xff0c;并解压 安装依赖包 进行预编译 、编译安装 安装php、设置开机自启 配置nginx让其支持php服务 浏览器测试 安装mariadb 部署discuz论坛 简介 LNMP架构是一种常见的Web服务器架构&#xff0c;由Linux、Nginx、MySQL和PHP组成。它…