【优选算法题练习】day2

摘星

发布于 2023-10-15 15:52:07

1380

发布于 2023-10-15 15:52:07

一、11. 盛最多水的容器

1.题目简介

11. 盛最多水的容器给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。

2.解题思路

3.代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int ret = 0;
        while(left < right)
        {
            if(height[left] < height[right])
            {
                ret = max(ret, (right - left) * height[left]);
                left++;
            }
            else
            {
                ret = max(ret, (right - left) * height[right]);
                right--;
            }
        }
        return ret;
    }
};

4.运行结果

二、611. 有效三角形的个数

1.题目简介

611. 有效三角形的个数给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

2.解题思路

3.代码

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int ret = 0;
        //1.排序
        sort(nums.begin(), nums.end(), [](int& x, int& y){return x < y;});
        //2.确定三条边中最长的那条边，然后用双指针法遍历其他两条边
        for(int i = nums.size() - 1;i >= 2; --i)
        {
            int left = 0, right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] <= nums[i])//不能组成三角形
                {
                    left++;
                }
                else//可以组成三角形
                {
                    ret += right - left;//这个right的值和i的值可以组成的三角形的种数
                    right--;
                }
            }
        }
        return ret;
    }
};

4.运行结果

三、剑指 Offer 57. 和为s的两个数字

1.题目简介

剑指 Offer 57. 和为s的两个数字输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

2.解题思路

3.代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //1.排序
        sort(nums.begin(), nums.end(), [](int& x, int& y){return x < y;});
        //2.用碰撞指针的方式找出符合条件的两个数
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int sum = nums[left] + nums[right];
            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else
            {
                return {nums[left], nums[right]};
            }
        }
        return {};
    }
};