LeetCode 题库

1、回文数

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

示例 1:

输入: 121
输出: true

示例 2:

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

示例 3:

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

Python解答：

# 回文数
def isPalindrome(self, x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return False

    revertedNumber = 0
    while x > revertedNumber:
        revertedNumber = revertedNumber * 10 + x % 10
        x = int(x/10)
    return x == revertedNumber or x == int(revertedNumber/10)

2、罗马数字转整数

题干：罗马数字包含以下七种字符: 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。

Python解答：

def romanToInt(self, s):
    dic = {"M":1000,"D":500,"C":100,"L":50,"X":10,"V":5,"I":1}
    result = 0
    for i in range(len(s) - 1):
        result = result - dic[s[i]] if dic[s[i]] < dic[s[i+1]] else result + dic[s[i]]
    return result + dic[s[-1]]

3、最长公共前缀

题干：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例 1:

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

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

Python解答：:

def longestCommonPrefix(self, strs):
    if len(strs) == 0:
        return ''
    prefix = strs[0]
    for index in range(1, len(strs)):
        while strs[index].find(prefix) != 0:
            prefix = prefix[0:len(prefix)-1]
            if len(prefix) == 0:
                return ''
    return prefix

4、 有效的括号

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

Python解答：:

def isValid(self, s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s :
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

5、 删除排序数组中的重复项

**题干：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。**

示例 1:

给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

Python解答：:

#  删除排序数组中的重复项
def removeDuplicates(self, nums):
    if len(nums) == 0 : return 0
    i = 0
    for j in range(1,len(nums)):
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    return i + 1

6、移除元素

题干：给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

Python解答

# 移除元素
def removeElement(self, nums, val):
    if not nums: return 0
    
    i = 0 
    for value in nums:
        if val != value:
            nums[i] = value
            i += 1
        
    return i

7、存在重复

给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1]
输出: true

示例 2:

输入: [1,2,3,4]
输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

Python解答

def containsDuplicate(nums):
    temp = set(nums)
    if len(temp) == len(nums):
        return False
    else:
        return True