代码随想录-算法训练营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

相关文章

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么?AlloyDB 的工作原理2.搭建测试环境3.代码工程1.

Java调用Python代码的几种方法小结

《Java调用Python代码的几种方法小结》Python语言有丰富的系统管理、数据处理、统计类软件包,因此从java应用中调用Python代码的需求很常见、实用,本文介绍几种方法从java调用Pyt... 目录引言Java core使用ProcessBuilder使用Java脚本引擎总结引言python

Java中ArrayList的8种浅拷贝方式示例代码

《Java中ArrayList的8种浅拷贝方式示例代码》:本文主要介绍Java中ArrayList的8种浅拷贝方式的相关资料,讲解了Java中ArrayList的浅拷贝概念,并详细分享了八种实现浅... 目录引言什么是浅拷贝?ArrayList 浅拷贝的重要性方法一:使用构造函数方法二:使用 addAll(

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,:本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一:“杨辉三角”题目链接二:题解代码:三:题解思路:总结一:“杨辉三角”题目链接题目链接:点击这里

SpringBoot使用注解集成Redis缓存的示例代码

《SpringBoot使用注解集成Redis缓存的示例代码》:本文主要介绍在SpringBoot中使用注解集成Redis缓存的步骤,包括添加依赖、创建相关配置类、需要缓存数据的类(Tes... 目录一、创建 Caching 配置类二、创建需要缓存数据的类三、测试方法Spring Boot 熟悉后,集成一个外

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象(DAO)和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类(Entity)3.创建数据访问对象(DAO

轻松掌握python的dataclass让你的代码更简洁优雅

《轻松掌握python的dataclass让你的代码更简洁优雅》本文总结了几个我在使用Python的dataclass时常用的技巧,dataclass装饰器可以帮助我们简化数据类的定义过程,包括设置默... 目录1. 传统的类定义方式2. dataclass装饰器定义类2.1. 默认值2.2. 隐藏敏感信息

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量

IDEA常用插件之代码扫描SonarLint详解

《IDEA常用插件之代码扫描SonarLint详解》SonarLint是一款用于代码扫描的插件,可以帮助查找隐藏的bug,下载并安装插件后,右键点击项目并选择“Analyze”、“Analyzewit... 目录SonajavascriptrLint 查找隐藏的bug下载安装插件扫描代码查看结果总结Sona

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的