题目连接
第一题:
给你一个二维整数数组 nums ,其中 nums[i] 是由 不同 正整数组成的一个非空数组,按 升序排列 返回一个数组,数组中
的每个元素在 nums 所有数组 中都出现过。
示例 1:
输入:nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
输出:[3,4]
解释:
nums[0] = [3,1,2,4,5],nums[1] = [1,2,3,4],nums[2] = [3,4,5,6],在 nums 中每个数组中都出现的数字是 3 和
4 ,所以返回 [3,4] 。
示例 2:
输入:nums = [[1,2,3],[4,5,6]]
输出:[]
解释:
不存在同时出现在 nums[0] 和 nums[1] 的整数,所以返回一个空列表 [] 。
提示:
1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
nums[i] 中的所有值 互不相同
分析:
这道题不难,思路就是:便利数组中的每个数组,进行计数,个数是大数组长
度的就满足条件,进行输出就可以啦。
代码实现:
class Solution {
public:
vector<int> intersection(vector<vector<int>>& nums) {
map<int,int > arr;
vector<int> ans;
for(int i=0;i<nums.size();i++)
{
for(auto aa:nums[i])
{
arr[aa]++;
}
}
for(auto it = arr.begin();it!= arr.end();++it)
{
if(it->second==nums.size())
{
ans.push_back(it->first);
}
}
return ans;
}
};
第二题:
给你一个二维整数数组 circles ,其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为 ri 的第 i
个圆,返回出现在 至少一个 圆内的 格点数目 。
注意:
格点 是指整数坐标对应的点。
圆周上的点 也被视为出现在圆内的点。
示例 1:
输入:circles = [[2,2,1]]
输出:5
解释:
给定的圆如上图所示。
出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2),在图中用绿色标识。
像 (1, 1) 和 (1, 3) 这样用红色标识的点,并未出现在圆内。
因此,出现在至少一个圆内的格点数目是 5 。
示例 2:
输入:circles = [[2,2,2],[3,4,1]]
输出:16
解释:
给定的圆如上图所示。
共有 16 个格点出现在至少一个圆内。
其中部分点的坐标是 (0, 2)、(2, 0)、(2, 4)、(3, 2) 和 (4, 4) 。
提示:
1 <= circles.length <= 200
circles[i].length == 3
1 <= xi, yi <= 100
1 <= ri <= min(xi, yi)
分析:
这道题就是很简单的暴力求解,题目描述分析一下知道,有效整数点的个数
为0--200,很小。但是只通过暴力的话,时间可能会超时,这时就要进行
优化。
优化:
注意到题目数据中半径的最大值是坐标值的最小值。这样可以不用枚举那么多的点数,从而减少时间复杂度。
代码实现:(优化后)
class Solution {
public:
int countLatticePoints(vector<vector<int>>& circles) {
int ans=0,mx=0;
for(auto &aa:circles) //此处的循环就是找到比较小的测试范围。
{
mx=max(mx,max(aa[0],aa[1]));
}
mx=mx*2;
for(int i=0;i<=mx;i++) //通过三层循环进行便利
{
for(int j=0;j<=mx;j++)
{
for(auto &sd:circles)
{
int a=i-sd[0];
int b=j-sd[1];
int c=sd[2];
if(a*a+b*b<=c*c)
{
ans++;
break; //注意这个break,这里非常的细节,因为题目中说至少存在一个圆内,所以只要
} //满足一个就退出这一层循环,进行下一个点的判断。
}
}
}
return ans;
}
};
最后一次更新于2022-04-24
0 条评论