文章目录

• 1.189轮转数组
• • 1.1.题目
  • 1.2.解答
• 2.724寻找数组的中心下标
• • 2.1.题目
  • 2.2.解答
• 3.922按奇偶排序数组II
• • 3.1.题目
  • 3.2.解答

1.189轮转数组

参考：代码随想录，189轮转数组；力扣题目链接

1.1.题目

1.2.解答

这道题目在字符串里其实很常见，我把字符串反转相关的题目列一下：

字符串：力扣541.反转字符串II、字符串：力扣151.翻转字符串里的单词、字符串：剑指Offer58-II.左旋转字符串

本题其实和字符串：剑指Offer58-II.左旋转字符串 就非常像了，剑指offer上左旋转，本题是右旋转。

注意题目要求是要求使用空间复杂度为 O(1) 的 原地 算法

原地左边旋转字符串：

• 反转区间为前n的子串
• 反转区间为n到末尾的子串
• 反转整个字符串

原地右边旋转字符串：

• 反转整个字符串
• 反转区间为前k的子串
• 反转区间为k到末尾的子串

需要注意的是，本题还有一个小陷阱，题目输入中，如果k大于nums.size了应该怎么办？

其实移动到num.size()次数之后就相当于没有移动，所以直接执行k % nums.size()次数就行。

最后给出代码如下，注意是右旋转，所以要先旋转整个字符串，再旋转子串。

void rotate(vector &nums, int k)
{k = k % nums.size();   // 防止k过大// 左移：先旋转子串，再旋转整个字符串；右移：先旋转子串，再旋转整个字符串reverse(nums.begin(), nums.end());          // 先旋转整个数组reverse(nums.begin(), nums.begin() + k);    // 在旋转前半部分reverse(nums.begin() + k, nums.end());  // 最后旋转后半部分
}

2.724寻找数组的中心下标

参考：代码随想录，724寻找数组的中心下标；力扣题目链接

2.1.题目

2.2.解答

首先注意不要把这道题目理解错了，其中说的左右相等的下标是不包括当前的数字的，而是不算当前数字，其左边的数字和右边的数字的和相等。

但是这道题目仍然非常简单：

• 遍历一遍求出总和sum
• 遍历第二遍求中心索引左半和leftSum
  同时根据sum和leftSum 计算中心索引右半和rightSum
  判断leftSum和rightSum是否相同

给出代码如下：

int pivotIndex(vector &nums)
{// 1.统计和int sum = 0;for(const auto& num : nums)sum += num;int left_sum = 0;int right_sum = 0;// 2.遍历求左边的和 和 右边的和for(int i = 0; i < nums.size(); i++){// 注意这个并不是真的left_sum，而是多加了nums[i]left_sum += nums[i];  // 所以这里right_sum就也要把nums[i]加上right_sum = sum - left_sum + nums[i];  if(left_sum == right_sum)return i;}// 运行到这里说明没找到，返回-1return -1;
}

注意：上述代码就是在计算过程中，遍历到当前的下标时，直接把左边的left_sum也加上了当前的nums[i]，此时i右边的数字综合是sum - left_sum。但是由于我们的left_sum多加了nums[i]，所以这里计算right_sum的时候也要多加nums[i]，即right_sum = sum - left_sum + nums[i]。比如1 7 3 6 5 6的例子，便利到6的时候，左边和是11，但是此时left_sum = 17，因为多加了当前的6；此时右边和是11，所以也要多加上当前的6，结果也是17.

另外一个方法其实就是可以便利到当前数字之后，就从总和中减去当前的数字，然后再/2，看结果和左边的和是否相等。此时的代码如下：

int pivotIndex(vector &nums)
{   // 1.计算总和int sum = 0;for(const auto& num : nums)sum += num;int left_sum = 0;   // 左边总和，不包括当前下标for(int i = 0; i < nums.size(); i++){// 如果此时总和/2等于左边的和if(left_sum * 2 == sum - nums[i])   return i;else left_sum += nums[i];   // 否则累加当前数字，给下一次准备}// 运行到这里说明没找到，返回-1return -1;
}

3.922按奇偶排序数组II

参考：代码随想录，922按奇偶排序数组II；力扣题目链接

3.1.题目

3.2.解答

这道题目直接的想法可能是两层for循环再加上used数组表示使用过的元素，这样的的时间复杂度是O(n^2)。

但是其实可以换一个角度想，建立一个结果数组，分别分成奇数索引的空位和偶数索引的空位。然后遍历原数组中的元素，如果是奇数，那么就填到奇数空位中；如果是偶数，就填到偶数索引的空位中，这样就很简单了。

直接给出代码如下：

vector sortArrayByParityII(vector &nums)
{vector result(nums.size(), 0);   // 先构造存储结果的数组int odd_idx = 1;   // 初始化奇数和偶数索引int even_idx = 0;   for(const auto& num : nums){if(num % 2 == 0)   // 偶数{result[even_idx] = num;even_idx += 2;}else   // 奇数{result[odd_idx] = num;odd_idx += 2;}}return result;
}