当前位置： 首页 > article >正文

算法解析-经典150（图论、回溯法）

article 2025/1/8 13:45:17

文章目录

  • 图论
    • 1.岛屿数量
        • 1.答案
        • 2.思路
    • 2.被围绕的区域
        • 1.答案1
        • 2.思路1
        • 3.答案2
        • 4.答案2
  • 回溯法
    • 1.电话号码的字母组合
        • 1.答案
        • 2.思路
    • 2.组合
        • 1.答案
        • 2.思路
    • 3.全排列
        • 1.答案
        • 2.思路
    • 4.组合总和
        • 1.答案
        • 2.思路
    • 5.括号生成
        • 1.答案
        • 2.思路
    • 6.单词搜索
        • 1.答案
        • 2.思路

图论

1.岛屿数量

1.答案
package com.sunxiansheng.classic150.g1;

/**
 * Description: 200. 岛屿数量
 *
 * @Author sun
 * @Create 2024/12/28 09:25
 * @Version 1.0
 */
public class t200 {

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int res = 0;
        // 当遇到一个1，岛屿数量就加一，然后将岛屿变为海洋，防止重复计算
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    // 将岛屿变为海洋
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    /**
     * dfs将岛屿变为海洋
     *
     * @param grid
     * @param i
     * @param j
     */
    public static void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        // 当越界或者是海洋的时候传递状态
        if (i < 0 || i > m - 1 || j < 0 || j > n - 1 || grid[i][j] == '0') {
            return;
        } else {
            // 将岛屿变为海洋
            grid[i][j] = '0';
            // 上下左右传递状态
            dfs(grid, i - 1, j);
            dfs(grid, i + 1, j);
            dfs(grid, i, j - 1);
            dfs(grid, i, j + 1);
        }
    }
}
2.思路

2.被围绕的区域

1.答案1
package com.sunxiansheng.classic150.g1;

/**
 * Description: 130. 被围绕的区域
 *
 * @Author sun
 * @Create 2024/12/28 09:41
 * @Version 1.0
 */
public class t130 {

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 只要发现没有触及边界，就说明被包围了，将O变为X
                if (board[i][j] == 'O' && !dfs(board, i, j, new boolean[board.length][board[0].length])) {
                    dfs2(board, i, j);
                }
            }
        }
    }

    /**
     * 判断是否触及边界
     *
     * @param board
     * @param i
     * @param j
     * @return
     */
    public static boolean dfs(char[][] board, int i, int j, boolean[][] visited) {
        int m = board.length;
        int n = board[0].length;

        if (i < 0 || i >= m || j < 0 || j >= n) {
            // 如果能够越界，就返回true
            return true;
        } else if (board[i][j] == 'X' || visited[i][j]) {
            // 如果是x，或者已经访问过了，就返回false
            return false;
        } else {
            // 标记为已访问
            visited[i][j] = true;
            boolean top = dfs(board, i - 1, j, visited);
            boolean bottom = dfs(board, i + 1, j, visited);
            boolean left = dfs(board, i, j - 1, visited);
            boolean right = dfs(board, i, j + 1, visited);
            // 只要有一个为true，就说明该岛屿触及了边界
            return top || bottom || left || right;
        }
    }

    // 将O变为X
    public static void dfs2(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        // 如果是x，就返回
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 'X') {
            return;
        } else {
            board[i][j] = 'X';
            dfs2(board, i - 1, j);
            dfs2(board, i + 1, j);
            dfs2(board, i, j - 1);
            dfs2(board, i, j + 1);
        }
    }
}
2.思路1

就是先用dfs判断O是否触及了边界，如果没有触及边界，就将这块区域变为X，否则就不变，注意需要使用visited数组来记录状态，否则会栈溢出，但是这样效率不高

3.答案2
package com.sunxiansheng.classic150.g1;


/**
 * Description: 130. 被围绕的区域
 *
 * @Author sun
 * @Create 2024/12/28 09:41
 * @Version 1.0
 */
