Leetcode--string未鎖30道easy+medium題目全解（未完待續(xù)）

過年期間，筆者實(shí)在無聊，而且年后要找關(guān)于數(shù)據(jù)方面的實(shí)習(xí)，就用了大概3天空閑時間二刷了leetcode的string題目。截止筆者寫此篇日志，關(guān)于string的題目一共有55道，easy+medium免費(fèi)公開的題目共30道，筆者做了其中的27道，我就將我所做的28道題目的題解以及自己的一些想法留在簡書這個平臺。由于并不是什么算法大牛，所以我會不斷調(diào)整代碼。
PS：筆者用的語言是python，筆者的目的更多的是實(shí)現(xiàn)功能，因此有些題目也就因?yàn)槭莗ython就偷懶了，有機(jī)會再把性能更好的代碼貼出來。

3. Longest Substring Without Repeating Characters

題目：給一個長字符串s尋找最長的子字符串，該字符串內(nèi)沒有重復(fù)的字符。
思路：遍歷長字符串，當(dāng)字符在子字符串出現(xiàn)，首先比較原子字符串是否是目前最長子字符串，如果是將長度存在count中；然后，找到子字符串重復(fù)字符位置，該位置的下一個位置就是新子字符串開始的位置。
注意：
（1）str.find(ch)的使用，返回第一個匹配位置，否則返回。
（2）循環(huán)結(jié)束需要再次算長度，初學(xué)者容易忘記。

def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """
    count = 0
    tmp_str = ""
    
    for ch in s:
        if ch in tmp_str:
            count = max(count,len(tmp_str))
            tmp_str = tmp_str[tmp_str.find(ch)+1:]
        tmp_str += ch
    count = max(count,len(tmp_str))
    return count

5. Longest Palindromic Substring

題目：尋找字符串中的最長回文字字符串。
思路：回文字符串有兩種，因此我們要分兩種情況，分別是“AA”和“ABA”。遍歷長字符串，看是否滿足兩種情況，如果滿足就像兩個方向上延伸，并記錄最長的那個子回文字符串。
注意：
（1）邊界的判斷
（2）我在s字符串后加了一個空格' '。目的是人工創(chuàng)建了一個邊界而不影響原字符串的特征，這樣我就可以不用檢測右側(cè)邊界了。

def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str

    """
    result= s[0]
    s = s+' '
    for num,ch in enumerate(s[:-1]):
        if ch == s[num+1]:
            point,len_pal = num,1
            while point+1-len_pal !=-1  and s[point+1-len_pal] == s[point+len_pal]:len_pal+=1
            len_pal-=1
            if len(result) <= len_pal*2 : result = s[point+1-len_pal:point+len_pal+1]
        if num-1!=-1 and s[num-1] == s[num+1]:
            point,len_pal = num,1
            while point-len_pal !=-1 and s[point+len_pal] == s[point-len_pal]:len_pal+=1
            len_pal-=1
            if len(result) <= len_pal*2+1 : result = s[point-len_pal:point+1+len_pal]             
    return result

6. ZigZag Conversion

題目：

P A H N
A P L S I I G
Y I R

用字符串表示為"PAHNAPLSIIGYIR"，我們要寫一個函數(shù)，函數(shù)的功能如下：

convert("PAYPALISHIRING", 3)
return "PAHNAPLSIIGYIR"

思路：這個題目主要就是找到回形針模式下字符串的規(guī)律，將給的字符串進(jìn)行三部分處理：第一行，中間數(shù)行，最后一行。原因很簡單，只有中間數(shù)行在一次回形針模式輸出中輸出兩次。數(shù)學(xué)規(guī)律并不難找，參考代碼即可。
注意：
（1）T是一個循環(huán)周期有多少字符數(shù)，row是處理回形針模式內(nèi)的所在行，offset是字符所在位置。
（2）中間行也可能輸出一次，出現(xiàn)這種情況只能是在最后一個不完整的周期內(nèi)。

