[leetcode]第二天

• 11.Container With Most Water
• 15.3sum
• 16.3Sum Closest
• 18.4Sum
• 53.Maximum Subarray
  • 解法一：DP
  • 解法二：分治
• 66.Plus One
• 88.Merge Sorted Array

11.Container With Most Water

给定 n 个非负整数 $a_1$，$a_2$，…，$a_n$，每个数代表坐标中的一个点 (i, $a_i$) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, $a_i$) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

//双指针法
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l,r;
        int M = -1;
        l = 0;
        r = height.size()-1;
        while(l<r)
        {
            M = max((r-l)*min(height[l],height[r]),M);
            if(height[l]<height[r])
                l++;
            else
                r--;      
        }
        return M;
    }
};

15.3sum

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

class Solution {
public: 
	vector<vector <int> > threeSum(vector<int>& nums)
	{
		vector<vector<int> > result;
		int i = 0, j = 0, k = 0, target = 0;
		sort(nums.begin(), nums.end()); //对数组进行排序 
		for (i = 0; i < nums.size(); i++) 
		{
			if (nums[i] > 0)
				break;
			else if (i > 0 && nums[i] == nums[i - 1]) //跳过重复元素 
				continue;
			target = -nums[i]; //更新target，转换为两数之和为target的问题 
			j = i + 1;
			k = nums.size() - 1;
			while (j < k)
			{
				if (nums[j] + nums[k] == target) 
				{
					result.push_back({ nums[i],nums[j],nums[k] });
                    //下面两行注意判断大小要在&&的前面，不然会溢出错误
					while (j < k && nums[j + 1] == nums[j]) ++j; //跳过重复元素 
					while (j < k && nums[k - 1] == nums[k]) --k; //跳过重复元素 
					++j, --k;
				}
				else if (nums[j] + nums[k] > target)
					--k;
				else
					++j;
			}
		}
		return result;
	}
};

另附一个完整的c++测试程序以供学习：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public: 
	vector<vector <int> > threeSum(vector<int>& nums)
	{
		vector<vector<int> > result;
		int i = 0, j = 0, k = 0, target = 0;
		sort(nums.begin(), nums.end()); //对数组进行排序 
		for (i = 0; i < nums.size(); i++) 
		{
			if (nums[i] > 0)
				break;
			else if (i > 0 && nums[i] == nums[i - 1]) //跳过重复元素 
				continue;
			target = -nums[i]; //更新target，转换为两数之和为target的问题 
			j = i + 1;
			k = nums.size() - 1;
			while (j < k)
			{
				if (nums[j] + nums[k] == target) 
				{
					result.push_back({ nums[i],nums[j],nums[k] });
					while (j < k && nums[j + 1] == nums[j]) ++j; //跳过重复元素 
					while (j < k && nums[k - 1] == nums[k]) --k; //跳过重复元素 
					++j, --k;
				}
				else if (nums[j] + nums[k] > target)
					--k;
				else
					++j;
			}
		}
		return result;
	}
};

int main()
{
	vector<vector<int> > vt;
	int a[] = { -2,13,-5,-4,-7,8,0,-9,6,7,0,-4,2,1,-2,4 };
	int len = sizeof(a) / sizeof(int);
	vector<int> t(a, a + len);
	Solution solu;
	vt = solu.threeSum(t);
	for (auto x : vt)
	{
		cout << "(";
		for (auto y : x)
			cout << y << "\t";
		cout << ")" << endl;
	}
	cout << endl;
	system("pause");
	return 0;
}

16.3Sum Closest

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

方法与15题类似

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans = nums[0]+nums[1]+nums[2];  //注意初始化使用给定内容
        int l,r,d;
        d = abs(ans - target);
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size(); i++)
        {
            l = i+1;
            r = nums.size()-1;            
            while(l<r)
            {
                int s = nums[l]+nums[r]+nums[i];
                if(d > abs(target-s)) 
                {
                    d = abs(target-s);
                    ans = s;
                }
                if(s < target)  //注意是判断s和target的大小
                    l++;
                else
                    r--;
            }
        }
        return ans;
    }
};

