牛客网《剑指offer》专栏刷题练习之数组专精
✅作者简介:C/C++领域新星创作者,CSDN内容合伙人
✨个人社区:微凉秋意社区
🔥系列专栏:剑指offer精讲
📃推荐一款模拟面试、刷题神器👉注册免费刷题
🔥前言
今天分享牛客网《剑指offer》专栏里的经典数组算法题的题解,从解题思路到具体代码解释步步到位。
经典数组算法题目录
- 一、 打印从1到最大的n位数
-
- 1、题目速览
- 2、个人题解
-
- 2.1、解题思路
- 2.2、代码实现
- 2.3、代码解析
- 二、 调整数组顺序使奇数位于偶数前面(一)
-
- 1、题目速览
- 2、个人题解
-
- 2.1、解题思路
- 2.2、代码实现
- 2.3、代码解析
- 三、 调整数组顺序使奇数位于偶数前面(二)
-
- 1、题目速览
- 2、个人题解
-
- 2.1、解题思路
- 2.2、代码实现
- 2.3、代码解析
一、 打印从1到最大的n位数
1、题目速览
2、个人题解
2.1、解题思路
-
由题目可以得知打印的结果取决于n的值且和10的倍数有密切关联:
- 若n为1,打印的最大值为9
- 若n为2,打印的最大值为99
。。。 - 若n为5,打印的最大值为99999
-
所以我们可以定义一个值为1的辅助数字,根据n的值来让辅助数字乘以不同数量的10
-
然后从1到辅助数字进行循环,将结果依次存入一个数组即可
2.2、代码实现
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 最大位数 * @return int整型vector */ vector<int> printNumbers(int n) { // write code here vector<int>res; int flag=1; for(int i=1;i<=n;i++) flag*=10; for(int i=1;i<flag;i++) res.push_back(i); return res; }};
2.3、代码解析
- 创建动态数组
res
,这是最终用来返回的整数列表 flag
是辅助数字,利用for循环来确定辅助数字的最终值- 从1开始到辅助数字结束,在for循环里将递增的数字存入数组中
- 最终返回
res
,算法结束
二、 调整数组顺序使奇数位于偶数前面(一)
1、题目速览
2、个人题解
2.1、解题思路
注意题目要求:奇数之间与偶数之间的相对位置不变,那么我的解题思路是:
- 新创建两个
vector
容器,对原数组里的元素值判断:- 若对2取余为零,证明是偶数,存入偶数容器里
- 若对2取余不为零,则存入奇数容器里
- 由于要求所有奇数在前,那就利用for循环将偶数容器里的元素全部尾插到奇数容器内
- 最终的奇数容器就是最终排序的结果
2.2、代码实现
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> reOrderArray(vector<int>& array) { // write code here if(array.size()==0||array.size()==1) return array; vector<int>os; vector<int>js; for(int i=0;i<array.size();i++){ if(array[i]%2==0) os.push_back(array[i]); else js.push_back(array[i]); } for(int i=0;i<os.size();i++){ js.push_back(os[i]); } return js; }};
2.3、代码解析
- 由于题目中原数组里元素个数可能为0或1,而且这种情况不需要排序,直接返回即可
os
和js
分别代表偶数和奇数容器- 对元素组中元素值判断,并插入到不同的容器中
- 最后将偶数容器内的元素插入到奇数容器内并返回即可
三、 调整数组顺序使奇数位于偶数前面(二)
1、题目速览
2、个人题解
2.1、解题思路
这一题不要求奇数间或者偶数间的位置了,因此可以采取元素交换的方法:
- 由于是奇数在前,那就直奔第一个偶数而去
- 在第一个偶数后找到第一个奇数并进行元素交换
- 继续向后遍历,重复以上操作即可
- 注意遍历越界的情况,在代码解析部分会有表示
2.2、代码实现
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> reOrderArrayTwo(vector<int>& array) { // write code here int i=0; while(i<array.size()){ if(array[i]%2==0){ int flag=i+1; while(array[flag]%2==0){ flag++; } if(flag>=array.size()) return array; int temp=array[i]; array[i]=array[flag]; array[flag]=temp; } i++; } return array; }};
2.3、代码解析
- 外层
while
循环结束的条件就是下标超过限制 - 找到第一个偶数时,定义辅助变量
flag
,并通过内层的while
循环来找到第一个奇数的位置 - 判断flag是否超过数组限制,如果超过就说明原数组满足题目要求,
return
返回即可 - 如果没有超过限制就进行经典的交换元素操作
- 最后
i++
,继续往后遍历,超过数组限制后也要利用return
返回
那么《剑指offer》专栏之数组专精的分享到此结束了,觉得写的好的朋友可以点赞鼓励一下哈,我们下篇再见!