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

本文主要是介绍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);}
};