18.4Sum

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

解法同上，多了层循环嵌套而已

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        set<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int l,r,i,j;
        for(i = 0; i < n; i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue;
            for(j = i+1; j < n; j++)
            {
                if((j>i+1)&&nums[j]==nums[j-1]) continue;
                l = j+1;
                r = n-1;
                while(l < r)
                {
                    if(target == nums[i]+nums[j]+nums[l]+nums[r])
                    {
                        vector<int> out{nums[i],nums[j],nums[l],nums[r]}; //删掉‘=’也可
                        ans.insert(out);
                        l++,r--;
                    }
                    else if(target < nums[i]+nums[j]+nums[l]+nums[r])
                        r--;
                    else
                        l++;
                }
                
            }
        }
        return vector<vector<int>> (ans.begin(),ans.end()); //注意转化成嵌套的vector
    }
};

53.Maximum Subarray

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解法一：DP

注意遍历的过程中要将sum与全局的最大值比较；

//DP
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = -1;
        int ans = INT_MIN;
        for(int i = 0; i < nums.size(); i++)
        {
            if(sum < 0)
                sum = nums[i];
            else
                sum += nums[i];
            ans = max(ans,sum);
        }
        return ans;
    }
};

解法二：分治

分治的三种情况：

• 左侧数组的最大子数组
• 右侧数组的最大子数组
• 左侧数组的以右侧边界为边界的最大子数组+右侧数组的以左侧边界为边界的最大子数组

  //分治
  class Solution {
  public:
      int maxSubArray(vector<int>& nums) {
      if(nums.size()==0) return 0; 
      if(nums.size()==1) return nums[0]; 
          
      vector<int> left(nums.begin(),nums.begin()+nums.size()/2); 
      int l=maxSubArray(left); 
      int l_mid=left[left.size()-1]; 
      int l_mid_max=l_mid; 
      for(int i=left.size()-2;i>=0;--i)
      { 
          l_mid+=left[i]; 
          if(l_mid>l_mid_max) l_mid_max=l_mid; 
      } 
      vector<int> right(nums.begin()+nums.size()/2,nums.end()); 
      int r=maxSubArray(right); 
      int r_mid=right[0]; 
      int r_mid_max=r_mid; 
          
      for(int i=1;i<right.size();++i)
      { 
          r_mid+=right[i]; if(r_mid>r_mid_max) r_mid_max=r_mid; 
      } 
      if(l>=r&&l>=(l_mid_max+r_mid_max)) return l; 
      if(r>=l&&r>=(l_mid_max+r_mid_max)) return r; 
      return l_mid_max+r_mid_max; 
      }
  };

  66.Plus One

  给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
  最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
  你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

class Solution { 
    public: 
    vector<int> plusOne(vector<int> &digits) { 
        int n = digits.size(); 
        for (int i = n - 1; i >= 0; --i) 
        { 
            if (digits[i] == 9) digits[i] = 0; 
            else 
            { 
                digits[i] += 1; 
                return digits; 
            } 
        } 
        if (digits.front() == 0) digits.insert(digits.begin(), 1); 
        return digits; 
    } 
};

88.Merge Sorted Array

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

//自己写的
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int l1 = nums1.size();
        int l2 = nums2.size();
        for(int i = 0; i < n; i++)
        {
            nums1.insert(nums1.begin()+m+i,nums2[i]);
        }
        nums1.erase(nums1.begin()+m+n,nums1.end());
        sort(nums1.begin(),nums1.end());
        return ;

    }
};

另一种方法就是将两个数组的最后（最大）元素比较，将更大的一个放在nums1的尾部，一直向前推进，最后如果nums2有剩余在把nums2省的属继续插入，nums1有剩余不用管，已经完成了。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) {
                nums1[k] = nums1[i];
                k--;
                i--;                
            }
            else {
                nums1[k] = nums2[j];
                k--;
                j--;
            }
        }
        while (j >= 0) {
            nums1[k] = nums2[j];
            k--;
            j--;
        }                 
    }
};