做网站 空间还是服务器广州网络推广平台

• 训练是否取等号，这里选择的是双边都闭合的空间
• 对于mid的计算方式，有两种mid = (left + right) / 2或者是mid = left + (left - right) / 2

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int mid;while (left <= right) {mid = (left + right) / 2;if (nums[mid] == target){return mid;} else if (nums[mid] < target){left = mid + 1;} else {right = mid - 1;}}return -1;}
};

• 双指针的思想
• 一个指针用来遍历数组中的所以元素（指向当前将要处理的元素）
• 一个指针用来记录下一个将要赋值的位置

class Solution {
public:int removeElement(vector<int>& nums, int val) {int i = 0;int j = 0;while (i < nums.size()) {if (nums[i] != val) {nums[j] = nums[i];j++;}i++;}return j;}
};

• 暴力的解放，利用sort函数
  • 基本的语法
    • vector的创建
      • vector<int> ans;
      • vector<int> ans(n);
    • vector中添加元素
      • ans.push_back(num);
    • vector的排序
      • sort(ans.begin(), ans.end());
  • 时间复杂度是 O(nlogn)，其中 n 是数组 nums的长度。
  • 空间复杂度是 O(logn)，除了存储答案的数组以外，我们需要 O(logn) 的栈空间进行排序

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int i = 0;vector<int> ans;while (i < nums.size()){ans.push_back(nums[i] * nums[i]);i++;}sort(ans.begin(), ans.end());return ans;}
};

• 双指针的解法
  • 非递减数组，元素当中存在负数
  • 第一个指针指向找到第一个大于等于0的元素
  • 如果第一个指针为0，则不需要第二个指针
  • 反之，第二个指针指向第一个元素左侧的元素
    • 比较左右指针两个元素的大小，逐个加入
    • 这里需要用到三个循环
    • 同时移动两个指针
    • 当一个指针已经移动完，则只移动单侧的指针
  • 时间复杂度是O(n)。其中 n 是数组 nums 的长度。
  • 空间复杂度是O(1)。除了存储答案的数组以外，我们只需要维护常量空间。

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int i = 0;vector<int> ans;for (int num : nums) {if (num < 0) {i++;} else {break;}}if (i == 0) {for (int num : nums) {ans.push_back(num * num);}return ans;} else {int j = i - 1;while (i < nums.size() && j >= 0) {if (nums[i] * nums[i] < nums[j] * nums[j]) {ans.push_back(nums[i] * nums[i]);i++;} else {ans.push_back(nums[j] * nums[j]);j--;}}while (i < nums.size()) {ans.push_back(nums[i] * nums[i]);i++;}while (j >= 0){ans.push_back(nums[j] * nums[j]);j--;}}return ans;}

• 双指针的解法二
  • 一个指针指向第一个元素
  • 另一个指针指向最后一个元素
  • 从后往前加元素
  • 时间复杂度是O(n)。其中 n 是数组 nums 的长度。
  • 空间复杂度是O(1)。除了存储答案的数组以外，我们只需要维护常量空间。

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int n = nums.size();vector<int> ans(n);for (int i = 0, j = n - 1, pos = n - 1; i <= j; pos--) {if (nums[i] * nums[i] > nums[j] * nums[j]) {ans[pos] = nums[i] * nums[i];i++;} else {ans[pos] = nums[j] * nums[j];j--;}}return ans;}
};

• 双指针的思想
  • 左右两个指针，当当前区间内的值小于target，则移动右指针；反之移动左指针
  • 区间是左闭右开的
  • 利用cnt来记录最短的长度；（right - left + 1）
  • 这道题感觉是滑动窗口的思想
• 基本语法知识
  • 三目运算符：条件表达式？True : False
  • INT的最大值：int ans = INT_MAX

// 有点冗余的写法
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0;int right = left + 1;int cnt = nums[0];int n = nums.size();int minlength = n + 1;while(right < n) {if (cnt < target) {cnt += nums[right];right++;} else if (cnt >= target) {if ((right - left) < minlength) {minlength = right - left;}cnt -= nums[left];left++;}}// 当right已经走到最右端了,但cnt依旧大于0while(left < n) {if (cnt >= target) {if ((right - left) < minlength) {minlength = right - left;}cnt -= nums[left];left++;} else {break;}}return (minlength > n) ? 0 : minlength;}
};

// 看完题解后的优化代码
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0;int right = 0;int cnt = 0;int n = nums.size();int minlength = n + 1;while(right < n) {cnt += nums[right];while (cnt >= target) {minlength = min(minlength, right - left + 1);cnt -= nums[left];left++;}right++;}return (minlength > n) ? 0 : minlength;}
};

• 时间复杂度为：O(n)
• 空间复杂度为：O(1)

• 用一个队列来存储当前窗口内的元素，对队列中的元素进行排序，取出最大值

• 使用字典，key为对应的元素，value为对应的出现次数；遍历整个数组，然后按照value进行排序，然后输出前K个结果；
• 思想是上述的思想；但是如何根据value排序是一个难点
• 这里用到了堆的思想，也就是优先队列的思想
• 基本语法：
  • priority_queue的基本函数：push(), pop(), top(), empty(), size();
  • 默认为大根堆
  • 如果想要小元素放在队首，则可以使用以下的方式
    priority_queue<int,vector<int>,greater<int>>q
  • C++11中的STL 可以使用emplace()与emplace_back()来代替insert()与push_back()

class Solution {public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> ans;for (int num : nums) {ans[num]++;}// 排序priority_queue<pair<int, int>> q;for (auto item : ans) {q.emplace(item.second, item.first);}//求解vector<int> res;while(k) {res.emplace_back(q.top().second);q.pop();--k;}return res;}
};