Longest Increasing Path in a Matrix

ralap 发布于2019-08-14 17:20 / 1301人阅读

摘要：题目链接记忆化搜索，用一个二维记录找到的最长路径的长度，如果发现证明这个点被找过，不用重复。和这题一个思路。

Longest Increasing Path in a Matrix

题目链接：https://leetcode.com/problems...

dfs + 记忆化搜索，用一个二维dp记录找到的最长路径的长度，如果发现dpi != 0,证明这个点被找过，不用重复。Number of Islands和这题一个思路。

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        // dp[i][j] the longest increasing len from (i, j)
        // enumerate all start position
        // dfs find the longest path, if not in dp[i][j]
        dp = new int[matrix.length][matrix[0].length];
        int global = 0;
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if(dp[i][j] == 0) {
                    dp[i][j] = dfs(matrix, i, j);
                }
                global = Math.max(global, dp[i][j]);
            }
        }
        return global;
    }
    int[][] dp;
    int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int dfs(int[][] matrix, int x, int y) {
        if(dp[x][y] != 0) return dp[x][y];
        int len = 1;
        for(int i = 0; i < dir.length; i++) {
            int nx = x + dir[i][0], ny = y + dir[i][1];
            if(nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length) {
                if(matrix[nx][ny] > matrix[x][y]) len = Math.max(len, dfs(matrix, nx, ny) + 1);
            }
        }
        dp[x][y] = len;
        return len;
    }
}

云服务器 GPU云服务器 Increasing Longest Matrix modelview matrix

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66571.html

leetcode 329. Longest Increasing Path in a Matrix

摘要：题目要求思路和代码这里采用广度优先算法加上缓存的方式来实现。我们可以看到，以一个节点作为开始构成的最长路径长度是确定的。因此我们可以充分利用之前得到的结论来减少重复遍历的次数。题目要求 Given an integer matrix, find the length of the longest increasing path. From each cell, you can ei...

heartFollower 2019-08-16 11:09 评论0 收藏0
329. Longest Increasing Path in a Matrix

摘要：题目解答最重要的是用保存每个扫过结点的最大路径。我开始做的时候，用全局变量记录的没有返回值，这样很容易出错，因为任何一个用到的环节都有可能改变值，所以还是在函数中定义，把当前的直接返回计算不容易出错。题目：Given an integer matrix, find the length of the longest increasing path. From each cell, y...

hqman 2019-08-14 14:17 评论0 收藏0
[LeetCode] 329. Longest Increasing Path in a Matri

Problem Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move ou...

hss01248 2019-08-16 13:25 评论0 收藏0
[LeetCode] 329. Longest Increasing Path in a Matri

Problem Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move ou...

antz 2019-08-06 12:26 评论0 收藏0
LeetCode 329. Longest Increasing Path in a Matrix

摘要：思路这道题主要使用记忆化递归和深度优先遍历。我们以给定的矩阵的每一个位置为起点，进行深度优先遍历。我们存储每个位置深度优先遍历的结果，当下一次走到这个位置的时候，我们直接返回当前位置记录的值，这样可以减少遍历的次数，加快执行速度。 Description Given an integer matrix, find the length of the longest increasing...

isLishude 2019-07-31 10:08 评论0 收藏0