leetcode解题报告-字符串

本贴最后更新于 2166 天前,其中的信息可能已经时异事殊

如果说链表让人又爱又恨的话,那么对字符串就只剩下恨了。个人认为,字符串题目是 leetcode 中最具备挑战性的,然而也是我们在日常编程中最常遇到的问题之一,因此学好字符串是非常重要的。

字符串是题型最多变的考点,通常考察点有子串、回文、数学、编辑距离、括号问题、模式匹配、类型转换、按要求格式化等等等等,采用的方法通常有栈、状态机、滑动窗口、哈希表、动态规划等。通常解法灵活多变。我暂时还没能力像链表一样对字符串题目进行比较好的归类和总结,因此只是把 leetcode 的题罗列在下。希望日后能有更深的理解,再来进一步总结。


##3.Longest Substring Without Repeating Characters (子串)

  • 难度:Medium

  • 题意:
    给定一个字符串,要求找出不重复的最长子串长度。

  • 思路:
    使用两个下标,每次尝试把 s[j]加入到字串 s[i:j]中,若 s[i:j]中不存在 s[j],则 j+=1,否则 i 向前推进到和 s[j]重复的索引的下一个。即,j 是每次 1 步向前推进,i 是每次跳跃到与 s[j]重复的下一个。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {integer}
          def lengthOfLongestSubstring(self, s):
              if not s:return 0
              s = ''.join([s,'#'])
              i,j = 0,1
              max = 1
              while j < len(s):
                  index  = s[i:j].find(s[j])
                  if index >= 0 or s[j] == '#':
                      if j - i > max:
                          max = j-i
                      i += index+1
                  j += 1
              return max
    

##5.Longest Palindromic Substring (回文子串)

  • 难度:Medium

  • 题意:
    给定字符串 s,找出最长回文字串。假定字符串最大长度为 1000,且仅存在唯一一个最长回文子串。

  • 思路:
    我这里挤破脑袋,只能想到最傻的办法,由于字符串最大长度只有 1000,所以时间上允许我这么做。遍历字符串,若该处可能成为回文串中心(奇和偶),则向两侧探索。
    不要小看代码中的 len(s)-it>len(subStr)/2,这个条件能减掉 1 半的枝,使时间缩短 1 半。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {string}
          def longestPalindrome(self, s):
              if not s or len(s) == 1:
                  return s
              subStr = ''
              it = 1
              s = ''.join(['~',s])
              while it < len(s)-1 and len(s)-it>len(subStr)/2:
                  if not(s[it] == s[it+1] or s[it-1] == s[it+1]):
                      it += 1
                      continue
                  if s[it] == s[it+1]:
                      l,r = it,it+1
                      subStr = self.trylr(s,l,r,subStr)
                  if s[it-1] == s[it+1]:
                      l,r = it-1,it+1
                      subStr = self.trylr(s,l,r,subStr)
                  it += 1
              return subStr
    
          def trylr(self,s,l,r,sub):
              while l>0 and r<len(s) and s[l]==s[r]:
                  l,r=l-1,r+1
              if r-l-1 > len(sbu):return s[l+1:r]
              else:return sub
    
  • 思路 2:
    思路一是最直观但也是最笨的办法。仔细思考,我们还得在思路 1 的基础上进行剪枝。回文串的处理最大的难度之一在于奇串和偶串,我们可以进一步把回文串的格式概括为以下格式:sub1+[s]*n+sub2。意思是,回文串的中间是 n 个相同的字母(n 可以是奇数也可以是偶数,当然也可以是 1),左右两侧是镜像对称的两个字符串。那么我们在判断是否为回文串的时候,可以直接找到中间相同的字符,再往两侧延伸。而且,更为关键的是,查找下一回文串的时候,可以直接跳过该中间重复字符(这个是最为关键的剪枝)。
    *代码 2:(参考大神的代码)

      def longestPalindrome(self, s):
          lenS = len(s)
          if lenS <= 1: return s
          minStart, maxLen, i = 0, 1, 0
          while i < lenS:
              if lenS - i <= maxLen / 2: break
              j, k = i, i
              while k < lenS - 1 and s[k] == s[k + 1]: k += 1
              i = k + 1
              while k < lenS - 1 and j and s[k + 1] == s[j - 1]:  k, j = k + 1, j - 1
              if k - j + 1 > maxLen: minStart, maxLen = j, k - j + 1
          return s[minStart: minStart + maxLen]
    

##6. ZigZag Conversion (格式化)

  • 难度:Easy

  • 题意:
    给定一个字符串,以 ZigZag 形式排列(大概以“N”的形式),然后按行重新排列。

  • 思路:
    没有特殊的方法,只要把题目的意思看懂就 ok 了,按照题目要求去做就行,找到字符序号和位置的相对关系。

  • 代码:

      class Solution:
          # @param {string} s
          # @param {integer} numRows
          # @return {string}
          def convert(self, s, numRows):
              if numRows == 1 or numRows >= len(s):
                  return s
              zig = [[] for i in range(numRows)]
              if numRows == 2:
                  return ''.join([''.join(s[::2]),''.join(s[1::2])])
              for i in range(len(s)):
                  rn = i%(2*numRows-2)
                  if rn<numRows:
                      zig[i%(2*numRows-2)].append(s[i])
                  else:
                      zig[2*numRows-2-rn].append(s[i])
              return ''.join(''.join(zig[i]) for i in range(numRows))
    

##8. String to Integer (类型转换)

  • 难度:Easy

  • 题意:
    实现 atoi 把字符串转化为数字。

  • 思路:
    面试最爱出的题目之一,重点考察对特殊情况的覆盖和处理,空字符,‘+/-’,非数字,溢出等。

  • 代码:

      class Solution:
      # @param {string} str
      # @return {integer}
      def myAtoi(self, str):
          str = str.lstrip()
          if not str: return 0
          for i in range(len(str)):
              if not('0'<=str[i]<='9' or str[i] in('+','-')):
                  str = str[:i:]
                  break
          try:
              f = 1
              intx = int(str)
              if intx >= 2147483647:
                  intx = 2147483647
              elif intx <= -2147483648:
                  intx = -2147483648
              return intx
          except:
              return 0
    

##10. Regular Expression Matching (模式匹配)

  • 难度:Hard

  • 题意:
    实现支持'.'和''的正则表达式。'.'匹配任何一个字符,''匹配一个或多个之前的字符。给出的表达式需要匹配整个字符串

  • 思路:
    翻回来,看到我自己的这个代码,也是无语了,我居然直接调用了 python 的 re 模块。。。。。。这道题就是要我实现这个。。。

  • 代码:

      import re
      class Solution:
          # @param {string} s
          # @param {string} p
          # @return {boolean}
          def isMatch(self, s, p):
              pattern = re.compile(p)
              match = pattern.match(s)
              if match:
                  if match.group() == s:
                      return True
              return False
    
  • 思路:
    好吧这回好好地思考以下,毕竟是一道 Hard 题。这道题的最难点在于 *,因为其可以匹配 0 个或多个字符,这使得直接遍历来匹配不可能实现。换个角度,递归行不行?这道题剪枝行不行?都还不行,那就是动态规划了。我认为,DP 是水平的分界线:完全不会 DP 的人,看得懂 DP 的人,可以设计 DP 的人。
    言归正传,我们以 dp[i][j]=True,表示前 i 个字母(s[0:i])可以匹配前 j 个模式(p[0:j])。

    • 若 p[j-1]不是 *,意味着在 dp[i-1][j-1]=True 的前提下,p[j-1]必须是 . 或等于 s[i-1],才可能匹配。
    • 若 p[j-1]是 *:
      • dp[i][j-2]匹配,p[j-2]* 表示 0 个字符
      • dp[i-1][j]匹配,p[j-2]* 多表示 1 个 s[i-1],则 p[j-2]必须是 s[i-1]或 .
  • 代码:

      class Solution:
          # @param {string} s
          # @param {string} p
          # @return {boolean}
          def isMatch(self, s, p):
              lens,lenp = len(s),len(p)
              dp = [[False]*(lenp+1) for i in range(lens+1)]
              dp[0][0]=True
              for j in range(2,lenp+1):
                  dp[0][j] = dp[0][j-2] and p[j-1]=='*'
    
              for i in range(1,lens+1):
                  for j in range(1,lenp+1):
                      if p[j-1]=='*':
                          dp[i][j] = dp[i][j-2] or dp[i-1][j] and p[j-2] in (s[i-1],'.')
                      else:
                          dp[i][j]=dp[i-1][j-1] and p[j-1] in (s[i-1],'.')
              return dp[lens][lenp]
    

##44. Wildcard Matching (模式匹配)

  • 难度:Hard

  • 题意:
    实现支持 ?* 的通配符匹配模式。
    ? 匹配任意单个字符
    * 匹配任意字符串序列,包括 0 个字符。注意和第 10 题的区别。

  • 思路:
    T.T。。。我居然变着法去调用 re 模块,然后也是通过了。。。。把 ? 替换成 .,把字符串以*分隔,然后分段用 re 去匹配。这份代码又臭又长,请直接看思路 2。

  • 代码:

      import re
      class Solution:
          # @param {string} s
          # @param {string} p
          # @return {boolean}
          def isMatch(self, s, p):
              if p == s:
                  return True
              if not p:
                  return False
              p = p.replace('?','.')
              ##split p by '*'
              plist = p.split('*')
              begin = 0
              for i,psplit in enumerate(plist):
                  if '.' in psplit:
                      ##last one
                      if i == len(plist)-1:
                          begin = self.regularMatch(s,psplit,begin,1)
                          if p[-1]!='*' and begin+len(psplit) !=len(s):
                              return False
                      else:
                          begin = self.regularMatch(s,psplit,begin,0)
                      if begin == -1:
                          return False
                      ## first one
                      if i==0 and p[0] != '*' and begin!= 0:
                          return False
                      begin += len(psplit)
                  else:
                      ##last one
                      if i == len(plist)-1:
                          lb = s.rfind(psplit)
                          if lb < begin:
                              return False
                          else:
                              begin = lb
                              if p[-1]!='*' and begin+len(psplit) !=len(s):
                                  return False
                      else:
                          begin = s.find(psplit,begin)
                      if begin == -1:
                          return False
                      ##first one
                      if i==0 and p[0] != '*' and begin!= 0:
                          return False
                      begin += len(psplit)
              return True
    
          def regularMatch(self, s, p,begin,islast):
                  pattern = re.compile(p)
                  result = pattern.search(s,begin)
                  if not result:
                      return -1
                  if not islast:
                      return result.start()
                  if islast:
                      while result:
                          begin = result.start()
                          result = pattern.search(s,begin+1)
                      return begin
    
  • 思路 2:我是不是有点不按套路出牌啊。正经来说,我们应该考虑以下动态规划的解法。我们以 dp[i][j]=True,表示前 i 个字母(s[0:i])可以匹配前 j 个模式(p[0:j])。

    • 若 p[j-1]不是 *,意味着在 dp[i-1][j-1]=True 的前提下,p[j-1]必须是 ? 或等于 s[i-1],才可能匹配。
    • 若 p[j-1]是 *:
      存在 dp[k][j-1]=True,1<=k<=i。因为*可以与任意 s[k:i]匹配

奇怪,搞不懂,代码报超时的 Testcase,我跑了以下均在 100ms 以内。
DP 通常会有多种解决方法,关键在于 DP 如何定义。这道题还可以使用一维 dp 能解决。

  • 代码:

      class Solution:
          # @param {string} s
          # @param {string} p
          # @return {boolean}
          def isMatch(self, s, p):
              lens,lenp = len(s),len(p)
              if lenp-p.count('*')>lens:return False
              dp = [[False]*(lenp+1) for i in range(lens+1)]
              dp[0][0]=True
              for j in range(1,lenp+1):
                  dp[0][j] = dp[0][j-1] and p[j-1]=='*'
    
              for i in range(1,lens+1):
                  for j in range(1,lenp+1):
                      if p[j-1]!='*':
                          dp[i][j]=dp[i-1][j-1] and p[j-1] in (s[i-1],'?')
                      else:
                          flag = 0
                          for k in range(i,-1,-1):
                              if dp[k][j-1]:
                                  dp[i][j],flag=True,1
                                  break
                          if not flag:
                              dp[i][j]=False
    
              return dp[lens][lenp]
    

