Blog

leetcode300最长上升子序列

leetcode300 Longest Increasing Subsequence

Posted by BY on January 25, 2019

前言

新的一年，好好学习

正文

问题来源

本问题来自leetcode上的300题。

问题描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例 1:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

分析：

思路1：使用动态规划。 状态的定义：以 num[i] 结尾的最长上升子序列的长度。 状态转移方程：之前的数中比 num[i] 小的最长上升子序列的长度 + 1。

func lengthOfLIS(nums []int) int {
    l := len(nums)
    if 0 == l {
        return 0
    }
    dp := make([]int, l)
    dp[0] = 1 
    max := 1//避免l为1的情况
    for i := 1; i < l; i++ {
        temp := nums[i]
        //dp[i] = 1
        maxTemp := 0
        for j := i-1; j>=0; j-- {
            if (nums[j] < temp) && (maxTemp < dp[j]) {
                maxTemp = dp[j] 
            }
        }
        dp[i] = maxTemp + 1
        if dp[i] > max {
            max = dp[i]
        }
    }
    //fmt.Println(dp)
    return max
}

思路2：使用贪心选择 + 二分查找算法。
贪心思路：一个更小的数a，后面接上一个随机数，比a大的可能性更大。
定义一个数组tail存放已有的最长上升子序列，当存在相同长短多个子序列时，数组中存放的是个元素最小的那一个子序列。
注意：这个数组虽然是一个升序数组，但是这个数组并不是时刻表示那个“最长上升子序列”。仅在数组尾部增加元素的时候，才表示当前得到的“最长上升子序列”。

假设输入数组nums为3 5 6 2 5 4 5 19 5 6 7 12

当前执行到的元素 数组中的元素
3 3
5 3 5
6 3 5 6
2 2 5 6
5 2 5 6
4 2 4 6
5 2 4 5
19 2 4 5 19
5 2 4 5 19
6 2 4 5 6
7 2 4 5 6 7
12 2 4 5 6 7 12 
func lengthOfLIS(nums []int) int {
    lens := len(nums)
    arr := make([]int, 0)
    for i := 0; i < lens; i++ {
        pos := find(arr, nums[i])
        if pos == - 1 {
            arr = append(arr, nums[i])
        } else {
            arr[pos] = nums[i]
        }
    }
    return len(arr)
}

func find(arr []int, x int) int {
    lens := len(arr)
    if lens == 0 {
        return -1
    }
    start := 0
    end := lens - 1
    mid := (start + end) / 2
    for start <= end {
        if arr[mid] > x {
            if mid == 0 {
                return mid
            }
            end = mid - 1
        } else if arr[mid] < x {
            if mid == lens - 1 {
                return -1
            }
            start = mid + 1
        } else {
            return mid
        }
        mid = (start + end) / 2
    }
    if arr[mid] < x {
        if mid == lens - 1 {
            return -1
        } else {
            return mid + 1
        }
    }
    return mid
}

时间复杂度为n * log(n)

总结：

勤思考。

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog