Google算法题:矩阵中的最长上升路径

xiaoxiao2021-02-28  100

题目

题目来源:Link

分析

1、自底向上

(1)对原始数据排序成List (2)遍历List,从最小的 x 开始计算路径 (3)对于当前遍历的节点 x , 检查其四周的点,如果四周点大于自身且 x 路径长+1 大于四周点记录的当前记录的最大路径长,则更新其路径值及路径来源 (4)记录路径最大点位置 (5)根据最大点位置重构路径

2、备忘录的自顶向下

(1)遍历数组 (2)根据 flag[i][j] 如果 dp[i][j] 的值已经确定,则不用再计算,直接返回 dp[i][j] (3)如果dp[i][j] 的值没有确定,则递归下去继续求解子问题

代码

package com.graph; import java.util.*; import org.omg.CORBA.INTERNAL; public class Solution { int[][] nums; //方法二:自底向上 //TC=O(n*m) //动态规划,自底向上 public void solve_downUp(int[][] nums){ List<Integer> res = new ArrayList<Integer>(); //special cases if(nums==null || nums.length==0) return; this.nums = nums; //sort the nums List<Position> list = new ArrayList<Position>(); int n = nums.length; int m = nums[0].length; //TC=O(n*m) for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ list.add(new Position(nums[i][j], i, j)); } } Collections.sort(list, new Comparator<Position>(){ @Override public int compare(Position a, Position b){ if(a.val>b.val) return 1; else if(a.val<b.val) return -1; else return 0; } }); //build record = new Record[n][m]; maxp = new Position(list.get(0).val,list.get(0).x,list.get(0).y); max = 1; //init record //TC=O(n*m) for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { record[i][j] = new Record(); } } //TC=O(n*m) for(int k=0; k<m*n; k++){ Position tmp = list.get(k); int i; int j; //上 i = tmp.x-1; j = tmp.y; if(i>=0&&i<n && j>=0&&j<m) updateRecord(i,j,tmp); //下 i = tmp.x+1; j = tmp.y; if(i>=0&&i<n && j>=0&&j<m) updateRecord(i,j,tmp); //左 i = tmp.x; j = tmp.y-1; if(i>=0&&i<n && j>=0&&j<m) updateRecord(i,j,tmp); //右 i = tmp.x; j = tmp.y+1; if(i>=0&&i<n && j>=0&&j<m) updateRecord(i,j,tmp); } //recostruct the result Record re = record[maxp.x][maxp.y]; StringBuffer tt = new StringBuffer(); while(re.from!=null){ //System.out.print(nums[maxp.x][maxp.y]); tt.append(nums[maxp.x][maxp.y]); maxp = re.from; re = record[maxp.x][maxp.y]; } tt.append(nums[maxp.x][maxp.y]); System.out.print(tt.reverse().toString()); } Record[][] record; Position maxp; int max; public void updateRecord(int i, int j, Position tmp){ if(nums[i][j]>tmp.val){ int con = record[tmp.x][tmp.y].pn+1; if(con>record[i][j].pn){ record[i][j].pn = con; record[i][j].from = new Position(tmp.val,tmp.x,tmp.y); if(con>max){ max=con; maxp=new Position(nums[i][j],i,j); } } } } class Record{ public Position from=null; public int pn=1; } class Position{ public int val; public int x; public int y; public Position(int val, int x, int y){ this.val = val; this.x = x; this.y = y; } } //方法二:备忘录的自顶向下 int[][] dp; int[][] flag; int n,m; public void solve_upDown(int[][] nums) { if(nums==null || nums.length==0) return; this.nums = nums; n = nums.length; m = nums[0].length; dp = new int[n][m]; flag = new int[n][m]; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { dp[i][j] = search(i,j); } } } int[] dx = {-1,0,1,0}; int[] dy = {0,1,0,-1}; public int search(int i, int j) { int res=1; if(flag[i][j]!=0) { return dp[i][j]; } //检查四周 //int maxk=0; for(int k=0; k<4; k++) { int x = i+dx[k]; int y = j+dy[k]; if(i>=0&&i<n && j>=0&&j<m) { if(nums[i][j]>nums[x][y]) { res = Math.max(res, search(x, y)+1); } } } flag[i][j]=1; dp[i][j]=res; return res; } public static void main(String[] args) { Solution s = new Solution(); s.solve_downUp(new int[][] {{9,9,4},{6,6,8},{2,1,1}}); } }

转载请注明原文地址: https://www.6miu.com/read-52517.html

最新回复(0)