資訊專欄INFORMATION COLUMN
摘要：題目鏈接主要兩種方法和用，就是每次找出為結(jié)尾的最長(zhǎng)的串的長(zhǎng)度就好了。所以分解成就是，這個(gè)復(fù)雜度是。用一個(gè)數(shù)組，表示的長(zhǎng)度為，表示長(zhǎng)度為的，最右邊的可能的最小值。這里只要求長(zhǎng)度即可，那就直接用就可以了，整個(gè)用個(gè)數(shù)組就行了。
Longest Increasing Subsequence
題目鏈接：https://leetcode.com/problems...
主要兩種方法：dp和greedy
dp：用dp table，就是每次找出nums[i]為結(jié)尾的最長(zhǎng)的increasing串的長(zhǎng)度就好了。所以分解成subproblem就是: dp[i] = max(dp[j]) + 1，這個(gè)復(fù)雜度是O(N^2)。
然后就是greedy + binary search的方法，改進(jìn)NlogN。用一個(gè)數(shù)組min[i]，i表示increasing sequence的長(zhǎng)度為i，min[i]表示長(zhǎng)度為i的increasing sequence，最右邊的num可能的最小值。整個(gè)是patient sort的思路。
http://www.cs.princeton.edu/c...
stack的top元素按從小到大的順序所以可以binary search。如果允許重復(fù)且重復(fù)的算在increasing sequence里面，那么重復(fù)的element就加到比它大的那個(gè)top下面就好了。如果重復(fù)的不算的話，就每次找>=的地方，查一下是否是重復(fù)，是就不加，不是就往里面加。
如果求路徑就加個(gè)parent point的輔助數(shù)組。這里只要求長(zhǎng)度即可，那就直接用top（min）就可以了，整個(gè)用個(gè)數(shù)組就行了。
public class Solution {
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0) return 0;
/* greedy + binary search
* min[i]: minimum rightmost element in increasing sequence with length = i + 1
*/
int[] min = new int[nums.length+1];
min[0] = nums[0];
int index = 0;
for(int i = 1; i < nums.length; i++) {
// new one >= rightmost one, increase the length of sequence
if(nums[i] > min[index]) {
min[++index] = nums[i];
}
// new one < leftmost, update the leftmost
else if(nums[i] <= min[0]) {
min[0] = nums[i];
}
// new one between [0, index + 1], find the place k that
// min[k-1] < nums[i] <= min[k], update min[k]
else {
int k = binarySearch(min, nums[i], 0, index);
min[k] = nums[i];
}
}
return index + 1;
}
private int binarySearch(int[] min, int x, int l, int r) {
while(l + 1 < r) {
int mid = l + (r - l) / 2;
if(min[mid] >= x) r = mid;
else l = mid;
}
if(min[l] >= x) return l;
return r;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66601.html
Problem Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. Clarification Whats the definition of longest increasing subsequence?...
摘要：解題思路求不必連續(xù)的最長(zhǎng)升序字符串長(zhǎng)度，采用動(dòng)態(tài)規(guī)劃，利用狀態(tài)表示以字符結(jié)尾的最長(zhǎng)子串的長(zhǎng)度，那么狀態(tài)轉(zhuǎn)移方程就是且必須小于另外還需維護(hù)一個(gè)最大長(zhǎng)度。 Longest Increasing SubsequenceGiven an unsorted array of integers, find the length of longest increasing subsequence. ...
Problem Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18]Output: 4 Explanation: The longest increasing subsequence is [2,3,7...
摘要：對(duì)于一個(gè)遞增子序列，想要增加它的長(zhǎng)度，就必須在尾部添加一個(gè)更大的值。表示以結(jié)尾的最長(zhǎng)遞增序列的長(zhǎng)度。長(zhǎng)度增加的條件就是一個(gè)數(shù)字比大。長(zhǎng)度最大值即為輸入數(shù)組的長(zhǎng)度。 Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10,...
摘要：再用二分法找當(dāng)前值應(yīng)該在排好序的數(shù)組中的插入位置。因?yàn)橐业氖亲铋L(zhǎng)的序列，所以每次將排好序的數(shù)組中替換成已經(jīng)排好序的，會(huì)能保證得到的結(jié)果是最長(zhǎng)的。保證升序相等也要替換這個(gè)值 LeetCode[300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longe...
閱讀 1123·2021-09-22 16:04
閱讀 1502·2019-08-30 15:43
閱讀 1110·2019-08-29 14:01
閱讀 3446·2019-08-26 12:19
閱讀 3361·2019-08-26 12:15
閱讀 1454·2019-08-26 12:13
閱讀 3273·2019-08-23 17:00
閱讀 1491·2019-08-23 15:38
