矩阵中的路径

题目描述

思路

深度优先搜索

朝一个方向搜索，不行的话就回溯到上一个节点往其他方向搜索

代码实现

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words=word.toCharArray();
        boolean result=false;
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                result=result || rs(board,words,i,j,0);                    
            }
        }
        return result;
    }
    public boolean rs(char [][]board,char [] words,int i,int j,int num){
        if(i<0||j<0||i>=board.length||j>=board[0].length||board[i][j]!=words[num])return false;
        if(num>=words.length-1)return true;
        //要学习这种标记方式
        board[i][j]='\0';
        boolean result = rs(board,words,i+1,j,num+1)||rs(board,words,i,j+1,num+1)||rs(board,words,i-1,j,num+1)|rs(board,words,i,j-1,num+1);
        board[i][j]=words[num];
        return result;

    }
}

复杂度分析

时间复杂度

O(3^K(MN))，3k来源于搜索深度为k，每次有3个搜索方向，深度优先搜索的时间复杂度就是如此分析

空间复杂度

O(K)

反思不足

思路

学习标记元素的方式

机器人的运动范围

题目描述

思路

本题要积累一些知识点

两位数的取余，每次只加1的情况下的渐变与突变

以及突变为减导致的仅需遍历等腰三角，即向右和向下搜索

要考虑等腰三角的重复

DFS

优先深度

BFS

利用队列实现，可用数组作为队列中的元素用以封装有关数据

代码实现

DFS

class Solution {
    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m; this.n = n; this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj) {
        if(i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
    }
}

BFS

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        Queue<int[]> queue= new LinkedList<int[]>();
        queue.add(new int[] { 0, 0, 0, 0 });
        while(queue.size() > 0) {
            int[] x = queue.poll();
            int i = x[0], j = x[1], si = x[2], sj = x[3];
            if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
            visited[i][j] = true;
            res ++;
            queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
            queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
        }
        return res;
    }
}

复杂度分析

时间复杂度

DFS

O(MN)

BFS

O(MN)

空间复杂度

DFS

O(MN)

BFS

O(MN)

反思不足

思路

用暴力的深度优先搜索也确实是做出来了，但是不知道各种规律，所以想不到巧的方法

BFS通常就是借助队列辅助实现的，无需怀疑

java se

新创建的整型数组内部元素初始全为0

递归调用函数对变量的修改如果不在返回上一层时赋给它会复原