嘉兴网站优化_陕西新冠疫情最新消息今天_抖音引流推广怎么做_搜狗站长工具平台

344. 反转字符串

• 344. 反转字符串
• 思路：双指针
• 时间：O(n)；空间：O(1)

class Solution {
public:void reverseString(vector<char>& s) {int size = s.size();for(int i = 0, j = size - 1; i < j; i++, j--){swap(s[i], s[j]);}}
};

11. 盛最多水的容器

• 11. 盛最多水的容器
• 思路：两端双指针
• 时间：O(n)；空间：O(1)

class Solution {
public:int maxArea(vector<int>& height) {// 双指针：S = (j - i) * min(height[i], height[j])// 两端双指针：表示全部范围；哪边高度低，哪边往中间移动，即范围减一，同时高度也变化int ret = 0;int size = height.size();for(int i = 0, j = size - 1; i < j;){ret = max(ret, (j - i) * min(height[i], height[j]));if(height[i] < height[j]){i++;} else{j--;}}return ret;}
};

75. 颜色分类

• 75. 颜色分类
• 思路：单循环两次，一次放0，一次放1；或者使用双指针，一个用于放0，一个放2
• 时间：O(n)；空间：O(1)

class Solution {
public:void sortColors(vector<int>& nums) {// 只有0，1，2三个数// 第一次遍历将0换到开头，第二次将1换到0后面int id = 0, size = nums.size();for(int i = 0; i < size; i++){if(nums[i] == 0){swap(nums[i], nums[id++]);}}for(int i = 0; i < size; i++){if(nums[i] == 1){swap(nums[i], nums[id++]);}}}
};

• 第二种做法：

class Solution {
public:void sortColors(vector<int>& nums) {int zero = 0, two = nums.size() - 1, cur = 0;while(cur <= two){  // =: 因为此时two位置的元素还没有遍历if(nums[cur] == 0){swap(nums[zero++], nums[cur++]);} else if(nums[cur] == 1){++cur;} else {swap(nums[cur], nums[two--]);  // 因为可能2和2交换，所以cur不动}}}
};