国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

leetcode第5題,最長回文子串

2019-11-08 03:08:33
字體:
來源:轉載
供稿:網友
一開始用的窮舉法,時間直接超了,后來稍作修改才被accept,但是只是打敗了70%的人。后來找到了大神寫的代碼,現在直接粘上如下: if (s.size() < 2) return s; int len = s.size(), max_left = 0, max_len = 1, left, right; for (int start = 0; start < len && len - start > max_len/2;) { left = right = start; while (right < len - 1 && s[right + 1] == s[right]) ++right; start = right + 1; while (right < len - 1 && left > 0 && s[right + 1] == s[left - 1]) { ++right; --left; } if (max_len < right - left + 1) { max_left = left; max_len = right - left + 1; } } return s.substr(max_left, max_len);

start每次從上次的沒有重復的right+1開始。 while (right < len - 1 && s[right + 1] == s[right]) ++right; 這個循環語句是考慮有連續字符的情況,比如“cbbd”,如果沒有這個循環 那么最后找到的答案是”c”,而不是“bb”。right一直加到沒有相等字符為止(不管是奇數個bbb還是偶數個bb)都是回文。 再次考慮這個while循環的意義,如果連續字符的個數是奇數,比如說“cbbbd”,沒有這個循環的話倒也檢測得出來(從start等于2開始檢測,可以檢出中間的bbb),可是如果連續字符的個數是偶數,比如說“cbbd”,那么沒有這個循環就檢測不出來了。如果是”cbbbbd”,那么只能檢測出三個。 綜上,這個循環是很重要的。然后start每次都要在right的基礎上加1。 后半部分的代碼則很好理解了。 需要注意的是,for循環里的條件,不能將len-start>maxlen/2換成len-start>maxlen.否則的話,“kanana”返回的結果是”ana”,因為在start=3的時候len-start=3,而maxlen也等于3。 其實可以刪去len-start>maxlen/2這句話,還是可以accepted。只不過最后會浪費一些時間。 這里的len-start>maxlen/2,maxlen/2選取的也很有講究。從start開始,剩下的字符串長度就是len-start,那么可能的回文串就是兩種情況,要么是len-start(連續的字符),要么是2(len-start)-1,所以要保證len-start>maxlen,或者2(len-start)-1>maxlen。而這里實際取了比這兩個條件還要寬松的條件。也就是len-start>maxlen/2。就是為了寧愿浪費時間也不要漏掉。


上一篇:CAS和ABA問題

下一篇:Crackme 4

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 木兰县| 新沂市| 浦县| 交城县| 睢宁县| 武穴市| 安塞县| 保山市| 威海市| 丹棱县| 四平市| 平和县| 黄骅市| 吴旗县| 石景山区| 信丰县| 韩城市| 皮山县| 梨树县| 大石桥市| 元氏县| 洮南市| 恩平市| 叙永县| 富川| 尼勒克县| 璧山县| 凤庆县| 兴山县| 温泉县| 仁寿县| 永春县| 威海市| 喀什市| 北安市| 延安市| 潞西市| 客服| 乌海市| 朝阳区| 岚皋县|