代码随想录-算法训练营day12【休息,复习与总结】

2024-04-14 17:36

本文主要是介绍代码随想录-算法训练营day12【休息,复习与总结】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

● day 12 周日休息(4.14)

目录

复习与总结

0417_图论-太平洋大西洋水流问题

0827_图论-最大人工岛


复习与总结

二刷做题速度提升了一大截,ヾ(◍°∇°◍)ノ゙加油~

0417_图论-太平洋大西洋水流问题

//从太平洋边界开始DFS
for (int i = 0; i < m; i++) {//遍历第一行,从第一行开始dfs(matrix, canReachPacific, i, 0);
}
for (int j = 1; j < n; j++) {//遍历第一列,然后从第一列的第二个元素开始dfs(matrix, canReachPacific, 0, j);
}//从大西洋边界开始DFS
for (int i = 0; i < m; i++) {//遍历最后一列,从最后一列开始dfs(matrix, canReachAtlantic, i, n - 1);
}
for (int j = 0; j < n - 1; j++) {//遍历最后一行,然后从最后一行的第一个元素开始dfs(matrix, canReachAtlantic, m - 1, j);
}

正确地遍历了太平洋和大西洋的边界。

  1. 对于太平洋来说,你从第一行开始,然后从第一列的第二个元素开始(因为第一个元素已经在第一行遍历过);
  2. 对于大西洋来说,你从最后一列开始,然后从最后一行的第一个元素开始(同样,最后一行的最后一个元素已经在最后一列遍历过)。

这种遍历边界的方法很好地处理了太平洋和大西洋的情况。

package com.question.solve.leetcode.programmerCarl._12_graphTheory;import java.util.ArrayList;
import java.util.List;public class _0417 {
}class Solution0417 {public List<List<Integer>> pacificAtlantic(int[][] matrix) {List<List<Integer>> result = new ArrayList<>();if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;int m = matrix.length, n = matrix[0].length;boolean[][] canReachPacific = new boolean[m][n];boolean[][] canReachAtlantic = new boolean[m][n];//从太平洋边界开始DFSfor (int i = 0; i < m; i++) {//遍历第一行,从第一行开始dfs(matrix, canReachPacific, i, 0);}for (int j = 1; j < n; j++) {//遍历第一列,然后从第一列的第二个元素开始dfs(matrix, canReachPacific, 0, j);}//从大西洋边界开始DFSfor (int i = 0; i < m; i++) {//遍历最后一列,从最后一列开始dfs(matrix, canReachAtlantic, i, n - 1);}for (int j = 0; j < n - 1; j++) {//遍历最后一行,然后从最后一行的第一个元素开始dfs(matrix, canReachAtlantic, m - 1, j);}//找到同时能够到达太平洋和大西洋的单元格for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (canReachPacific[i][j] && canReachAtlantic[i][j]) {List<Integer> cell = new ArrayList<>();cell.add(i);cell.add(j);result.add(cell);}}}return result;}private void dfs(int[][] matrix, boolean[][] canReach, int i, int j) {int m = matrix.length;int n = matrix[0].length;if (canReach[i][j]) return; //已经访问过该单元格canReach[i][j] = true; //标记为能够到达//搜索上下左右四个方向int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};for (int[] dir : directions) {int x = i + dir[0];int y = j + dir[1];if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] >= matrix[i][j]) {dfs(matrix, canReach, x, y);}}}//    private void dfs(char[][] matrix, boolean[][] canReach, int i, int j) {
//        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || canReach[i][j]) return;
//        canReach[i][j] = true; //标记为能够到达
//        dfs(matrix, canReach, i + 1, j);
//        dfs(matrix, canReach, i - 1, j);
//        dfs(matrix, canReach, i, j + 1);
//        dfs(matrix, canReach, i, j - 1);
//    }
}

0827_图论-最大人工岛

LeetCode题解:https://leetcode.cn/problems/making-a-large-island/solutions/1830957/by-muse-77-37hi/

package com.question.solve.leetcode.programmerCarl._12_graphTheory;import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;public class _0827_最大人工岛 {
}class Solution0827 {private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};//四个方向/*** @param grid 矩阵数组* @param row  当前遍历的节点的行号* @param col  当前遍历的节点的列号* @param mark 当前区域的标记* @return 返回当前区域内 1 的数量*/public int dfs(int[][] grid, int row, int col, int mark) {int ans = 0;grid[row][col] = mark;for (int[] current : position) {int curRow = row + current[0], curCol = col + current[1];if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid.length) continue;//越界if (grid[curRow][curCol] == 1)ans += 1 + dfs(grid, curRow, curCol, mark);}return ans;}public int largestIsland(int[][] grid) {int ans = Integer.MIN_VALUE, size = grid.length, mark = 2;Map<Integer, Integer> getSize = new HashMap<>();for (int row = 0; row < size; row++) {for (int col = 0; col < size; col++) {if (grid[row][col] == 1) {int areaSize = 1 + dfs(grid, row, col, mark);getSize.put(mark++, areaSize);}}}for (int row = 0; row < size; row++) {for (int col = 0; col < size; col++) {//当前位置如果不是 0,那么直接跳过,因为我们只能把 0 变成 1if (grid[row][col] != 0) continue;Set<Integer> hashSet = new HashSet<>();//防止同一个区域被重复计算//计算从当前位置开始获取的 1 的数量,初始化 1 是因为把当前位置的 0 转换成了 1int curSize = 1;for (int[] current : position) {int curRow = row + current[0], curCol = col + current[1];if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid.length) continue;int curMark = grid[curRow][curCol];//获取对应位置的标记//如果标记存在hashSet中,说明该标记被记录过一次,如果不存在 getSize 中说明该标记是无效标记(此时 curMark = 0)if (hashSet.contains(curMark) || !getSize.containsKey(curMark)) continue;hashSet.add(curMark);curSize += getSize.get(curMark);}ans = Math.max(ans, curSize);}}//当 ans == Integer.MIN_VALUE,说明矩阵数组中不存在 0,全都是有效区域,返回数组大小即可return ans == Integer.MIN_VALUE ? size * size : ans;}
}

这篇关于代码随想录-算法训练营day12【休息,复习与总结】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,:本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,