3152. 特殊数组 II

代码

这种解法不是一个一个的对比，只要给定区间的一个踏入 非特殊数组的行列，这个是关键。

关键词，点位最近符合条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n = nums.size();
	vector<int> last_same(n);
	//核心思想是记录一个点位的左侧最近不是 特殊数组 的右边界
	for (int i = 1; i < n; i++)
	{
		last_same[i] = nums[i] % 2 == nums[i - 1] % 2 ? i : last_same[i - 1];
	}
 
	vector<bool> res(queries.size());
 
//排查该点位左侧距离最近的
	for (int i = 0; i < queries.size(); i++)
	{
		auto& it = queries[i];
		res[i] = last_same[it[1]] <= it[0];
	}
 
	return res;

讲解

一开始的想法是从给定的矩阵中进行枚举，这个时候再去加入计算，然后慢慢扩张 特殊数组 的边界，加入pair数组存储 特殊数组 边界断裂的情况。显而易见的是，每次查询一个进来的区域是不是 特殊数组 的时候都需要遍历一次 specialRange ，这个时候的区间确定逻辑比较复杂，因此淘汰，这种思路应用的区间思想有一个解，但是在时间复杂度上稍差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n = queries.size();
	vector<bool> res(n);
 
	//左右指定区间扩展
	int left = 0, right = 0;
	vector<pair<int, int>> specialRange; //存储可能的区间
 
	function<bool(int, int)> f = [&](int l, int r)
	{
 
		};
 
	for (auto v : queries)
	{

区间合并方法的正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
	class Solution {
		using pii = pair<int, int>;
#define x first
#define y second
 
	public:
		vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
			vector<bool> res;
			vector<pii> v; //存放区间
			v.push_back({ 0,0 });
			for (int i = 1; i < nums.size(); i++)
			{
				if ((nums[i] % 2) != (nums[i - 1] % 2)) //说明可以更新到区间中
					v.back().y = i;
				else
					v.push_back({ i,i });
			}
			//然后开始进行二分，由于初始化就是有序的，固然不用再进行排序
			int n = queries.size();
			for (int i = 0; i < n; i++)
			{
				int target = queries[i][0];
				int l = 0, r = v.size() - 1;
				while (l < r) //二段性：前面都符合，后面反之
				{ //寻找右边界（找出最后一个满足v[mid].x<=target的元素）
					int mid = (l + r + 1) >> 1;
					if (v[mid].x <= target) //说明符合
						l = mid;
					else
						r = mid - 1;
				}
				//然后去判断
				if (v[l].x <= queries[i][0] && queries[i][1] <= v[l].y)
					res.push_back(true);
				else
					res.push_back(false);
			}
 
			return res;