代码随想录算法第五十三天| KamaCoder110字符串迁移、KamaCoder105有向图的完全联通、KamaCoder106海岸线的计算

KamaCoder 110 字符串迁移题目链接110.字符串迁移文档讲解代码随想录视频讲解 字符串迁移思路与感想直接卡在读懂题意这一关了我还纳闷输出结果怎么跟自己理解的差那么多。卡哥讲完之后才明白题目的推导过程和具体的难点在哪。本题的难点主要就是每个作为单个路径的字符串之间如何相连以及如何找到这个最短路径。自己敲完代码之后着重理解了一下这两个难点首先就是字符串之间如何相连这个其实就要回归题意了那就是每次替换只能替换一个字符且替换后的新字符串必须在字典srtList中这样一来一个暴力的想法就是尝试遍历这个当前字符串每个字符然后试着把它每个字符用二十六个字母一一替换如果替换后的新字符串存在于字典中并且之前没有访问过这个新字符串说明就可以把它加入到队列里面这样就是字符串相连了。至于最短路径就是要想清楚广搜这个搜索模式的特质并结合本题的具体搜索情况如果当前遍历的字符串进行替换操作存在多种走向即多个新字符串存在于字典中鉴于广搜是每个方向雨露均沾地搜搜到一个新的就放入队列可见每个方向的搜素速度是相同的不会存在深搜那样一个方向搜到底再搜另一个方向。这样一来只要搜到了endStr就直接return即可这样获得的路径长度一定是最短的。整道题的代码实现还是难度挺大的还要注意替换字符后的回溯操作以及对map和set的使用这些对于代码的掌控能力的要求还是挺大的。收获1.广搜与深搜的区别2.广搜的使用场景// 广搜BFS import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); // 接收字典strList的长度 sc.nextLine(); String beginStr sc.next(); // 接收起始字符串 String endStr sc.next(); // 接收目标末尾字符串 ListString wordList new ArrayList(); // 构建字典 sc.nextLine(); for (int i 0; i n; i) { wordList.add(sc.nextLine()); // 把字典里面的字符串加入字典 } int count bfs(beginStr, endStr, wordList); // 广搜获取最短路径 System.out.println(count); // 输出结果 } public static int bfs(String beginStr, String endStr, ListString wordList) { HashSetString set new HashSet(wordList); // 用set表示字典高效判断某个字符串是否存在于字典中 MapString,Integer map new HashMap(); // 类似visited但又有value来记录起点到当前字符串的最短路径 QueueString queue new LinkedList(); map.put(beginStr, 1); queue.add(beginStr); // 开始广搜 while (!queue.isEmpty()) { String node queue.poll(); // 获取当前字符串 char[] charArray node.toCharArray(); // 转为char数组方便替换操作 for (int i 0; i charArray.length; i) { // 遍历该字符串所有字母 char old charArray[i]; // 记录原字母方便后续回溯消除影响 for (char j a; j z; j) { // 把每个字母尝试替换为二十六个字母 charArray[i] j; // 替换操作 String newWord new String(charArray); // 构建新字符串 if (newWord.equals(endStr)) { // 如果这个新字符串就是末尾目标字符串直接返回它的最短路径当前字符串的value 1就是新字符串的最短路径 return map.get(node) 1; } if (set.contains(newWord) !map.containsKey(newWord)) { // 如果新字符串在字典里面并且还没有被访问过即加入到map中就可以把它加入到队列和map中进行进一步广搜 map.put(newWord, map.get(node) 1); queue.add(newWord); } } charArray[i] old; // 回溯消除替换此字符的影响再i替换当前字符串的下一个字符 } } return 0; // 循环结束了仍然没有返回说明无法从起始字符串到目标终点字符串直接return 0 } }KamaCoder 105 有向图的完全联通题目链接105.有向图的完全联通文档讲解代码随想录视频讲解有向图的完全联通思路与感想本题开始从岛屿之类的无向图转为有向图了就立马想起了最初接触图论的第一道深搜可到达路径题目。观察了下边和节点个数想到随之用邻接矩阵去构造图沿用上一题利用HashSet判断某个节点是否重复访问刚做的时候有点迷糊用了两个HashSet一个set记录可以到达的节点另一个visited记录已经访问的节点其实本质上一个set就能解决的事。然后没有跟可到达路径那道题区分开盲目地进行回溯了导致出现死循环即重复访问。后面仔细想了想没有必要进行回溯因为本题是看某个节点能不能到达而不是说有多少种不同的路径需要你拐弯重走什么的后面回溯操作一删除就通过了。看卡哥的方法主要学习了邻接表怎么使用然后还有本题的广搜写法。收获1.邻接表的使用2.回溯操作的时机// 深搜DFS(邻接矩阵构造图HashSet作为visited数组) import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); int[][] grid new int[n 1][n 1]; // 邻接矩阵构造图 for (int i 0; i k; i) { // 能到达的赋值为1 grid[sc.nextInt()][sc.nextInt()] 1; } HashSetInteger set new HashSet(); // 记录被访问过的节点即能到达的节点 set.add(1); // main中提前处理起点 dfs(grid, set, 1); // 深搜逻辑里面是处理下一个节点 if (set.size() n) { // 如果set长度刚好等于n说明每个节点都可以到达 System.out.println(1); } else { System.out.println(-1); } } public static void dfs(int[][] grid, HashSetInteger set, int cur) { for (int i 1; i grid.length; i) { // 遍历当前节点可以前往的所有节点 if (grid[cur][i] 0 || set.contains(i)) { // 如果无法前往i节点或者i节点已经被到达过了就直接continue continue; } int nextCur i; // i其实就是即将访问的节点nextCur set.add(nextCur); // 符合条件加入set记录避免重复访问 dfs(grid, set, nextCur); // 继续深搜 } } }// 深搜DFS(邻接表构造图) import java.util.*; public class Main { public static ListListInteger grid new ArrayList(); // 邻接表构造 public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); for (int i 0; i n; i) { grid.add(new LinkedList()); // 邻接表的初始化 } for (int j 0; j k; j) { int start sc.nextInt(); int end sc.nextInt(); grid.get(start - 1).add(end - 1); // 同上 } boolean[] visited new boolean[n]; // 定义visited数组记录可到达的节点 dfs(visited, 0); // 深搜逻辑是处理当前节点 for (int i 0; i n; i) { // 如果深搜过后仍然存在未到达节点直接输出-1 if (!visited[i]) { System.out.println(-1); return; } } System.out.println(1); } public static void dfs(boolean[] visited, int key) { if (visited[key]) { // 已经到达的节点不重复深搜 return; } visited[key] true; // 记录已到达 ListInteger nextKeys grid.get(key); // 获取当前节点能够前往的各个节点相比于邻接矩阵的优点就体现出来了后续只遍历能到达的节点不能到达的干脆不遍历浪费时间 for (Integer nextKey : nextKeys) { dfs(visited, nextKey); } } }// BFS广搜(邻接表构造图) import java.util.*; public class Main { public static ListListInteger grid new ArrayList(); public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); for (int i 0; i n; i) { grid.add(new LinkedList()); } for (int j 0; j k; j) { int start sc.nextInt(); int end sc.nextInt(); grid.get(start - 1).add(end - 1); } boolean[] visited new boolean[n]; bfs(visited, 0); for (int i 0; i n; i) { if (!visited[i]) { System.out.println(-1); return; } } System.out.println(1); } public static void bfs(boolean[] visited, int key) { QueueInteger queue new LinkedList(); queue.add(key); // 开始广搜 visited[key] true; // 加入队列的同时置visited为true while (!queue.isEmpty()) { int node queue.poll(); // 获取当前节点 ListInteger nextNodes grid.get(node); // 获取当前节点所能前往的所有节点 for (Integer nextNode : nextNodes) { // 遍历一一尝试访问到达 if (!visited[nextNode]) { // 访问前检查目标节点是否被访问过了不重复访问 queue.add(nextNode); visited[nextNode] true; // 加入队列就立马置为true } } } } }KamaCoder 106 海岸线计算题目链接106.海岸线计算文档讲解代码随想录视频讲解海岸线的计算思路与感想本题的一个难点在于海岸线的长度要怎么计算说实话写出上面那段话我自己都想笑因为题目不正是海岸线计算吗哈哈哈哈哈。但这确实是事实这个玩意让我想起来初中学摆方块找其中规律得出这个大方块周长的感觉很像。我当时也想了一会这个海岸线长度到底跟什么有关能不能根据陆地数量找出某种可以推导出海岸线周长的公式后面感觉实在找不出啥必然联系就猛然想起之前做过几道题都提倡逆向思维行那我也逆向一下不再着眼于陆地了我看海洋跟这个海岸线长度有什么联系随后马上有了惊喜的发现那就是陆地四周的海洋方块个数就是这个陆地方块对海岸线总长度的贡献值我立马把代码写出来验证我的猜想后面果然输出正确的答案不过提交的时候报错了原因是我忘记判断grid[nextX][nextY] 0前判断新坐标的合法性导致了下标越界补上了之后发现提交发现运行答案又有误了一看案例发现自己漏考虑了陆地方块四周为整个案例边界的时候长度len也要照常自增不能直接continue。改了之后就通过了。这道题并没有用到深搜和广搜大概这就是卡哥提示这道题不能惯性思维的原因吧。题目确实简单只要想清楚海岸线怎么求就可以了。卡哥的解法和我如出一辙但是我自以为想到这个海岸线跟陆地四周的海洋格子数有关还是听巧妙的结果卡哥说这是一种朴实无华的想法当场吐血。还有另一种方法就是先统计所有的陆地数量然后*4就是每个陆地最多能贡献的海岸线长度但是因为陆地与陆地相靠的时候这个贡献值会削减削减值为相靠陆地数量*2最终就得到了海岸线的长度。收获1.正难则反2.思维要严谨周到// 朴素存储模拟法(思路每个陆地格子对海岸线长度的贡献即它四周的海洋格子数) import java.util.Scanner; public class Main { static int len 0; static int[][] dir {{0,1},{1,0},{-1,0},{0,-1}}; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 1) { // 只对陆地格子进行长度累加操作 for (int k 0; k 4; k) { // 遍历四周格子 int nextX i dir[k][0]; // 获取四周格子的坐标 int nextY j dir[k][1]; if (nextX 0 || nextX n || nextY 0 || nextY m) { // 判断越界保险 len; // 越界说明这个方向陆地格子的边本身就是海岸线也需要累加 continue; } if (grid[nextX][nextY] 0) { // 四周是海洋长度累加 len; } } } } } System.out.println(len); } }今天花了大概六个小时第一题确实有点难花的时间比较久后面两道题自己手搓出来了。没有DDL的期末周真是惬意啊下午依旧健身练的胸认真地打磨动作感受对抗阻力的过程尽可能让力线流畅卧推前检查好几个点下颚收好眼神对杠不要塌腕肩胛骨保持稳定出杠时先吸气落杠吐气核心收紧不能松否则会懈力背部紧贴坐垫。不再追求重量和所谓的组数享受打磨动作和健身的过程不求力竭重视每次的质量如何如果疲劳了即使停止训练避免第二天无法恢复影响生活。热爱健身将其作为终身保持的良好习惯不盲目追求大重量导致自己动作框架变形甚至受伤同时不把健身当作体力劳动追求练到极致急于求成可能往往适得其反。Patience is key in life!健身需要耐心刷算法题也是如此。