【C++】 —— 笔试刷题day_29

一、排序子序列

题目解析

一个数组的连续子序列，如果这个子序列是非递增或者非递减的；这个连续的子序列就是排序子序列。

现在给定一个数组，然后然我们判断这个子序列可以划分成多少个排序子序列。

例如：1 2 3 2 2 1 可以划分成 1 2 3和2 2 1两个排序子序列

算法思路

对于这道题，思路就很简单了：

暴力解法

从0位置开始遍历，寻找一段连续子序列，直到这一段子序列不满足排序子序列的条件，即找到了一个排序子序列；

然后继续从上次遍历结束位置接着遍历数组，寻找下一个子序列。

贪心优化：

当我们遍历到数组中数值相同的区域时，我们要知道，要找的子序列是非递增或者非递减的；

所以这一段相等的序列，我们可以加到前面或者后面的任意序列中。

所以我们在遇到数值相等的子序列时，继续向后遍历即可。

但是这样我们会发现两个问题：

1. 如果数组刚开始位置的数据是相等的，我们不知道这段子序列是非递增的还是非递减的；
2. 我们在遍历过程中会用到下一个位置的值来判断是非递增还是非递减，那最后一个位置该怎么办？

对于数组开头的相等子序列，我们可以直接跳过，因为这一段相等的序列可以加到后面的子序列中；

而对于最后一个位置，如果它不能和前面序列组成一个排序子序列，那就只能让它自己组成一个排序子序列了。

