- 浏览: 173216 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
Example 2:
nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
我们采用DFS+memory的方法,就是在DFS的同时,记录当前元素所能构成的最大长度,如果下次再访问到这个点的时候直接返回这个点在memory中的值就可以了。时间复杂度为O(m*n),空间复杂度也是O(m*n)。代码如下:
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
nums = [
[9,9,4],
[6,6,8],
[2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].
Example 2:
nums = [
[3,4,5],
[3,2,6],
[2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
我们采用DFS+memory的方法,就是在DFS的同时,记录当前元素所能构成的最大长度,如果下次再访问到这个点的时候直接返回这个点在memory中的值就可以了。时间复杂度为O(m*n),空间复杂度也是O(m*n)。代码如下:
public class Solution { public int longestIncreasingPath(int[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int[][] memory = new int[matrix.length][matrix[0].length]; int max = 1; for(int i = 0; i < matrix.length; i++) { for(int j = 0; j < matrix[0].length; j++) { max = Math.max(max, getLength(i, j, Integer.MIN_VALUE, memory, matrix)); } } return max; } public int getLength(int i, int j, int min, int[][] memory, int[][] matrix) { if(i < 0 || j < 0 || i == matrix.length || j == matrix[0].length || matrix[i][j] <= min) return 0; if(memory[i][j] != 0) return memory[i][j]; min = matrix[i][j]; int a = getLength(i - 1, j, min, memory, matrix) + 1; int b = getLength(i + 1, j, min, memory, matrix) + 1; int c = getLength(i, j + 1, min, memory, matrix) + 1; int d = getLength(i, j - 1, min, memory, matrix) + 1; memory[i][j] = Math.max(a, Math.max(b, Math.max(c, d))); return memory[i][j]; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 384Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 347There are n bulbs that are init ...
相关推荐
Estimating the Longest Increasing Subsequence in Nearly Optimal Time_在近似最优时间内估计最长增长子序列.pdf
LMS Longest Monotonically Increasing Sequence Algorithm
A multistage graph is a graph (1) G=(V,E) with V partitioned into K >= 2 disjoint subsets such that if (a,b) is in E, then a is in Vi , and b is in Vi+1 for some subsets in the partition; and (2) | ...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
java动态规划的最长公共子序列算法和最长递增子序列算法
2.2.2 最长递增子序列(Longest increasing subsequence) 2.2.3 Sequence alignment 2.2.4 最长相同子序列(Longest common subsequence) 2.3.5 Matrix-chain multiplication 2.3.6 树上的独立集 (Max ...
The game of chess is the longest-studied domain in the history of artificial intelligence. The strongest programs are based on a combination of sophisticated search techniques, A general reinforcement...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
a major change in the design specification that was not verified. To save on construction cost, the engineer in charge of the project increased the span of the bridge from 1600 to 1800 feet, turning ...
关于Longest Common Subsequences演算法
Kth Smallest Element in a BST 二叉树的递归 Minimum Depth of Binary Tree Maximum Depth of Binary Tree Path Sum Path Sum II Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum ...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
Longest Ordered Subsequence,算法分析与设计,C语言程序
Longest Common Ancestor classic ppt...
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划
He described it as 'a very agreeable situation located within two small hills in the midst of which flowed a great river.' Though Verrazano is by no means considered to be a great explorer, his name ...
The Complexity of Word Circuits.- On the Density of Regular and Context-Free Languages.- Extensions of the Minimum Cost Homomorphism Problem.- The Longest Almost-Increasing Subsequence.- Universal ...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...