leetcode做题记录 —— longest-increasing-subsequence

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example, 
Given [10, 9, 2, 5, 3, 7, 101, 18], 
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Longest Increasing Subsequence 
题目大意是， 给予一个无序的数组 ，找出该数组的最长增长子序列（注意是子序列，不是字串，子序列不需要连续）的长度。 
如数组 [10, 9, 2, 5, 3, 7, 101, 18]的最长增长子序列为[2, 3, 7, 101]，所以该数组的最长子序列的长度为 4 。 
要求时间复杂度为 

解法一 

对原有数组进行排序去重，得到排序后的数组后，求排序后数组和原数组的最长子序列 
如数组 
[10, 9, 2, 5, 3, 7, 101, 18] 
排序后 
[2, 3, 5, 7, 9, 10, 18, 101] 
得到最长公共子序列为 
[2, 3, 7, 101] 
这个最长公共子序列即为最长增长子序列了

一定要去重，不然的话得到的最长公共子序列可能不是最长增长子序列了 
比如数组 
[10, 9, 2, 5, 5, 3, 7, 101, 18] 
排序后 
[2, 3, 5, 5, 7, 9, 10, 18, 101] 
得到最长公共子序列为 
[2, 5, 5, 7, 101] 
这个最长公共子序列明显不符合最长增长子序列的定义

而数组 
[10, 9, 2, 5, 5, 3, 7, 101, 18] 
排序去重后 
[2, 3, 5, 7, 9, 10, 18, 101] 
得到最长公共子序列为 
[2, 3, 7, 101] 
即为最长增长子序列

1.//Javascript
2.var lengthOfLCS = function(nums1, nums2) {
3.    let w = nums1.length + 1;
4.    let h = nums2.length + 1;
5.
6.    //由于只需要求长度，不需要还原整个序列，
7.    //而计算只需要前一行的数据，所以不需要w * h的矩阵 
8.    let matrix = new Array(w * 2).fill(0);
9.    for( let y = 1; y < h; y++ )
10.    {
11.        let ay = y % 2;
12.        let ty = (y - 1) % 2;
13.        for( let x = 1; x < w; x++ )
14.        {
15.            let lx = (x - 1);
16.            let index = ay * w + x;
17.            let leftTop = ty * w + lx;
18.            let leftCenter = ay * w + lx;
19.            let topCenter = ty * w + x;
20.            if( nums1[x - 1] === nums2[y - 1] )
21.            {
22.                matrix[index] = matrix[leftTop] + 1;
23.            }
24.            else if( matrix[topCenter] >= matrix[leftCenter] )
25.            {
26.                matrix[index] = matrix[topCenter];
27.            }
28.            else
29.            {
30.                matrix[index] = matrix[leftCenter];
31.            }
32.        }
33.    }
34.    return matrix[(((h + 1) % 2) * w + w) - 1];
35.};
36.
37.var lengthOfLIS = function(nums) {
38.    return lengthOfLCS(nums, [...new Set(nums)].sort((a, b)=>a - b));
39.};

解法二

开辟一个额外的数组比如dp，每次遍历到a[i]的时候，找到dp数组中第一个比a[i]大的元素，并用a[i]替换，如果dp中没有比a[i]大的元素，直接添加到dp末尾。最后dp的长度即为最长递增子序列的长度。 
比如 
[1, 3, 7, 2, 4, 9, 8, 5] 
每轮循环后dp的值

1.dp = [1] //a[i] = 1
2.dp = [1, 3] //a[i] = 3
3.dp = [1, 3, 7] //a[i] = 7
4.dp = [1, 2, 7] //a[i] = 2
5.dp = [1, 4, 7] //a[i] = 4
6.dp = [1, 4, 7, 9] //a[i] = 9
7.dp = [1, 4, 7, 8] //a[i] = 8
8.dp = [1, 4, 5, 8] //a[i] = 5

得到的序列并不是最小递增子序列，不过这不影响长度是正确的，因为每次dp的长度扩展，a[i]的值必然比dp里的所有值都大，也就是 i 之前必然有 dp.length 个元素比a[i] 小。 
这样处理的dp必然是有序的，所以可以用二分来查找dp数组中第一个比a[i]大的元素，从而得到的复杂度。

1.//Javascript
2.var lengthOfLIS = function(nums) {
3.    let dp = [];
4.    for( let i = 0; i < nums.length; i++ )
5.    {
6.        let num = nums[i];
7.        let left = 0;
8.        let right = dp.length - 1;
9.        while( left <= right )
10.        {
11.            let mid = (left + right) >> 1;
12.            if( dp[mid] < num )
13.            {
14.                left = mid + 1;
15.            }
16.            else
17.            {
18.                right = mid - 1;
19.            }
20.        }
21.        dp[left] = num;
22.    }
23.    return dp.length;
24.};

End