10-31 LeetCode 491. Increasing Subsequences
Description
Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .
Example:
Input:
[4, 6, 7, 7]
Output:
[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
Note:
The length of the given array will not exceed 15.
The range of integer in the given array is [-100,100].
The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.
提供一個(gè)整數(shù)數(shù)組，你的任務(wù)是找到所有不同的升序子序列玉吁，升序子序列的大小至少為2.
注意：
數(shù)組長(zhǎng)度不會(huì)超過(guò)15
數(shù)組元素的值在-100到100之間
數(shù)組中可能有重復(fù)的值腺劣，并且兩個(gè)相等的整數(shù)也應(yīng)該算作一個(gè)特殊的升序序列
Solution 1:
這題我用的遞歸去解決。現(xiàn)在我自己寫(xiě)遞歸有點(diǎn)困惑壳澳，一個(gè)模模糊糊的想法告訴我就是那樣寫(xiě)，但是不能夠很清晰的理解為什么是這么寫(xiě)惠窄×吕保可能是跟我的算法不明確有關(guān)系吧懦窘，也可能是表達(dá)能力不夠前翎。
遞歸時(shí)傳給遞歸函數(shù)一個(gè)index值，記錄需要去遍歷的數(shù)組的首地址畅涂，然后比較這個(gè)值與升序子序列的最后一個(gè)值得大小關(guān)系港华，大于則加入，進(jìn)入下一個(gè)遞歸調(diào)用午衰，否則index加一后重復(fù)上述過(guò)程立宜。
這題第一次提交時(shí)有個(gè)錯(cuò)誤，是我對(duì)Python語(yǔ)法不熟悉造成的臊岸，升序子序列不能重復(fù)橙数，很自然而然的就想到了用set這個(gè)內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，但是set里的元素不能是list,于是網(wǎng)上搜索了一下如何二維數(shù)組去重帅戒，代碼里很清晰的展示了這一步驟灯帮。
代碼：
class Solution(object):
def findSubsequences(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
self.find(result, nums, [], 0)
result = list(set(tuple(t) for t in result))
return [lists for lists in result]
def find(self, result_set, nums, lists, index):
if len(lists) >= 2:
result_set.append(lists)
for i in range(index, len(nums)):
if not lists:
self.find(result_set, nums, [nums[i]], i+1)
else:
if nums[i] >= lists[-1]:
self.find(result_set, nums, lists+[nums[i]], i+1)
Solution2:
提交之后，我又花了點(diǎn)時(shí)間看了一下別人的算法蜘澜，有不少人用遞歸施流，但是還有用動(dòng)態(tài)規(guī)劃的。動(dòng)態(tài)規(guī)劃的念頭在我腦海中出現(xiàn)過(guò)鄙信，但是第一時(shí)間想不到狀態(tài)轉(zhuǎn)移方程瞪醋，沒(méi)有去深思∽肮睿看了下別人的代碼银受，發(fā)覺(jué)還是挺簡(jiǎn)單的。代碼我就不貼出來(lái)了鸦采，因?yàn)闆](méi)有自己去實(shí)現(xiàn)宾巍。我介紹下大概的思路。
首先考慮一個(gè)元素的子序列渔伯，那毫無(wú)疑問(wèn)全是升序顶霞，將這些子序列添加到result數(shù)組中，然后在一個(gè)元素的序列的基礎(chǔ)上考慮兩個(gè)元素的升序子序列锣吼，也添加到result數(shù)組中选浑，從而考慮三個(gè)的，四個(gè)的………………
最后返回結(jié)果時(shí)去除result中長(zhǎng)度小于2的元素,以及去重操作玄叠。
for num in nums:
for array in result:
if num >= array[-1]:
result.append(array+[num])
result.append(num)
感想
今天是10月的最后一天了古徒，時(shí)間過(guò)得真快啊。但是我這個(gè)月也沒(méi)有刷多少題读恃，在網(wǎng)上查找其他解題思路時(shí)隧膘，發(fā)現(xiàn)有很多人都分享自己的刷題過(guò)程代态。跟他們相比，我就是個(gè)渣渣= = 疹吃。
