【C++每日一练2】双指针2 力扣(61,11) 剑指Office 57

发布时间:2024年01月01日
//剑指Office57
class Solution {
public:
   //解题思路,双指针 
   //根据题意,定位双指针遍历,比对s保存返回即可
	vector<int>twoSum(vector<int>& nums, int target)
	{
		int left = 0;//左指针
		int right = nums.size() - 1;//右指针
		int sum = 0;//比较数值
		while (left < right)//判断条件,如果left>right证明越界
		{
			if (nums[left] + nums[right] > target)//如果大于right减少范围
			{
				right--;
			}
			else if (nums[left] + nums[right] < target)//如果小于left增加距离
			{
				left++;
			}
			else
				return { nums[left],nums[right] };,//相等返回
		}
		return { -1,-1 };//如果没找到,返回-1;
	}
};
class Solution {
public:
    //水桶原理,木桶的水量由最小值决定
    // 由最大值确定宽度,开始遍历枚举
    //定位指针,判定大小会出现两种情况
    //1,高度不变,宽度减少, 水量减少
    //2.高度减少,宽度减少,水量减少
    //由此得出,遍历指针指向的最小值,保存数据,指针移动,继续遍历,丢弃最小值
    //直到遍历完成得出合适的值
    int maxArea(vector<int>& height)
    {
        size_t  left = 0;
        size_t right = height.size() - 1;//定义指针
        int Max = 0;
        while (left < right)//left必须小于right,当==是证明没有水
        {
            int v = (right - left) * min(height[right], height[left]);//计算本次遍历的数值
            Max = max(v, Max);//比较大小
            if (height[right] > height[left])//如果right指向的值大于left,则++left,继续遍历
            {
                left++;
            }
            else//相反
            {
                right--;
            }
        }
        return Max;//返回最大值
    }
};
class Solution {
public:
    //解题思路 ,三角新的最小两边之和如果大于第三边
    //则构成三角形,根据该定律,sort出最大值和最小值
    //三角形的总个数 = right-left
    //right--计算下一数的三角形个数即可
    int triangleNumber(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());//排序
        int sum = 0;
        for (int i = nums.size() - 1; i >= 2; i--)//定位最大值,开始遍历
        {
            int left = 0;//定位到最小数
            int right = i - 1;//定位到最大数的前一个
            while (left < right)//循环该数据内的三角形总个数
            {
                if (nums[left] + nums[right] > nums[i])//如果成立相加
                {
                    sum += right - left;
                    right--;
                }
                else//不成立改变最小值,继续判定
                    left++;
            }
        }
        return sum;
    }
};
文章来源:https://blog.csdn.net/nanmiao666/article/details/135326582
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。