罗马数字包含以下七种字符: 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 2 3 4 5 6 7 8 9 10 11 def romanToInt (s ): a = {'I' :1 , 'V' :5 , 'X' :10 , 'L' :50 , 'C' :100 , 'D' :500 , 'M' :1000 } ans = 0 for i in range (len (s)): if i<len (s)-1 and a[s[i]] < a[s[i+1 ]]: ans -= a[s[i]] else : ans += a[s[i]] return ans print (romanToInt('XXVII' ))
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 “”。
示例 1:输入: [“flower”,”flow”,”flight”] 输出: “fl”
示例 2:输入: [“dog”,”racecar”,”car”] 输出: “” 解释: 输入不存在公共前缀。
说明:所有输入只包含小写字母 a-z 。
1 2 3 4 5 6 7 8 9 10 def longestCommonPrefix (l ): if not l: return "" s1 = min (l) s2 = max (l) for i, x in enumerate (s1): if x != s2[i]: return s2[:i] return s1 print (longestCommonPrefix(['float' , 'flo' , 'flood' ]))
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1:输入: “()” 输出: true
示例 2:输入: “()[]{}” 输出: true
示例 3:输入: “(]” 输出: false
示例 4:输入: “([)]” 输出: false
示例 5:输入: “{[]}” 输出: true
1 2 3 4 5 6 7 8 def isValid (s ): while '{}' in s or '()' in s or '[]' in s: s = s.replace('{}' , '' ) s = s.replace('[]' , '' ) s = s.replace('()' , '' ) return s == '' print (isValid('()[]' ))
给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串,返回其最后一个单词的长度。如果不存在最后一个单词,请返回 0 。 说明:一个单词是指由字母组成,但不包含任何空格的字符串。
示例:输入: “Hello World” 输出: 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def lengthOfLastWord (s ): tailOfLastWord = len (s) - 1 while tailOfLastWord >= 0 and s[tailOfLastWord] == ' ' : tailOfLastWord -= 1 headOfLastWord = tailOfLastWord while headOfLastWord >= 0 and s[headOfLastWord] != ' ' : headOfLastWord -= 1 return tailOfLastWord - headOfLastWord def lengthOfLastWord2 (s ): return len (s.split(' ' )[-1 ]) if (len (s.split(' ' )) != 0 ) else 0 print (lengthOfLastWord('hello world' ))print (lengthOfLastWord2('hello world' ))
给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。
示例 1: 输入: a = “11”, b = “1” 输出: “100”
示例 2: 输入: a = “1010”, b = “1011” 输出: “10101”
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def addBinary (a, b ): r, p = '' , 0 d = len (b) - len (a) a = '0' * d + a b = '0' * -d + b for i, j in zip (a[::-1 ], b[::-1 ]): s = int (i) + int (j) + p r = str (s % 2 ) + r p = s // 2 return '1' + r if p else r print (addBinary('1011' ,'1001' ))
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def addStrings (a, b ): r, p = '' , 0 d = len (b) - len (a) a = '0' * d + a b = '0' * -d + b for i, j in zip (a[::-1 ], b[::-1 ]): s = int (i) + int (j) + p r = str (s % 10 ) + r p = s // 10 return '1' + r if p else r print (addStrings('587' ,'23' ))
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明:本题中,我们将空字符串定义为有效的回文串。
示例 1: 输入: “A man, a plan, a canal: Panama” 输出: true
示例 2: 输入: “race a car” 输出: false
1 2 3 4 5 6 7 def isPalindrome (s ): if not s: return True s = '' .join(filter (str .isalnum, s)).lower() return s == s[::-1 ] print (isPalindrome('A man, a plan, a canal: Panama' ))
假设给定 API read4 可以从文件中读取 4 个连续的字符。 现要求通过使用 read4 方法,实现 read 方法。该方法可以从文件中读取 n 个字符并将其存储到缓存数组 buf[] 中。您不能直接操作文件。
示例1: 输入: file = “abcde”, n = 5 输出: 5 解释: 当执行你的 rand 方法后,buf 需要包含 “abcde”。文件共 5 个字符,因此返回 5。
示例2: 输入: file = “leetcode”, n = 5 输出: 5 解释: 当执行你的 rand 方法后,buf 需要包含 “leetc”。文件中一共 5 个字符,因此返回 5。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 def read (buf, n ): tmp = ["" ,"" ,"" ,"" ] cnt = 0 read4(tmp) while tmp != ["" ,"" ,"" ,"" ]: for i in range (4 ): if tmp[i]: buf[cnt] = tmp[i] cnt += 1 if cnt == n + 1 : return n tmp = ["" ,"" ,"" ,"" ] read4(tmp) return cnt
给定一个只有 + 和 - 的字符串。 要求写出一个函数能计算出将连续的两个 “++” 反转成 “–”的所有情况。
示例: 输入: s = “++++” 输出: [ “–++”, “+–+”, “++–” ]
1 2 3 4 5 6 7 8 def generatePossibleNextMoves (s ): ans=[] for i in range (len (s)-1 ): if s[i]==s[i+1 ]=='+' : ans.append(s[:i]+'--' +s[i+2 :]) return ans print (generatePossibleNextMoves('+++++' ))
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例: 输入:[“h”,”e”,”l”,”l”,”o”] 输出:[“o”,”l”,”l”,”e”,”h”]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def reverseString1 (s ): s.reverse() return s def reverseString2 (s ): s[0 ::] = s[::-1 ] return s def reverseString3 (s ): i, j = 0 , len (s) - 1 while i < j: s[i], s[j] = s[j], s[i] i += 1 j -= 1 return s print (reverseString1(list ('abcdef' )))print (reverseString2(list ('abcdef' )))print (reverseString3(list ('abcdef' )))
编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
示例: 输入: “hello” 输出: “holle”
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def reverseVowels (s ): seed = "aeiouAEIOU" s = list (s) l, r = 0 , len (s)-1 while l < r: if s[l] not in seed: l += 1 if s[r] not in seed: r -= 1 if s[l] in seed and s[r] in seed: s[l], s[r] = s[r], s[l] l += 1 r -= 1 return "" .join(s) print (reverseVowels(list ('hello' )))
为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。 给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成,返回 true ;否则返回 false。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 def canConstruct1 (ransomNote, magazine ): ''' 统计两个字符串的char,进行减法操作,如果有剩余证明结果是false。 ''' import collections return not collections.Counter(ransomNote) - collections.Counter(magazine) def canConstruct2 (ransomNote, magazine ): magazine_dict = {} for c in magazine: if c in magazine_dict: magazine_dict[c] += 1 else : magazine_dict[c] = 1 for c in ransomNote: if c in magazine_dict and magazine_dict[c] > 0 : magazine_dict[c] -= 1 else : return False return True print (canConstruct1('abcc' ,'aabc' ))print (canConstruct2('abcc' ,'aabc' ))
给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
示例1: s = “leetcode” 返回 0
示例2: s = “loveleetcode” 返回 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 def firstUniqChar1 (s ): dic = {c: s.count(c) for c in set (s)} for i, c in enumerate (s): if dic[c] == 1 : return i return -1 def firstUniqChar2 (s ): min_unique_char_index = len (s) for c in "abcdefghijklmnopqrstuvwxyz" : i = s.find(c) if i != -1 and i == s.rfind(c): min_unique_char_index = min (min_unique_char_index, i) return min_unique_char_index if min_unique_char_index != len (s) else -1 print (firstUniqChar1('loveleetcode' ))print (firstUniqChar2('loveleetcode' ))
给定一组字符,使用原地算法将其压缩。压缩后的长度必须始终小于或等于原数组长度。数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。 在完成原地修改输入数组后,返回数组的新长度。
示例 1: 输入: [“a”,”a”,”b”,”b”,”c”,”c”,”c”] 输出: 返回6,输入数组的前6个字符应该是:[“a”,”2”,”b”,”2”,”c”,”3”] 说明: “aa”被”a2”替代。”bb”被”b2”替代。”ccc”被”c3”替代。
示例 2: 输入: [“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”] 输出: 返回4,输入数组的前4个字符应该是:[“a”,”b”,”1”,”2”]。 说明: 由于字符”a”不重复,所以不会被压缩。”bbbbbbbbbbbb”被“b12”替代。 注意每个数字在数组中都有它自己的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 def compress (chars ): count = 1 length = len (chars) for index in range (length-1 , -1 , -1 ): if index > 0 and chars[index] == chars[index-1 ]: count += 1 else : end = index+count chars[index: end] = [chars[index]] if count == 1 else [chars[index]] + list (str (count)) count = 1 return len (chars) print (compress(["a" ,"b" ,"b" ,"b" ,"b" ,"b" ,"b" ,"b" ,"b" ,"b" ,"b" ,"b" ,"b" ]))
给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
示例 1: 输入: “abab” 输出: True 解释: 可由子字符串 “ab” 重复两次构成。
示例 2: 输入: “aba” 输出: False
1 2 3 4 5 6 7 8 9 10 11 12 def repeatedSubstringPattern1 (s ): return (s + s)[1 :-1 ].count(s) != 0 def repeatedSubstringPattern2 (s ): return (s + s)[1 :-1 ].find(s) != -1 def repeatedSubstringPattern3 (s ): return s in (s + s)[1 : -1 ] print (repeatedSubstringPattern1('aba' ))print (repeatedSubstringPattern2('aba' ))print (repeatedSubstringPattern3('aba' ))
给定一个单词,你需要判断单词的大写使用是否正确。 我们定义,在以下情况时,单词的大写用法是正确的: 全部字母都是大写,比如”USA”。 单词中所有字母都不是大写,比如”leetcode”。 如果单词不只含有一个字母,只有首字母大写, 比如 “Google”。 否则,我们定义这个单词没有正确使用大写字母。
示例 1: 输入: “USA” 输出: True
示例 2: 输入: “FlaG” 输出: False
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def detectCapitalUse1 (word ): a = word b = word[1 :] if a == a.upper() or a == a.lower(): return True elif a[0 ] == a[0 ].upper() and b == b.lower(): return True else : return False def detectCapitalUse2 (word ): return word.isupper() or word.islower() or word.istitle() print (detectCapitalUse1('aBa' ))print (detectCapitalUse2('aBa' ))