Leetcode 38. 报数

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1
11
21
1211
111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
示例 1:
输入: 1
输出: "1"
示例 2:
输入: 4
输出: "1211"

解题思路：三次遍历

class Solution:
    def countAndSay(self, n: int) -> str:
        s = '1' 
        # the number of output lines
        for i in range(n-1):
            
            output = ''
            j = 0
            # in the same line
            while j < len(s):
                k = j
                while k < len(s) and s[k] == s[j]:
                    k += 1
                output += str(k-j) + s[j] 
                j = k
                
            s = output
        return s

Leetcode 49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。

解题思路：
对每个词中的所有字母进行排序，排序后的词作为哈希表的索引，输出所有索引相同的词即可。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if len(strs) == 0:
            return None
        output = []
        dic = {}
        for word in strs:
            key = "".join((lambda x:(x.sort(),x)[1])(list(word)))
            if key in dic.keys():
                dic[key].append(word)
            else:
                dic[key] = [word]
        for k in dic.keys():
            output.append(dic[k])
        return output

Leetcode 151. 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

解题思路：
先翻转整个字符串，然后翻转每个单词。在Python中可以通过分割字符来移除多余空格。

class Solution:
    def reverseWords(self, s: str) -> str:
        # reverse the whole sentence
        s = self.reverse(s)
        result = [self.reverse(i) for i in s.split()]
        res = ''
        for i in result:
            res += i
            res += ' '
        return res.strip()
    
    def reverse(self, word):
        return word[::-1]

Leetcode 165. 比较版本号

比较两个版本号 version1 和 version2。
如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。你可以假设版本字符串非空，并且只包含数字和 . 字符。 . 字符不代表小数点，而是用于分隔数字序列。例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。
你可以假设版本号的每一级的默认修订版号为 0。例如，版本号 3.4 的第一级（大版本）和第二级（小版本）修订号分别为 3 和 4。其第三级和第四级修订号均为 0。
示例 1:
输入: version1 = "0.1", version2 = "1.1"
输出: -1
示例 2:
输入: version1 = "1.0.1", version2 = "1"
输出: 1
示例 3:
输入: version1 = "7.5.2.4", version2 = "7.5.3"
输出: -1
示例 4：
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，“01” 和 “001” 表示相同的数字 “1”。
示例 5：
输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有第三级修订号，这意味着它的第三级修订号默认为 “0”。
提示：
版本字符串由以点 （.） 分隔的数字字符串组成。这个数字字符串可能有前导零。
版本字符串不以点开始或结束，并且其中不会有两个连续的点。

解题思路：
用‘.’将版本号分开，将对较短的版本号末尾填充0，对比相应位数上的值。

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        v1 = version1.split('.')
        v2 = version2.split('.')
        a = len(v1)
        b = len(v2)
        while a < b:
            v1.append('0')
            a += 1
        while b < a:
            v2.append('0')
            b += 1
            
        for i in range(len(v1)):
            if int(v1[i]) < int(v2[i]):
                return -1
            elif int(v1[i]) > int(v2[i]):
                return 1  
        return 0

Leetcode 929. 独特的电子邮件地址

每封电子邮件都由一个本地名称和一个域名组成，以 @ 符号分隔。
例如，在 alice@leetcode.com中， alice 是本地名称，而 leetcode.com 是域名。除了小写字母，这些电子邮件还可能包含 '.' 或 '+'。如果在电子邮件地址的本地名称部分中的某些字符之间添加句点（'.'），则发往那里的邮件将会转发到本地名称中没有点的同一地址。例如，"alice.z@leetcode.com” 和 “alicez@leetcode.com” 会转发到同一电子邮件地址。 （请注意，此规则不适用于域名。）如果在本地名称中添加加号（'+'），则会忽略第一个加号后面的所有内容。这允许过滤某些电子邮件，例如 m.y+name@email.com 将转发到 my@email.com。 （同样，此规则不适用于域名。）可以同时使用这两个规则。给定电子邮件列表 emails，我们会向列表中的每个地址发送一封电子邮件。实际收到邮件的不同地址有多少？

