Leetcode#1@2017

week6题目列表：74,240,53,152,278,34,35.
前两周我没有参与。第三周深搜。第四周和第五周主要dp。
题目不难，就不搬过来了。
2017开始把解题报告发到简书。主要是因为懒。这个blog比较好操作。
当然也因为好看，(⊙v⊙)嗯。

---

74的时候直接写了排序。
240的时候突然发现，哦，原来你想要的是搜索。
智障如我是这样的：从左往右看 如果一旦超过目标。那就去下一行。（真是暴力）

        while(i<m and j<n):
            if(matrix[i][j]==target):
                return True
            elif(matrix[i][j]<target):
                if(j==n-1):
                    if(i==m-1):
                        return False
                    else:
                        i=i+1
                        j=0
                else: 
                    j=j+1
            else:
                if(i<m-1):
                    i=i+1
                    j=0
                else:
                    return False

老脸一红。。。战胜了千分之一点六的py，丢你老母啊。
所以从右往左搜。。。这样比较快get到。
题目给出的规律是右大于左，下大于上。
所以比较快的路径是从右向左从上到下。这个方案战胜了70%
当然从下往上从左到右也可以。（真废话不都是O（m+n）吗）
但是智障的我从左到右从上到下就是O（m*n）了，GG

        while(i<m and j>=0):
            if(matrix[i][j]==target):
                return True
            elif((matrix[i][j]<target)):
                i=i+1
            else:
                j=j-1
        return False

53是经典的最大子段和 dp很好做，但是题目给了提示用分治法。
还是先dp了=。=
这题有坑，当数组全为负的时候，最大字段和不是0.(冤枉啊空集也是子集嘛)

        sum,b=nums[0],0
        for i in nums:
            if b>0:
                b=b+i
            else:
                b=i
            sum=max(sum,b)
        return sum

152还是dp的想法。

        r=nums[0]
        imax,imin=r,r
        for i in nums[1:]:
            if(i<0):
                imax,imin=imin,imax
            imax=max(i,imax*i)
            imin=min(i,imin*i)
            r=max(r,imax)
        return r

278折半

        l,r,m=0,n,(1+n)/2
        while(l<r):
            if(isBadVersion(m)):
                r=m
            else:
                l=m
            m=(l+r)/2
            if(l+1==r):
                return r

34比较水。

        flag1,flag2=True,True
        l,r=-1,-1
        n=len(nums)
        for i in range(n):
            if(nums[n-1-i]==target and flag2):
                flag2=False
                r=n-1-i
            if(nums[i]==target and flag1):
                flag1=False
                l=i
        return [l,r]

35折半

        while(l<=r):
            if(target<=nums[l]):
                return l
            if(target>nums[r]):
                return r+1
            if(target==nums[m]):
                return m
            if(l+1==r):
                return r
            elif(target>nums[m]):
                l,m=m,(l+r)/2
            else:
                r,m=m,(l+r)/2