##12. Integer to Roman (类型转换)

  • 难度:Medium

  • 题意:
    给一个数字,转化成罗马数字表示。输入数字范围在 1 到 3999 之间。

  • 思路:
    先了解以下罗马数字的表示法:I 代表 1,V 代表 5,X 代表 10,L 代表 50,C 代表百,D 代表 500,M 代表 1000。放在更高阶符号左边表示减,右边表示加,不允许出现 3 个以上同阶符号。这个代码不可避免会比较长,但是思路确是很简单。

  • 代码:

      class Solution:
          # @param {integer} num
          # @return {string}
          def intToRoman(self, num):
              roman=''
              roman = ''.join([roman,'M'*(num//1000)])
              num %= 1000
              if num//100<4:
                  roman = ''.join([roman,'C'*(num//100)])
              elif num//100==4:
                  roman = ''.join([roman,'CD'])
              elif num//100<9:
                  roman = ''.join([roman,'D','C'*(num//100-5)])
              else:
                  roman = ''.join([roman,'CM'])                
              num %= 100
              if num//10<4:
                  roman = ''.join([roman,'X'*(num//10)])
              elif num//10==4:
                  roman = ''.join([roman,'XL'])
              elif num//10<9:
                  roman = ''.join([roman,'L','X'*(num//10-5)])
              else:
                  roman = ''.join([roman,'XC']) 
              num %= 10
              if num<4:
                  roman = ''.join([roman,'I'*num])
              elif num==4:
                  roman = ''.join([roman,'IV'])
              elif num<9:
                  roman = ''.join([roman,'V','I'*(num-5)])
              else:
                  roman = ''.join([roman,'IX'])
              return roman
    

##13. Roman to Integer (类型转换)

  • 难度:Easy

  • 题意:
    给一个字符串表示的罗马数字,转化阿拉伯数字表示。输入数字范围在 1 到 3999 之间。

  • 思路:
    和上一题刚好是相反,然而确是简单了许多。若当前符号不大于前一个符号,直接加上,相反则需要减去之前那个符号。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {integer}
          def romanToInt(self, s):
              ints = pre = 0
              mp = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
              for i in range(len(s)):
                  if mp[s[i]]<=pre:ints += mp[s[i]]
                  else:ints = ints - 2*pre + mp[s[i]]
                  pre = mp[s[i]]
              return ints
    

##14. Longest Common Prefix (子串)

  • 难度:Easy

  • 题意:
    给定一个字符串数组,找出最长公共前缀

  • 思路:
    由于是公共前缀,只需要以第一个字符串的前缀去匹配其他字符串即可。

  • 代码:

      class Solution:
          # @param {string[]} strs
          # @return {string}
          def longestCommonPrefix(self, strs):
              if not strs:return ''
              if len(strs)==1:return strs[0]
              for i in range(1,len(strs[0])+1):
                  for j in range(1,len(strs)):
                      if strs[j].find(strs[0][:i])!=0:
                          if not i:return ''
                          else:return strs[0][:i-1]
              return strs[0]
    

##17. Letter Combinations of a Phone Number (格式化)

  • 难度:Medium

  • 题意:
    手机九宫格,输入一个字符串代表的数字,输出所有可能的字母组合。

  • 思路:
    最直观的思路就是做笛卡尔乘积即可。
    这里也可用递归回溯来实现。题目比较简单就不单独实现了。

  • 代码:

      class Solution:
          # @param {string} digits
          # @return {string[]}
          def letterCombinations(self, digits):
              digitsMap={'2':['a','b','c'],
                         '3':['d','e','f'],
                         '4':['g','h','i'],
                         '5':['j','k','l'],
                         '6':['m','n','o'],
                         '7':['p','q','r','s'],
                         '8':['t','u','v'],
                         '9':['w','x','y','z'],
                         '1':[],'0':[]}
              result = []
              for i in digits:
                  result = self.mass(result,digitsMap[i])
              return result
    
          def mass(self,lista,listb):
              if not lista:return listb
              if not listb:return lista
              result = []
              for a in lista:
                  for b in listb:
                      result.append(''.join([a,b]))
              return result
    

##20. Valid Parentheses(括号问题)

  • 难度:Easy

  • 题意:
    给定一个字符串,只包含 (){}[],检测该字符串是否有效,即括号是否能匹配。

  • 思路:
    使用栈,当是左括号时,压入栈,当是右括号时,弹出栈顶,检查是否匹配。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {boolean}
          def isValid(self, s):
              m = {'(':')','[':']','{':'}'}
              stacklist = []
              for p in s:
                  if p in('(','{','['):
                      stacklist.append(p)
                  else:
                      if not stacklist or p != m[stacklist[-1]]:
                          return False
                      else:
                          stacklist.pop()
    
              if not stacklist:return True
              else:return False
    

##22. Generate Parentheses (括号问题)

  • 难度:Medium

  • 题意:
    给定 n 对小括号,要求写出所有合法的形式。

  • 思路:
    由于都是小括号,在左边是完整模式时,下一个必须是左括号。在以上前提下,只要把 n 个左括号和 n 个右括号全部消费完即可。使用递归,记录目前左括号和右括号的消费情况。

  • 代码:

    class Solution:
    # @param {integer} n
    # @return {string[]}
    def generateParenthesis(self, n):
    self.result = []
    left = right = n
    self.generate('',left,right)
    return self.result

      def generate(self,seq,left,right):
          if left == right == 0:
              self.result.append(seq)
          elif left == right: 
              self.generate(''.join([seq,'(']),left-1,right)
          elif left < right:
              if left:
                  self.generate(''.join([seq,'(']),left-1,right)
              if right:
                  self.generate(''.join([seq,')']),left,right-1)
    

##28. Implement strStr() (子串)

  • 难度:Easy

  • 题意:
    实现 strStr(),也就是寻找子串在母串中的第一次出现位置,若无出现返回-1

  • 思路:
    也就是让我们实现 python 里的 find 函数,然而我又一次直接调用 find 然后 AC 了。这道题是典型的查找字串问题,使用暴力方法时间复杂度是 O(m*n)。当然我们也不会忘记算法课那个让我们头疼的 KMP 算法,时间复杂度是 O(m+n)。这里我先实现暴力方法,用两个下标太麻烦,我干脆直接用了递归。实现完之后发现这种暴力的方法和 python 的 find 时间是基本一样的,都是 40+ms,这么优秀的复杂度,说明这道题没有必要去实现 KMP(这可是一道 Easy)。

  • 代码:

      class Solution:
          # @param {string} haystack
          # @param {string} needle
          # @return {integer}
          def strStr(self, haystack, needle):
              ##return haystack.find(needle)
              lenN,lenH=len(needle),len(haystack)
              if lenN>lenH:
                  return -1
              elif not needle or haystack[:lenN]==needle:
                  return 0
              else:
                  res = self.strStr(haystack[1:],needle)
                  return 1+res if res!=-1 else -1
    

##30. Substring with Concatenation of All Words (子串)

  • 难度:Hard

  • 题意:
    给定一个字符串 s,及一个单词表,单词表中的每个单词长度均相同,要求找出 s 的每个子串的 index,子串满足:由单词表中所有单词连接构成,且单词之间不相互交叉。

  • 思路:
    使用两个下标 i、j,i 表示子串开始位置,然后判断 s[j:j+len(word)]是否存在单词表中,由于限制单词之间不能相互交叉,因此在匹配的情况下,j 每次推进 len(word)。又要求包含每个单词,且相同单词可能出现多次,因此我们使用 map 来记录,当前子串还需覆盖的单词及数量。

  • 代码:

      class Solution:
          # @param {string} s
          # @param {string[]} words
          # @return {integer[]}
          def findSubstring(self, s, words):
              result,wordDir = [],{}
              if not s or not words:
                  return result
              for w in words:
                  if wordDir.get(w):
                      wordDir[w] += 1
                  else:
                      wordDir[w] =1
              i = j =0
              slen,wordlen,wordslen = len(s),len(words[0]),len(words[0])*len(words)
              while i+wordslen<= slen:
                  tag = wordDir.copy()
                  j = i
                  while j+wordlen <= slen:
                      count = tag.get(s[j:j+wordlen])
                      if count and count != 1:
                          tag[s[j:j+wordlen]] -= 1
                          j += wordlen
                      elif count and count ==1:
                          del tag[s[j:j+wordlen]]
                          j += wordlen
                      else:
                          break
                  if not tag:
                      result.append(i)
                  i+=1
              return result
    

##32. Longest Valid Parentheses (括号,子串)

  • 难度:Hard

  • 题意:
    给定一个只包含 () 的字符串,要求找出最长的括号合法的子串长度。

  • 思路:
    这道题我尝试了很多种思路,若按照常规思路,最难判断的是我如何向前推进去探索这个字符串,若是每次 1 步肯定超时。因此还是老办法:常规思路?-> 递归?-> 剪枝?->DP。没错了这道题就是 DP。
    我们记 dp[i]=n 表示以 s[i]为结尾的字符串的最长合法子串为 n。若当前字符是 ),当前字符左侧是一个合法子串,合法子串的左边是 ),则有如下关系:dp[i]=dp[i-1]>0,最后还需把两个连续和合法串连接起来。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {integer}
          def longestValidParentheses(self, s):
              if not s:return 0
              dp = [0]*len(s)
              for i in range(1,len(s)):
                  if s[i] == ')':
                      if i-1-dp[i-1]>= 0 and s[i-1-dp[i-1]] == '(':
                          dp[i] = dp[i-1]+2
                          if i-1-dp[i-1]>0:
                              dp[i] = dp[i] + dp[i-1-dp[i-1]-1]
              return max(dp)
    

##38. Count and Say (格式化)

  • 难度:Easy

  • 题意:
    给定一个“数-说”数字序列,其中第一个数是 1,每个数字是前一个数字的表达:
    c 个 n

  • 思路:
    常规思路,关键是要看懂问题,不是输入一个数字输出该数字的表达。而是问你以 1 开始的序列的第 n 个数字是多少。若是采用 int 型直接处理会比较麻烦,转为 string 类型会简单很多。

  • 代码:

      class Solution:
          # @param {integer} n
          # @return {string}
          def countAndSay(self, n):
              if not n:return
              strn,result = str(n),'1'
              for i in range(n,1,-1):
                  result = self.countPre(result)
              return result
    
          def countPre(self, pre):
              result,count='',1
              for i in range(1,len(pre)+1):
                  if i == len(pre) or pre[i] != pre[i-1]:
                      result = ''.join([result,str(count),pre[i-1]])
                      count = 1
                  else:
                      count += 1
              return result
    

##43. Multiply Strings (数学)

  • 难度:Medium

  • 题意:
    给定两个字符串格式的数字,要求以字符串的格式返回两个数字的乘积。

  • 思路:
    直接把两个数字转成 int,乘积再转会 string 不就行了吗?确实是可以。但是你太年轻了,没有猜透出题人的想法。这道题是考察字符串的 Medium 难度的题。这道题你需要像小学乘法一样一位一位去乘,然后相加,计算进位。。。。然而我认为这道题意义不大,所以我直接转 int 了。T.T,原谅我

  • 代码:

      class Solution:
      # @param {string} num1
      # @param {string} num2
      # @return {string}
      def multiply(self, num1, num2):
          return str(int(num1)*int(num2))
    

##49. Group Anagrams (哈希)

  • 难度:Medium

  • 题意:
    给定一个字符数组,将字母完全相同的分为一组。

  • 思路:
    将每个字符串进行排序,然后放在 hash 表中,key 是排序后的字符串,value 是排序前字符串列表。

  • 代码:

      class Solution:
          # @param {string[]} strs
          # @return {string[]}
          def anagrams(self, strs):
              strsDir = {}
              result = []
              for i,str in enumerate(strs):
                  tmp = "".join((lambda x:(x.sort(),x)[1])(list(str)))
                  if not strsDir.get(tmp):
                      strsDir[tmp] = []
                  strsDir[tmp].append(i)
              for value in strsDir.values():
                  if len(value) >1:
                      for index in value:
                          result.append(strs[index])
    
              return result
    

##58. Length of Last Word (字符串分割)

  • 难度:Easy

  • 题意:
    给定一个字符串,字符串包含大小写字母和空格,求最后一个单词的长度。

  • 思路:
    简单题,将字符串以空格分割,返回最后一个单词长度即可。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {integer}
          def lengthOfLastWord(self, s):
              strlist = s.split()
              return 0 if not strlist else len(strlist[-1])
    

##65. Valid Number (状态机)

  • 难度:Easy

  • 题意:
    判断给定字符串是否为数字

  • 思路:
    这答题最大的难度在于将所以的情况覆盖完全,空格,正负号,数字,非数字,点,科学计数法。使用状态机解决该题目。只要把各种状态转移弄清楚了,写出状态转移表,这道题就迎刃而解了。状态机没办法别人告诉你怎么画,必须自己耐心细心地画一遍才是自己的。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {boolean}
          def isNumber(self, s):
              inputType = [[' '],['+','-'],
                           ['0','1','2','3','4','5','6','7','8','9'],
                           ['.'],['e','E']]
              transitionTable=[[0,1,2,3,-1,-1],
                               [-1,-1,2,3,-1,-1],
                               [9,-1,2,4,6,-1],
                               [-1,-1,5,-1,-1,-1],
                               [9,-1,5,-1,6,-1],
                               [9,-1,5,-1,6,-1],
                               [-1,7,8,-1,-1,-1],
                               [-1,-1,8,-1,-1,-1],
                               [9,-1,8,-1,-1,-1],
                               [9,-1,-1,-1,-1,-1]]
              state = 0
              for c in s:
                  if state == -1:
                      return False
                  f = 0
                  for i in range(5):
                      if c in inputType[i]:
                          state = transitionTable[state][i]
                          f = 1
                          break
                  if f == 0:
                      state = -1
              if state  in(2,4,5,8,9):
                  return True
              else:
                  return False
    

##67. Add Binary (数学)

  • 难度:Easy

  • 题意:
    给定两个字符串表示的二进制数,同样以二进制字符串的形式返回俩数之和。

  • 思路:
    1.从后往前按位加,记录进位。和求两个链表表示的数字和思路一致。
    2.转为 10 进制数字求和再转为 2 进制字符串。

  • 代码:

      class Solution:
          # @param {string} a
          # @param {string} b
          # @return {string}
          def addBinary(self, a, b):
              return bin(int(a,2)+int(b,2)).split('b')[1]
    

##68. Text Justification (格式化)

  • 难度:Hard

  • 题意:
    给定一个单词表和长度 L,将单词进行格式化,使每一行长度为 L,且按要求格式化。每一行应该放入尽可能多的单词,需要的时候填充空格使每一行恰好长度为 L。添加的空格应该尽可能平均分布在任意两个单词之间,若无法平均分布,则左边的空格必须多余右边的空格。最后一行,必须左对齐,且单词之间不允许填充额外的空格。

  • 思路:
    把题目中所说的规则看明白就费了半天。使用一个单词列表代表一行,用一个变量记录列表中所有单词的长度之和,若单词加入之后不超出长度则加入列表,否则不加入,计算可以补空格的空缺数(列表长度-1,注意只有一个单词时也是 1),计算每个空缺可以补充空格个数,然后插入到列表中合适的位置,最后把列表中的单词按顺序组合起来即可。注意最后一行需要特殊处理。我这种思路没有什么难度,就是处理逻辑比较繁琐。

  • 代码:

      class Solution:
          # @param {string[]} words
          # @param {integer} maxWidth
          # @return {string[]}
          def fullJustify(self, words, maxWidth):
              groups,group =[],[]
              width = 0
              for word in words:
                  width += len(word)
                  if width + len(group) > maxWidth:
                      pos = len(group) if len(group)==1 else len(group)-1
                      space = (maxWidth-width+len(word))//pos
                      spaceLeft =  (maxWidth-width+len(word))% pos
                      for i in range(1,2*pos,2):
                          if spaceLeft:
                              group.insert(i,' '*(space+1))
                              spaceLeft -= 1
                          else:
                              group.insert(i,' '*(space))
                      groups.append(group)
                      group = []
                      width = len(word)
                  group.append(word)
              pos = len(group) if len(group)==1 else len(group)-1
              space = (maxWidth-width)
              for i in range(1,2*pos,2):
                  if space:
                      group.insert(i,' ')
                      space-=1
              group.insert(len(group),' '*space)
              groups.append(group)
              return [''.join(groups[i]) for i in range(len(groups))]
    

##71. Simplify Path (栈)

  • 难度:Medium

  • 题意:
    以 Unix 风格给出一个绝对路径,要求简化路径。/. 表示当前路径;/.. 表示上层路径

  • 思路:
    将字符串以 / 分割(注意如果你是 java 你需要转义 s.split("////"))。使用栈记录路径,若是 . 直接跳过,.. 弹出栈顶,其他直接入栈,最后将栈内目录连接起来即可。

  • 代码:

      class Solution:
          # @param {string} path
          # @return {string}
          def simplifyPath(self, path):
              stack = []
              for p in path.split('/'):
                  if not p or p == '.':
                      continue
                  elif p == '..':
                      if stack:
                          stack.pop(-1)
                  else:
                      stack.append(p)
              return '/' + '/'.join(stack)
    

##72. Edit Distance (编辑距离)

  • 难度:Hard

  • 题意:
    给定两个单词,求从单词 1 转化为单词 2 的最少步骤数。允许的操作是:插入一个字符,删除一个字符,替换一个字符。

  • 思路:
    最短编辑距离,超级经典的 DP 问题。我们定义 dp[i][j]表示 word1[:i]到 word2[:j]的编辑距离。则有如下关系:

    • 若 word1[i-1]和 word[j-1]相同,则有 dp[i][j]=dp[i-1][j-1]
    • 若 word1[i-1]和 word[j-1]不相同,则有 3 中解决办法,在 word1[:i-1]到 word2[:j-1]编辑距离基础上,把 word1[i-1]改为 word[j-1];在 word1[:i]到 word2[:j-1]编辑距离基础上,在 word1 末尾删除一个字符;在 word1[:i-1]到 word2[:j]编辑距离的基础上,在 word1 末尾增加一个字符。
  • 代码:

      class Solution:
          # @param {string} word1
          # @param {string} word2
          # @return {integer}
          def minDistance(self, word1, word2):
              d = [[0 for j in range(len(word2)+1)]for i in range(len(word1)+1)]
              for i in range(len(word1)+1):
                  for j in range(len(word2)+1):
                      if i == 0:
                          d[i][j] = j
                      elif j == 0:
                          d[i][j] = i
                      elif word1[i-1] == word2[j-1]:
                          d[i][j] = d[i-1][j-1]
                      else:
                          d[i][j] = min(d[i-1][j-1],d[i][j-1],d[i-1][j])+1
              return d[-1][-1]
    

##115. Distinct Subsequences(编辑距离)

  • 难度:Hard

  • 题意:
    给定字符串 S 和 T,要求只通过删除字符的形式将 S 转化为 T 的方法数。

  • 思路:
    这道题跟最短编辑距离基本上是一样的,不过编辑方法限制为只能删除。因此还是用动态规划。我们定义 dp[i][j]表示:s[:i]转化为 t[:j]的方法数。则有以下关系:

    • 删除 s[i-1],dp[i][j]=dp[i-1][j],这一项必有
    • 如果 s[i-1]=t[j-1],则保留 s[i-1],有 dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
  • 代码:

      class Solution(object):
          def numDistinct(self, s, t):
              """
              :type s: str
              :type t: str
              :rtype: int
              """
              if not(s and t):return 0
              c1,c2 = len(s),len(t)
              if c1<c2:return 0
              dp=[[0 for i in range(c2+1)] for j in range(c1+1)]
              for i in range(c1+1):dp[i][0] = 1
              for i in range(1,c1+1):
                  for j in range(1,c2+1):
                      dp[i][j]=dp[i-1][j]
                      if s[i-1]==t[j-1]:
                          dp[i][j]+=dp[i-1][j-1]
              return dp[-1][-1]
    

##76. Minimum Window Substring(子串)

  • 难度:Hard

  • 题意:
    给定字符串 T 和 S,找到字符串 S 包含 T 中全部字符的最短子串。

  • 思路:
    T 串放到哈希表中,用来判断是否完全覆盖。使用滑动窗口来寻找子串,左游标直接跳过没在哈希表中的字符,右游标向前推进直到哈希表中所有值均为 0。注意左游标移动的时候需要恢复现场。代码写得比较凌乱。

  • 代码:

      class Solution:
          # @param {string} s
          # @param {string} t
          # @return {string}
          def minWindow(self, s, t):
              result = ''
              if not t:return result
              dicT = {}
              for char in t:
                  if not dicT.get(char):
                      dicT[char] = 0
                  dicT[char] += 1 
              i=j=0
              while i<len(s) and  s[i] not in t:
                          i += 1
              s = s[i:]
              i = 0
              while j <len(s) or max(dicT.values())<=0:
                  if max(dicT.values())<=0:
                      ##get window
                      if not result:
                          result = s[i:j]
                      elif j-i < len(result):
                          result = s[i:j]
                      dicT[s[i]] += 1
                      i += 1
                      while i<len(s) and  s[i] not in t:
                          i += 1
                      continue
                  while j< len(s) and s[j] not in t:
                      j += 1
                  if j<len(s):
                      dicT[s[j]] -= 1
                      j += 1
              return result
    

##87. Scramble String (树)

  • 难度:Hard

  • 题意:
    通过将字符串分割成两个非空的部分构成一个二叉树。选择任意非叶子节点,交换其左右子节点位置。求问字符串 s1 能否通过这种形式转化为 s2

  • 思路:
    看到凡是跟树有关的题,应该往递归上靠一下,因为树的定义本身就是递归的。只要能想到用递归解决这道题就完成一大半了。s1 是 s2 的变换,则有从某处分割,s1 的左子串是 s2 左子串的变换且 s1 右子串是 s2 右子串的变换,或 s1 左子串是 s2 右子串的变化且 s1 右子串是 s2 左子串的变化。这个检验过程本身也是递归的。

  • 代码:

      class Solution(object):
          def isScramble(self, s1, s2):
              """
              :type s1: str
              :type s2: str
              :rtype: bool
              """
              length = len(s1)
              if length!=len(s2):return False
              if s1==s2:return True
              count = [0]*26zhu'yi
              for c in s1:
                  count[ord(c)-97]+=1
              for c in s2:
                  count[ord(c)-97]-=1
              for c in count:
                  if c!=0:return False
              for i in range(1,length):
                  if (self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:])) or (self.isScramble(s1[:i],s2[length-i:]) and self.isScramble(s1[i:],s2[:length-i])):
                      return True
              return False
    

##91. Decode Ways (格式化)

  • 难度:Medium

  • 题意:
    有一个包含字母 A-Z 的信息,使用以下编码方式 A->1,B->2...Z->26。给定一个编码后的信息,求出其所有可能的解码种类,如 12 可解码为 AB 或 L。

  • 思路:
    这是一道比 Hard 通过率还低的 Medium 题,因为这是一道 DP 题,说明大家对 DP 的理解还是不够深,找个机会把我之前学习 DP 的笔记整理再发出来(又是一个坑)。我们定义 dp[i]=n 表示表示 s[-i:]的可能的解码数,为什么要从后往前遍历,一会你就可以体会到。则有如下关系:

    • 若 s[-i]=='0',则解码数为 0(0 无对应解码)
    • 若 s[-i]!='0',则可以 s[-i]单独解码的情况 + 若 s[-i:-i+2]可解码两种可能情况。
      相同的思路,如果以从前往后遍历,则需要分析的情况会复杂许多。
  • 代码:

      class Solution:
          # @param {string} s
          # @return {integer}
          def numDecodings(self, s):
              if not s: return 0
              count = [1]
              if s[-1] == '0':
                  count.append(0)
              else:
                  count.append(1)
              for i in range(2,len(s)+1):
                  c = 0 if s[-i]=='0' else count[-1]
                  if '10'<=s[-i:][0:2]<='26':
                      print(s[-i:][0:2])
                      c += count[-2]
                  count.append(c)
              return count[-1]
    

##93. Restore IP Addresses(格式化)

  • 难度:Medium

  • 题意:
    给定一个字符串表示的数字,要求将其转化为所有可能的 IP 地址。

  • 思路:
    IP 地址由 4 个小于 256 的整数构成,注意不允许连续 0。这道题使用递归可以很容易解决。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {string[]}
          def restoreIpAddresses(self, s):
              self.result = []
              self.reduce(s,[])
              return self.result
          def reduce(self,s0,ele0):
              s = s0[::]
              ele = ele0[::]
              if len(ele)==4 and not s:
                  self.result.append('.'.join(ele))
              elif len(ele)<4 and s:
                  for i in range(1,len(s)+1):
                      if int(s[:i])<256:
                          if len(s[:i])>1 and s[0]=='0':
                              break
                          ele.append(s[:i])
                          self.reduce(s[i:],ele)
                          ele.pop(-1)
                      else:
                          break
    

##97. Interleaving String (子串)

  • 难度:Hard

  • 题意:
    给定 s1,s2,s3,求 s3 是否由 s1 和 s2 交织得到。

  • 思路:
    题意是要求在 s3 中 s1 和 s2 中的字符的相对顺序保持不变。这道题的难点在于当一个字符同时出现在 s1 和 s2 中时,如何判断是属于谁。若用递归回溯,直接就超时了,题目的规模过大。因此启用固定解题法,递归回溯走不同的时候就 DP。
    我们定义 dp[i][j]=True 表示 s1[:i]和 s2[:j]可以交织成 s[:i+j],则有如下关系:

    • 若 s1[i]==s3[i+j+1],则有 dp[i+1][j+1]=dp[i][j+1],(最后一个字符由 i 来出)
    • 若 s2[j]==s3[i+j+1],则有 dp[i+1][j+1]=dp[i+1][j],(最后一个字符由 j 来出)
      注意这两者是或的关系,有可能均相等或均不相等的情况。
  • 代码:

      class Solution(object):
          def isInterleave(self, s1, s2, s3):
              """
              :type s1: str
              :type s2: str
              :type s3: str
              :rtype: bool
              """
              if not s2:return s1==s3
              elif not s1:return s2==s3
              len1,len2=len(s1),len(s2)
              if len1+len2!=len(s3):return False
              dp = [[False for i in range(len2+1)] for j in range(len1+1)]
              dp[0][0] = True
              for i in range(len2):
                  dp[0][i+1] = (dp[0][i] and s2[i]==s3[i])
              for i in range(len1):
                  dp[i+1][0] = (dp[i][0] and s1[i]==s3[i])
              for i in range(len1):
                  for j in range(len2):
                      dp[i+1][j+1] = ((dp[i][j+1] and s1[i]==s3[i+j+1]) or
                                      (dp[i+1][j] and s2[j]==s3[i+j+1]))
              return dp[len1][len2]  
    

##125. Valid Palindrome (回文)

  • 难度:Easy

  • 题意:
    给定一个字符串,判断其是否为回文串,不考虑大小写及空格和标点

  • 思路:
    去掉空格和标点,转化为小写字母,然后将字符串逆序比较。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {boolean}
          def isPalindrome(self, s):
              slist = []
              for c in s:
                  if c.isalpha() or c.isdigit():
                      slist.append(c.lower())
              return slist==slist[::-1]
    

##127. Word Ladder (编辑距离)

  • 难度:Medium

  • 题意:
    给定两个单词 beginWord 和 endWord,已经一个单词表,求通过单词表中的词从 beginword 到 endWord 的最短变化序列的长度。变化要求每次只能改变一个字符。

  • 思路:
    这道题其实也是编辑距离的变种,编辑时限制只能改变字符,且改变必须在给定的单词表范围内。然而我们这次不使用 dp,原因是在没有限制时,每一步编辑的结果是无限的,现在加上限制只有,每一步编辑的结果是可列举的,我们可以把所有单词的变化现象成一棵树。要求最短距离,基本固定模式就是按层次遍历,第一次到达 endWord 时的层次就是最短编辑距离。

  • 代码:

      class Solution(object):
          def ladderLength(self, beginWord, endWord, wordDict):
              """
              :type beginWord: str
              :type endWord: str
              :type wordDict: Set[str]
              :rtype: int
              """
              letter=[chr(97+i) for i in range(26)]
              queue=[beginWord]
              dic={beginWord:1}
              while queue:
                  word = queue.pop(0)
                  level = dic[word]
                  for i in range(len(word)):
                      tmpword = list(word)
                      for j in letter:
                          if tmpword[i]==j:continue
                          tmpword[i]=j
                          tmp = ''.join(tmpword)
                          if tmp==endWord:return level+1
                          if tmp in wordDict and tmp not in dic:
                              queue.append(tmp)
                              dic[tmp]=level+1
    
              return 0
    

##126. Word Ladder II (编辑距离)

  • 难度:Hard

  • 题意:
    与 127 题意基本一样,不同的是要求返回所有最短序列的具体路径

  • 思路:
    我采用的思路还是和 127 题一样,使用队列按层次遍历,当时同时需要注意的是,遍历的同时需要记录父节点。且由于要求返回所有最短,因此最短那一层必须完全遍历,而不是像 127 一样遇到 endword 即可。

  • 代码:

      class Solution(object):
          def findLadders(self, beginWord, endWord, wordlist):
              """
              :type beginWord: str
              :type endWord: str
              :type wordlist: Set[str]
              :rtype: List[List[int]]
              """
              letter=[chr(97+i) for i in range(26)]
              queue=[beginWord]
              dic={beginWord:1}。
              self.father={beginWord:{}}
              self.res=[]
              end=2**31
              while queue:
                  word = queue.pop(0)
                  level = dic[word]
                  if level>end:
                      break
    
                  for i in range(len(word)):
                      tmpword = list(word)
                      for j in letter:
                          if tmpword[i]==j:continue
                          tmpword[i]=j
                          tmp=''.join(tmpword)
                          if tmp==endWord:
                              end=level
                          if (tmp in wordlist and (tmp not in dic or dic[tmp]>=level+1)) or tmp==endWord:
                              if tmp not in self.father:
                                  self.father[tmp]=set()
                              self.father[tmp].add(word)
                              if tmp not in dic and tmp!=endWord:
                                  queue.append(tmp)
                                  dic[tmp]=level+1
    
              self.buildPath([endWord])
              return self.res
    
          def buildPath(self,path0):
              path=path0[::]
              if path[-1] not in self.father:return
              if not self.father[path[-1]]:
                  self.res.append(path[::-1])
              for p in self.father[path[-1]]:
                  path.append(p)
                  self.buildPath(path)
                  path.pop(-1)
    

##151. Reverse Words in a String (反转)

  • 难度:Medium

  • 题意:
    输入一个字符串,要求以单词为单位进行反转。

  • 思路:
    按照空格分割成列表,将列表反转后再用空格连接。

  • 代码:

      class Solution:
          # @param s, a string
          # @return a string
          def reverseWords(self, s):
              return ' '.join(s.split()[::-1])
    

##165. Compare Version Numbers

  • 难度:Easy

  • 题意:
    比较两个版本号大小。

  • 思路:
    版本号大小规则与 float 大小规则不一样,版本号点后面的部分不是小数部分,而应该当作整数来对待。将版本号以第一个点分割成左边 left 和右边 right,左边大小直接决定了版本号的大小关系,若相等则递归比较右边(有可能出现多个点,右边也是一个完整的版本号)。这道 easy 题的通过率比很多 Hard 都低。

  • 代码:

      class Solution:
          # @param {string} version1
          # @param {string} version2
          # @return {integer}
          def compareVersion(self, version1, version2):
              left1,right1=self.splitVersion(version1)
              left2,right2=self.splitVersion(version2)
              if left1>left2:return 1
              elif left1<left2:return -1
              elif left1==left2 and not right1 and not right2:return 0
              else:
                  return self.compareVersion(right1,right2)
    
          def splitVersion(self,version):
              if not version:return 0,''
              i = version.find('.')
              if i==-1:
                  return int(version),''
              return int(version[:i]),version[i+1:]
    

##214. Shortest Palindrome (回文)

  • 难度:Hard

  • 题意:
    给定一个字符串 S,可以通过在字符串头部添加字符将 S 转换为回文串。返回通过这种转换方式能够得到的最短回文串。

  • 思路:
    求第一个字符开始的最长回文串,然后把剩下的部分逆序补到头部即可。因此这道题的难点在如何找到以第一个字符开始的最长回文串,而不超时。
    这里推荐一种很巧妙的算法 mancher,mancher 在 O(n)时间复杂度内可以求出以每个字符为中心的回文串长度。算法巧妙之处在与,在字符中间插入了特殊符号,使奇和偶回文统一处理。是用辅助数组 P[i]记录以字符串 s[i]为中心的最长回文串可以向左或向右扩张的长度(包括自己)。记录当前最长回文串中心和覆盖范围,然后大家就画图观察吧,这个算法我也是画图弄了很久才学明白,然而还没办法用语言表达出来。

  • 代码:

      class Solution(object):
          def shortestPalindrome(self, s):
              """
              :type s: str
              :rtype: str
              """
              pos = self.manacher(s)
              return ''.join([s[pos::][::-1],s])
    
    
          def manacher(self,s):
              s1 = list('#'.join(s))
              s1.insert(0,'*')
              s1.append('$')
              p=[0]*len(s1)
              mi,res=0,0 #mi能覆盖右侧最远的回文串中心,res以第一个字符为开始的最大回文串
              for i in range(1,len(s1)-1):
                  if i < mi+p[mi]:
                      p[i] = min(p[2*mi-i],mi+p[mi]-i)
                  else:
                      p[i] = 1
                  while s1[i+p[i]]==s1[i-p[i]]:
                      p[i]+=1
                  if mi+p[mi] < i+p[i]:
                      mi = i
                  if p[i]==i:
                      res = max(res,i)
              return res
    

##224. Basic Calculator (数学)

  • 难度:Medium

  • 题意:
    实现一个基本的计算器,用于计算简单的字符串表示的算式。字符算式包括括号,+,-和非负整数和空格。

  • 思路:
    使用栈实现,一个栈记录数字(需要先把数字进行处理,去除空格转化为 int),另一个栈记录符号,由于 + 和-是同级符号,只要不存在括号直接弹栈计算即可,注意考虑输入为各种可能。思路还是比较简单。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {integer}
          def calculate(self, s):
              result = 0
              nums = []
              ops = []
              if not s:
                  return 0
    
              tmps = s.replace(' ', '')
              i=0
              while i < len(tmps):
                  #数字处理
                  if tmps[i] not in('+','-','(',')'):
                      numstr=[]
                      while i < len(tmps)  and tmps[i] not in ('+','-','(',')'):
                          numstr.append(tmps[i])
                          i += 1
                          ttt = ''.join(numstr)
                      i -= 1
                      nums.append(ttt)
                  #+,-,)
                  elif tmps[i] in('+','-',')'):
                      #若操作栈中有非(的操作,出栈计算
                      if ops and ops[-1] !='(':
                          num_a = int(nums.pop())
                          num_b = int(nums.pop())
                          op = ops.pop()
                          if op == '+':
                              result = num_b+num_a
                          else:
                              result = num_b-num_a
                          nums.append(result)
                      #若操作栈中最后一个为),新操作直接入栈
                      if tmps[i] != ')':
                          ops.append(tmps[i])
                      else:
                          ops.pop()
                  #(直接进ops
                  elif tmps[i] == '(':
                      ops.append(tmps[i])
                  i += 1
    
              #最后出栈    
              if ops:
                  num_a = int(nums.pop())
                  num_b = int(nums.pop())
                  op = ops.pop()
                  if op == '+':
                      result = num_b+num_a
                  else:
                      result = num_b-num_a
              else:
                  result = int(nums.pop())
              return result
    

##227. Basic Calculator II (数学)

  • 难度:Medium

  • 题意:
    与 224 题意一致,不过这回少了括号,但是多了乘法和除法

  • 思路:
    还是使用两个栈来存储运算符和数字。运算符的优先级 *=/ > +=-,因此运算符在入栈前,需要比较栈顶符号,若平级则弹出栈顶符号和对应的数字进行计算。若栈顶符号优先级低,则直接入栈。

  • 代码:

      class Solution:
          # @param {string} s
          # @return {integer},
          def calculate(self, s):
              s += '#'
              num = 0
              a = b = None
              preop = op = None
              for c in s:
                  if c in ('+','-','*','/','#'):
                      if op is None:
                          a = num
                      elif op in ('+','-'):
                          if preop is None:
                              b = num
                          else:
                              a = a + b if preop == '+' else a - b
                              b = num
                          preop = op
                      else:
                          if preop is None:
                              a = a * num if op == '*' else a / num
                          else:
                              b = b * num if op == '*' else b / num
                      op = c
                      num = 0
                  elif c != ' ':
                      num = num * 10 + int(c)
              if preop is None:
                  return a
              return a + b if preop == '+' else a - b
    

##273. Integer to English Words (格式化)

  • 难度:Medium
  • 题意:
    将数字转化为英文的表示方式。数字小于 2^31-1。例如:123 -> "One Hundred Twenty Three"
  • 思路:
    思路比较简单,英文的数字表达方式是 3 位为一组,每 3 位的表达方式相同,最后再加入单位即可。注意 3 位全为 0 和输入就是 0。注意英文拼写。
  • 代码:

class Solution(object):

one_nine=['0','One','Two','Three','Four','Five','Six','Seven','Eight','Nine']
ten_nineteen=['Ten','Eleven','Twelve','Thirteen','Fourteen','Fifteen','Sixteen','Seventeen','Eighteen','Nineteen']
twenty_ninety=['0','0','Twenty','Thirty','Forty','Fifty','Sixty','Seventy','Eighty','Ninety']
unit=['','Thousand','Million','Billion','Trillion']

def numberToWords(self, num):
    """
    :type num: int
    :rtype: str
    """
    num,i,res = str(num),0,[]
    while True:
        temp = self.three(int(num[-3:]))
        if temp:
            if i!=0:
                res.append(self.unit[i])
            res.append(temp)
        if len(num)<=3:break
        num = num[:-3]
        i+=1
    return 'Zero' if not res else ' '.join(res[::-1])

def three(self,num):
    res = ""
    if num//100>0:
        res = ' '.join([res,self.one_nine[num//100],'Hundred'])
        num%=100
    if 10<=num<=19:
        res = ' '.join([res,self.ten_nineteen[num-10]])
    elif num>=20:
        res = ' '.join([res,self.twenty_ninety[num//10]])
        num%=10
    if 0<num<10:
        res = ' '.join([res,self.one_nine[num]])
    return res[1:]
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Swagger

    Swagger 是一款非常流行的 API 开发工具,它遵循 OpenAPI Specification(这是一种通用的、和编程语言无关的 API 描述规范)。Swagger 贯穿整个 API 生命周期,如 API 的设计、编写文档、测试和部署。

    26 引用 • 35 回帖 • 1 关注
  • 工具

    子曰:“工欲善其事,必先利其器。”

    286 引用 • 729 回帖
  • 安全

    安全永远都不是一个小问题。

    199 引用 • 816 回帖 • 1 关注
  • Oracle

    Oracle(甲骨文)公司,全称甲骨文股份有限公司(甲骨文软件系统有限公司),是全球最大的企业级软件公司,总部位于美国加利福尼亚州的红木滩。1989 年正式进入中国市场。2013 年,甲骨文已超越 IBM,成为继 Microsoft 后全球第二大软件公司。

    105 引用 • 127 回帖 • 382 关注
  • H2

    H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。

    11 引用 • 54 回帖 • 654 关注
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖 • 1 关注
  • CSDN

    CSDN (Chinese Software Developer Network) 创立于 1999 年,是中国的 IT 社区和服务平台,为中国的软件开发者和 IT 从业者提供知识传播、职业发展、软件开发等全生命周期服务,满足他们在职业发展中学习及共享知识和信息、建立职业发展社交圈、通过软件开发实现技术商业化等刚性需求。

    14 引用 • 155 回帖
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 3 关注
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    85 引用 • 139 回帖 • 1 关注
  • SSL

    SSL(Secure Sockets Layer 安全套接层),及其继任者传输层安全(Transport Layer Security,TLS)是为网络通信提供安全及数据完整性的一种安全协议。TLS 与 SSL 在传输层对网络连接进行加密。

    70 引用 • 193 回帖 • 431 关注
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 700 关注
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 173 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 709 关注
  • FFmpeg

    FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。

    23 引用 • 32 回帖
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    12 引用 • 54 回帖 • 65 关注
  • 大疆创新

    深圳市大疆创新科技有限公司(DJI-Innovations,简称 DJI),成立于 2006 年,是全球领先的无人飞行器控制系统及无人机解决方案的研发和生产商,客户遍布全球 100 多个国家。通过持续的创新,大疆致力于为无人机工业、行业用户以及专业航拍应用提供性能最强、体验最佳的革命性智能飞控产品和解决方案。

    2 引用 • 14 回帖
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    543 引用 • 672 回帖 • 1 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 9 关注
  • CentOS

    CentOS(Community Enterprise Operating System)是 Linux 发行版之一,它是来自于 Red Hat Enterprise Linux 依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码,因此有些要求高度稳定的服务器以 CentOS 替代商业版的 Red Hat Enterprise Linux 使用。两者的不同在于 CentOS 并不包含封闭源代码软件。

    238 引用 • 224 回帖
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    266 引用 • 665 回帖
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 19 关注
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    86 引用 • 122 回帖 • 625 关注
  • TGIF

    Thank God It's Friday! 感谢老天,总算到星期五啦!

    287 引用 • 4484 回帖 • 669 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖
  • JRebel

    JRebel 是一款 Java 虚拟机插件,它使得 Java 程序员能在不进行重部署的情况下,即时看到代码的改变对一个应用程序带来的影响。

    26 引用 • 78 回帖 • 664 关注
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    12 引用 • 54 回帖 • 165 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 595 关注