【每日刷题】Day123
【每日刷题】Day123
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 673. 最长递增子序列的个数 - 力扣（LeetCode）
2. LCR 083. 全排列 - 力扣（LeetCode）
1. 673. 最长递增子序列的个数 - 力扣（LeetCode）
//思路：子序列动态规划问题。
//这题难度还是比较大的，有各种细节处理。
class Solution {
public:
int findNumberOfLIS(vector<int>& nums)
{
int n = nums.size(),maxval = 1,ans = 0;
vector<int> len(n,1);
vector<int> count(n,1);
for(int i = 1;i<n;i++)
{
for(int j = i-1;j>=0;j--)
{
if(nums[i]>nums[j])
{
if(len[j]+1>len[i])
{
len[i] = len[j]+1;
maxval = maxval>len[i]?maxval:len[i];
count[i] = count[j];
}
else if(len[j]+1==len[i]) count[i]+=count[j];
}
}
}
for(int i = 0;i<n;i++)
{
if(len[i]==maxval) ans+=count[i];
}
return ans;
}
};
2. LCR 083. 全排列 - 力扣（LeetCode）
//思路：深搜+回溯+剪枝。
class Solution {
public:
vector<vector<int>> ans;
vector<int> arr;
bool check[7];//check：检查当 i 位置的数是否已经排入
void _permute(vector<int>& nums)
{
if(arr.size()==nums.size())//递归出口
{
ans.push_back(arr);//排完后将 arr 放入 ans 中
return;
}
for(int i = 0;i<nums.size();i++)
{
if(!check[i])//遍历nums，判断 i 位置数是否已经排入，如果没排入则排入
{
arr.push_back(nums[i]);
check[i] = true;//排入后将 i 位置设为 "已排入" 状态
_permute(nums);//深搜
arr.pop_back();//返回时需要将最后一个排入的数排出
check[i] = false;//并将其设为 "未排入" 状态
}
}
}
vector<vector<int>> permute(vector<int>& nums)
{
_permute(nums);
return ans;
}
};