今天去面試又被電了
可悲如我，實力差找不到好工作，只好回來寫個leetcode
結果又被這題電了...
看來會被電的到哪都會被電啊=ˇ=
好吧那來看題目吧
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,101], therefore the length is4.
那就... 直接解吧XD
Sol：
先說結論，我完全不知道怎麼辦，最後是直接去看答案了
不過講道理應該是要有點頭緒才對，所以我先來記錄一下我大概的想法
首先第一個想到的是把所有可能都找出來
...話是這麼說，不過要我找出全部的可能，我也不太知道怎麼找
再來想到要用Dynammic Programming的方式做，但也不知從何下手...
看完答案就證明一件事情，就是我都只學半套的
這兩種做法都是可行的，我們就來看看吧
首先是brute force的方法：
int lengthOfLIS(vector<int>& nums) {
return helper(nums, INT_MIN, 0);
}
int helper(vector<int>& nums, int prev, int curpos)
{
if (curpos == nums.size())
return 0;
int len_taken = 0;
if (nums[curpos] > prev)
{
len_taken = 1 + helper(nums, nums[curpos], curpos+1); // 如果有包含現在這個數值，那麼就把回傳的值加1，並更改prev的值，計算後面的結果
}
int len_nottaken = helper(nums, prev, curpos+1); // 不管有沒有包含現在的值，後面計算的結果還是要算
return max(len_taken, len_nottaken);
}
總之就是檢查這個數值是不是要被納入這次的計算當中，要的話就加1然後算接下來的
然後如果不納入的話... 還是要算接下來的啊XD
不然你的計算就直接斷在這邊了不是嗎，後面的還是要算啊XD
總之不管有沒有要納入現在這個值，後面的結果都是要算的，只是prev的值改變了而已
所以這個方法，非常的恐怖...
其實我看完答案之後，反而還覺得DP的方法比較好懂
那我們就來看Dynammic Programming的做法：
int lengthOfLIS(vector<int>& nums) {
if (nums.empty())
return 0;
int memo[nums.size()];
for (int i = 0; i < nums.size(); ++i)
{
memo[i] = 1;
}
int LIS = 1;
for (int i = 1; i < nums.size(); ++i)
{
int maxval = 0;
for (int j = 0; j < i; ++j)
{
if (nums[i] > nums[j])
{
maxval = max(maxval, memo[j]);
}
}
memo[i] = maxval + 1;
LIS = max(LIS, memo[i]);
}
return LIS;
}
反正Dynammic Programming的重點就是... 這個memo到底是存什麼的
在這題裡面呢，memo[i]就是表示：從0到i之間最大的LIS
所以如果要算memo[j]的話，會等於多少呢？
memo[j] = max(memo[i]) + 1, 0 <= i < j , memo[j] > memo[i]
乾這到底誰想的... 真的天才ㄟ= =
簡單說memo[i]就是到i這個為止最大的LIS，如果memo[j] > memo[i]的話memo[j]就是memo[i]+1這樣
所以只要找出符合memo[j] > memo[i]這個條件中最大的memo[i]，然後把它加1就是memo[j]了
好吧我大概了解了，但是後來又看到一個更神奇的作法
我就不解釋了，這些人真的是跟鬼一樣ㄟ
看來還真的是... 充滿進步空間啊XD
持續練習努力吧~
留言列表
