Day14_剑指Offer

本文主要是介绍Day14_剑指Offer，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

今天这两道题，真的不太懂，基础知识不太牢固，得去补补了，尽力理解，实在理解不下来，背，背，我都要背下来，加油~~

package com.sorrymaker.day3814;

import org.junit.Test;

/**
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
 * 也不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。
 * 但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 * @Author nextGame
 * @Date 2021/8/25 21:18
 * @Version 1.0
 */
public class MovingCount {



    // 棋盘的行列
    int m, n;
    // 记录位置是否被遍历过
    boolean[][] visited;

    @Test
    public void test(){
        System.out.println(movingCount(3, 3, 2));
    }

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        visited = new boolean[m][n];
        return dfs(0, 0, k);
    }

    private int dfs(int i, int j, int k) {
        // i >= m || j >= n是边界条件的判断
        if (i >= m || j >= n

                // visited[i][j]判断这个格子是否被访问过
                || visited[i][j] == true

                // k < sum(i, j)判断当前格子坐标是否满足条件
                || k < sum(i, j)) {
            //当数组越界，或者被访问过，或者是不满住sum(i,j)的条件的话， 就返回0，不计入可达解总数中。
            return 0;
        }
        // 标注这个格子被访问过
        visited[i][j] = true;
        // 沿着当前格子的右边和下边继续访问
        //返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。
        return 1 + dfs(i + 1, j, k) + dfs(i, j + 1, k);
    }

    // 计算两个坐标数字的和
    private int sum(int i, int j) {
        int sum = 0;
        while (i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while (j != 0) {
            sum += j % 10;
            j /= 10;
        }
        return sum;
    }
}

package com.sorrymaker.day3814;

/**
 * 矩阵中的路径
 *  DFS + 剪枝 ， 真看不懂，要慢慢消化。。。
 * @Author nextGame
 * @Date 2021/8/25 20:50
 * @Version 1.0
 */
public class ExistsWords {

    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        //一个一个字母来尝试，每一次尝试都是dfs遍历成功的一种可能性
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0)) {
                    return true;
                }
            }
        }
        //遍历完成，仍没有成功的路径，返回False
        return false;
    }
    // board：网格, i：当前行, j：当前列, word：待匹配字符串, k：当前匹配到字符串word的位置
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        // 用来判断程序是否越界，还有第一个字母是否匹配，第一个都不匹配直接返回False

        // 1. 下标越界，2. 当前位置与word中字符不匹配，则可以直接返回（剪枝）
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) {
            return false;
        }
        //当程序跑到word的最后一个字母时，这时无需再dfs，直接返回True
        //说明word中的字符全部被匹配
        if(k == word.length - 1) {
            return true;
        }
        //把访问过的字母标记为空，这样可以避免程序多次访问同一元素
        // 使用board数组充当了访问标记数组，节省了空间（非常妙！）???
        board[i][j] = '\0';
        //剪枝顺序：左、右、下、上
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        //一趟dfs结束后把原来设的空改回来，以免影响后面的dfs遍历使用
        board[i][j] = word[k];
        return res;
    }
}

这篇关于Day14_剑指Offer的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！