摘要:給定的字符串只含有小寫英文字母,并且長度不超過。其他這題了,要重做看了其他的人的題解,使用的是無限逼近中位值的辦法,理論基礎應該是泰勒公式。萬萬沒想到居然用到了泰勒公式手工執行了下算法,反而理解的更快,但是泰勒公式還得再復習下。
寫在前面的話
今天持續做題ing,python有意思~
今天的題有點虐心...興許是我太笨了...
會努力學習的!
動態規劃我來啦~
459. 重復的子字符串
難度:簡單
給定一個非空的字符串,判斷它是否可以由它的一個子串重復多次構成。給定的字符串只含有小寫英文字母,并且長度不超過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
我的思路:
參考了小佳揚的思路后,重新寫了一遍。
主要是因為如果存在重復的話,
第一個字母開始就會形成重復
最小字符串的長度可以被字符串長度給整除
那么就記錄下第一個字母每次出現的地方,檢查每次字符出現的前一段字符串是否可以形成重復。
其他:
寫的時候遇到一個坑,一直遇到報錯
integer division or modulo by zero
檢查了一圈發現,是在第二個循環的時候,i從0開始作為除數,所以產生了報錯。
5. 最長回文子串 ----超時需要再解答
難度:中等
給定一個字符串s,找到s中最長的回文子串。你可以假設s的最大長度為 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 #存儲數據 length = len(res) return mark
我的思路:
用的是最暴力的解法,雙重循環,逐個字段進行比較,復雜度應該是O(N2)
(這個復雜度超時很必然啊,被pia飛....
其他:
這題超時了,要重做!!!!
可以執行通過較短的字符串,但是超過一定長度之后就會超時。
建議使用動態規劃,好好學習!!!重新做一次。
69. x 的平方根 ----超出內存需要再解答
難度:簡單
實現int sqrt(int x)函數。
計算并返回x的平方根,其中x是非負整數。
由于返回類型是整數,結果只保留整數的部分,小數部分將被舍去。
我的題解:
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
我的思路:
因為只取整數部分,所以值會介于i的平方及i+1的平方之間。
其他:
這題Memory Error了,要重做!!!!
看了其他的人的題解,使用的是無限逼近中位值的辦法,理論基礎應該是泰勒公式。
(萬萬沒想到居然用到了泰勒公式....
手工執行了下算法,反而理解的更快,但是泰勒公式還得再復習下。
今天的做題就到這里啦,還有很多要學習的地方~
數據結構與算法要加油呀!
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/43301.html
摘要:第二題漢明距離難度簡單兩個整數之間的漢明距離指的是這兩個數字對應二進制位不同的位置的數目。給出兩個整數和,計算它們之間的漢明距離。第三題買賣股票的最佳時機難度簡單給定一個數組,它的第個元素是一支給定股票第天的價格。 寫在前面 這幾天斷斷續續做了題目,也在慢慢體會一些數據思維。終于不用邊做視頻邊寫題目啦~開心~把這幾天的題解發一下~ 認真做題的分割線 第一題 977. 有序數組的平方難度...
摘要:給定一個大小為的數組,找到其中的眾數。第五題合并兩個有序數組難度簡單給定兩個有序整數數組和,將合并到中,使得成為一個有序數組。說明初始化和的元素數量分別為和。第六題二叉樹的最大深度難度簡單給定一個二叉樹,找出其最大深度。 寫在前面的話 做做做題,慢慢上手了就覺得刷題速度變快了,果然還是有點笨~希望最后一竅快點通吧~ 開始做題 第一題 169. 求眾數難度:簡單給定一個大小為 n 的數組...
摘要:寫在前面今天沒有叨逼叨但是又一次錯過了競賽愛睡覺的小李下周要上班,下下周一定要參加了握拳認真做題的分割線第一題兩地調度公司計劃面試人。第人飛往市的費用為,飛往市的費用為。示例輸入輸出解釋第一個人去市,費用為。 寫在前面 今天沒有叨逼叨...但是又一次錯過了競賽...愛睡覺的小李...下周要上班,下下周一定要參加了(握拳 認真做題的分割線 第一題 1029. 兩地調度公司計劃面試2N人。...
摘要:認真做題的分割線第一題乘積最大子序列難度中等給定一個整數數組,找出一個序列中乘積最大的連續子序列該序列至少包含一個數。 寫在前面的話 慢慢轉變思路,不再死磕不會做的題,思路可以先借鑒,但是一定要吃透透。上周末看完看完了《算法圖解》,感覺對一些題目的思路有比較大的幫助,但是還是要在實踐中理解。 認真做題的分割線 第一題 152. 乘積最大子序列難度:中等給定一個整數數組nums,找出一個...
摘要:不過可能還沒有抓到動態規劃的真諦,總覺得哪里需要再校正下思路。這題也是動態規劃的題目,目標總是要分解為子問題??偨Y看算法圖解的時候,涉及動態規劃的小結中有這樣的每種動態規劃解決方案都涉及網格。 寫在前面的話 感覺做題越多遇到的寫法越多,有種躍躍欲試的感覺~ 認真做題 第一題 70. 爬樓梯難度:簡單假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。你有多少...
閱讀 929·2021-11-23 09:51
閱讀 993·2021-11-18 10:02
閱讀 1908·2021-09-10 11:27
閱讀 3139·2021-09-10 10:51
閱讀 779·2019-08-29 15:13
閱讀 2064·2019-08-29 11:32
閱讀 2502·2019-08-29 11:25
閱讀 3045·2019-08-26 11:46