头像

CodeWater




离线:1小时前



思路

二叉搜索树,左子树小于根,根小于右子树。所以如果是中序遍历的话,得到的序列就是一个有序的序列。
这里就是用中序遍历。
另外,注意的是,最小值就是相邻结点之间的差值,不可能这个点隔着几个点的差值最小。如图:
783二叉搜索树结点最小距离.png

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    //res答案  last遍历的上一个数
        int res, last;
        //标记是不是第一个元素,因为第一个元素没有上一个元素
        bool isFirst;

    int minDiffInBST(TreeNode* root) {
        //初始化答案为正无穷    isFirst为true
        res = INT_MAX ,  isFirst = true;
        //遍历一下所有元素
        dfs(root);
        return res;
    }

    //遍历
    void dfs(TreeNode* root){
        //如果当前树为空,直接结束
        if(!root)  return ;
        //中序遍历:左根右
        dfs(root -> left);
        //如果是第一个元素
        if(isFirst){
            //改变标记,表示已经处理过第一个元素
            isFirst = false;
            //将当前元素存放到last中
            last = root -> val;
        }else{//如果不是第一个元素
            //算一下当前元素跟上一个元素的差值,更新答案
            res = min(res , root -> val - last);
            //然后再将当前元素存放到last中 ,用于下一次的比较
            last = root -> val;

        }

        //最后遍历一下右子树
        dfs(root -> right);
    }
};


活动打卡代码 AcWing 844. 走迷宫

/*宽搜的优势:可以搜到最短路径
注意:只有当边的权值都是1时,才可以用BFS。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;
typedef pair<int , int > PII;

int n  , m ;
//g数组存放的是迷宫
int g[N][N];
//d数组存放的是每个点到起点的距离
int d[N][N];

int bfs(){
    queue<PII> q;
    //初始化d数组
    memset(d , -1 , sizeof d);
    //起始点距离为0
    d[0][0] = 0;
    //起始点入队列
    q.push({0 , 0});

    //定义左上右下点的偏移量,dx和dy中的一一对应
    int dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0 ,1 , 0 ,-1};
    //当队列不空
    while(q.size()){
        //取队头元素
        auto t = q.front();
        //弹出队头
        q.pop();
        //以当前点往周围四个方向遍历(即用到刚刚定义的偏移量)
        for(int i = 0 ; i < 4 ; i++){
            //x横坐标    y纵坐标
            int x = t.first + dx[i] , y = t.second + dy[i];
            //如果遍历到的下一个点在范围内,并且可走而且是第一次走到
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                //符合条件就更新d数组,距离加1
                d[x][y] = d[t.first][t.second] + 1;
                //入队列
                q.push({x , y});
            }
        }
    }
    //返回最后记录的值
    return d[n - 1][m - 1];
}

int main(){
    cin>> n >> m;

    //读入整个地图
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
            cin>>g[i][j];

    cout<<bfs()<<endl;
    return 0;
}



题目描述

给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。

最初,有一个人位于左上角 (1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问,该人从左上角移动至右下角 (n,m) 处,至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。

输出格式
输出一个整数,表示从左上角移动至右下角的最少移动次数。

数据范围
1≤n,m≤100
输入样例:
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例:
8


算法BFS

宽搜的优势:可以搜到最短路径
注意:只有当边的权值都是1时,才可以用BFS。

acwing844走迷宫.png

参考文献

y总


C++ 代码


#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;
typedef pair<int , int > PII;

int n  , m ;
//g数组存放的是迷宫
int g[N][N];
//d数组存放的是每个点到起点的距离
int d[N][N];

int bfs(){
    queue<PII> q;
    //初始化d数组
    memset(d , -1 , sizeof d);
    //起始点距离为0
    d[0][0] = 0;
    //起始点入队列
    q.push({0 , 0});

    //定义左上右下点的偏移量,dx和dy中的一一对应
    int dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0 ,1 , 0 ,-1};
    //当队列不空
    while(q.size()){
        //取队头元素
        auto t = q.front();
        //弹出队头
        q.pop();
        //以当前点往周围四个方向遍历(即用到刚刚定义的偏移量)
        for(int i = 0 ; i < 4 ; i++){
            //x横坐标    y纵坐标
            int x = t.first + dx[i] , y = t.second + dy[i];
            //如果遍历到的下一个点在范围内,并且可走而且是第一次走到
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                //符合条件就更新d数组,距离加1
                d[x][y] = d[t.first][t.second] + 1;
                //入队列
                q.push({x , y});
            }
        }
    }
    //返回最后记录的值
    return d[n - 1][m - 1];
}

int main(){
    cin>> n >> m;

    //读入整个地图
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
            cin>>g[i][j];

    cout<<bfs()<<endl;
    return 0;
}


活动打卡代码 LeetCode 263. 丑数

class Solution {
public:
    bool isUgly(int n) {
        //因为丑数是正整数,所以对于负数进行特判
        if(n <= 0) return false;
        /*
        下满就是进行模运算,判断是否包含2,3,5这些质因子,然后通过不断整除,去除掉这些质因子。

        */
        while(n % 2 == 0) n /= 2;
        while(n % 3 == 0) n /= 3;
        while(n % 5 == 0) n /= 5;
        //最后判断除掉2,3,5剩下来的数是否大于1,如果大于1说明还有其他因子,如果等于1说明正好是丑数
        return n == 1;
    }
};


