Day6

作者: wendy_要努力努力再努力 | 来源:发表于2017-11-04 10:53 被阅读0次
  1. 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

  1. 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

相关文章

网友评论

      本文标题:Day6

      本文链接:https://www.haomeiwen.com/subject/vrdfmxtx.html