Commit6eb479c

committed

longest_increasing_subsequence

1 parent7baa429 commit6eb479cCopy full SHA for 6eb479c

File tree

+58

-0

lines changed

+58

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -215,6 +215,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t`
`215`	`215`	`####[295. Find Median from Data Stream](https://github.com/hitzzc/go-leetcode/tree/master/find_median_from_data_stream)`
`216`	`216`	`####[297. Serialize and Deserialize Binary Tree](https://github.com/hitzzc/go-leetcode/tree/master/serialize_and_deserialize_binary_tree)`
`217`	`217`	`####[299. Bulls and Cows](https://github.com/hitzzc/go-leetcode/tree/master/bulls_and_cows)`
	`218`	`+####[300. Longest Increasing Subsequence](https://github.com/hitzzc/go-leetcode/tree/master/longest_increasing_subsequence)`
`218`	`219`
`219`	`220`
`220`	`221`

Lines changed: 57 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,57 @@`
	`1`	`+#include<vector>`
	`2`	`+usingnamespacestd;`
	`3`	`+`
	`4`	`+classSolution {`
	`5`	`+public:`
	`6`	`+intlengthOfLIS(vector<int>& nums) {`
	`7`	`+if (nums.size() ==0)return0;`
	`8`	`+int max =1;`
	`9`	`+ vector<int>fn(nums.size(),0);`
	`10`	`+ fn[0] =1;`
	`11`	`+for (int i =0; i < nums.size(); ++i) {`
	`12`	`+for (int j =0; j < i; ++j) {`
	`13`	`+if (nums[i] > nums[j] && fn[j]+1 > fn[i])`
	`14`	`+ fn[i] = fn[j]+1;`
	`15`	`+ }`
	`16`	`+if (fn[i] > max) max = fn[i];`
	`17`	`+ }`
	`18`	`+return fn.back();`
	`19`	`+ }`
	`20`	`+`
	`21`	`+intlengthOfLIS2(vector<int>& nums) {`
	`22`	`+if (nums.size() <2)return nums.size();`
	`23`	`+ vector<int>vec(1, nums[0]);`
	`24`	`+for (int i =1; i < nums.size(); ++i) {`
	`25`	`+if (nums[i] > vec.back()) {`
	`26`	`+ vec.push_back(nums[i]);`
	`27`	`+continue;`
	`28`	`+ }elseif (nums[i] == vec.back()) {`
	`29`	`+continue;`
	`30`	`+ }else{`
	`31`	`+int pos =binary_search(vec, nums[i]);`
	`32`	`+ vec[pos] = nums[i];`
	`33`	`+ }`
	`34`	`+ }`
	`35`	`+return vec.size();`
	`36`	`+ }`
	`37`	`+`
	`38`	`+intbinary_search(vector<int>& nums,int target) {`
	`39`	`+int start =0;`
	`40`	`+int end = nums.size();`
	`41`	`+int idx = -1;`
	`42`	`+int mid;`
	`43`	`+while (start < end) {`
	`44`	`+ mid = start + (end-start)/2;`
	`45`	`+if (nums[mid] == target) {`
	`46`	`+return mid;`
	`47`	`+ }elseif (nums[mid] < target) {`
	`48`	`+ idx = mid+1;`
	`49`	`+ start = mid+1;`
	`50`	`+ }else{`
	`51`	`+ idx = mid;`
	`52`	`+ end = mid;`
	`53`	`+ }`
	`54`	`+}`
	`55`	`+return idx;`
	`56`	`+}`
	`57`	`+};`

Comments

(0)