当前位置: 首页 > news >正文

国家建设部网站注册工程师人员查询Wordpress和jamel

国家建设部网站注册工程师人员查询,Wordpress和jamel,表白网页制作软件,亚马逊建站服务130. 被围绕的区域 leetcode链接#xff1a;题目链接 这题看起来很复杂#xff0c;其实跟之前找飞地和找边缘地区的是差不多的#xff0c;主要分三步#xff1a; 使用dfs将边缘的岛都找出来#xff0c;然后用A代替防止混淆#xff1b;再用dfs找中间不与任何岛相连的飞地…130. 被围绕的区域 leetcode链接题目链接 这题看起来很复杂其实跟之前找飞地和找边缘地区的是差不多的主要分三步 使用dfs将边缘的岛都找出来然后用A代替防止混淆再用dfs找中间不与任何岛相连的飞地最后把之前的A替换成O。 最终代码 class Solution { public:void dfs(vectorvectorchar board, int i, int j, char ch){//找到o把其周围转化为chvectorint dir {0,-1,0,1,1,0,-1,0};if(i 0 || j 0 || i board.size() || j board[0].size()){return;}if(board[i][j] X || board[i][j] a){return;}board[i][j] ch;for(int idx 0; idx 4; idx){dfs(board, i dir[2 * idx], j dir[2 * idx 1],ch);}}void solve(vectorvectorchar board) {int m board.size();int n board[0].size();for(int i 0; i m; i){if(board[i][n - 1] O){dfs(board,i, n - 1, a);}if(board[i][0] O){dfs(board,i,0, a);}}for(int j 0; j n; j){if(board[0][j] O){dfs(board,0, j,a);}if(board[m - 1][j] O){dfs(board, m - 1, j,a);}}for(int i 0; i m; i){for(int j 0; j n;j){if(board[i][j] O){board[i][j] X;}if(board[i][j] a){board[i][j] O;}}} // for(int i 0; i m; i){ // for(int j 0; j n;j){ // if(board[i][j] a){ // board[i][j] O; // } // } // }} };这里有几点注意的 dfs函数中除了等于X需要return等于A也需要return否则递归就没办法结束。只需要dfs淹没周围一圈的岛中间的岛不用再dfs找了直接替换就行因为本题没有让我们以整个岛为单位做一些事情。 417. 太平洋大西洋水流问题 leetcode链接题目链接 输入: heights [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] 示例 2输入: heights [[2,1],[1,2]] 输出: [[0,0],[0,1],[1,0],[1,1]]首先这题题目我都没怎么看懂理解一下题意。 输入是一个二维数组只要位于该点的值比四个方向的高就可以流向其他方向最终既可以流向右边、下边大西洋又可以流向左边、上边太平洋的符合结果输出result。 首先能想到一个很朴素的思路就是对每个点都判断一下是否能同时流向大西洋和太平洋。这种思路的实现代码如下 class Solution { private:int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1};void dfs(vectorvectorint heights, vectorvectorbool visited, int x, int y) {if (visited[x][y]) return;visited[x][y] true;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx heights.size() || nexty 0 || nexty heights[0].size()) continue;if (heights[x][y] heights[nextx][nexty]) continue; // 高度不合适dfs (heights, visited, nextx, nexty);}return;}bool isResult(vectorvectorint heights, int x, int y) {vectorvectorbool visited vectorvectorbool(heights.size(), vectorbool(heights[0].size(), false));// 深搜将x,y出发 能到的节点都标记上。 dfs(heights, visited, x, y);bool isPacific false;bool isAtlantic false;// 以下就是判断xy出发是否到达太平洋和大西洋 for (int j 0; j heights[0].size(); j) {if (visited[0][j]) {isPacific true;break;}}for (int i 0; i heights.size(); i) {if (visited[i][0]) {isPacific true;break;}}for (int j 0; j heights[0].size(); j) {if (visited[heights.size() - 1][j]) {isAtlantic true;break;}}for (int i 0; i heights.size(); i) {if (visited[i][heights[0].size() - 1]) {isAtlantic true;break;}}if (isAtlantic isPacific) return true;return false;} public:vectorvectorint pacificAtlantic(vectorvectorint heights) {vectorvectorint result;// 遍历每一个点看是否能同时到达太平洋和大西洋 for (int i 0; i heights.size(); i) {for (int j 0; j heights[0].size(); j) {if (isResult(heights, i, j)) result.push_back({i, j});}}return result;} }; 这种思路很直白但很明显以上代码超时了。 来看看时间复杂度。 遍历每一个节点是 m * n遍历每一个节点的时候都要做深搜深搜的时间复杂度是 m * n 那么整体时间复杂度 就是 O(m^2 * n^2) 这是一个四次方的时间复杂度。 优化 那么我们可以 反过来想从太平洋边上的节点 逆流而上将遍历过的节点都标记上。 从大西洋的边上节点 逆流而长将遍历过的节点也标记上。 然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。 class Solution { private:int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向// 从低向高遍历注意这里visited是引用即可以改变传入的pacific和atlantic的值void dfs(vectorvectorint heights, vectorvectorbool visited, int x, int y) {if (visited[x][y]) return;visited[x][y] true;for (int i 0; i 4; i) { // 向四个方向遍历int nextx x dir[i][0];int nexty y dir[i][1];// 超过边界if (nextx 0 || nextx heights.size() || nexty 0 || nexty heights[0].size()) continue;// 高度不合适注意这里是从低向高判断if (heights[x][y] heights[nextx][nexty]) continue;dfs (heights, visited, nextx, nexty);}return;}public: vectorvectorint pacificAtlantic(vectorvectorint heights) {vectorvectorint result;int n heights.size();int m heights[0].size(); // 这里不用担心空指针题目要求说了长宽都大于1// 记录从太平洋边出发可以遍历的节点vectorvectorbool pacific vectorvectorbool(n, vectorbool(m, false));// 记录从大西洋出发可以遍历的节点vectorvectorbool atlantic vectorvectorbool(n, vectorbool(m, false));// 从最上最下行的节点出发向高处遍历for (int i 0; i n; i) {dfs (heights, pacific, i, 0); // 遍历最上行接触太平洋dfs (heights, atlantic, i, m - 1); // 遍历最下行接触大西洋}// 从最左最右列的节点出发向高处遍历for (int j 0; j m; j) {dfs (heights, pacific, 0, j); // 遍历最左列接触太平洋dfs (heights, atlantic, n - 1, j); // 遍历最右列接触大西洋}for (int i 0; i n; i) {for (int j 0; j m; j) {// 如果这个节点从太平洋和大西洋出发都遍历过就是结果if (pacific[i][j] atlantic[i][j]) result.push_back({i, j});}}return result;} }; 所以 调用dfs函数只要参数传入的是 数组pacific那么地图中 每一个节点其实就遍历一次无论你调用多少次。 同理调用 dfs函数只要 参数传入的是 数组atlantic地图中每个节点也只会遍历一次。 所以以下这段代码的时间复杂度是 2 * n * m。 地图用每个节点就遍历了两次参数传入pacific的时候遍历一次参数传入atlantic的时候遍历一次。 827. 最大人工岛 leetcode链接力扣链接 给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后grid 中最大的岛屿面积是多少岛屿 由一组上、下、左、右四个方向相连的 1 形成。示例 1:输入: grid [[1, 0], [0, 1]] 输出: 3 解释: 将一格0变成1最终连通两个小岛得到面积为 3 的岛屿。 示例 2:输入: grid [[1, 1], [1, 0]] 输出: 4 解释: 将一格0变成1岛屿的面积扩大为 4。 示例 3:输入: grid [[1, 1], [1, 1]] 输出: 4 解释: 没有0可以让我们变成1面积依然为 4。https://www.programmercarl.com/0827.%E6%9C%80%E5%A4%A7%E4%BA%BA%E5%B7%A5%E5%B2%9B.html#%E4%BC%98%E5%8C%96%E6%80%9D%E8%B7%AF 先放这里放一下。题目居然是hard不太想做岛屿类的题了换换脑子。 总结 岛屿问题的dfs/bfs的代码基本大差不差主要还是主函数中处理逻辑的问题学习带有 visited的dfs的写法。
http://www.sadfv.cn/news/356299/

