牛客网《剑指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;
    }
};


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返回

相关文章
|
云安全 运维 架构师
阿里云ACE认证含金量高不高?考试内容难不难?
IT行业可以说是现在最热门的行业之一,很多人都想在这一行有所建树,于是他们就会选择考取阿里云人才认证来帮助自己提升技能、升职加薪。
1545 1
阿里云ACE认证含金量高不高?考试内容难不难?
|
SQL 存储 安全
【SQL刷题】Day3----SQL必会的常用函数专项练习
【SQL刷题】Day3----SQL必会的常用函数专项练习
308 0
【SQL刷题】Day3----SQL必会的常用函数专项练习
|
消息中间件 存储 缓存
消息中间件ActiveMQ常见问题解析
消息中间件ActiveMQ常见问题解析
501 94
|
运维 供应链 数据挖掘
PaaS市场规模 2022年PaaS行业前景及趋势分析报告
PaaS行业市场前景及现状如何?在PaaS服务逐渐成熟的同时,一些开构建在的IaaS层之上的PaaS服务也开始出现,成为IaaS的增值服务,使得两者的界限逐步开始模糊。此外,一些可以构建在多种IaaS服务上的“开放PaaS”平台的出现,更进一步方便了IaaS服务商提供附加的PaaS服务
1353 0
PaaS市场规模 2022年PaaS行业前景及趋势分析报告
|
存储 SQL JSON
[SIGMOD 21 学习] 《JSON Tiles》解读: 半结构化 JSON 存算优化
本文是对 SIGMOD 2021 上《JSON Tiles: Fast Analytics on Semi-Structured Data》的学习总结,有错误之处欢迎交流。
883 2
|
JSON Prometheus 监控
Spring Boot 怎么做监控?这篇总算整明白了。。。(2)
Spring Boot 怎么做监控?这篇总算整明白了。。。(2)
339 0
Spring Boot 怎么做监控?这篇总算整明白了。。。(2)
|
前端开发 Java Linux
springboot整合pagehelper插件失效
springboot整合pagehelper插件失效
springboot整合pagehelper插件失效
|
监控 安全 数据可视化
IoT 安全运营中心(SOC)最佳实践|学习笔记
快速学习 IoT 安全运营中心(SOC)最佳实践
673 0
IoT 安全运营中心(SOC)最佳实践|学习笔记
|
关系型数据库 网络安全 定位技术
常见概念和使用场景|学习笔记
快速学习常见概念和使用场景
常见概念和使用场景|学习笔记
Google Earth Engine——1992—至今混合坐标海洋模型、水温和盐度(全球海洋数据集HYCOM)
Google Earth Engine——1992—至今混合坐标海洋模型、水温和盐度(全球海洋数据集HYCOM)
704 0
Google Earth Engine——1992—至今混合坐标海洋模型、水温和盐度(全球海洋数据集HYCOM)