def convert(self, s, numRows):
    """
    :type s: str
    :type numRows: int
    :rtype: str
    """
    if numRows == 1 or not s : return s
    
    T,row,offset= (numRows-2)*2+2,1,0
    result = ""
    for offset in range(0,len(s),T):result+=s[offset]
    while(numRows - row -1):
        for offset in range(row,len(s),T):result = result+s[offset]+s[offset+T-2*row] \
        if offset+T-2*row < len(s) else result+s[offset]
        row+=1
    for offset in range(numRows-1,len(s),T):result+=s[offset]
    return result

8. String to Integer (atoi)

12. Integer to Roman

題目：將整型數(shù)字轉(zhuǎn)化為羅馬數(shù)字（字符串）。
思路：暴力蛤希表，羅馬數(shù)字的規(guī)則請自行百度谷歌。暴力代碼如下（碼的挺累的）
注意：哈希表中加入0這個元素，可以有效地減少代碼量。
補(bǔ)充：/和//的區(qū)別。如果除數(shù)與被除數(shù)都是整型，結(jié)果是一樣的。問題出在如果除數(shù)為浮點(diǎn)數(shù)，那么結(jié)果雖然同為浮點(diǎn)數(shù)，但/的結(jié)果是向下取整，而//的結(jié)果是四舍五入。

def intToRoman(self, num):
    """
    :type num: int
    :rtype: str
    """
    dict={0:"",1:"I",2:"II",3:"III",4:"IV",5:"V",6:"VI",7:"VII",8:"VIII",9:"IX",\
    10:"X",20:"XX",30:"XXX",40:"XL",50:"L",60:"LX",70:"LXX",80:"LXXX",90:"XC",\
    100:"C",200:"CC",300:"CCC",400:"CD",500:"D",600:"DC",700:"DCC",800:"DCCC",900:"CM",\
    1000:"M",2000:"MM",3000:"MMM"}
    
    result = ""
    for i in range(3,-1,-1):
        tmp = num/(10**i)
        result += dict[tmp*(10**i)]
        num %=10**i
    return result

13. Roman to Integer

題目：將羅馬數(shù)字（字符串）轉(zhuǎn)化為整型數(shù)字。
思路：當(dāng)羅馬數(shù)字5，50，500左側(cè)出現(xiàn)1，10，100是右減左，其他都是順次做加法。因此，代碼如下。

def romanToInt(self, s):
    """
    :type s: str
    :rtype: int
    """
    roman = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
    z = 0
    for i in range(0, len(s) - 1):
        if roman[s[i]] < roman[s[i+1]]:
            z -= roman[s[i]]
        else:
            z += roman[s[i]]
    return z + roman[s[-1]]

14. Longest Common Prefix

題目：尋找字符串?dāng)?shù)組中最長的公共前綴
思路：遍歷數(shù)組即可。

def longestCommonPrefix(self, strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    result = strs[0] if strs else ""
    for str in strs:
        for num in range(min(len(str),len(result))):
            if str[num]!=result[num]:
                result = result[:num]
                break
        result = result[:min(len(str),len(result))]
        if not result: return ""
    return result

17. Letter Combinations of a Phone Number

題目： 給一個數(shù)字字符串，返回所有可能的字符串組合（數(shù)字與字符的映射關(guān)系參照手機(jī)）
思路：建立一個哈希表，用以表示數(shù)字和字母間的映射關(guān)系。主體是兩個循環(huán)，第一個循環(huán)的給定字符串中的數(shù)字，第二個循環(huán)是相應(yīng)數(shù)字的不同字符。
注意：拷貝方式，這里我們用result = tmp[:]用以表示result拷貝tmp內(nèi)的所有內(nèi)容，而不是兩個變量都指向同一個數(shù)組地址，否則改變?nèi)魏我粋€變量，數(shù)組的改變都是聯(lián)動的。