活动打卡代码 AcWing 843. n-皇后问题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//数据方位开两倍,因为对角线的数量是2倍
const int N = 20;
//n行n列h个皇后
int n;
//g数组记录n皇后的一种摆放方案
char g[N][N];
//row标记一行上能不能放置,col标记一列上能不能放置 ,dg数组标记斜线上能不能放置,udg是反对角线,同理
bool row[N] , col[N] , dg[N ] , udg[N];

//x横坐标 y纵坐标  s皇后的个数
void dfs(int x ,int y , int s){

    //皇后的个数不会超过n
    if(y == n) y = 0 , x++;
    //当x= n的时候说明已经枚举完最后一行了
    if(x == n){
        //当s=n的时候,说明找到一组解
        if(s == n){
            //输出这组解
            for(int i = 0 ; i < n ; i++)puts(g[i]);
            puts("");

        }
        return;
    }
    //开始枚举每个格子的选择
    //第一种,不放皇后的选择,就直接递归到下一层
    dfs(x , y + 1 , s);
    //第二种,放皇后,先进行条件判断这个格子的这一行列和对角线上没有皇后才能放
    if(!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){

        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n ] = true;
        dfs(x , y + 1 , s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }

}

int main(){
    cin>>n;
    //初始化
    for(int i = 0 ;i < n ; i++){
        for(int  j = 0 ; j < n ; j++){
            g[i][j] = '.';
        }
    }
    dfs(0 , 0 , 0);

    return 0;
}



题目描述

n− 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n,请你输出所有的满足条件的棋子摆法。

输入格式
共一行,包含整数 n。

输出格式
每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围
1≤n≤9
输入样例:
4
输出样例:
.Q..
…Q
Q…
..Q.

..Q.
Q…
…Q
.Q..


算法dfs

acwing843n皇后问题.png


参考文献

y总


C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//数据方位开两倍,因为对角线的数量是2倍
const int N = 20;
//n行n列h个皇后
int n;
//g数组记录n皇后的一种摆放方案
char g[N][N];
//col数组标记一列上能不能放置 ,dg数组标记斜线上能不能放置,udg是反对角线,同理
bool col[N] , dg[N] , udg[N];

void dfs(int u ){
    if(u == n){//u=n说明已经搜索到最后一层了
        //当找到一种方案的时候,直接输出
        for(int i  = 0 ; i < n ; i++)puts(g[i]);//g是二维数组,但是这里是直接输出一行
        puts("");
        return ;
    }
    //开始枚举
    for(int i = 0 ; i < n ; i++ )   {
        //首先这一列上之前没有放过一个皇后,对角线和反对角线上也是
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){//对角线的坐标不懂可以看图解
            g[u][i] = 'Q';
            //当选定i列之后,就要标记这一列不能再放置了,对角线上也是
            col[i] = dg[u + i] = udg[n - u + i] = true ;
            dfs(u + 1);
            //搜索完下面的层数之后,回到当前层的时候要恢复现场
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';  
        }

    }
}

int main(){
    cin>>n;
    //初始化
    for(int i = 0 ;i < n ; i++){
        for(int  j = 0 ; j < n ; j++){
            g[i][j] = '.';
        }
    }
    dfs(0);

    return 0;
}

算法dfs(搜索顺序不一样)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

//数据方位开两倍,因为对角线的数量是2倍
const int N = 20;
//n行n列h个皇后
int n;
//g数组记录n皇后的一种摆放方案
char g[N][N];
//row标记一行上能不能放置,col标记一列上能不能放置 ,dg数组标记斜线上能不能放置,udg是反对角线,同理
bool row[N] , col[N] , dg[N ] , udg[N];

//x横坐标 y纵坐标  s皇后的个数
void dfs(int x ,int y , int s){

    //皇后的个数不会超过n
    if(y == n) y = 0 , x++;
    //当x= n的时候说明已经枚举完最后一行了
    if(x == n){
        //当s=n的时候,说明找到一组解
        if(s == n){
            //输出这组解
            for(int i = 0 ; i < n ; i++)puts(g[i]);
            puts("");

        }
        return;
    }
    //开始枚举每个格子的选择
    //第一种,不放皇后的选择,就直接递归到下一层
    dfs(x , y + 1 , s);
    //第二种,放皇后,先进行条件判断这个格子的这一行列和对角线上没有皇后才能放
    if(!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){

        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n ] = true;
        dfs(x , y + 1 , s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }

}

int main(){
    cin>>n;
    //初始化
    for(int i = 0 ;i < n ; i++){
        for(int  j = 0 ; j < n ; j++){
            g[i][j] = '.';
        }
    }
    dfs(0 , 0 , 0);

    return 0;
}



解题思路

