精华内容
下载资源
问答
  • DFS

    2021-04-26 09:15:36
    文章目录前言一、DFS是什么?二、例题,模板1.AcWing842. 排列数字本题分析AC代码2.AcWing 843. n-皇后问题本题分析AC代码三、时间复杂度 前言 复习acwing算法基础课的内容,本篇为讲解基础算法:DFS,关于时间...


    前言

    复习acwing算法基础课的内容,本篇为讲解基础算法:DFS,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。


    一、DFS是什么?

    DFS即深度优先搜索,不同于BFS,DFS会一路走到头,然后再回溯,DFS可以搜到结果,但这个结果可能不是最优解,这个也是我们需要明确的.


    二、例题,模板

    1.AcWing842. 排列数字

    本题链接:AcWing842. 排列数字
    本博客给出本题截图:

    在这里插入图片描述

    本题分析

    本题是按位填写
    dfs(0);代表从第0位开始(即未开始)p数组中存的是每一位的值,s数组存的是该数是否已经填写过了,比如已经用过了i这个数,对应成代码就是s[i] = true;填写完数字之后要执行dfs(u + 1);,就是继续dfs下一位,最后记得要恢复现场s[i] = false

    AC代码

    #include <cstdio>
    
    using namespace std;
    
    const int N = 10;
    
    int p[N], n;
    bool s[N];
    
    void dfs(int u)
    {
        if (u == n)
        {
            for (int i = 0; i < n; i ++ ) 
                printf("%d ", p[i]);
            puts("");
        }
        
        for (int i = 1; i <= n; i ++ )
        {
            if (!s[i])
            {
                s[i] = true;
                p[u] = i;
                
                dfs(u + 1);
                
                s[i] = false;
            }
        }
    }
    
    int main()
    {
        scanf ("%d", &n);
        
        dfs(0);
        
        return 0;
    }
    

    2.AcWing 843. n-皇后问题

    本题链接:AcWing 843. n-皇后问题
    本博客给出本题截图:

    在这里插入图片描述
    在这里插入图片描述

    本题分析

    本题需要记录:行,列,对角线,反对角线是否有元素,故需要开4个bool数组
    这里我们具体来说一下对角线和反对角线的表示方法:
    首先来看一下我们建立的x和y轴:

    在这里插入图片描述
    再来看对角线:

    在这里插入图片描述
    再来看反对角线:

    在这里插入图片描述

    AC代码

    #include <cstdio>
    
    using namespace std;
    
    const int N = 20;
    
    char g[N][N];
    bool row[N], col[N], dg[N], udg[N];
    int n;
    
    void dfs(int x, int y, int s)
    {
        if (y == n) x ++, y = 0;
        
        if (x == n)
        {
            if (s == n)
            {
                for (int i = 0; i < n; i ++ ) puts(g[i]);
                puts("");
            }
            return;                //这里注意需要加return,否则会一直dfs下去导致爆内存
        }
        
        dfs(x, y + 1, s);
        
        if (!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n])
        {
            row[x] = col[y] = dg[x + y] = udg[y - x + n] = true;
            g[x][y] = 'Q';
            
            dfs(x, y + 1, s + 1);
            
            row[x] = col[y] = dg[x + y] = udg[y - x + n] = false;
            g[x][y] = '.';
        }
    }
    
    int main()
    {
        scanf("%d", &n);
        
        for (int i = 0; i < n; i ++ ) 
            for (int j = 0; j < n; j ++ )
                g[i][j] = '.';
        
        dfs(0, 0, 0);
        
        return 0;
    }
    

    三、时间复杂度

    关于DFS算法的时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

    展开全文
  • hadoop Non DFS Used是什么

    2017-11-13 15:02:00
    首先我们先来了解一下Non DFS User是什么? Non DFS User的意思是:非hadoop文件系统所使用的空间,比如说本身的linux系统使用的,或者存放的其它文件 它的计算公式: non dfs used = configured capacity - ...
    首先我们先来了解一下Non DFS User是什么?
    Non DFS User的意思是:非hadoop文件系统所使用的空间,比如说本身的linux系统使用的,或者存放的其它文件
     
    它的计算公式:
    non dfs used = configured capacity - remaining space - reserved space
     
    如果给datanode配置了预留磁盘空间参数的话,可以用下面的公式计算
    Non DFS used = ( Total Disk Space - Reserved Space) - Remaining Space - DFS Used
     
    我们来看个例子:
    如果有100G磁盘,设置dfs.datanode.du.reserved这个值为30G,在该磁盘上系统和其他文件使用了40G,
    DFS使用了10GB。如果执行df -h,可以看到有效空间是50G.
     
    在HDFS web 界面上,会看到
    non dfs user=100(total)-30(reserved)-10(dfs used)-50(remaing)=10G.
     
    所以实际上,你初始预留了30G给non dfs使用,70G给hdfs.然而,实际出来的non dfs使用超过了30G并且吃掉了属于hdfs的10g空间。
     
    “non dfs used”应该这样子定义“how much configured dfs capacity are occupied by non dfs use”.
    译为:配置的dfs的空间有多少被不是hdfs的文件占用了
     
    结论是:
    如果没有配置dfs.datanode.du.reserved,默认值是0,也就是磁盘的所以空间都给dfs,更好理解non dfs used了,就是给dfs配置的空间有多少被系统、系统进程使用了
     
    在hadoop集群内部使用率是如此高
    可用用‘lsof|grep delete’,该命令可以帮你确认哪些已经打开的文件被删除了。有时候,hadoop的进程(例如hive/yarn/mapred/hdfs等)也会引用这些已经删除的文件。这些引用也会占用磁盘空间。
     
    可以用这个命令
    du -hsx * | sort -rh | head -10
    查看排行10的最大文件夹或是文件。

    转载于:https://www.cnblogs.com/gentlemanhai/p/7826392.html

    展开全文
  • 【算法与数据结构 03】什么是DFS和BFS? 这两周陷入了测试和作业的漩涡中,今天才有时间坐在电脑前码字了。好吧,我承认我在找借口了QAQ 文章目录【算法与数据结构 03】什么是DFS和BFS?引入介绍DFSBFS应用DFS...

    这两周陷入了测试和作业的漩涡中,今天才有时间坐在电脑前码字了。好吧,我承认我是在找借口了QAQ

    引入

    DFS(Depth First Search) 即深度优先搜索,而提到DFS就得说起BFS(Breadth First Search) 广度优先搜索 了

    在我的上一篇文章 二叉树的引入 当中,我有提到 二叉树的前序、中序、后序遍历本质和DFS相同,而层序遍历本质和BFS相同,那么,DFSBFS又是什么呢,怎么去实现它们呢~

    来看看我在百科上看到的图,是和这次谈到的内容有关的哦~

    自然界中的宽搜


    介绍

    DFS

    假如去游玩一个市里面的景点,从景点0开始:

    DFS的介绍

    要去玩这些景点有很多种方式,那怎样才算是DFS呢~

    这里先给出DFS的概念

    深度优先搜索 简单来说就是 先深入探索,走到头再回退来寻找其他路径继续,以此反复 的遍历方式

    也就是说,它可以是这样去走的:

    DFS的介绍

    拿二叉树举例来说可以是这样走的(二叉树的前序遍历):

    二叉树的DFS

    那如果不是二叉树呢,而是在一个图中呢,就比如一个二维数组中:

    二维数组

    又怎么走完这个图中的灰色部分呢?

    首先依照遍历二维数组的方式,总可以找到第一个灰色部分,然后从这个灰色部分开始 深入探索

    因为是要走完所有的灰色部分,所以很显然要先探索与之相邻的四个方框(当然,不符合就直接return啦~):

    图的BFS

    再然后像之前走完所有符合的路径就像下面这个样子了:

    图的BFS

    细心的读者可能会发现,因为是要探索与之相邻的四个方框,那么到下一相邻方框时岂不是要返回重新来过一遍,这里先将这个疑问放着,等介绍算法实现部分再来解释吧~

    BFS

    BFS简单来说就是 一层一层由内而外 的遍历方式

    那么,又怎么通过BFS的方式来走完上面的景点呢,它可以是这样走的:

    BFS的介绍

    对于二叉树来说差不多是这样走的(二叉树的层序遍历):

    二叉树的层序遍历

    那如果是在一个二维数组中呢,与DFS又有什么不同呢?

    它也是从一个方框依次向周围探索,与DFS区别不是很大,直接上图:

    二维数组的BFS

    相信到这里朋友们对于DFSBFS是怎样走的应该了解了,那么接下来该说说它们的应用及算法实现了

    应用

    DFS应用一:二叉树中的遍历

    DFS在二叉树中的遍历概括起来就是使用递归:

    void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
    }
    

    然后根据遍历父结点的顺序分为了前序、中序、后序遍历(这里不深入探讨了)

    DFS应用二:岛屿问题

    由 m*n 个小方块组成的网格上(每一个小方块都与周围四个相邻,可以参考上文),在这样的网格上进行搜索

    空头说感觉不太好说,不如直接拿道题出来说说吧~

    比如在这道题中:

    463. 岛屿的周长

    1表示陆地,0表示水域(目的是遍历完陆地的部分):

    岛屿的周长

    在上文也提到 从一个小方格要去探索周围四个方格,以此来走完所有陆地的部分

    首先要注意的是边界的问题:

    void dfs(int[][] grid, int r, int c){
        // 如果坐标不合法,直接返回
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
    		return;
    	}
    }
    

    另外要注意的就是上面留下的疑问了:遍历过的网格如何确定它遍历过没有,这样就不至于卡在死循环里

    题目中是用数值来表示陆地和水域,那么可以改变遍历过的网格 的数值(当然,这个值别是01就好),以此来判断它走没走过,是不是很巧妙 😄

    最后实现起来大抵是这样:

    void dfs(int[][] grid, int r, int c){
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
    		return;
    	}
        // 如果这个方格不是岛屿,也直接返回
        if (grid[r][c] != 1) {
            return;
        }
        grid[r][c] = 2; // 标记遍历过的岛屿
        dfs(grid, r - 1, c); // 探索上边的方格
        dfs(grid, r + 1, c); // 下边的
        dfs(grid, r, c - 1); // 左边的
        dfs(grid, r, c + 1); // 右边的
    }
    

    除了上述两种应用较多外,还有其他的问题大抵上也都是用的 回溯 的思想

    这里提到了 回溯 :从一条路往前走,能进则进,不能进则退回来,换一条路再试 或者说 自后向前,追溯曾经走过的路径

    而想要实现 回溯,可以利用 的先入后出的特性,也可以采用 递归 的方式,而递归本身就是基于方法调用栈来实现的

    而相对的,BFS的实现关键在于 重放,也就是 将遍历过的结点按之前的遍历顺序重新回顾,可以利用队列的先入先出的特性来实现。说那么多 不如来看看下面的例子吧~

    BFS应用一:二叉树的层序遍历

    BFS在二叉树中的遍历使用队列:

    void bfs(TreeNode node){
    	Queue<TreeNode> queue = new LinkedList<>();
    	queue.add(node);
    	while (!queue.isEmpty()){
    		int n = queue.size();
    		for (int i = 0; i < n; i++) {
    			TreeNode cur = queue.poll();
    			if(cur.left != null) {
    				queue.add(cur.left);
    			}
    			if(cur.right != null) {
    				queue.add(cur.right);
     			}
    		}
    	}
    }
    

    相比于DFSBFS就显得比较繁琐了,这是因为 递归 隐含的使用了系统的 ,而我们就不需要自己维护一个数据结构了

    除此之外,两者遍历结点的顺序也不同

    BFS应用二:图的BFS

    图的BFS
    与层序遍历类似,同样需要使用队列,它的代码框架大概时这样的:

    Queue<TreeNode> queue = new ArrayDeque<>();
    while (!queue.isEmpty()){
    	int n = queue.size();
    	for (int i = 0; i < n; i++) {
            queue.poll();
            if () { // 若m结点没有访问过
                queue.add(m);
    		}
        }
    }
    

    上面的岛屿问题也可以用BFS来实现,也与上面的图的BFS类似

    BFS应用三:岛屿问题

    图的BFS
    同样的,0表示海洋,1表示陆地,从陆地依次向外遍历

    BFS又是如何实现探索周围四个方块,这里可以用两个数组来间接实现:

    void bfs(int[][] grid){
        //当前结点下标依次加上 dx[i], dy[i] 就可以得到新的下标
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
    }
    

    另外还需要队列来实现BFS,最后大概是这样子的:

    void bfs(int[][] grid){
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        
        Queue<int[]> queue = new ArrayDeque<>();
    	int m = grid.length, n = grid[0].length;
        // 将所有的陆地都入队。
    	for (int i = 0; i < m; i++) {
    		for (int j = 0; j < n; j++) {
    			if (grid[i][j] == 1) {
    				queue.offer(new int[] {i, j});
    			}
    		}
    	}
        
        // 然后从陆地开始一圈一圈的遍历
        int[] point = null;
    	while (!queue.isEmpty()) {
    		point = queue.poll();
    		int x = point[0], y = point[1];
    		// 取出队列的元素,将其四周的海洋入队。
    		for (int i = 0; i < 4; i++) {
    			int newX = x + dx[i];
    			int newY = y + dy[i];
                 // 边界的判断
    			if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] != 0) {
    				continue;
    			}
    			// 这里直接修改了原数组的值,以此来标记是否被访问
    			grid[newX][newY] = grid[x][y] + 1; 
    			queue.offer(new int[] {newX, newY});
    		}
    	}
    }
    

    那么,关于DFSBFS的介绍就到这里啦~,如果朋友们觉得有用的话不妨点个赞 😄


    题外话

    感觉自己的输出效率蛮低的,可能还是不太会写博客吧,不过我会坚持下去的:D

    展开全文
  • 1.BFS是用来搜索最短径路的解是比较合适的,比如求最少步数的解,最少交换次数的解,因为BFS搜索过程中遇到的解一定是离根最近的,所以遇到一个解,一定就是最优解,此时搜索算法可以...2.空间优劣上,DFS是有优势的...

    1.BFS是用来搜索最短径路的解是比较合适的,比如求最少步数的解,最少交换次数的解,因为BFS搜索过程中遇到的解一定是离根最近的,所以遇到一个解,一定就是最优解,此时搜索算法可以终止。这个时候不适宜使用DFS,因为DFS搜索到的解不一定是离根最近的,只有全局搜索完毕,才能从所有解中找出离根的最近的解。(当然这个DFS的不足,可以使用迭代加深搜索ID-DFS去弥补)
    2.空间优劣上,DFS是有优势的,DFS不需要保存搜索过程中的状态,而BFS在搜索过程中需要保存搜索过的状态,而且一般情况需要一个队列来记录。
    3.DFS适合搜索全部的解,因为要搜索全部的解,那么BFS搜索过程中,遇到离根最近的解,并没有什么用,也必须遍历完整棵搜索树,DFS搜索也会搜索全部,但是相比DFS不用记录过多信息,所以搜素全部解的问题,DFS显然更加合适。




    链接:https://www.zhihu.com/question/23780297/answer/167225829

     

    展开全文
  • DFS和BFS都图的遍历的两种形式。 DFS的特点不具有BFS中按层次顺序遍历的特性,所以DFS不具有最优性。DFS因此常用来求解有没有的问题。DFS所得到的解不一定最优解。当题目中出现问题是否有解等字眼时,常用DFS...
  • DFS原理与案例

    2018-01-28 15:55:35
    首先DFS是什么呢? D—depth,F—first,S—serach,形象一点的讲法就是一条道路走到黑,直到走到终点或者前面没有路,可以理解为一根筋。 DFS算法大同小异,只要抓住其核心思想,那么关于DFS的题目在你看来就像是...
  • DFS和BFS用来干什么

    2013-05-01 18:45:48
    DFS(Depth-First-Search)深度优先搜索算法,搜索算法的一种。一种在开发爬虫早期使用较多的方法。它的目的要达到被搜索结构的叶结点 宽度优先搜索算法(又称广度优先搜索)最简便的图的搜索算法之一,这一...
  • 文章目录一、DFS是什么?二、BFS是什么?三、BFS和DFS的区别四、需要注意的点五、二分是什么?六、专题题解1. Lake Counting2.Red and Black3. Accepted Necklace 一、DFS是什么? dfs是指深度优先搜索。从我的理解...
  • 已经配置了hadoop的环境变量,也source过了,但是只要不在hadoop/bin下面使用hdfs dfs -ls / 查询到的就是本地文件目录,并且报错: ``` Warning: fs.defaultFS is not set when running "ls" command. ``` 如图...
  • void dfs(int i,int cnt) { if(i == 0) { ans = max(ans,cnt); return ; } if(ans == V || cnt+sum[i] ) //cut return ; if(cnt+w[i] ) dfs(i-1,cnt+w[i]); dfs(i-1,cnt); } int main() { int t; scanf("%d",&t); ...
  • DFS

    2021-02-20 20:25:51
    什么是DFS序呢?顾名思义,深搜序号。不要小瞧他,若运用得当,在线段树等实现中,可以省空间的。 首先,对于一张图的DFS,我们知道的。 void dfs(int x) { vis[x]=true;//标记已来过 for(int i=head[x];i;...
  • 双向dfs

    2021-05-08 12:18:59
    什么要用双向dfs? 如果dfs调栈超过1e5时,那么考虑双向dfs 当进行的变换可逆的时候,且规定步数的上限时,可以使用双向dfs从源点和终点一起搜索。这样可以把时间从O(n)->O(n/2) 核心就是两个dfs分别处理一半...
  • DFS入门

    2018-11-05 23:03:59
    关于dfs参数问题,什么在变化,就把什么设置成参数。 DFS基本框架 void dfs()//参数用来表示状态 { if(到达终点状态) { ...//根据题意添加 return; } if(越界或者不合法状态) return; if(特殊...
  • DFS学习

    2019-08-14 20:12:31
    关于dfs参数问题,什么在变化,就把什么设置成参数。 void dfs()//参数用来表示状态 { if(到达终点状态) { ...//根据题意添加 return; } if(越界或者不合法状态) return; if(特殊状态)//...
  • 这个DFS是什么意思啊? DFS是深度优先搜索(Depth First Search)的简写。看看百度这个老妖怪的说法:…算了,不看了,它这个妖怪都不知道在说什么。 推荐这个视频,比较好入门。 ...为什么它要回头走啊?...
  • 题目 给出一个n*m的迷宫,其中标记为1的为障碍,标记为0的为可以通行的地方。 迷宫的入口为左上角,出口为右下角,只能从一个位置走到这个它的上...被一种思维误导了,我总是喜欢回溯来解决DFS问题,我总是怕终点路的行
  • 常见遍历写法 或者说书上一般的范例写法 此处特指王道,天勤等考研递归写法 void PrintTree(BiTree* T) { if (T) { PrintTree(T->lchild); PrintTree(T->rchild);...string dfs(int root
  • DFS回溯标记什么时候需要还原

    千次阅读 2014-08-13 11:36:00
    1.如果visit[i]这种标记,如果回溯后
  • dfs.namenode.name.dir 和dfs.datanode.data.dir分别是什么目录? dfs.namenode.name.dir 和dfs.datanode.data.dir分别是什么目录?有何作用?我们可以在本地文件系统中找到HDFS文件系统中文件或目录的位置吗? 我们...
  • DFS和BFS

    2021-01-29 13:20:39
    文章目录什么是DFS?什么是BFS?DFS与BFS的区别应用举例 什么是DFS? 深度优先遍历(DFS)也叫深度优先搜索。顾名思义,深度优先,则以深度为准则,先一条路走到底,直到达到目标。这里称之为递归下去。 DFS相当与一...
  • (1) fs是文件系统, dfs是分布式文件系统。 (2) fs > dfs。 (3) 分布式环境情况下,fs与dfs无区别。 (4) 本地环境中,fs就是本地文件,dfs就不能用了。 (5) fs涉及到一个通用的文件系统,可以指向任何的文件系统...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,276
精华内容 1,310
关键字:

dfs是什么