前言

本系列，希望使用Python通关LeetCode，暂时开始做简单题。
初次刷LeetCode目的是为了提高自己的算法能力，我的解法在时间复杂度上肯定不是最优的，忘各位指导。
另外，LeetCode早已推出了中文官网https://leetcode-cn.com，希望各位亲自尝试这些题目。

1. 两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路：先使用enumerate()将nums转换为可遍历的对象，接下来开始遍历，用已知的两数之和target减去nums遍历的值，得到一个数字，如果这个数字在nums[index+1:]中，我们就可以得到这个数字的索引了。注意如何还原在该数字在原nums中的索引。

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for index, value in enumerate(nums):
            sub = target - value
            if sub in nums[index+1:]:
                return [index, nums[index+1:].index(sub)+len(nums[:index+1])]
            else:
                pass

7.反转整数

给定一个 32 位有符号整数，将整数中的数字进行反转。
注意:
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

思路：这道题非常简单，利用Python的切片很容易的将转为str类型的整数反转，只需要判断符号，负数就在反转之后的数字加上负号。本题的坑就在于32位有符号整数，在返回值时不能越界。

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x > 0:
            nums = str(x)[::-1]
        else:
            nums =  '-' + str(-x)[::-1]    
        if int(nums) < 2147483648 and int(nums) >= -2147483648:
            return int(nums)
        else:
            return 0

9.回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:
输入: 121
输出: true

示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

思路：本题同样使用Python的切片，将数字反转，若反转之后的list与反转之前的list值相同，则这个数字是一个回文数。

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        num = str(x)
        if x >= 0:
            if num[::-1] == num:
                return True
            else:
                return False
        else:
                return False
        

13.罗马数字转整数

罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。
字符 数值
I —— 1
V —— 5
X —— 10
L —— 50
C —— 100
D —— 500
M —— 1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:
输入: "III"
输出: 3

示例 2:
输入: "IV"
输出: 4

示例 3:
输入: "IX"
输出: 9

示例 4:
输入: "LVIII"
输出: 58
解释: C = 100, L = 50, XXX = 30, III = 3.

示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

思路：建立罗马数字对应整数的dict，将输入的罗马数字转为list，遍历这个list（除去最后一个元素），从左往右，左边的数字大于右边的数字，则加左边对应的整数，若是左边的数字小与右边的数字，则减去左边对应的整数。最后加最后一个罗马数字对应的整数。

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

14.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。

思路：首先选出这个list中最长的字符串，将最长的这个字符串作为基准，嵌套遍历最长的字符串以及剩下的字符串，判断作为基准的字符串的第一个字母是否等于下一个字符串的第一个字符，如果相同则将这个字符加入公共前缀，以此类推，若不相等，则开始检查下一个字符串。

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        common = ""
        if len(strs) == 0:
            return common

        temp = strs[0]

        for word in strs:
            if len(word) < len(temp):
                temp = word
    
        for i in range(len(temp)):
            for j in range(len(strs)):
                if temp[i] != strs[j][i]:
                    return common
            common += temp[i]
        return common
        

20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

思路：设置这样一个dict，key为左括号，value为右括号。遍历这个由括号组成的字符串，如果这个符号不是这个dict的key，将这个符号加入一个名为brackets_list的list中，如果这个符号是dict中的key，则将这个符号加入另一个名为reult的list中，当遍历到一个符号对应的dict中的key在result这个list中，则将对应的key从result中删除，同时删除brackets_list中的这个符号，否则开始下一轮循环。遍历结束后，若result与brackets_list中都没有任何元素，则返回Ture，反之返回False。

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        brackets_dict = {"(" : ")", "[": "]", "{": "}"}
        str_list = list(s)
        result = []
        brackets_list = []

        for bracket in str_list:
            if bracket not in brackets_dict:
                brackets_list.append(bracket) 
            if bracket in brackets_dict:
                result.append(bracket)
            if len(result) > 0:
                if bracket == brackets_dict[result[-1]]:
                    result.pop(-1)
                    brackets_list.remove(bracket)

        if len(result) > 0 or len(brackets_list) > 0:
            return False
        else:
            return True