image.png
image.png
image.png
image.png
image.png
第二题答案：
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int i = 0; i < nums.size(); ++i) {
int left = 0, right = dp.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (dp[mid] <= nums[i]) left = mid + 1;
else right = mid;
}
if (right >= dp.size()) dp.push_back(nums[i]);
else dp[right] = nums[i];
}
return dp.size();
}
int main() {
int n;
vector<int> nums;
std::cin >>n;
for (int i = 0; i < n; ++i) {
int item;
std::cin >> item;
nums.push_back(item);
}
std::cout << lengthOfLIS(nums);
}
最长递增子序列
头条题
image.png
image.png
image.png
第一题是朋友圈，并查集典型题
public:
int dfs(vector<vector<int>> M, vector<bool> &visited, int p) {
if(visited[p]) return 0; //如果当前节点被访问过 直接结束
else {
visited[p] = true; //将当前节点标记为访问过
int count =1;
for (int i = 0; i < M.size(); i++) {//遍历 找到当前这个人的朋友
if (M[p][i] == 1 && !visited[i] && i != p) { //如果M数组值为1 且这个人不是自己 就是朋友
count += dfs(M, visited, i); //接着找朋友
}
}
return count; //最后返回一共找了几次朋友 虽然并不需要这个值 只要有朋友就可以了
}
}
int findCircleNum(vector<vector<int>>& M) {
int py = 0; //朋友圈的个数
vector<bool> visited(M.size(), false);//初始化一个visited数组 用于记录访问的情况
for(int i=0;i<M.size();i++)
if(dfs(M,visited,i)) py++;//如果dfs的结果不是0，证明存在朋友圈。
return py;
}
};
第二题是卡特兰典型题