class Solution(object):
    def numUniqueEmails(self, emails):
        """
        :type emails: List[str]
        :rtype: int
        """
        new_emails = {}
        for email in emails:
            name, domain = email.split('@')
            name = name.split('+')[0]
            name = name.replace('.', '')
            new_email = name + '@' + domain
            
            if new_email not in new_emails.keys():
                new_emails[new_email] = 1
        
        return len(new_emails.keys())

Leetcode 5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"

解题思路：暴力解法，从头开始遍历枚举所有中心节点，看这个中心节点两段的最长回文字符串，取最大值即可。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = ""
        i = 0
        while i < len(s):
            k = i
            j = i
            while k >= 0 and j < len(s) and s[k] == s[j]:
                if len(res) < j - k + 1:
                    res = s[k:j+1]
                k -= 1
                j += 1
            
            k = i
            j = i + 1
            while k >= 0 and j < len(s) and s[k] == s[j]:
                if len(res) < j - k + 1:
                    res = s[k:j+1]
                k -= 1
                j += 1
            i += 1
        return res

Leetcode 6. Z字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

解题思路：
把这个问题看做一个找规律的问题：可以看到，第一行和最后一行都是等差数列。中间的行是交错的等差数列，如：1， 9；7， 15。找到其中的规律，然后按顺序输出等差数列。

图片.png

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1:
            return s
        n = numRows
        res = ""
        for i in range(n):
            if i == 0 or i == n - 1:
                j = i
                while j < len(s):
                    res += s[j]
                    j += 2 * (n - 1)
            else:
                j = i
                k = 2 * (n - 1) - i
                while j < len(s) or k < len(s):
                    if j < len(s):
                        res += s[j]
                    if k < len(s):
                        res += s[k]
                    j += 2 * (n - 1)
                    k += 2 * (n - 1)
        return res

Leetcode 3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

解题思路：
从头开始遍历，建立哈希表储存字符的位置，如果当前遍历到的字符在哈希表中没有出现过，则添加该字符；如果出现过，则原先不重复字符的起点需要加1，然后更新重复字符的出现位置。当新的不重复字符串长度大于原先字符串长度时，更新字符串长度。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        l = 0
        start = 0
        dic = {}
        
        for i in range(len(s)):
            cur = s[i]
            if cur not in dic.keys():
                dic[cur] = i
            else:
                if dic[cur] + 1 > start:
                    start = dic[cur] + 1
                dic[cur] = i
            
            if i - start + 1 > l:
                l = i - start + 1
        return l

Leetcode 273. 整数转英文表示

将非负整数转换为其对应的英文表示。可以保证给定输入小于 231 - 1 。
示例 1:
输入: 123
输出: "One Hundred Twenty Three"
示例 2:
输入: 12345
输出: "Twelve Thousand Three Hundred Forty Five"
示例 3:
输入: 1234567
输出: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

class Solution(object):
    def __init__(self):
        self.small = ['Zero','One ', 'Two ', 'Three ', 'Four ', 'Five ', 'Six ', 'Seven ', 'Eight ', 'Nine ', 'Ten ', 'Eleven ', 'Twelve ', 'Thirteen ', 'Fourteen ', 'Fifteen ', 'Sixteen ', 'Seventeen ', 'Eighteen ', 'Nineteen ']
        self.decade = ['', '', 'Twenty ', 'Thirty ', 'Forty ', 'Fifty ', 'Sixty ', 'Seventy ', 'Eighty ', 'Ninety ']
        self.big = ['Billion ', 'Million ', 'Thousand ', '']
    
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        i = 1000000000
        j = 0
        res = ''
        while i > 0:
            if num >= i:
                res += self.part(int(num/i)) + self.big[j]
                num %= i
            i /= 1000
            j += 1
        return res.strip()
                
    def part(self, num):
        res = ''
        if num >= 100:
            res += self.small[int(num / 100)] + 'Hundred ' 
            num %= 100
        if num == 0:
            return res
        if num >= 20:
            res += self.decade[int(num / 10)]
            num %= 10
        if num == 0:
            return res
        res += self.small[int(num)]
        return res