代码实现

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int n;
int main() {cin >> n;for (int i = 0; i < n; i++)  cin >> arr[i];int ret = 0;for (int i = 0; i < n; i++) {if (i == n - 1) { //数组最后一个位置ret++;break;}if (arr[i] < arr[i + 1]) {//非递增while (i < n && arr[i] <= arr[i + 1])i++;ret++;} else if (arr[i] > arr[i + 1]) {//非递减while (i < n && arr[i] >= arr[i + 1])i++;ret++;} else {//数组开始位置的相等子序列while (i < n && arr[i] == arr[i + 1])i++;}}cout << ret << endl;return 0;
}

二、消减整数

题目解析

这道题给定一个正整数H，然后从1开始减，第一次减去1，之后每一次减去的数要么和上一次相等，要么是上一次的两倍；

简单来说就是：h每次减去一个数，x起始是1；之后每一h减去x或者2*x（x表示上次减去的数）。

现在，最少需要几次才能将h减到0。

算法思路

对于这道题，暴力解法：

h每次减去x或者2*x，让它一值减，直到h减到0或者<0。

简单来说就是分情况讨论：第一次减去1，之后分别考虑减去x和减去2*x的情况。

这样时间复杂度和空间复杂度都太大了；并且h每一次减也不一定会恰好等于0。

贪心优化：

这道题要我们求的是将x减到0的最少次数；

那如果我们的h减去某一个数是无法减到0的，那我们就不用去考虑它了；

所以，我们现在要考虑的是，h减的过程中，减去x能否减到0；减去2*x能否减到0。

这个也非常容易判断了，如果h是x的整数倍，那减去x就肯定可以减到0；如果h是2*x的整数倍，那减去2*x就也能减到0。

现在有一个问题，如果h既是x的倍数，也是2*x的倍数， 那是减去x还是2*x呢？

很显然是减去2*X，因为我们要求的是h减到0的最小次数，那可以是减去大的数次数更小啊。

所以我们整体思路就出来了，在减的过程中，判断h是2*x的倍数，如果是就减去2*x；如果不是就减去x。

代码实现

#include <iostream>
using namespace std;
int main()
{int t;cin>>t;while(t--){int n;cin>>n;n--;//第一次减去1int ret = 1,x = 1;while(n){if(n % (2*x) == 0)x*=2;n-=x;ret++;}cout<<ret<<endl;}return 0;
}

三、最长上升子序列(二)

题目解析

对于这道题，给定一个数组，然后我们要找到这个数组中最长严格上升子序列的长度；

严格上升子序列：一个数组删掉其中一些数（可以不删）之后，形成的新数组它是严格上升（非递减）的。

简单来说就是：一个数组的子序列，这个子序列是严格上升的。

现在我们要找到所有上升子序列中长度最长的子序列；然后返回它的长度。

算法思路

对于这道题，一眼看起，可以说毫无思路；这该如何去找啊？

细细看来：

我们要找所有严格上升的子序列，当我们遍历到某一个位置时，我们要知道这个位置的数据和前面位置的数据是否能够形成严格上升的子序列；所以我们就要知道这个位置前面有多少个严格上升的子序列，这个位置的数据能放到哪些子序列当中去？

所以我们就要记录：当前所有的严格上升子序列，以及子序列中的元素。

那我们如何去记录所有的严格上升子序列呢？

当遍历到一个位置时：

这个位置如果是大于等于前面所有位置的，那我们可以把这个位置的元素放到任意一个子序列的后面形成一个新的子序列；

但是，我们没有必要去把这个元素放到每一个子序列的后面形成新的子序列。

加入前面有子序列1、1,2、1,2,4，当前位置数据是7，我们可以形成1,7、1,2,7和1,2,4,7三个新的子序列；但是我们可以发现长度为2的子序列有两个1,2和1,7，我们有必要把这两个长度一样的子序列都记录下来吗？

很显然是不需要的，我们只需要记录长度为n的子序列它最后一个元素最小的子序列即可

所以，我们只需要按长度n（1,2,3...n）记录子序列即可。

那问题又来了，我们要记录子序列中的所有元素吗？

比如1、1,2、1,2,4、1,2,4,7，我们要记录子序列中的所有元素吗？

当然也是没有必要的；当我们遍历一个位置时，我们只需要判断这个位置的能否和前面的子序列组成新的子序列；我们不需要关心这个子序列是什么，所以我们只需要保存子序列最后一个位置的元素即可。

那现在还有一个问题：遍历一个位置时，它可以与前面子序列形成新的子序列，但是长度不是最大的怎么办？

简答来说：现在有子序列1、1,2、1,2,4、1,2,4,7四个子序列，现在遍历到某一个位置，这个位置的值是3；

它可以和1形成1,3但是最后一个元素是3是大于1,2的最后一个元素2的，我们可以不用考虑。

它可以和1,2形成1,2,3，它最后一个元素3是小于1,2,4最后一个元素4的，我们就要修改长度为3的子序列，将4修改成3。

OK啊，现在大致明白了这道题如何去解决；

但是我们要遍历一遍数组，而且还要去判断一个某一个位置是否能和前面子序列形成新的子序列，形成新的子序列是否比之前的子序列更好；那就要存放每一个长度的子序列对应的最后一个元素的值；时间复杂度那不就是O(n^2)了，题目明确要求时间复杂度是O(n log N)啊。

二分查找

所以这里我们要使用二分算法去优化查找。

当我们遍历到一个位置时，当这个位置的值是>=dp[pos]（大于长度最大的子序列的最后一个位置），它可以和长度最大的子序列形成一个新的子序列，长度就是pos+1，直接新增一个位置即可（dp[pos+1] = x）。

但是如果这个位置的值是小于长度最大的子序列的最后一个位置，它可能可以和前面的某一个子序列形成新的子序列，而形成新的子序列的最后一个位置的值，一定是小于等于之前该长度的子序列最后一个位置的值的。

所以我们就要找到这个子序列；

我们按暴力查找它的时间复杂度是O(n)；但是我们仔细思考可以发现，我们存放的是长度为n的子序列的最后一个位置的值，那这个数组dp是不是就是非递减的了？

所以我们就可以使用二分查找来搜索这个子序列，而我们要找的也就是>=当前位置的值的区间左端点。

代码实现

class Solution {public:int dp[100001];int pos = 0;int LIS(vector<int>& a) {for (auto& e : a) {if (pos == 0 || e >= dp[pos])dp[++pos] = e;else {int l = 1, r = pos;while (l < r) {int mid = l + (r - l) / 2;if (dp[mid] >= e)r = mid;elsel = mid + 1;}dp[l] = e;}}return pos;}
};

到这里，本篇文章内容就结束了。
继续加油啊！！！