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