相关文章:

  • 交通银行网站开发泉州 网站制作
  • 自己做的网站怎么添加采集模块全国统一信息查询平台
  • 公司想做一个网站首页怎么做聊城app开发公司
  • 网站建设课程设计实验报告怎样找外贸公司合作
  • 宝塔面板上传自己做的网站专业网站设计力荐亿企邦
  • 湖北营销型网站建设费用wordpress 添加文章列表
  • 海淀企业网站搭建装修企业网站源码
  • 网站建设课设心得网站开发类投标文件
  • 营销型企业网站建设ppt常用的网页制作工具有什么
  • 常州网站建设常州如何申请企业邮箱免费
  • 推荐网站网页app开发公司名字
  • 手机上可建网站做淘宝客吗唐山乾正建设工程材料检测公司网站
  • 深圳最大的招聘网站是什么广东前20大互联网公司
  • 有什么网站做可以国外的生意专业推广网站
  • 做卷皮网类似网站2017年网站建设工作总结
  • 南宁网站关键词推广微信视频号怎么引流推广
  • 网站设计软件下载wordpress多站点 文章
  • 北京做的比较好的网站公司wordpress积分充值插件
  • 58网站开发要多少钱建网站要多少钱一台
  • 手机网站导航代码ICP网站忘记密码
  • 网站负责人核验照片国外flash网站欣赏
  • 使用vue做的商城网站像那种代刷网站怎么做
  • 网站改版不收录上海网站制作怎么选
  • 婚介网站怎么做公司介绍ppt模板免费
  • pc网站如何转为手机版网站广告如何做
  • 金汇网站建设项目符号在哪里设置
  • 如何做高端网站广州英铭网站建设
  • 一般建设网站需要多少预算深圳网络推广营销
  • 国外炫酷网站贵阳网络推广公司哪家强
  • 泰安专业网站开发公司公司用wordpress