牛客网《剑指offer》专栏刷题练习之数组专精

✅作者简介：C/C++领域新星创作者，CSDN内容合伙人
✨个人社区：微凉秋意社区
🔥系列专栏：剑指offer精讲
📃推荐一款模拟面试、刷题神器👉注册免费刷题

🔥前言

今天分享牛客网《剑指offer》专栏里的经典数组算法题的题解，从解题思路到具体代码解释步步到位。

一、 打印从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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.3、代码解析

• 创建动态数组res，这是最终用来返回的整数列表
• flag是辅助数字，利用for循环来确定辅助数字的最终值
• 从1开始到辅助数字结束，在for循环里将递增的数字存入数组中
• 最终返回res，算法结束

二、 调整数组顺序使奇数位于偶数前面(一)

1、题目速览

2、个人题解

2.1、解题思路

注意题目要求：奇数之间与偶数之间的相对位置不变，那么我的解题思路是：

1. 新创建两个vector容器，对原数组里的元素值判断：
   • 若对2取余为零，证明是偶数，存入偶数容器里
   • 若对2取余不为零，则存入奇数容器里
2. 由于要求所有奇数在前，那就利用for循环将偶数容器里的元素全部尾插到奇数容器内
3. 最终的奇数容器就是最终排序的结果

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;
    }
};
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

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;
    }
};
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

2.3、代码解析

• 外层while循环结束的条件就是下标超过限制
• 找到第一个偶数时，定义辅助变量flag，并通过内层的while循环来找到第一个奇数的位置
• 判断flag是否超过数组限制，如果超过就说明原数组满足题目要求，return返回即可
• 如果没有超过限制就进行经典的交换元素操作
• 最后i++，继续往后遍历，超过数组限制后也要利用return返回

---

那么《剑指offer》专栏之数组专精的分享到此结束了，觉得写的好的朋友可以点赞鼓励一下哈，我们下篇再见！