首页 > 编程语言 >408算法题leetcode--第九天

408算法题leetcode--第九天

时间:2024-09-22 21:20:47浏览次数:18  
标签:第九天 cur nums -- ++ height int leetcode size

344. 反转字符串

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. 盛最多水的容器

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

标签:第九天,cur,nums,--,++,height,int,leetcode,size
From: https://blog.csdn.net/weixin_58073817/article/details/142366486

相关文章

  • C++入门——类和对象(上)
    文章目录一、类的定义1.1类的定义格式1.2访问限定符1.3类域二、实例化2.1实例化概念2.2对象大小三、this指针四、C++和C语言实现Stack栈的对比总结一、类的定义1.1类的定义格式class为定义类的关键字,Stack为类的名字,{}中为类的主体,注意类定义结束时后⾯分......
  • DDD分层架构
    DDD分层架构、整洁架构、六边形架构都是以领域模型为核心,实行分层架构。内部核心业务逻辑与外部应用、资源隔离并解耦。从而设计出“高内聚、低耦合”的微服务,以实现微服务的架构演进。DDD分层架构使得微服务的架构边界变得清晰。六边形架构提到微服务架构,一定会涉及到六......
  • 力扣72-编辑距离(Java详细题解)
    题目链接:力扣72-编辑距离前情提要:因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。dp五部曲。1.确定dp数组和i下标的含义。2.确定递推公式。3.dp初始化。4.确定dp的遍历顺序。5.如果没有ac打印dp数组利于debug。每一个dp题目如果都用这五步分析清楚,那么......
  • 2024“华为杯”数模研赛E数据提取代码
    2024年数学建模研究生赛E题从视频中提取数据的代码。主要包括三个部分:车流量计算、各车道车流量计算和平均速度计算。主要讲述了代码的使用方法,包括需要修改的参数和文件路径,以及一些特殊情况的处理方法。同时还提供了参数估计和绘图的相关代码,以及如何根据不同视频视角调整代码......
  • Python 客户端类库之paho-mqtt学习总结
    实践环境Python3.9.13paho-mqtt2.1.0简介EclipsePahoMQTTPython客户端类库实现了MQTT协议版本5.0,3.1.1,和3.1。该类库提供一个客户端类,允许应用连接到MQTT代理并发布消息,订阅主题并检索发布的消息。同时还提供了一个写其它辅助函数,使向MQTT服务器发布一次性消息变......