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;
    }
}
上一篇:艺卓CG2700X / S显示器评测


下一篇:Aurora HDR 2019 for Mac 1.0.1 高级 HDR 软件。