给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:
可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-increasing-subsequence 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
动态+二分
int lengthOfLIS(vector<int>& nums) {
int ans = 1;
if(nums.size()==0) return 0;
vector<int> dp(nums.size(), 1);
for(int i=1;i<nums.size();i++){
for(int j=0;j<i;j++){
if(nums[j]<nums[i]){
dp[i] = max(dp[i], dp[j]+1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。
示例 1:
输入: [10,2]
输出: 210
示例 2:
输入: [3,30,34,5,9]
输出: 9534330
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/largest-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
bool cmp(int a, int b)
{
string sa = to_string(a) + to_string(b);
string sb = to_string(b) + to_string(a);
if (sa.compare(sb) > 0) return true;
else return false;
}
class Solution {
public:
string largestNumber(vector<int>& nums) {
string res = "";
sort(nums.begin(),nums.end(),cmp);
if (nums[0] == 0) return "0";
for (int i = 0; i < nums.size(); i++)
{
res += to_string(nums[i]);
}
return res;
}
};
思路很直接,周赛一题选手已就位