我在LeetCode上解决了最长递增子序列问题:https://leetcode.com/problems/longest-increasing-subsequence/
Given an unsorted array of integers, find the length of longest increasing subsequence. For
[10,9,2,5,3,7,101,18]
, the answer is4
(size of[2,3,7,101]
).
class Solution {
public:
int helper(vector<int>& nums, unordered_map<int, vector<int>>& dp, int lastNum, int startIndex) {
if(startIndex>=nums.size()) return 0;
if(dp.find(lastNum)!=dp.end() && dp[lastNum].size()>=startIndex && dp[lastNum][startIndex]!=INT_MIN) {
return dp[lastNum][startIndex];
}
int ans=0;
if(nums[startIndex]>lastNum) ans=1+helper(nums, dp, nums[startIndex], startIndex+1);
ans=max(ans, helper(nums, dp, lastNum, startIndex+1));
return dp[lastNum][startIndex]=ans;
}
int lengthOfLIS(vector<int>& nums) {
int ans=0;
unordered_map<int, vector<int>> dp;
dp[INT_MIN].resize(10001, INT_MIN);
for(int i=0; i<nums.size(); i++) dp[nums[i]].resize(10001, INT_MIN);
return helper(nums, dp, INT_MIN, 0);
}
};
请注意,我也在使用上面的dp
表并使用两种状态lastNum
(我们在上一次递归中选择的nums[i]
值)和startIndex
来记住它。在solution section中,它们使用两种状态prev
(索引,与我使用lastNum
传递的值不同)和curpos
(类似于startIndex
)。我很困惑,因为我仍然获得TLE。现在,我知道在线法官设置的时间限制是任意的,但我希望了解为什么使用
lastNum
而不是prev
作为状态会导致更多的执行时间。同样,我还能进行其他优化吗?谢谢!
编辑:根据评论中Igor的建议,我将其更改为
10001
,所有测试用例现在都通过了,但是需要很多时间:24 / 24 test cases passed, but took too long.
Edit2:换句话说,我想我的问题是,作为一名面试官,一个什么样的建议可以向正确的方向推选候选人(使用
prev
而不是lastNum
)?
最佳答案
不确定您的解决方案,但是我有点困惑:dp[INT_MIN].resize(10000001, INT_MIN);
,也许您的解决方案不是O(N)。这会被接受:
#include <vector>
#include <algorithm>
struct Solution {
static const inline int lengthOfLIS(const std::vector<int> &nums) {
std::vector<int> longest;
for (unsigned int index = 0; index < nums.size(); index++) {
const auto iter = std::lower_bound(longest.begin(), longest.end(), nums[index]);
if (iter == longest.end()) {
longest.emplace_back(nums[index]);
} else {
*iter = nums[index];
}
}
return longest.size();
}
};
引用文献
如果您正在准备interviews:
关于c++ - 进一步优化DP解决方案的提示,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62856344/