5/24刷题

1.寻找两个正序数组的中位数
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
思路一：对比两个数组，一直查找到len/2（len为两个数组的长度和），如果len是奇数，就返回left和right相加和除以二，否则返回right。复杂度是O（m+n）

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1=nums1.size();
        int len2=nums2.size();
        int len=len1+len2;
        int left=-1,right=-1;//记录中位数,如果是奇数就返回right，是偶数则返回二者相加除以2
        int ans1=0,ans2=0;
        for(int i=0;i<=(len/2);i++)
        {
            left=right;//这里是保证left是right的上一个数
            if(ans1<len1&&(ans2>=len2||nums1[ans1]<nums2[ans2]))//注意这个条件
            {
                right=nums1[ans1++];//数组1的值小于数字2，数组一后移
            }
            else
            {
                right=nums2[ans2++];//否则数组二后移
            }
        }
        if((len&1)==0)
        {
            return (left+right)/2.0;
        }
        else
        {
            return right;
        }       
    }
};

2.剪绳子
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

class Solution {
public:
    int cutRope(int number) {
        if(number<2)
            return 0;
        if(number==2)
            return 1;
        if(number==3)
            return 2;//特殊情况
        //动态规划
        vector<int> best(number+1,0);//用于存储不同长度绳子的最优值
        best[0]=0;
        best[1]=1;
        best[2]=2;
        best[3]=3;
        for(int i=4;i<=number;i++)//由小到达计算函数值
        {
            for(int j=1;j<=i/2;j++)
            {
                best[i]=max(best[i],best[j]*best[i-j]);
            }
        }
        int res=best[number];
        return res;

        /*
        贪婪，如果绳子长度大于等于5，就减3，一直减到小于5
        int sum=0;
        int res=1;
        while(number>=5)
        {
            number-=3;
            sum++;
        }
        for(int i=0;i<sum;i++)
        {
            res*=3;
        }
        if(number==4)
            return res*4;
        if(number==3)
            return res*3;
        if(number==2)
            return res*2;*/
    }
};