189. 轮转数组

189. 轮转数组 - 力扣（LeetCode）

class Solution {
public:
  void reverse(vector<int>::iterator begin, vector<int>::iterator end) {
    size_t dist = std::distance(begin, end);
    for (int i = 0; i < dist / 2; ++i)
      std::swap(*(begin + i), *(begin + dist - 1 - i));
  }
  void rotate(vector<int>& nums, int k) {
    int mod_k = k % nums.size();
    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + mod_k);
    reverse(nums.begin() + mod_k, nums.end());
  }
};

转三次其实很难想到，但是动动笔还是有好处的，在纸上画一下可以发现很多端倪。当然有的时候光是比划也还不行，得拿笔算一算，比如 142. 环形链表 II。

二刷

class Solution {
  void Reverse(vector<int> &V, int Begin, int End) {
    int Distance = End - Begin;
    for (int i = 0; i < Distance / 2; ++i)
      std::swap(V[Begin + i], V[End - 1 - i]);
  }
public:
  void rotate(vector<int>& nums, int k) {
    int Size = nums.size();
    int Actual = k % Size;
    Reverse(nums, 0, Size - Actual);
    Reverse(nums, Size - Actual, Size);
    Reverse(nums, 0, Size);
  }
};

我服了，合着 reverse() 不用自己写啊？

class Solution {
public:
  void rotate(vector<int>& nums, int k) {
    int Size = nums.size();
    int Actual = k % Size;
    std::reverse(nums.begin(), nums.begin() + Size - Actual);
    std::reverse(nums.begin() + Size - Actual, nums.end());
    std::reverse(nums.begin(), nums.end());
  }
};

然后其实你可以发现这里有一个 Size - Actual 的操作，这是因为如果我们「先转小再转大」，我们就必须以 Size - Actual 为轴点来旋转。如果我们「先转大再转小」，那就完全不用担心这个事情了。

$$ \begin{align} S-A=5&&A=2\\ [1\ 2\ 3\ 4\ 5\ 6\ 7]&&[1\ 2\ 3\ 4\ 5\ 6\ 7]\\ \to[5\ 4\ 3\ 2\ 1|7\ 6]&&\to[7\ 6|5\ 4\ 3\ 2\ 1]\\ \to[6\ 7|1\ 2\ 3\ 4\ 5]&&\to[6\ 7|1\ 2\ 3\ 4\ 5] \end{align} $$

class Solution {
public:
  void rotate(vector<int>& nums, int k) {
    int Actual = k % nums.size();
    std::reverse(nums.begin(), nums.end());
    std::reverse(nums.begin(), nums.begin() + Actual);
    std::reverse(nums.begin() + Actual, nums.end());
  }
};

我服了，就这么一个小小的题目竟然还可以考虑这么多东西。

三刷

class Solution {
  void Reverse(vector<int>& nums, int L, int R) {
    int M = L + (R - L) / 2;
    for (int i = L; i < M; ++i)
      swap(nums[i], nums[R + L - 1 - i]);
  }
public:
  void rotate(vector<int>& nums, int k) {
    Reverse(nums, 0, nums.size());
    Reverse(nums, 0, k % nums.size());
    Reverse(nums, k % nums.size(), nums.size());
  }
};

如果真的要手写Reverse()的话，需要考虑翻转的起始点在L处而不是0处，所以这里写了一个nums[R + L - 1 - i]。但是说实话，官解的方法明显要更好一点，很符合直觉，不动点也更清晰，也不用考虑什么中轴的问题。

void reverse(vector<int>& nums, int start, int end) {
    while (start < end) {
        swap(nums[start], nums[end]);
        start += 1;
        end -= 1;
	}
}