小李飛刀：做題第六彈！

BigNerdCoding 發(fā)布于2019-07-31 10:08 / 3212人閱讀

摘要：給定的字符串只含有小寫英文字母，并且長(zhǎng)度不超過。其他這題了，要重做看了其他的人的題解，使用的是無限逼近中位值的辦法，理論基礎(chǔ)應(yīng)該是泰勒公式。萬萬沒想到居然用到了泰勒公式手工執(zhí)行了下算法，反而理解的更快，但是泰勒公式還得再?gòu)?fù)習(xí)下。

寫在前面的話

今天持續(xù)做題ing，python有意思~
今天的題有點(diǎn)虐心...興許是我太笨了...
會(huì)努力學(xué)習(xí)的！
動(dòng)態(tài)規(guī)劃我來啦~

開始做題

第一題

459. 重復(fù)的子字符串
難度：簡(jiǎn)單
給定一個(gè)非空的字符串，判斷它是否可以由它的一個(gè)子串重復(fù)多次構(gòu)成。給定的字符串只含有小寫英文字母，并且長(zhǎng)度不超過10000。
我的題解：

class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) <= 1 : return False
        res = []
        n = 0
        length = len(s)
        for i in range(1,length):
            if s[i] == s[0]:
                res.append(i)
        for i in range(1,length):
            a = s[:i]
            length_a = len(a)
            n = length/length_a
            if a * n == s:
                return True
        return False

我的思路：
參考了小佳揚(yáng)的思路后，重新寫了一遍。
主要是因?yàn)槿绻嬖谥貜?fù)的話，

第一個(gè)字母開始就會(huì)形成重復(fù)

最小字符串的長(zhǎng)度可以被字符串長(zhǎng)度給整除

那么就記錄下第一個(gè)字母每次出現(xiàn)的地方，檢查每次字符出現(xiàn)的前一段字符串是否可以形成重復(fù)。
其他：
寫的時(shí)候遇到一個(gè)坑，一直遇到報(bào)錯(cuò)
integer division or modulo by zero
檢查了一圈發(fā)現(xiàn)，是在第二個(gè)循環(huán)的時(shí)候，i從0開始作為除數(shù)，所以產(chǎn)生了報(bào)錯(cuò)。

第二題

5. 最長(zhǎng)回文子串 ----超時(shí)需要再解答
難度：中等
給定一個(gè)字符串s，找到s中最長(zhǎng)的回文子串。你可以假設(shè)s的最大長(zhǎng)度為 1000。
我的題解：

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        l = len(s)
        if len(s) <= 1:
            return s
        length = 0
        for i in range(0,l):
            for j in range(i+1,l+1):
                res = s[i:j]
                if res == res[::-1]: #逆向相等
                    if (len(res) > length):
                        mark = res #存儲(chǔ)數(shù)據(jù)
                        length = len(res)
        return mark

我的思路：
用的是最暴力的解法，雙重循環(huán)，逐個(gè)字段進(jìn)行比較，復(fù)雜度應(yīng)該是O(N2)
（這個(gè)復(fù)雜度超時(shí)很必然啊，被pia飛....
其他：
這題超時(shí)了，要重做!!!!
可以執(zhí)行通過較短的字符串，但是超過一定長(zhǎng)度之后就會(huì)超時(shí)。
建議使用動(dòng)態(tài)規(guī)劃，好好學(xué)習(xí)!!!重新做一次。

第三題

69. x 的平方根 ----超出內(nèi)存需要再解答
難度：簡(jiǎn)單
實(shí)現(xiàn)int sqrt(int x)函數(shù)。
計(jì)算并返回x的平方根，其中x是非負(fù)整數(shù)。
由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。
我的題解：

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        for i in range(x):
            if i**2 <= x and (i+1)**2 >x:
                return i

我的思路：
因?yàn)橹蝗≌麛?shù)部分，所以值會(huì)介于i的平方及i+1的平方之間。
其他：
這題Memory Error了，要重做!!!!
看了其他的人的題解，使用的是無限逼近中位值的辦法，理論基礎(chǔ)應(yīng)該是泰勒公式。
（萬萬沒想到居然用到了泰勒公式....
手工執(zhí)行了下算法，反而理解的更快，但是泰勒公式還得再?gòu)?fù)習(xí)下。

總結(jié)

今天的做題就到這里啦，還有很多要學(xué)習(xí)的地方~
數(shù)據(jù)結(jié)構(gòu)與算法要加油呀！