跟上一题类似,只不过多了一些重复的元素,所以我们在处理的时候,去除掉重复的元素即可。
不懂得可看上一题题解
去除重复的元素详见代码。

代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        //定义n为数组的最后一个元素的下标 
        int n = nums.size() - 1;
        //删除第二段中最后一个元素可能与第一段第一个元素相同的值
        while( n > 0 && nums[n] == nums[0]) n--;
        //判断一下有一段有序还是两段有序
        if(nums[n] >= nums[0]) return nums[0];//只有一段有序的序列
        //否则有两段有序的序列,进行二分
        int l =  0 , r = n ;
        while(l < r){
            int mid = l + r >> 1;
            //最小值在第二段,缩小右边界
            if(nums[mid] < nums[0]) r = mid;
             //否则mid在第一段,而最小值在第二段,缩小左边界,让其在第二段中继续搜索
            else l = mid + 1;
        }

        return nums[l];
    }
};


活动打卡代码 AcWing 842. 排列数字

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;
//整数n
int n;
//path数组记录一种方案
int path[N];
//bool标记该位置的点是否被用过(true为用过)
bool st[N];

void dfs(int u){
    //当u=n的时候,说明已经搜索到最后一层了,这时候只要输出path数组里面的记录的路径即可
    if(u == n){
        for(int i = 0 ; i < n ; i++) printf("%d " , path[i] );
         puts("");
        return;
    }

    //当u小于n的时候,说明还没有搜索完,所以要枚举一下当前位置可以填哪些数
    for(int i  = 1 ; i <= n ; i++){
        //如果当前位置为false,说明这个位置可以填入数字。false取反之后为true,符合条件
        if(!st[i]){
            //把i放入到当前这个位置上去
            path[u] = i;
            //同时记录这个位置已经被用过了
            st[i] = true;
            //处理完当前这一层之后,开始搜索下一层
            dfs(u + 1);
            //当dfs函数搜索完下面所有的层数之后,回到当前层,要恢复成原来的状态,方便
            //下一次的搜索
            /*path[u] = 0;思考一下可以看出,path数组这个不需要恢复,因为每一次搜索的时候
            这个位置上的数都会被覆盖掉,不影响结果。
            但是st标记数组需要恢复,因为每一次都需要他来进行判断当前这个位置可不可以进行
            填值
            */
            st[i] = false;
        }
    }
}

int main(){
    cin >> n;
    //从第0个位置开始搜索
    dfs(0);

    return 0;
}



题目描述

给定一个整数 n,将数字 1∼n 排成一排,将会有很多种排列方法。

现在,请你按照字典序将所有的排列方法输出。

输入格式
共一行,包含一个整数 n。

输出格式
按字典序输出所有排列方案,每个方案占一行。

数据范围
1≤n≤7
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1


算法:dfs

acwing842排列数字.png


参考文献

y总


C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;
//整数n
int n;
//path数组记录一种方案
int path[N];
//bool标记该位置的点是否被用过(true为用过)
bool st[N];

void dfs(int u){
    //当u=n的时候,说明已经搜索到最后一层了,这时候只要输出path数组里面的记录的路径即可
    if(u == n){
        for(int i = 0 ; i < n ; i++) printf("%d " , path[i] );
         puts("");
        return;
    }

    //当u小于n的时候,说明还没有搜索完,所以要枚举一下当前位置可以填哪些数
    for(int i  = 1 ; i <= n ; i++){
        //如果当前位置为false,说明这个位置可以填入数字。false取反之后为true,符合条件
        if(!st[i]){
            //把i放入到当前这个位置上去
            path[u] = i;
            //同时记录这个位置已经被用过了
            st[i] = true;
            //处理完当前这一层之后,开始搜索下一层
            dfs(u + 1);
            //当dfs函数搜索完下面所有的层数之后,回到当前层,要恢复成原来的状态,方便
            //下一次的搜索
            /*path[u] = 0;思考一下可以看出,path数组这个不需要恢复,因为每一次搜索的时候
            这个位置上的数都会被覆盖掉,不影响结果。
            但是st标记数组需要恢复,因为每一次都需要他来进行判断当前这个位置可不可以进行
            填值
            */
            st[i] = false;
        }
    }
}

int main(){
    cin >> n;
    //从第0个位置开始搜索
    dfs(0);

    return 0;
}



二分图解

153寻找旋转排序数组中的最小值.png
(详见代码)

class Solution {
public:
    int findMin(vector<int>& nums) {
        //特判一下特殊情况,只有一段升序的,例如示例3,直接返回nums[0]即可
        if(nums.back() >= nums[0]) return nums[0];

        //正常有两段不一样的有序序列,进行二分
        int l = 0 , r = nums.size() -  1 ; 
        while(l < r){
            //中间值
            int mid = l + r >> 1;
            //mid,最小值在第二段序列上,调整右边界
            if(nums[mid] < nums[0])   r = mid;
            //mid在第一序列上,调整到第二段上去
            else l = mid + 1 ;
        }
        //最后return,此时L 和R相等,随便返回一个即可
        return nums[l];
    }
};