public class t130 {

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        // 直接遍历边界，将边界的岛屿变为'A'，表示不会被围绕
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                dfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                dfs(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                dfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                dfs(board, m - 1, j);
            }
        }
        // 再遍历一遍数组，将A变为O，将O变为X
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    // 将O变为A
    private void dfs(char[][] board, int i, int j) {
        int m = board.length;
        int n = board[0].length;
        // 如果越界，或者是X，或者是A就返回，防止栈溢出
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 'X' || board[i][j] == 'A') {
            return;
        } else {
            board[i][j] = 'A';
            dfs(board, i - 1, j);
            dfs(board, i + 1, j);
            dfs(board, i, j - 1);
            dfs(board, i, j + 1);
        }
    }
}
4.答案2

直接遍历边界，将边界的岛屿变为’A’，表示不会被围绕，再遍历一遍数组，将A变为O，将O变为X

回溯法

1.电话号码的字母组合

1.答案
package com.sunxiansheng.classic150.g1;

import java.util.*;

/**
 * Description: 17. 电话号码的字母组合
 *
 * @Author sun
 * @Create 2024/12/29 09:59
 * @Version 1.0
 */
public class t17 {

    // 静态初始化映射表
    private static final Map<Character, String> PHONE_MAP = new HashMap<>();

    static {
        PHONE_MAP.put('2', "abc");
        PHONE_MAP.put('3', "def");
        PHONE_MAP.put('4', "ghi");
        PHONE_MAP.put('5', "jkl");
        PHONE_MAP.put('6', "mno");
        PHONE_MAP.put('7', "pqrs");
        PHONE_MAP.put('8', "tuv");
        PHONE_MAP.put('9', "wxyz");
    }

    public List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return Collections.emptyList();
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < digits.length(); i++) {
            list.add(PHONE_MAP.get(digits.charAt(i)));
        }
        List<String> res = new ArrayList<>();
        backtrace(0, new StringBuilder(), res, list);
        return res;
    }

    public static void backtrace(int startIndex, StringBuilder path, List<String> res, List<String> list) {
        if (path.length() == list.size()) {
            // 记录结果
            res.add(path.toString());
            return;
        } else {
            // 获取数组
            char[] charArray = list.get(startIndex).toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                // 记录路径
                path.append(charArray[i]);
                // 循环传递状态
                backtrace(startIndex + 1, path, res, list);
                // 回溯
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}
2.思路

startIndex是数组下标，首先得到数组然后循环传递状态

2.组合

1.答案
package com.sunxiansheng.classic150.g1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Description: 77. 组合
 *
 * @Author sun
 * @Create 2024/12/29 09:32
 * @Version 1.0
 */
public class t77 {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrace(1, new LinkedList<>(), res, n, k);
        return res;
    }

    public static void backtrace(int startIndex, LinkedList<Integer> path, List<List<Integer>> res, int n, int k) {
        if (path.size() == k) {
            // 终止条件，记录结果
            res.add(new ArrayList<>(path));
            return;
        } else {
            // 参数，循环传递状态
            for (int i = startIndex; i <= n; i++) {
                // 将当前结果加入到path
                path.add(i);
                // 递归
                backtrace(i + 1, path, res, n, k);
                // 回溯
                path.removeLast();
            }
        }
    }
}
2.思路

startIndex，拿到，循环传递状态

3.全排列

1.答案
package com.sunxiansheng.classic150.g1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Description: 46. 全排列
 *
 * @Author sun
 * @Create 2024/12/29 10:24
 * @Version 1.0
 */
public class t46 {

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrace(0, new LinkedList<>(), res, nums);
        return res;
    }

    public static void backtrace(int startIndex, LinkedList<Integer> path, List<List<Integer>> res, int[] nums) {
        if (path.size() == nums.length) {
            // 记录结果
            res.add(new ArrayList<>(path));
            return;
        } else {
            for (int i = startIndex; i < nums.length; i++) {
                // 判断跟路径中的最后一个元素是否一样，如果一样就跳过
                if (!path.isEmpty() && path.contains(nums[i])) {
                    continue;
                }
                // 加入路径
                path.add(nums[i]);
                // 递归
                backtrace(startIndex, path, res, nums);
                // 回溯
                path.removeLast();
            }
        }
    }
}
2.思路

startIndex不变，增加剪枝操作，去除重复元素

4.组合总和

1.答案
package com.sunxiansheng.classic150.g1;

import java.nio.file.Path;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Description: 39. 组合总和
 *
 * @Author sun
 * @Create 2024/12/29 10:37
 * @Version 1.0
 */
