#########简单#########
共25道：
1. 两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums) # len（[2, 7, 11, 15]） = 4
for i in range(0, n-1): #range(x,y)的取值范围是[x,y),下标值从0开始，同样元素不能重复所以range（0，n-1）
for j in range(i+1, n):
if(nums[i] + nums[j] == target):
return [i, j]
2. 给定一个 32 位有符号整数，将整数中的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
s = int(str(abs(x))[::-1]) #取绝对值，翻转 if s > 2147483647 or s < -2147483648 : #如果溢出 返回0
return 0
return s if x > 0 else -s #如果原始值<0，反转后的值为-s
3.回文判断
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
x = str(x)
huiwen = x[::-1] #翻转字符串变成回文
result = cmp(x,huiwen) #比较与原字符串是否相同
return True if result==0 else False
4. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
解题思路： zip函数可以将对象中对应的元素打包成一个个元组，然后返回由这些元组（tuple）组成的列表，然后通过len（set（i））判断如果存在len(set(i)) > 1 返回“”，停止迭代； 否则 ans += i[0] # i[0] 是str类型数据
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
# write your code here
ans = "" for i in zip(*strs): #zip（*strs） 如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。
if len(set(i)) > 1: #set()去掉重复的字符，如果长度为1，则表示存在公共字符
return ans
ans += i[0] return ans
5. x 的平方根
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
思路：python中内置函数return int(math.sqrt(x))； 二分法 mid = (min + max) // 2
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
#return int(math.sqrt(x)) min = 0
max = x
mid = x // 2 #向下取整
while min <= max:
m =mid * mid
if m > x:
max = mid -1
elif m < x:
min = mid + 1
else:
return mid
break
mid = (min + max) // 2
return mid
6. 实现strStr()
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
return haystack.find(needle)
7.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
解题思路：考察栈操作；如果收到一个右括号，但是res中无左括号，直接返回False，其余情况，出栈一个左括号，判断左括号+右括号是否有效；
如果所有括号对都满足，但是res还有左括号，返回False
class Solution:
def isValid(self, s):
# Write your code here
if s is None: return False
x = ['[','(','{']
y = ["]",")","}"]
z = ["()","[]","{}"]
res = []
for i in s:
if i in x:
res.append(i) # 入栈
elif i in y:
# 如果收到一个右括号，但是res中无左括号，直接返回False
if res == []:
return False
else:
temp = res.pop(-1) + i
# 其余情况，出栈一个左括号，判断左括号+右括号是否有效
if temp not in z:
return False
# 如果所有括号对都满足，但是res还有左括号，返回False
if len(res) != 0:
return False
return True
8. 删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为1,2。 你不需要考虑数组中超出新长度后面的元素。
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if (len(nums) <= 0): #特殊情况判断
return 0
else:
i = 0 # 下标值从0开始
for j in range(0, len(nums)):
if (nums[j] != nums[i]):
i = i + 1
nums[i] = nums[j] #原地删除重复出现的元素
return i + 1
#########中等#########
共15道
#########困难#########
共10道