🌈个人主页:聆风吟
🔥系列专栏:数据结构、剑指offer每日一练
🔖少年有梦不应止于心动,更要付诸行动。
文章目录
- 一. ⛳️寻找文件副本(题目难度:简单)
- 1.1 题目
- 1.2 示例
- 1.3 限制
- 1.4 解题思路一
- c++代码
- 1.5 解题思路二
- c++代码
- 二. ⛳️螺旋遍历二维数组(题目难度:简单)
- 1.1 题目
- 1.2 示例
- 1.3 限制
- 1.4 解题思路
- c++代码
- 📝结语
一. ⛳️寻找文件副本(题目难度:简单)
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
1.1 题目
设备中存有 n
个文件,文件 id
记于数组 documents
。若文件 id
相同,则定义为该文件存在副本。请返回任一存在副本的文件 id
。
1.2 示例
输入: documents = [2, 5, 3, 0, 5, 0]
输出: 0 或 5
1.3 限制
- 0 ≤ documents[i] ≤ n-1
- 2 <= n <= 100000
1.4 解题思路一
排序+遍历
对数组首先进行排序,然后遍历数组,如果documents[i] = documents[i+1],则返回doucuments[i]即可。
c++代码
class Solution {
public:
int findRepeatDocument(vector<int>& documents) {
//对数组进行排序
sort(documents.begin(),documents.end());
//遍历查找,判断documents[i]是否等于documents[i+1]
for(int i=0;i<documents.size()-1;i++)
{
if(documents[i]==documents[i+1]) return documents[i];
}
//如果不存在,返回-1
return -1;
}
};
1.5 解题思路二
哈希表
利用数据结构特点,容易想到使用哈希表记录数组的各个数字,当查找到重复数字则直接返回。
- 初始化: 新建 HashSet ,记为 map ;
- 遍历数组 documents 中的每个数字 doc:
- 如果doc在hmap中,说名重复,直接返回doc;
- 如果不在,将doc添加至hmap中;
- 如果不存在,返回-1。
c++代码
class Solution {
public:
int findRepeatDocument(vector<int>& documents) {
//新建 HashSet ,记为 map
unordered_map<int, bool> map;
//遍历数组 documents 中的每个数字 doc
// 1. 如果doc在hmap中,说名重复,直接返回doc;
// 2. 如果不在,将doc添加至hmap中;
for(int doc : documents) {
if(map[doc]) return doc;
map[doc] = true;
}
//如果不存在,返回-1
return -1;
}
};
二. ⛳️螺旋遍历二维数组(题目难度:简单)
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
1.1 题目
给定一个二维数组 array,请返回「螺旋遍历」该数组的结果。
螺旋遍历: 从左上角开始,按照 向右、向下、向左、向上 的顺序 依次 提取元素,然后再进入内部一层重复相同的步骤,直到提取完所有元素。
1.2 示例
输入: array = [ [1, 2, 3], [8, 9, 4], [7, 6, 5] ]
输出: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
1.3 限制
- 0 <= array.length <= 100
- 0 <= array[i].length <= 100
1.4 解题思路
根据题目示例 array = [ [1, 2, 3], [8, 9, 4], [7, 6, 5] ]
,对应的输出为 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
,可以发现,顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。
解题过程:
- 判断
arr
是否为空值,如果为空直接返回[ ]
即可; - 初始化左边界,右边界,上边界,下边界分别为
l
,r
,t
,b
,并创建容器res
用于存储要打印的结果; - 循环打印: “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印;
- 将按顺序添加到
res
中 - 打印一行或一列,让边界收缩 1,代表已经打印
- 判断边界是否相遇,如果相遇则打印完毕,跳出循环。
- 将按顺序添加到
- 返回
res
c++代码
class Solution {
public:
vector<int> spiralArray(vector<vector<int>>& array) {
if (array.empty()) return {};
vector<int> res;
int l = 0, r = array[0].size() - 1;
int t = 0, b = array.size() - 1;
while(true)
{
//从左向右
for(int i = l; i <= r; i++) res.push_back(array[t][i]);
if(++t > b) break;
//从上向下
for(int i = t; i <= b; i++) res.push_back(array[i][r]);
if(--r < l) break;
//从右向左
for(int i = r; i >= l; i--) res.push_back(array[b][i]);
if(--b < t) break;
//从下向上
for(int i = b; i >= t; i--) res.push_back(array[i][l]);
if(++l > r) break;
}
return res;
}
};
📝结语
今天的干货分享到这里就结束啦!如果觉得文章还可以的话,希望能给个三连支持一下,聆风吟的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是作者前进的最大动力!