C++刷题笔记(3)——leetcode977、189、167

2024-02-02 19:32

本文主要是介绍C++刷题笔记(3)——leetcode977、189、167,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目1:977.有序数组的平方

在这里插入图片描述

暴力排序

给数组中的每个数平方,然后排序

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for (int i = 0; i < nums.size(); i++) {             //遍历数组nums[i] *= nums[i];                             //平方}sort(nums.begin(), nums.end());                     //从小到大排序return nums;}
};

双指针法

双向双指针方法:

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int size = nums.size() - 1;vector<int> result(nums.size(), 0);              //定义一个和nums数组一样大的新数组for (int i = 0, j = nums.size() - 1; i <= j;) {  //i左指针、j右指针,注意这里要i <= j,因为最后要处理两个元素if (nums[i] * nums[i] < nums[j] * nums[j]) {result[size--] = nums[j] * nums[j];j--;}else {result[size--] = nums[i] * nums[i];i++;}}return result;
};

双向双指针方法解题思路:
这一题其实代码并不难懂,无非是定义了一个新的数组,但是要注意这里for循环的书写比较巧妙
在这里插入图片描述

题目2:167.两数之和Ⅱ-输入有序数组

在这里插入图片描述
这题要注意的是下标从1开始,但是不要被下标迷惑,在代码中还是以下标0开始,直到返回整数下标的时候进行加1即可

二分查找

这里用二分查找纯粹是为了巩固前面学的二分查找的知识,但是也有必要细看这里的代码

解题思路:
可以首先固定第一个数,然后寻找第二个数(中间值),第二个数等于目标值减去第一个数的差

为了避免重复寻找,在寻找第二个数时,只在第一个数的右侧寻找。

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {for (int i = 0; i < numbers.size(); i++) {int left = i + 1;                                     //第一个数的右侧开始避免重复寻找int right = numbers.size() - 1;                       //定义target在左闭右闭的区间里[left,right]while (left <= right) {                               //当left == right时,区间[left, right]仍然有效int mid = (right - left) / 2 + left;              //定义中间值if (numbers[mid] == target - numbers[i]) {        //如果中间值等于目标值减去第一个数的差return { i + 1, mid + 1};                     //返回满足条件两个数的下标,加1因为题目要求下标从1开始}else if (numbers[mid] > target - numbers[i]) {    //如果中间值大于目标值减去第一个数的差right = mid - 1;                              //左侧找}else {                                            //numbers[mid] < target - numbers[i]left = mid + 1;                               //右侧找}}}return { -1, -1 };                                        //未找到目标值}
};

双指针法

解题思路:
1.初始状态下,零left指向数组第一个元素,right指向最后一个元素
2.进入循环,控制循环退出条件为left>=right
3.在每一次循环中,如果left与right的数字之和等于所给target,则返回当前的left、right
4.若left与rigth的数字之和小于所给target,left=left+1,继续循环
5.若left与rigth的数字之和大于所给target,right=right-1,继续循环

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int left = 0,                                         //左指针,指向数组第一个元素int right = numbers.size() - 1;                       //右指针,指向数组最后一个元素while (left < right) {int sum = numbers[left] + numbers[right];         //计算两数之和if (sum == target) {                              //两数之和等于目标值return { left + 1, right + 1 };               //返回两数的下标}else if (sum < target) {                          //两数之和小于目标值++left;                                       //left=left+1}else {                                            //两数之和大于目标值--right;                                      //right = right - 1} }return { -1, -1 };}
};

题目3:189.轮转数组

在这里插入图片描述

数组翻转

class Solution {
public:void reverse(vector<int>& nums, int start, int end) {    //翻转数组while (start < end) { swap(nums[start], nums[end]);start ++;end --;}}void rotate(vector<int>& nums, int k) {k %= nums.size();                        //k mod n;  3 mod 7 = 3; reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};

解题思路:
在这里插入图片描述
以k=3为例,在第k个元素处把数组切成两个子数组,将两个子数组再进行翻转
在这里插入图片描述

这篇关于C++刷题笔记(3)——leetcode977、189、167的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/671728

相关文章

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++