给定一个n*m矩阵,找出最长上升序列

题目:给定一个n*m 矩阵,找出矩阵中最长的上升子序列。这种题的解决方案都是回溯法,使用双重for循环加递归。双重 for 循环就是从矩阵第一个元素开始遍历,然后递归的对第一个元素进行条件判断。都是套路。这种题的难点是怎么优化空间复杂度和时间复杂度。一般都主要是优化空间复杂度。能优化到 O(1)或者 O(max(n,m))。

下面给出两种解法:

  • 第一种是回溯法
  • 第二种是 动态规划

第二种方法主要是用了一个额外数组进行保存每一个起始位置的最大上升子序列。避免了重复计算一些子问题

据说这是头条的面试题,难度一般。有事没事敲一道题舒服一下。^_^

回溯法
下面给出自己写的 时间复杂度和空间复杂度 O(n*m)的解决方案

package com.wxy.toutiao;

/**
 * Created by Kode on 2019/1/18.
 */
public class 最长上升子序列 {
    public static void main(String[] args){
       /* int[][] input = new int[][]{
                {1,2,3,4,5},
                {16,17,24,23,6},
                {15,18,25,22,7},
                {14,19,20,21,8},
                {13,12,11,10,9}
        };*/
        int[][] input = new int[][]{
                {1,3,5,7,9},
                {16,17,24,23,6}
        };
        int row = input.length;
        int col = input[0].length;
        boolean[][] visit = new boolean[row][col];
        int max = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                count = getMaxAscendSeq(i, j, input, visit);
                max = max > count ? max : count;
            }
        }
        System.out.println(max);
    }

    private static int getMaxAscendSeq(int i, int j, int[][] input, boolean[][] visit) {
        if (i >= input.length || i < 0 || j >= input[i].length || j < 0) {
            return 0;
        }
        int count = 1;
        visit[i][j] = true;
        int tmp = 0;
        if (i-1 >= 0 && !visit[i - 1][j] && input[i - 1][j] > input[i][j]) {

            count = getMaxAscendSeq(i - 1, j, input, visit) + 1;
        }
        if (i + 1 <= input.length - 1 && !visit[i + 1][j] && input[i + 1][j] > input[i][j]) {
            tmp =  getMaxAscendSeq(i + 1, j, input, visit) + 1;
            count = count > tmp ? count : tmp;
        }
        if (j-1 >= 0 &&!visit[i ][j - 1] && input[i ][j - 1] > input[i][j]) {
            tmp = getMaxAscendSeq(i , j - 1, input, visit) + 1;
            count = count > tmp ? count : tmp;
        }
        if (j + 1 <= input[i].length - 1 && !visit[i ][j + 1] && input[i ][j + 1] > input[i][j]) {
            tmp = getMaxAscendSeq(i , j + 1, input, visit) + 1;
            count = count > tmp ? count : tmp;
        }
        visit[i][j] = false;
        return count;
    }
}

动态规划法

package com.wxy.toutiao;

/**
 * Created by chengdu_brother on 2019/1/19.
 */
public class FindMaxLengthSeqInMatrix {
    public static void main(String[] args){
        /*int[][] input = new int[][]{
                {1,2,3,4,5},
                {16,17,24,23,6},
                {15,18,25,22,7},
                {14,19,20,21,8},
                {13,12,11,10,9}
        };*/
        int[][] input = new int[][]{
                {1,3,5,7,9},
                {16,17,24,23,6}
        };
        int res = new FindMaxLengthSeqInMatrix().maxSeq(input);
        System.out.println(res);
    }
    public int maxSeq(int[][] data) {
        if (data == null) return -1;
        int row = data.length;
        int col = data[0].length;
        int[][] length = new int[row][col];
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                visited[i][j] = false;
                length[i][j] = 0;
            }
        }
        length[0][0] = 1;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                getMaxLength(data, length, visited, i, j);
            }
        }
        int maxLength = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(length[i][j] + ", ");
                if (length[i][j] > maxLength) {
                    maxLength = length[i][j];
                }
            }
            System.out.println();
        }
        return maxLength;
    }

    private int getMaxLength(int[][] data, int[][] length, boolean[][] visited, int i, int j) {
        if (visited[i][j] == true) return 0;
        visited[i][j] = true;
        int row = data.length;
        int col = data[0].length;
        int maxLength = 1;
        //go left
        if (j > 0 && data[i][j] < data[i][j - 1]) {
            if (visited[i][j - 1] == false) {
                maxLength = Math.max(maxLength, getMaxLength(data, length, visited, i, j - 1) + 1);
            } else {
                maxLength = Math.max(maxLength, length[i][j - 1] + 1);
            }
        }
        //go up
        if (i > 0 && data[i][j] < data[i - 1][j]) {
            if (visited[i - 1][j] == false) {
                maxLength = Math.max(maxLength, getMaxLength(data, length, visited, i - 1, j) + 1);
            } else {
                maxLength = Math.max(maxLength, length[i - 1][j] + 1);
            }
        }
        //go right
        if (j < col - 1 && data[i][j] < data[i][j + 1]) {
            if (visited[i][j + 1] == false) {
                maxLength = Math.max(maxLength, getMaxLength(data, length, visited, i, j + 1) + 1);
            } else {
                maxLength = Math.max(maxLength, length[i][j + 1] + 1);
            }
        }
        //go left
        if (i < row - 1 && data[i][j] < data[i+1][j]) {
            if (visited[i + 1][j] == false) {
                maxLength = Math.max(maxLength, getMaxLength(data, length, visited, i + 1, j) + 1);
            } else {
                maxLength = Math.max(maxLength, length[i + 1][j] + 1);
            }
        }
        length[i][j] = maxLength;
        return maxLength;
    }
}

发表评论

电子邮件地址不会被公开。

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部