def letterCombinations(self, digits):
    """
    :type digits: str
    :rtype: List[str]
    """
    if not digits: return []
    dict = {1:"*",2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz",0:" "}
    result = [""]
    for digit in digits:
        tmp = []
        for ch in dict[int(digit)]:
            tmp += [element+ch for element in result]
        result = tmp[:]
    return result

20. Valid Parentheses

題目：給一個字符串只包含'(', ')', '{', '}', '[' 和 ']'，問字符串是否符合閉合規(guī)則。
思路：標(biāo)準(zhǔn)棧的題目，只要處理好進(jìn)棧和出棧的順序即可。
注意：如何數(shù)組為空，調(diào)用list.pop()會報錯。

def isValid(self, s):
    """
    :type s: str
    :rtype: bool
    """
    dict= {"(":")","[":"]","{":"}"}
    
    stack = ["0"]
    
    for ch in s:
        if ch in dict : stack.append(dict[ch])
        else:
            if not ch == stack.pop(): return False
    return True if stack ==["0"] else False

22. Generate Parentheses

題目：給定n組括號（），將所有括號的組合列舉出來。比如n=3:

["((()))","(()())","(())()","()(())","()()()]

思路：標(biāo)準(zhǔn)的回溯算法題目。

def helper(self, part, left, right, result):
    if left: self.helper(part+'(', left-1, right, result)
    if right > left: self.helper(part+')', left, right-1, result)
    if not right: result.append(part)
    return result
def generateParenthesis(self, n):
    """
    :type n: int
    :rtype: List[str]
    """
    return self.helper("",n,n,[])

28. Implement strStr()

題目：在一個字符串中找一個與給定值相等的字符串。
思路：暴力遍歷，我們直接進(jìn)行了字符串比較而不是字符比較，所以損失些性能，但寫起來更簡單。

def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    if not len(needle) : return 0
    if len(needle) > len(haystack) : return -1
    for num in range(len(haystack[:len(haystack)-len(needle)+1])):
        print num
        if haystack[num:num+len(needle)] == needle:return num
    return -1

38. Count and Say

題目：給一個整數(shù)n，按照下面規(guī)律找第n個序列。

1 被讀作 "one 1" or 11.
11 被讀作 "two 1s" or 21.
21 被讀作 "one 2, 然后 one 1" or 1211.

思路：以“1”開始循環(huán)n-1次，用count變量計數(shù)，遇到前后不相等的情況就更新數(shù)據(jù)，從而得到最后序列。
注意：在result后面加0，0不可能與之前的數(shù)字相等，所以當(dāng)循環(huán)的下一個為0時，一定會調(diào)用else里面的內(nèi)容，這樣可以減少代碼量。

def countAndSay(self, n):
    """
    :type n: int
    :rtype: str
    """
    result = "1"
    
    for i in range(n-1):
        count,tmp = 1,""
        result+="0"
        for ch in range(len(result[:-1])):
            if result[ch] == result[ch+1]: count+=1
            else:
                tmp = tmp+str(count)+result[ch]
                count = 1
        result = tmp[:]
    return result

43. Multiply Strings

作為python選手，我就先不想那么多。。。。。

def multiply(self, num1, num2):
    """
    :type num1: str
    :type num2: str
    :rtype: str
    """
    return str(int(num1)*int(num2))

49. Group Anagrams

題目：對同字母異序詞進(jìn)行分類。
思路：說話講，這道題目我參考了discuss區(qū)大神的解法，所以在這里注明下，代碼十分簡潔。其實(shí)主要就是幾次基于原有列表的排序。sorted(strs, key=sorted)根據(jù)列表中每一個自排序后的字符串進(jìn)行排序，比如：

input: ["a","da","c"]
output:["a","da","c"]

itertools.groupby(list, sorted)的意思是按照排序進(jìn)行分組，所以比如說"abb","bab"就是存在同一個二級列表中。sorted(members)的意義是對二級列表內(nèi)元素進(jìn)行排序。代碼如下：

def groupAnagrams(self, strs):
    """
    :type strs: List[str]
    :rtype: List[List[str]]
    """
    groups = itertools.groupby(sorted(strs, key=sorted), sorted)
    return [sorted(members) for _, members in groups]

58. Length of Last Word

題目：找一個字符串中的最后一個單詞的長度。
思路：先把兩端的空格刪去，然后從最后一個字符開始統(tǒng)計，遇到空格就跳出循環(huán)，返回正確值。

def lengthOfLastWord(self, s):
    """
    :type s: str
    :rtype: int
    """
    s = s.strip()
    if not s : return 0
    count = 0
    for ch in s[::-1]:
        if ch !=' '  : count+=1
        else : break
    return count

67. Add Binary

題目：兩個二進(jìn)制數(shù)相加。
思路：python玩家不要多想，直接調(diào)用函數(shù)就好。
注意：bin轉(zhuǎn)換后，得到的是字符串，格式："0bXXXXX"，所以要[2:]

def addBinary(self, a, b):
    """
    :type a: str
    :type b: str
    :rtype: str
    """
    return bin(int(a,2)+int(b,2))[2:]

71. Simplify Path

題目：化簡所給路徑為絕對路徑
思路：將原字符串按斜杠進(jìn)行分割成一個列表。然后借助棧來處理。".."代表著pop()；"."代表著無操作。最后再將結(jié)果join成字符串。

def simplifyPath(self, path):
    """
    :type path: str
    :rtype: str
    """
    path_list = path.split("/")
    stack= []
    for str in path_list:
        if not str.strip() or str.strip() == "." or(str.strip() == ".." and not stack): continue
        elif str.strip() == ".." and stack: stack.pop()
        else: stack.append(str)
    return '/'+'/'.join(stack)

91. Decode Ways

題目：

'A' -> 1
'B' -> 2
...
'Z' -> 26

給一個數(shù)字，問有多少種解讀方式。
思路：主體思路是動態(tài)規(guī)劃。然后就是對情況的總結(jié)，順次5種情況，先后順序一定要注意。

def numDecodings(self, s):
    """
    :type s: str
    :rtype: int
    """
    if not len(s) : return 0
    DP = [1,1]
    s = "0"+s
    
    for num in range(1,len(s),1):
        tmp = int(s[num-1:num+1])
        if tmp ==10 or tmp ==20: DP.append(DP[-2])
        elif not tmp%10 : return 0
        elif tmp<10: DP.append(DP[-2])
        elif tmp>10 and tmp<27:DP.append(DP[-2]+DP[-1])
        else: DP.append(DP[-1])
    return DP[-1]

93. Restore IP Addresses

題目：給一個只包含數(shù)字的字符串。將其不同的IP組合存入一個列表中。

"25525511135"
["255.255.11.135", "255.255.111.35"]

思路：標(biāo)準(zhǔn)的動態(tài)規(guī)劃+回溯法。當(dāng)連續(xù)順次的4個數(shù)字字符串能夠組合且不多余數(shù)字的時候，就是一個合格的子答案。所有的答案都儲存在列表中。
注意：不能有以0為開頭的數(shù)字。

def restoreIpAddresses(self, s):
    """
    :type s: str
    :rtype: List[str]
    """
    result = []
    if len(s) > 15: return result
    self.helper(4,s,"",result)
    return result
    
def helper(self,n,new_s,tmp_result,result):
    if n == 0 and len(new_s) == 0:
        result.append(tmp_result[1:])
    for i in range(3): 
        if i < len(new_s) and int(new_s[:i+1]) < 256:
            self.helper(n-1,new_s[i+1:],tmp_result+'.'+new_s[:i+1],result)
            if new_s[0] == "0" : break
        else: break

未完待續(xù)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • leetcode刷題記錄本文記錄一下leetcode刷題記錄，記錄一下自己的解法和心得。 LeetCode Two...
    EarthChen閱讀 3,599評論 0贊 6
  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪：刷leetcod...
    土汪閱讀 12,899評論 0贊 33
  • 1. Java基礎(chǔ)部分 基礎(chǔ)部分的順序：基本語法，類相關(guān)的語法，內(nèi)部類的語法，繼承相關(guān)的語法，異常的語法，線程的語...
    子非魚_t_閱讀 34,642評論 18贊 399
  • 不知道在你23歲以前，有沒有人給你過生日？ 好像，有過一次，初中的時候。 不管怎么樣，都希望你在新的一歲要懂事，好...
    減肥的女孩閱讀 500評論 0贊 1
  • 還是那句老話，只提想法，不論證可行性。 ■ 關(guān)于官方專題的審稿 我時常會遇到這樣的情況，投《首頁投稿》被拒，后來又...
    逸之閱讀 856評論 6贊 6

友情鏈接更多精彩內(nèi)容