国庆弯道超车之最长递增子序列衍生的一类题
目录
一.马戏团
二.信封嵌套问题
三.马戏团问题
四.拦截导弹
五.蔚来笔试题
六.动物叠罗汉问题
一.马戏团
1.对应oj链接：
合唱队形_牛客题霸_牛客网 (nowcoder.com)
2.题目描述：
3.解题思路：
从题目的意思来看这不就是求以每个位置结尾的从最长递增子序列和以每个位置开头的情况下最长递增子序列是多长吗？我们只要求出每个位置开头和每个位置结尾的情况下最长递增子序列的长度是多长，然后再遍历一遍不就行了求出最长最好的答案然后再用总长度减去这个不就行了。下面我们来看看代码如何来写。
4.对应代码：
#include <iostream> #include<vector> using namespace std; int Serach(vector<int>&ends,int target, int right) { //用来找大于等于target最左边的位置 int L = 0; int R = right; int ans = right + 1; //如果没有大于等于nums[i]的数扩充有效区 while (L <= R) { int mid = (L + R) / 2; if (ends[mid] >= target) { ans = mid; //找到大于等于nums[i]最左边的元素 R = mid - 1; } else { L = mid + 1; } } return ans; } int main() { int N; cin >> N; vector<int>nums(N); for (int i = 0; i < N; i++) { cin >> nums[i]; } vector<int>ends(N);//ends[i]的含义目前长度为i+1的最小结尾 vector<int>dpL(N,1); //dp[i]代表以每个位置结尾的情况下最长递增子序列可以是多长 int right = 0; //用来控制ends数组的有效范围 ends[0] = nums[0]; for (int i = 1; i < N; i++) { int ans=Serach(ends,nums[i],right); dpL[i] = ans + 1; right = max(ans, right); ends[ans] = nums[i]; } //然后再从右往左来一遍 ends.clear();//先清空再说 ends[0] = nums[N - 1]; right = 0; vector<int>dpR(N,1); for (int i = N - 2; i >= 0; i--) { int ans=Serach(ends,nums[i],right); dpR[i]=ans+1; right=max(ans,right); ends[ans]=nums[i]; } int maxLen=0; for(int i=0;i<N;i++) { maxLen=max(maxLen,dpL[i]+dpR[i]-1); //注意以某个位置开头和结尾这个位置被算过两次所以需要减少一次 } cout<<N-maxLen<<endl; return 0; }
二.信封嵌套问题
1.对应OJ链接
354. 俄罗斯套娃信封问题 - 力扣（LeetCode）
2.题目描述
3.解题思路
1.首先按照题目的意思只有当一个信封的宽和高都比一个信封的宽和高都要大的时候另外一个信封才能放到这个信封里面来。我们非常容易能够想到排序按照这个宽度排序然后再求宽度的最长递增子序列不就是答案吗？答案是不对的如果此时出现了宽度一样但是高度不一样了，此时我们就要注意了如果宽度一样我们需要按照高度降序排序，这是为什么了。这是因为我们按照这种排序方式排好序之后，将这个第二维数据拿出来也就是高度。如果我的高度比你高那么我的宽度一定比你宽不存在相等的情况，因为宽度相等的高度比我矮的在我的后面。这样就不会影响最终的答案了。
4.对应代码：
class Solution { public: int maxEnvelopes(vector<vector<int>>& envelopes) { if(envelopes.empty()) { return 0; } auto cmp=[&](vector<int>&a,vector<int>&b){return a[0]==b[0]?a[1]>b[1]:a[0]<b[0];}; sort(envelopes.begin(),envelopes.end(),cmp); //先按照信封的宽度进行排序，如果宽度相等再按照信封的高度进行排序，这样就能够保证我高度 //比你高的宽度一定比你宽不可能相等这是因为宽度相等的在我的后面不会影响我 vector<int>height;; for(auto&envelope:envelopes) { height.push_back(envelope[1]); } int maxLen=1; int right=0; int N=height.size(); vector<int>ends(N); //ends[i]的含义长度为i+1的最小结尾 ends[0]=height[0]; for(int i=1;i<N;i++) { int L=0; int R=right; int ans=right+1;//默认找不到如果找不到扩充有效区 while(L<=R) { int mid=(L+R)/2; if(ends[mid]>=height[i]){ ans=mid; R=mid-1; } else { L=mid+1; } } maxLen=max(maxLen,ans+1); ends[ans]=height[i]; right=max(right,ans); } return maxLen; } };
如果对最长递增子序列问题还有问题的朋友可以看看我的那篇关于最长递增子序列的博客，在这里就不重复了。
三.马戏团问题
1.对应letecode链接
面试题 17.08. 马戏团人塔 - 力扣（LeetCode）
2.题目描述：
3.解题思路：
本题的解题思路和上题一模一样首先按照升高进行排序，身高相同的按照体重降序排序。具体原因在上面已经说过了再这里就不再赘述了下面我们直接来上代码。
4.对应代码：
class Solution { public: int bestSeqAtIndex(vector<int>& height, vector<int>& weight) { int N = height.size(); vector<vector<int>>help(N, vector<int>(2)); for (int i = 0; i < N; i++) { help[i][0] = height[i]; help[i][1] = weight[i]; } auto cmp = [&](vector<int>& a, vector<int>& b) { return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]; }; //升高升序排序体重降序排序否则就会出身高一样我体重比较大但是我两身高一样 sort(help.begin(), help.end(), cmp); int maxLen = 1; vector<int>ends(N); ends[0] = help[0][1]; int right = 0; for (int i = 1; i < N; i++) { int L = 0; int R = right; int ans = right + 1; while (L <= R) { int mid = (L + R) / 2; if (ends[mid] >= help[i][1]) { ans = mid; R = mid - 1; } else { L = mid + 1; } } maxLen = max(maxLen, ans + 1); ends[ans] = help[i][1]; right = max(right, ans); } return maxLen; } };
四.拦截导弹
1.对应OJ链接
拦截导弹_牛客题霸_牛客网 (nowcoder.com)
2.题目描述
3.解题思路
第一位的答案非常的明显第一问就是最长递减子序列的长度但不是严格递减的就是相等也算。是不是非常的简单，下面我们来看第二问，第二问有一个贪心，下面我们就以上面这个例子389 207 155 300 299 170 158 65为例。一开始389了我们需要开一门大炮来拦截它那么这门大炮能够打的高度就变为了389，然后来了一个207、155此时这门大炮都能够拦截但是当来到300时这时候就拦截不了需要再开一门大炮来拦截了，这门大炮能够拦截的最大高度就是300了然后来到299这个300这门大炮可以拦截170也是300这么大炮可以拦截158也是这么大炮来拦截但是65这么大炮要交给能够拦截155的这么大炮了二不是158的，这样158的这么大炮就可以拦截的更多。这里有一个小小的贪心
4.对应代码：
#include <iostream> #include<vector> #include<map> using namespace std; int main() { int N; cin >> N; vector<int>arr(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } int maxLen = 1; vector<int>ends(N); ends[0] = arr[N - 1]; int right = 0; //求最长递减子序列就等于倒着求最长递增子序列 for (int i = N - 2; i >= 0; i--) { int L = 0; int R = right; int ans = right + 1; while (L <= R) { int mid = (L + R) / 2; if (ends[mid] > arr[i]) { ans = mid; R = mid - 1; } else { L = mid + 1; } } maxLen = max(maxLen, ans + 1); ends[ans] = arr[i]; right = max(right, ans); } map<int, int>TreeMap; //值为key的大炮有几个 int cnt = 0; for (int i = 0; i < N; i++) { auto iter = TreeMap.lower_bound(arr[i]); //如果发现没有可以拦截自己的大炮直接新增大炮 if (iter == TreeMap.end()) { TreeMap[arr[i]] = 1; } else { //目前还可以拦截不需要开辟新的大炮来拦截 if (iter->first == arr[i]) { continue; } else { TreeMap.erase( iter);//这么大炮能够拦截的导弹的高度减少我们将其删除即可 TreeMap.insert({arr[i], 1}); //能够拦截导弹新的高度 } } } for (auto x : TreeMap) { cnt += x.second; } cout << maxLen << endl; cout << cnt << endl; } // 64 位输出请用 printf("%lld")
五.蔚来笔试题
1.这道题了没有这个笔试链接，在这里给出题目描述和解题思路以及对应的代码
2.题目描述:
给定一个无序数组，对数组中的每个元素可进行如下操作：
- 将元素移动至数组的头部
- 将元素移动至数组的尾部
注意：这里的移动不是通过元素的交换完成的，而是直接将元素移动到指定位置，空出来的位置由别的元素顺次填满。
问：最少经过几次操作可以使数组变为非降序状态。
3.解题思路
1.首先将数组的值和下标整合成为一个Node并将其放入到容器当中
2.按照值将容器进行排序
3.取出排序好容器对应的下标并将其保持到一个容器当中
4.求这个容器当中最长连续子序列的最长的长度
5.需要移动的最小次数就是数组的长度-最长连续递增子序列的长度
4.对应代码
#include<iostream> #include<vector> #include<algorithm> using std::cin; using std::cout; using std::endl; struct Node { Node(int v,int i) :val(v),index(i) {} int val; int index; }; int main() { int N; cin >> N; std::vector<Node>arr; for (int i = 0; i < N; i++) { int tmp; cin >> tmp; arr.push_back(std::move(Node(tmp, i) ) );//记录每个数的对应的下标 } auto cmp = [](Node& a, Node& b) {return a.val < b.val; };//根据val的大小从小到大排序 sort(arr.begin(), arr.end(), cmp); std::vector<int>ids;//用来记录排序后每个数对应的下标 for (int i = 0; i < N; i++) { ids.push_back(arr[i].index); } //求最长连续递增子序列 std::vector<int>dp(N, 1); int maxLen = 1; for (int i = 1; i < N; i++) { dp[i] = ids[i] > ids[i - 1] ? dp[i - 1] + 1 : 1; maxLen = std::max(maxLen, dp[i]); } cout << N - maxLen << endl; }
六.动物叠罗汉问题
1.同样的这题没有测试链接，在这里也只给出这个题目的解题思路和对应的代码
2.题目描述
有n个动物重量分别是a1、a2、a3.....an， 这群动物一起玩叠罗汉游戏， 规定从左往右选择动物，每只动物左边动物的总重量不能超过自己的重量
返回最多能选多少个动物，求一个高效的算法。 比如有7个动物，从左往右重量依次为：1，3，5，7，9，11，21 则最多能选5个动物：1，3，5，9，21 注意本题给的例子是有序的，但是实际给定的动物数组，可能是无序的， 要求从左往右选动物，且不能打乱原始数组。
3.解题思路
可能很多老铁一看这不是很明显的背包问题吗？每个位置选择或者不选择并且选择的这个数不能比前面选择过的数的累加和要小不就可以了吗？非常的简单。确实这个思路确实很简单下面我们来看看如何进行尝试
4.对应代码：
int process(std::vector<int> &nums, int index, int prev) { if (index == nums.size()) { return 0; } int p1 = process(nums, index + 1, prev); //不要当前的数 //可能性二:要当前的数那么就要求一定要比前面的累加和要大才能选择 int p2 = 0; if (prev <= nums[index]) { p2 = process(nums, index + 1, prev + nums[index]) + 1; } return std::max(p1, p2); } int main() { int N; std::vector<int> arr{1, 3, 5, 7, 9, 11, 21}; cout << process(arr, 0, 0) << endl; return 0; }
上面的这个思路确实很简单。下面我们来看看这个最长递增子序列的解法
1.和最长递增子序列问题一样我们需要一个ends数组但是这个ends数组的含义发生了变化，ends[i]的含义表示长度为i+1的最小重量和。基本流程和最长递增子序列问题差不多只不过这里是最小重量和，当我们决定某个值能够落到那个位置时我们不在是找大于等于最左边的位置了，而是找小于等于他最右边的位置，如果最右边的位置已经来到了数组的末尾位置我们需要扩充有效区。并将之前的累加和都加上，如果有我们则需要看当前位置ends数组里面的值是否+nums[i]是否小于ends数组当中后一位的值如果小于那么则更新后面的值为nums[i]+当前位置ends数组当中的值
对应代码：
#include <iostream> #include <vector> #include <algorithm> using namespace std; //有n个动物重量分别是a1、a2、a3.....an， //这群动物一起玩叠罗汉游戏， //规定从左往右选择动物，每只动物左边动物的总重量不能超过自己的重量 //返回最多能选多少个动物，求一个高效的算法。 //比如有7个动物，从左往右重量依次为：1，3，5，7，9，11，21 //则最多能选5个动物：1，3，5，9，21 //注意本题给的例子是有序的，但是实际给定的动物数组，可能是无序的， //要求从左往右选动物，且不能打乱原始数组 int process1(std::vector<int> &nums, int index, int prev) { if (index == nums.size()) { return 0; } int p1 = process1(nums, index + 1, prev); //不要当前的数 //可能性二要当前的数 int p2 = 0; if (prev <= nums[index]) { p2 = process1(nums, index + 1, prev + nums[index]) + 1; } return std::max(p1, p2); } std::vector<int> getRandom(int N, int V) { std::vector<int> arr; for (int i = 0; i < N; i++) { arr.push_back(rand() % V + 1); } return arr; } int process2(std::vector<int> &nums) { int N = nums.size(); std::vector<int> ends(N + 1); //方便处理 int maxLen = 1; int right = 1; //注意这个维护的是右边界 for (int i = 0; i < N; i++) { int find = 0; int L = 0; int R = right - 1; //注意right代表的是ends数组有效区的长度 while (L <= R) { int mid = L + (R - L) / 2; if (ends[mid] <= nums[i]) { find = mid; L = mid + 1; } else { R = mid - 1; } } //需要扩充有效区 if (find == right - 1) { ends[right] = ends[right - 1] + nums[i]; ++right; } else { if (ends[find] + nums[i] < ends[find + 1]) { ends[find + 1] = ends[find] + nums[i]; } } maxLen = max(maxLen, find + 1); } return maxLen; } int main() { srand(time(0)); int times = 500; for (int i = 0; i < times; i++) { std::vector<int> arr = getRandom(101, 3222); int ans1 = process1(arr, 0, 0); int ans2 = process2(arr); if (ans1 != ans2) { cout << "error" << endl; cout << ans1 << ":" << ans2 << endl; for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } return 0; } } cout << "accpter" << endl; return 0; }