LeetCodeDay02

189. 旋转数组

描述

• 将包含 n 个元素的数组向右旋转 k 步。
• 例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

注意:

• 尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。

[显示提示]

• 要求空间复杂度为 O(1)
• 关联的问题: 反转字符串中的单词 II

思路：

1. 最蠢的方法，就是没旋转一次就移动一次所有元素，总共的时间复杂度O(K*N)。以后这种一想到的蠢方法还是要落于实践，有时候想到和写出来是不一样的。这次在写的过程中就犯傻了，一定要从左往右一个一个复制，不知都从后往前可以省事很多。
2. 最优解是基于旋转的，先全部旋转，在旋转左边，旋转右边即可。不要被右移这个操作给蒙蔽了，其实仔细观察源字符串和结果，其本质是个旋转的过程。

// 蠢方法01
class Solution_189_01 {
 public:
  void rotate(vector<int>& nums, int k) {
    if (nums.empty() || k < 1) return;
    int len = nums.size();
    k = k % len;
    for (int i = 0; i < k; i++) {
      int pre = nums[0];
      for (int j = 0; j < len; j++) {
        int next = nums[j + 1];
        nums[j + 1] = pre;
        pre = next;
      }
      nums[0] = pre;
    }
  }
};

// 蠢方法02
class Solution_189_02 {
 public:
  void rotate(vector<int>& nums, int k) {
    if (nums.empty() || k < 1) return;
    int len = nums.size();
    k = k % len;
    while (k) {
      int tail = nums[len - 1];
      for (int i = len - 1; i > 0; i--) {
        nums[i] = nums[i - 1];
      }
      nums[0] = tail;
      k--;
    }
  }
};

// 基于旋转
class Solution_189_03 {
 public:
  void rotate(vector<int>& nums, int k) {
    int len = nums.size();
    if (len < 1 || k < 1) {
      return;
    }
    k = k % len;
    reverse(nums, nums.begin(), nums.end() - 1);
    reverse(nums, nums.begin(), nums.begin() + k - 1);
    reverse(nums, nums.begin() + k, nums.end() - 1);
  }
  void reverse(vector<int>& nums, vector<int>::iterator start,
               vector<int>::iterator end) {
    while (start < end) {
      int tmp = *start;
      *start = *end;
      *end = tmp;
      start++;
      end--;
    }
  }
};

217. 存在重复

定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数应该返回 true。如果每个元素都不相同，则返回false。

思路：
1、暴力解法，时间复杂度O(n^2)
2、容器，利用一个set保存出现过的数字。时间复杂度O(1)，空间复杂度O(n)
3、排序，会改变元素组，具体复杂度依赖排序算法。

描述

• 定一个整数数组，判断是否存在重复元素。
• 如果任何值在数组中出现至少两次，函数应该返回 true。如果每个元素都不相同，则返回false。

思路：

1. 暴力解法，时间复杂度O(n^2)
2. 容器，利用一个set保存出现过的数字。时间复杂度O(1)，空间复杂度O(n)
3. 排序，会改变元素组，具体复杂度依赖排序算法。

class Solution_217_01 {
 public:
  bool containsDuplicate(vector<int>& nums) {
    if (nums.size() <= 1) return false;
    for (auto iter = nums.begin(); iter != nums.end(); iter++) {
      for (auto val = nums.begin(); val != nums.end(); val++) {
        if (*iter == *val && iter != val) return true;
      }
    }
    return false;
  }
};

class Solution_217_02 {
 public:
  bool containsDuplicate(vector<int>& nums) {
    if (nums.size() <= 1) return false;
    set<int> numSet;
    for (auto iter = nums.begin(); iter != nums.end(); iter++) {
      if (numSet.find(*iter) == numSet.end()) {
        numSet.insert(*iter);
      } else {
        return true;
      }
    }
    return false;
  }
};

class Solution_217_03 {
 public:
  bool containsDuplicate(vector<int>& nums) {
    if (nums.size() <= 1) return false;
    sort(nums.begin(), nums.end());
    for (auto iter = nums.begin(); iter != nums.end() - 1; iter++) {
      if (*iter == *(iter + 1)) {
        return true;
      }
    }
    return false;
  }
};
``