【Leetcode】189. 轮转数组

189. Rotate Array
     Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Example 1:

**Input**: nums = [1,2,3,4,5,6,7], k = 3
**Output**: [5,6,7,1,2,3,4]
1
2

Explanation:

**rotate 1 steps to the right**: [7,1,2,3,4,5,6]
**rotate 2 steps to the right**: [6,7,1,2,3,4,5]
**rotate 3 steps to the right**: [5,6,7,1,2,3,4]
1
2
3

Example 2:

**Input**: nums = [-1,-100,3,99], k = 2
**Output**: [3,99,-1,-100]
1
2

Explanation:

rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
1
2

Constraints:

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
1
2
3

Follow up:

Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
Could you do it in-place with O(1) extra space?

---

该题重点需要学习的是 O(1) 空间复杂度的原地算法
原地算法（in-place algorithm）指的是一种在不使用额外的存储空间（或仅使用固定量的额外空间）的情况下，来执行某种操作或算法的方法。这种算法通常需要就地修改输入数据，因此称为原地算法。

原地算法通常在空间受限或需要尽量避免额外的空间消耗的情况下使用，它们可以避免在操作大型数据集时产生过多的内存开销，同时也可以通过减少内存分配和释放的次数来提高执行效率。在许多情况下，原地算法也可以简化代码并提高可读性。

---

AC：

/*
 * @lc app=leetcode.cn id=189 lang=cpp
 *
 * [189] 轮转数组
 */

// @lc code=start
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

很巧妙，通过全面🔪局部反转，从而实现数组右旋！
步骤如下：

1. 反转区间为前n的子串
2. 反转区间为n到末尾的子串
3. 反转整个字符串

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

举个例子，比较容易想，

例如，1,2,3,4,5,6,7 如果右移动15次的话，是 7 1 2 3 4 5 6 。

所以其实就是右移 k % nums.size() 次，即：15 % 7 = 1

---

同样的，类似的还有这么一道题！
541. Reverse String II
Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

Example 1:

**Input**: s = "abcdefg", k = 2
**Output**: "bacdfeg"
1
2

Example 2:

Input: s = "abcd", k = 2
Output: "bacd"
1
2

Constraints:

1 <= s.length <= 104
s consists of only lowercase English letters.
1 <= k <= 104
1
2
3

---

AC:

/*
 * @lc app=leetcode.cn id=541 lang=cpp
 *
 * [541] 反转字符串 II
 */

// @lc code=start
class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i += (2 * k)) {
            if(i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k);
            }
            else
                reverse(s.begin() + i, s.end());
        }
        return s;
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21