本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
