- Count and Say
**思路:这道题做的我元气大伤,一度想要弃题,总是会有很多边边角角数不到。我的原始思路是,把字符串从左到右开始判断,如果相同,计数值加一,不同的话,重新开始计数,到最后的数,如果与倒数第二个相同还好 ,不同还得计一个新的数,看上去很简单的思路,但是一直报错,数组的Index会溢出。
class Solution(object):
def countStr(self,s):
count = 0;ans = "";tmp = s[0]
for i in range(len(s)):
if s[i] == tmp:
count += 1
else:
ans += str(count) + tmp
tmp = s[i];count = 1
ans += str(count) + tmp
return ans
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
ans = '1'
while n > 1:
ans = self.countStr(ans)
n -= 1
return ans
学会调用函数,学会简单化代码,我写的太乱了,你看看人家字符相同就计数加一,字符不同就换个基准字符,计数从1开始,前面的累加。我的怎么就这么乱
以下是我的失败版本:
class Solution(object):
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
if n == 1:
return '1'
str1 = '1'
while n >1:
i=0
str2 = ''
if len(str1) == 1:
str2 = '1'+str1[0]
str1 = str2
else:
while i < len(str1)-1:
count = 1
while str1[i]==str1[i+count]:
count +=1
if i+count == len(str1):
break
str2 = str2+str(count)+str1[i]
i = i +count
if str1[len(str1)-2] == str1[len(str1)-1]:
str1 = str2
else:
str1 = str2 + '1'+str1[len(str1)-1]
n-=1
return str1
- Maximum Subarray
**思路:终于开始用到动态规划了,乍一看从后往前推,这样可以避免动不动就index溢出了。后一个的最大值,后两个数组的子数组最大值,后三个数组成的数组的子数组的最大值。
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
sum1 = nums[-1]
maxSum= sum1
for i in range(len(nums)-2,-1,-1):
sum1 = max(nums[i],nums[i]+sum1)
maxSum = max(sum1,maxSum)
return maxSum
网友评论