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 解释: L = 50, V= 5, III = 3.示例 5:
输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.思路：罗马数字表示中，小的数放在大的数左边，表示用大的数减去小的数，小的数放在大的数右边，表示用大的数加上小的数，所以这道题的思路可以转化为：对于列表中前n-1个元素，依次遍历每个元素与下一个元素，当前元素小于下一个元素时，sum减去当前元素，当前元素大于下一个元素时，sum加上当前元素。最后sum再加上最后一个元素。
代码如下：
class Solution(object): def romanToInt(self, s): """ :type s: str :rtype: int """ sum=0 roman_int={'M':1000,'D':500,'C':100,'L':50,'X':10,'V':5,'I':1} for i in range(len(s)-1): if roman_int[s[i]]<roman_int[s[i+1]]: sum-=roman_int[s[i]] else: sum+=roman_int[s[i]] sum+=roman_int[s[-1]] return sum14.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"] 输出: "fl"示例 2:
输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。说明:
所有输入只包含小写字母 a-z 。
思考：该处只有一个列表，可使用zip(*)把列表中每个字符串的对应位置的字母打包成一个元组，再利用set()函数去重之后判断元组长度是否为1，是则添加该字母，否则输出结果。
代码如下：
class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ res='' if len(strs)==0: return res for each in zip(*strs): if len(set(each))==1: res+=each[0] else: return res return res20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true示例 2:
输入: "()[]{}" 输出: true示例 3:
输入: "(]" 输出: false示例 4:
输入: "([)]" 输出: false示例 5:
输入: "{[]}" 输出: true思考：字典匹配左右括号，在进行判断：若为左括号则压入栈中，若为右括号则弹出，再判断弹出的元素的值是否与进行判断的元素一致，若不一致则输出False。另外，奇数个元素一定不匹配，且空元素应返回True。
代码如下：
class Solution(object): def isValid(self, s): """ :type s: str :rtype: bool """ if len(s)%2==1: return False if len(s)==0: return True stack=[] d={'{':'}','(':')','[':']'} for i in s: if i in d: stack.append(i) else: if not stack or d[stack.pop()]!=i: return False return stack==[]28.实现strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll" 输出: 2示例 2:
输入: haystack = "aaaaa", needle = "bba" 输出: -1说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
思考：直接使用库函数find()。
代码如下：
class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ return haystack.find(needle)58.最后一个单词的长度
给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例:
输入: "Hello World" 输出: 5思考：使用rstrip(' ')去掉右边空格，再使用split(' ')以空格划分单词，再输出最后一个单词的长度即可。
代码如下：
class Solution(object): def lengthOfLastWord(self, s): """ :type s: str :rtype: int """ return len(s.rstrip(' ').split(' ')[-1])67.二进制求和
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1" 输出: "100"示例 2:
输入: a = "1010", b = "1011" 输出: "10101"思考：先用int(num,base=2)将str类型的a和b转化为二进制，再求和，再用bin函数将结果转化为二进制，由于bin的结果前两位是“0b”开头，故手动从第三位开始取结果。
代码如下：
class Solution(object): def addBinary(self, a, b): """ :type a: str :type b: str :rtype: str """ ans=bin(int(a,2)+int(b,2)) return ans[2:]125.验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama" 输出: true示例 2:
输入: "race a car" 输出: false思路：首先将用isalnum()将数字和字母添加进新的列表，再用s1==s1[::-1]判断是否为回文。
代码如下：
class Solution(object): def isPalindrome(self, s): """ :type s: str :rtype: bool """ s1=[] for i in range(len(s)): if s[i].isalnum(): s1.append(s[i].lower()) if s1==s1[::-1]: return True else: return False