给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = {}
for index, num in enumerate(nums):
#enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
another_num = target - num
if another_num in res:
return [res[another_num], index]
res[num] = index
return None
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入:123
输出:321
示例 2:
输入:-123
输出:-321
示例 3:
输入:120
输出:21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
解：
class Solution:
def reverse(self, x: int) -> int:
if x==0:
return 0
str_x = str(x) #转换成字符串str
x = ''
if str_x[0] == '-': #如果是负数
x += '-'
x += str_x[len(str_x)-1::-1].lstrip("0").rstrip("-")
#str[len(str) -1::-1]：字符串[开始点，结束点，步长]，步长为负，从右到左
#lstrip() 方法用于截掉字符串左边的空格或指定字符；rstrip()方法用于截掉字符串右边的空格或指定字符。
x = int(x) #变回整数int
if -2**31
return x
return 0
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入:121
输出:true
示例 2:
输入:-121
输出:false
解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入:10
输出:false
解释:从右向左读, 为 01 。因此它不是一个回文数。
解：
class Solution:
def isPalindrome(self, x: int) -> bool:
if x<0:
return False
else:
res = str(x)[::-1] #逆序
if res == str(x):
return True
else:
return False
罗马数字包含以下七种字符: 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.
解：
class Solution:
def romanToInt(self, s: str) -> int:
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
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入:["flower","flow","flight"]
输出:"fl"
示例 2:
输入:["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
解：
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
ss = list(map(set, zip(*strs)))#ss = [{'f'}, {'l'}, {'i', 'o'}, {'w', 'g'}]
res = ""
for i, x in enumerate(ss):
x = list(x)
if len(x) > 1:
break
res = res + x[0]
return res
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入:"()"
输出:true
示例 2:
输入:"()[]{}"
输出:true
示例 3:
输入:"(]"
输出:false
示例 4:
输入:"([)]"
输出:false
示例 5:
输入:"{[]}"
输出:true
解：
class Solution:
def isValid(self, s: str) -> bool:
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
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 == None: #注意判断链表为空的情况
return l2
elif l2 == None:
return l1
lN = None #设置新链表
if l1.val
lN = l1
lN.next = self.mergeTwoLists(l1.next,l2)
else:
lN = l2
lN.next = self.mergeTwoLists(l1,l2.next)
return lN
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
//nums是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
解：
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if nums == []: #判断列表为空的情况
return None
else:
a = nums[0]
for i in nums[1:]:
if i == a: #后一个数值与前一个比较
nums.remove(i) #相同的数删除
else:
a = i
return len(nums)
给定一个数组 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。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
解：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
if nums == []: #判断列表为空的情况
return None
else:
for i in range(len(nums)):
if val in nums:
nums.remove(val)
return len(nums)
实现 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() 定义相符。
解：
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
else:
l1 = len(needle)
l2 = len(haystack)
i = 0
for x in haystack:
if x == needle[0] and i+l1 <= l2 and haystack[i:i+l1] == needle:
return i
i +=1
return -1
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入:[1,3,5,6], 5
输出:2
示例 2:
输入:[1,3,5,6], 2
输出:1
示例 3:
输入:[1,3,5,6], 7
输出:4
示例 4:
输入:[1,3,5,6], 0
输出:0
解：
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if target > nums[-1]:
return len(nums)
if target < nums[0]:
return 0
if nums[0] <= target <= nums[-1]:
for i in range(len(nums)):
if nums[i] == target:
return i
elif nums[i] < target < nums[i+1]:
return i+1
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入:[-2,1,-3,4,-1,2,1,-5,4],
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大，为 6。
解：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
nums[i]= nums[i] + max(nums[i-1], 0)
return max(nums)
给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例:
输入:"Hello World"
输出:5
解：
class Solution:
def lengthOfLastWord(self, s: str) -> int:
#s = "Hello World"
l = s.split()
#l = ['Hello', 'World']
if len(l)==0:
return 0
return len(l[-1])
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入:[1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。
示例 2:
输入:[4,3,2,1]
输出:[4,3,2,2]
解释:输入数组表示数字 4321。
解：
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
num = ''.join(map(str, digits))
print(num) # 123
result = map(int, str(int(num) + 1))
return list(result) #[1,2,4]
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入:a = "11", b = "1"
输出:"100"
示例 2:
输入:a = "1010", b = "1011"
输出:"10101"
解：
class Solution:
def addBinary(self, a: str, b: str) -> str:
x = int(a,2) #二进制转换成十进制
y = int(b,2)
z = bin(x+y)[2:] #十进制转换成二进制
return z
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入:4
输出:2
示例 2:
输入:8
输出:2
说明:8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
解：
class Solution:
def mySqrt(self, x: int) -> int:
if x <= 1:
return x
else:
for i in range(x+1):
if i*i > x:
return i-1
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入：2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
解：
class Solution:
def climbStairs(self, n: int) -> int:
a =1
b =1
for i in range(n):
a,b = b,a+b
return a
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入:1->1->2
输出:1->2
示例 2:
输入:1->1->2->3->3
输出:1->2->3
解：
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
ans = head
while head != None:
if head.next != None and head.val == head.next.val:
head.next = head.next.next
else:
head = head.next
return ans
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解：
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
res1 = nums1[0:m]
res2 = nums2[0:n]
nums1[0:m+n]= sorted(res1+res2)
解：（二）
res1 = nums1[0:m]
res2 = nums2[0:n]
res1.extend(res2)
nums1[0:m+n]=sorted(res1)
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出:true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出:false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出:false
解：
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p == None and q == None:
return True
elif p and q:
if p.val == q.val:
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
else:
return False
else:
return False
