408算法题leetcode--第九天

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不动
            }
        }
    }
};