描述
给定一个 3xn
的矩阵 number,并且该矩阵只含有1到9的正整数。
考虑有一个大小为 3x3
滑动窗口,从左到右遍历该矩阵 number, 那么该滑动窗口在遍历整个矩阵的过程中会有n-2
个。
现在你的任务是找出这些滑动窗口是否含有1到9的所有正整数
请返回一个长度为n-2
的答案数组,如果第 i 个滑动窗口含有1到9的所有正整数,那么答案数组的第 i 个元素为true,否则为false
示例
输入:[[1,2,3,2,5,7],[4,5,6,1,7,6],[7,8,9,4,8,3]]
输出:[true,false,true,false]
解释:第一个和第三个滑动窗口含有1到9所有数字,
其他的滑动窗口不含有1到9的所有数字
class Solution {
public:
/**
* @param number: an only contains from 1 to 9 array
* @return: return whether or not each sliding window position contains all the numbers for 1 to 9
*/
vector<bool> SlidingWindows(vector<vector<int>> &number) {
// write your code here
int n = number[0].size();
vector<bool> ans(n-2, false);
vector<int> flag(10, 0);
for(int i = 0; i < 3; i++)
{
for(int k = 0; k < 2; k++)
{ //前3行,2列的数字的个数
flag[number[i][k]]++;
}
}
for(int j = 2; j < n; j++)
{ //右端点 的列加入
for(int i = 0; i < 3; i++)
{
flag[number[i][j]]++;
}
bool res = true;
for(int x = 1; x <= 9; x++)
{ //检查1-9 是不是都是1个
if(flag[x] != 1)
{
res = false;
break;
}
}
ans[j-2] = res;
for(int i = 0; i < 3; i++)
{ // 左端点的列 j-2列 计数减去
flag[number[i][j-2]]--;
}
}
return ans;
}
};
603ms C++