public class t39 {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        backtrace(0, new LinkedList<>(), res, 0, candidates, target);
        return res;
    }

    public static void backtrace(int startIndex, LinkedList<Integer> path, List<List<Integer>> res, int sum, int[] candidates, int target) {
        if (sum > target) {
            // 超过了就直接返回
            return;
        } else if (sum == target) {
            // 符合要求就记录结果
            res.add(new ArrayList<>(path));
            return;
        } else {
            for (int i = startIndex; i < candidates.length; i++) {
                // 加入路径
                path.add(candidates[i]);
                // 递归
                backtrace(i, path, res, sum + candidates[i], candidates, target);
                // 回溯
                path.removeLast();
            }
        }
    }
}
2.思路

使用sum来记录和，当满足要求就记录结果

5.括号生成

1.答案
package com.sunxiansheng.classic150.g1;

import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;

/**
 * Description: 22. 括号生成
 *
 * @Author sun
 * @Create 2024/12/29 10:54
 * @Version 1.0
 */
public class t22 {

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrace(new StringBuilder(), res, 0, 0, n);
        return res;
    }
    
    public static void backtrace(StringBuilder path, List<String> res, int left, int right, int n) {
        if (path.length() == 2 * n) {
            // 记录结果
            res.add(path.toString());
            return;
        } else {
            // 加左括号的情况
            if (left < n) {
                // 加入路径
                path.append("(");
                // 递归
                backtrace(path, res, left + 1, right, n);
                // 回溯
                path.deleteCharAt(path.length() - 1);
            }
            // 加右括号的情况
            if (right < left) {
                // 加入路径
                path.append(")");
                // 递归
                backtrace(path, res, left, right + 1, n);
                // 回溯
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}
2.思路

就是一个二叉树加上回溯，主要判断加左右括号的情况即可

6.单词搜索

1.答案
package com.sunxiansheng.classic150.g1;

/**
 * Description: 79. 单词搜索
 *
 * @Author sun
 * @Create 2024/12/29 11:58
 * @Version 1.0
 */
public class t79 {

    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 每个元素都作为起点去搜索
                if (backtrace(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean backtrace(char[][] board, String word, int x, int y, int index) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || word.charAt(index) != board[x][y]) {
            // 如果越界，或者当前的元素不等于index指向的元素，就返回false
            return false;
        }
        // 到这里一定是当前单词满足要求了，如果长度够的话，就直接返回true
        if (index == word.length() - 1) {
            return true;
        } else {
            // 记录当前单词，方便回溯
            char cur = board[x][y];
            // 标记为已访问
            board[x][y] = '#';
            // 上下左右访问
            boolean found = backtrace(board, word, x + 1, y, index + 1)
                    || backtrace(board, word, x - 1, y, index + 1)
                    || backtrace(board, word, x, y + 1, index + 1)
                    || backtrace(board, word, x, y - 1, index + 1);
            // 回溯
            board[x][y] = cur;
            return found;
        }
    }
}
2.思路

dfs加上回溯


http://www.kler.cn/a/469917.html

相关文章：

  • LRU（1）
  • Python自学 - 函数初步(内置函数、模块函数、自定义函数)
  • R语言基础| 中级绘图
  • 查询Mysql中被锁住的表以及如何解锁
  • [paddle] 非线性拟合问题的训练
  • 通过爬虫方式实现视频号助手发布视频
  • websocket在各主流浏览器中默认的请求头是如何设置的？
  • SQL语言的语法糖
  • 【MySQL】表的基本操作
  • MYSql------视图
  • 基于transformer的目标检测：DETR
  • KAGGLE竞赛实战2-捷信金融违约预测竞赛-part1-数据探索及baseline建立
  • 结构型模式2.桥接模式
  • springboot配置线程池
  • 今日总结 2025-01-06
  • 软件工程大复习之（四）——面向对象与UML
  • win32汇编环境，在窗口程序中画五边形与六边形
  • Unity3D PBR光照计算公式推导详解
  • 土建施工员考试题库及答案
  • 社交新零售下开源 AI 智能名片 2+1 链动模式 S2B2C 商城小程序的促单策略研究
  • MR20强抗干扰一体式IO模块的革新力量
  • KACL：Knowledge-Adaptive Contrastive Learning for Recommendation
  • C++ 原子变量
  • Bash语言的函数实现
  • Spring Boot 项目离线环境手动构建指南
  • Android客制化------7.0设置壁纸存在的一些问题