剑指offer之Python实现
发布于 2017-07-29 · 本文总共 46776 字 · 阅读大约需要
134 分钟
数组中重复的数字
description
面试题03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
solutions
class Solution(object):
def findRepeatNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 排序；O(nlgn);O(1)
nums = sorted(nums)
pre = None
for i in range(len(nums)):
if pre == nums[i]:
return pre
pre = nums[i]
# 哈希表；O(n);O(n)
# hash_map = {}
# for num in nums:
# if num in hash_map:
# return num
# else:
# hash_map[num] = 1
# ；O(n);O(1)
# for i in range(len(nums)):
# while i != nums[i]:
# if nums[nums[i]] == nums[i]:
# return nums[i]
# nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
二维数组中的查找
description
面试题04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
solutions
best solution
O(m+n)
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not matrix[0]:
return False
col_len = len(matrix)
row_len = len(matrix[0])
i = 0
j = row_len -1
while i < col_len and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
j -= 1
else:
i += 1
return False
binary search
mlgn
class Solution1(object):
def findNumberIn2DArray(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# matrix = list(zip(matrix))
if not matrix or not matrix[0]:
return False
col_len = len(matrix)
row_len = len(matrix[0])
def binary_find(arr):
l,r = 0, len(arr)-1
while l <= r:
mid = (l + r) / 2
if target < arr[mid]:
r = mid - 1
elif target > arr[mid]:
l = mid + 1
else:
return True
return False
for i in range(col_len):
if matrix[i][row_len-1] >= target:
res = binary_find(matrix[i])
if res:
return True
else:
continue
return False
violence solution
m*n
class Solution2(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
for nums in matrix:
for num in nums:
if num == target:
return True
return False
替换空格
description
面试题05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：
0 <= s 的长度 <= 10000
solutions
方法1：遍历字符串，每次遇到空格，就将后面的元素后移，然后替换 //时间O(n^2)，空间O(1)
方法2：先统计空格数量，然后扩展数组，双指针进行填充 //时间O(n)
but
class Solution(object):
def replaceSpace(self, s):
"""
:type s: str
:rtype: str
"""
return s.replace(" ", "%20")
从尾到头打印链表
description
面试题06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
solutions
递归
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reversePrint(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
if not head:
return []
p = self.reversePrint(head.next)
p.append(head.val)
return p
使用栈
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution1(object):
def reversePrint(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
vals = []
while head:
vals.append(head.val)
head = head.next
return vals[::-1]
重建二叉树
description
面试题07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
限制：
0 <= 节点个数 <= 5000
solutions
递归
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
# inorder [左，根，右]
# postorder [左，右，根]
if not inorder or not postorder:
return None
root = TreeNode(postorder[-1])
root_index = inorder.index(root.val)
left = self.buildTree(inorder[:root_index], postorder[:root_index])
right = self.buildTree(inorder[root_index+1:], postorder[root_index:-1])
root.left = left
root.right = right
return root
迭代
TODO
用两个栈实现队列
description
232. 用栈实现队列
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
232. Implement Queue using Stacks
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
solutions
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack_in = []
self.stack_out = []
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: None
"""
self.stack_in.append(x)
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
res = self.stack_out.pop()
return res
def peek(self):
"""
Get the front element.
:rtype: int
"""
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
res = self.stack_out[-1] if self.stack_out else None
return res
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return not self.stack_in and not self.stack_out
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
斐波那契数列
description
面试题10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
注意：本题与主站 509 题相同：https://leetcode-cn.com/problems/fibonacci-number/
solutions
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
# if n < 2:
# return n
# dp = [0,1]
# for i in range(2, n+1):
# dp.append(dp[i-1] + dp[i-2])
# return dp[n] % 1000000007
a, b = 0, 1
for i in range(n):
a, b = b, a+b
return a % 1000000007
青蛙跳台阶问题
description
面试题10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
提示：
0 <= n <= 100
注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/
solutions
动态规划
class Solution1(object):
def numWays(self, n):
"""
:type n: int
:rtype: int
"""
# dp = [1,1]
# for i in range(2, n+1):
# dp.append((dp[i-1] + dp[i-2]) % 1000000007)
# return dp[n]
节省空间
class Solution(object):
def numWays(self, n):
"""
:type n: int
:rtype: int
"""
a, b = 1,1
for i in range(n):
a,b = b%1000000007, (a+b)%1000000007
return a
旋转数组的最小数字
description
153. 寻找旋转排序数组中的最小值
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]
输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]
输出: 0
153. Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0
solutions
二分查找的变形，中间mid = (i + j) / 2； 比较中间值和最右，如果比最右小，说明最小值只能在[i, mid]之间 如果mid比最右要大，则查找范围在[mid+1, j]
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i, j = 0, len(nums) - 1
while i < j:
# print(i, j)
mid = (i + j) / 2
if nums[mid] > nums[j]:
i = mid + 1
else:
j = mid
# print(i, j)
return nums[i]
矩阵中的路径
description
79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
提示：
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
79. Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally
or vertically neighboring. The same letter cell may not be used more than once.
Example:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
Constraints:
board and word consists only of lowercase and uppercase English letters.
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
solutions
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
add_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
col_len = len(board)
if not col_len or not word or not board[0]:
return False
row_len = len(board[0])
def dfs(i, j, k):
if i < 0 or j < 0 or i >= col_len or j >= row_len:
return False
if not board[i][j] or board[i][j] != word[k]:
return False
if k + 1 >= len(word):
return True
tmp = board[i][j]
board[i][j] = ""
for add_i, add_j in add_list:
res = dfs(i + add_i, j + add_j, k + 1)
if res:
return True
board[i][j] = tmp
for i in range(col_len):
for j in range(row_len):
if word[0] == board[i][j]:
res = dfs(i, j, 0)
if res:
return True
return False
机器人的运动范围
description
面试题13. 机器人的运动范围
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 1：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 100
0 <= k <= 20
solutions
class Solution(object):
def movingCount(self, m, n, k):
"""
:type m: int
:type n: int
:type k: int
:rtype: int
"""
def check_sum(n):
res = 0
while n:
res += n % 10
n /= 10
return res
visted = [(0, 0)]
for i in range(m):
for j in range(n):
if check_sum(i) + check_sum(j) <= k and ((i-1, j) in visted or (i, j-1) in visted):
visted.append((i, j))
# count += 1
return len(visted)
剪绳子
description
343. 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
343. Integer Break
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
solutions
class Solution(object):
def integerBreak(self, n):
"""
:type n: int
:rtype: int
"""
dp = [1 for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, i):
dp[i] = max(dp[i], dp[i-j]*j, (i-j)*j)
# print(dp)
return dp[-1]
class Solution2(object):
def cuttingRope(self, n):
"""
:type n: int
:rtype: int
"""
div = n / 3
if n <= 3:
return [1,1,1,2][n]
remainder = n % 3
if remainder == 0:
return 3**div
elif remainder == 1:
return (3**(div-1))*4
elif remainder == 2:
return (3**div)*2
剪绳子 II
description
面试题14- II. 剪绳子 II
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1 ]...k[m] 。请问 k[0]*k[1 ]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 1000
同上题
二进制中1的个数
description
191. Number of 1 Bits
Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).
Example 1:
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
Note:
Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3 above the input represents the signed integer -3.
Follow up:
If this function is called many times, how would you optimize it?
191. 位1的个数
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
进阶:
如果多次调用这个函数，你将如何优化你的算法？
solution
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
while n:
res += 1
n = n & (n-1)
return res
数值的整数次方
description
50. Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (xn).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−231, 231 − 1]
50. Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
solution
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n == 0:
return 1
elif n == 1:
return x
exp = abs(n)
ret = self.myPow(x, exp >> 1)
ret *= ret
if exp & 0x1 == 1:
ret = x * ret
if n > 0:
return ret
return 1.0000000000 / ret
打印从1到最大的n位数
删除链表的节点
description
237. 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
237. Delete Node in a Linked List
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Given linked list -- head = [4,5,1,9], which looks like following:
Example 1:
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Example 2:
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.
Note:
The linked list will have at least two elements.
All of the nodes' values will be unique.
The given node will not be the tail and it will always be a valid node of the linked list.
Do not return anything from your function.
solutions
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
if node.next == None:
node = None
node.val, node.next = node.next.val, node.next.next
变形题目：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteNode(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
res = ListNode()
res.next = head
new_head = res
while new_head and new_head.next:
if new_head.next.val == val:
new_head.next = new_head.next.next
new_head = new_head.next
return res.next
正则表达式匹配
表示数值的字符串
调整数组顺序使奇数位于偶数前面
description
面试题21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 10000
solutions
class Solution(object):
def exchange(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
i,j = 0,0
while j < len(nums) and i < len(nums):
if nums[i] % 2 == 1:
i += 1
else:
if nums[j] % 2 == 1:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j += 1
return nums
class Solution2(object):
def exchange(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
i, j = 0, 0
while j < len(nums):
while j < len(nums) and nums[j] % 2 == 1:
nums[i], nums[j] = nums[j], nums[i]
j += 1
i += 1
j += 1
return nums
链表中倒数第k个节点
description
面试题22. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
solutions
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getKthFromEnd(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head:
return head
first = head
second = head
while k:
k -= 1
first = first.next
while first:
first = first.next
second = second.next
return second
反转链表
description
// 206. 反转链表
// 反转一个单链表。
//
// 示例:
//
// 输入: 1->2->3->4->5->NULL
// 输出: 5->4->3->2->1->NULL
// 进阶:
// 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
// 206. Reverse Linked List
// Reverse a singly linked list.
//
// Example:
//
// Input: 1->2->3->4->5->NULL
// Output: 5->4->3->2->1->NULL
// Follow up:
//
// A linked list can be reversed either iteratively or recursively. Could you implement both?
solutions
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
type ListNode struct {
Val int
Next *ListNode
}
// 递归
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
p := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return p
}
// 迭代
func reverseList1(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
return pre
}
合并两个排序的链表
description
21. 合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
solutions
recursively
# 递归
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
# if not l1:
# return l2
# if not l2:
# return l1
# if l1.val <= l2.val:
# l1.next = self.mergeTwoLists(l1.next, l2)
# return l1
# elif l1.val > l2.val:
# l2.next = self.mergeTwoLists(l1, l2.next)
# return l2
if l1 and l2:
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
return l1 if not l2 else l2
iteratively
# 迭代
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution1(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1:
return l2
if not l2:
return l1
pre = ListNode(0)
cur = pre
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return pre.next
树的子结构
description
面试题26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3
/ \
4 5
/ \
1 2
给定的树 B：
4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000
solutions
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def dfs(self, A, B):
if not B:
return True
if not A:
return False
if A.val == B.val:
return self.dfs(A.left, B.left) and self.dfs(A.right, B.right)
else:
return False
def isSubStructure(self, A, B):
"""
:type A: TreeNode
:type B: TreeNode
:rtype: bool
"""
if not B or not A:
return False
return self.dfs(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)
二叉树的镜像
description
226. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。
226. Invert Binary Tree
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
solutions
def invertTree(self, root):
if root:
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
# Maybe make it four lines for better readability:
def invertTree(self, root):
if root:
invert = self.invertTree
root.left, root.right = invert(root.right), invert(root.left)
return root
# And an iterative version using my own stack:
def invertTree(self, root):
stack = [root]
while stack:
node = stack.pop()
if node:
node.left, node.right = node.right, node.left
stack += node.left, node.right
return root
Max Howell
对称的二叉树
description
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
说明:
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。
solutions
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution1(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def is_mirror(l, r):
if not l and not r:
return True
if not l or not r:
return False
return l.val == r.val and is_mirror(l.left, r.right) and is_mirror(l.right, r.left)
return is_mirror(root, root)
顺时针打印矩阵
description
54. 螺旋矩阵
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
solutions
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
res = []
while matrix:
res.extend(matrix.pop(0))
matrix[:] = list(zip(*matrix))[::-1]
return res
包含min函数的栈
description
155. 最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
155. Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
solution
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.items = []
self.mins = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.items.append(x)
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
# print(self.mins)
def pop(self):
"""
:rtype: None
"""
if not self.items:
return None
res = self.items.pop()
# self.mins.pop()
if self.mins and self.mins[-1] == res:
self.mins.pop()
return res
def top(self):
"""
:rtype: int
"""
if not self.items:
return None
return self.items[-1]
def getMin(self):
"""
:rtype: int
"""
if self.mins:
return self.mins[-1]
return None
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
栈的压入、弹出序列
description
946. 验证栈序列
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
946. Validate Stack Sequences
Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.
Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Example 2:
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.
Note:
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed is a permutation of popped.
pushed and popped have distinct values.
solution
class Solution(object):
def validateStackSequences(self, pushed, popped):
"""
:type pushed: List[int]
:type popped: List[int]
:rtype: bool
"""
stack = []
k = 0
for i in range(len(pushed)):
stack.append(pushed[i])
while stack and stack[-1] == popped[k]:
stack.pop()
k += 1
return k == len(pushed)
# Runtime: 52 ms, faster than 95.70% of Python online submissions for Validate Stack Sequences.
# Memory Usage: 12.8 MB, less than 87.70% of Python online submissions for Validate Stack Sequences.
从上到下打印二叉树
description
面试题32 - I. 从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
提示：
节点总数 <= 1000
solutions
递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
def dfs(root, deep):
if not root:
return
if len(res) < deep + 1:
res.append([])
res[deep].append(root.val)
dfs(root.left, deep+1)
dfs(root.right, deep+1)
dfs(root, 0)
nums = []
# print(res)
for l in res:
nums.extend(l)
return nums
迭代
class Solution1(object):
def levelOrder(self, root):
import collections
if not root: return []
res, queue = [], collections.deque()
queue.append(root)
while queue:
node = queue.popleft()
res.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return res
从上到下打印二叉树 II
description
102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
102. 二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
solution
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
self.vals = []
def dfs(root, deepth):
if not root:
return
if len(self.vals) < deepth + 1:
self.vals.append([root.val])
else:
self.vals[deepth].append(root.val)
dfs(root.left, deepth + 1)
dfs(root.right, deepth + 1)
dfs(root, 0)
return self.vals
从上到下打印二叉树 III
description
103. 二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
solutions
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution1(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
self.vals = []
def dfs(root, deepth):
if not root:
return
if not self.vals or len(self.vals) < deepth +1:
self.vals.append([root.val])
else:
if deepth % 2 == 1:
self.vals[deepth] = [root.val] + self.vals[deepth]
else:
self.vals[deepth].append(root.val)
dfs(root.left, deepth + 1)
dfs(root.right, deepth + 1)
dfs(root, 0)
# for i in range(len(self.vals)):
# if i % 2 == 1:
# self.vals[i] = self.vals[i][::-1]
return self.vals
# Runtime: 20 ms, faster than 74.47% of Python online submissions for Binary Tree Zigzag Level Order Traversal.
# Memory Usage: 13 MB, less than 82.26% of Python online submissions for Binary Tree Zigzag Level Order Traversal.
二叉搜索树的后序遍历序列
二叉树中和为某一值的路径
复杂链表的复制
二叉搜索树与双向链表
序列化二叉树
字符串的排列
数组中出现次数超过一半的数字
最小的k个数
数据流中的中位数
连续子数组的最大和
description
# leetcode 53
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
solutions
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return -2147483648
max_sum, cur_sum = nums[0], nums[0]
for i in range(1, len(nums)):
cur_sum = nums[i] if cur_sum < 0 else cur_sum + nums[i]
max_sum = max(cur_sum, max_sum)
return max_sum
class Solution1(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(1, len(nums)):
nums[i] = max(nums[i], nums[i] + nums[i-1])
return max(nums)
1～n整数中1出现的次数
数字序列中某一位的数字
description
400. 第N个数字
在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
注意:
n 是正数且在32位整数范围内 ( n < 231)。
示例 1:
输入:
3
输出:
3
示例 2:
输入:
11
输出:
0
说明:
第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。
400. Nth Digit
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:
3
Output:
3
Example 2:
Input:
11
Output:
0
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
solutions
数学题
class Solution(object):
def findNthDigit(self, n):
"""
:type n: int
:rtype: int
"""
steps = [10]
j = 2
step = 10
while step <= 2**31 and n >= step:
step += j*9*(pow(10, (j-1)))
steps.append(step)
j += 1
if n < 10:
return n
for k in range(1, len(steps)+1):
if n < steps[k]:
return int(str(10**k + (n - steps[k-1]) / (k+1))[(n-steps[k-1])%(k+1)])
把数组排成最小的数
description
面试题45. 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
solutions
golang
func minNumber(nums []int) string {
strs := []string{}
for i := range nums {
strs = append(strs, strconv.Itoa(nums[i]))
}
sort.Slice(strs, func(i, j int) bool {
x := strs[i]
y := strs[j]
return x+y < y+x
})
return strings.Join(strs, "")
}
python
class LargerNumKey(str):
def __lt__(x, y):
return x+y < y+x
class Solution(object):
def minNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
new_nums = sorted(map(str, nums), key=LargerNumKey)
return "".join(new_nums)
import functools
class Solution1(object):
def minNumber(self, nums):
def sort_rule(x, y):
a, b = x + y, y + x
if a > b: return 1
elif a < b: return -1
else: return 0
strs = [str(num) for num in nums]
strs.sort(key=functools.cmp_to_key(sort_rule))
return ''.join(strs)
把数字翻译成字符串
description
面试题46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
0 <= num < 231
solution
class Solution(object):
def translateNum(self, num):
"""
:type num: int
:rtype: int
"""
self.res_list = []
vals = [int(i) for i in str(num)]
a_num = ord("a")
def dfs(s=None, res=""):
if not s:
self.res_list.append(res)
else:
tmp = s.pop(0)
dfs(s[:], res+chr(a_num+tmp))
if s:
tmp = tmp*10 + s.pop(0)
if 10 <= tmp <=25:
dfs(s[:], res+chr(a_num+tmp))
dfs(vals, "")
return len(self.res_list)
动态规划
class Solution1(object):
def translateNum(self, num):
"""
:type num: int
:rtype: int
"""
num_list = [i for i in str(num)]
dp = [1 for i in range(len(num_list))]
for i in range(1, len(num_list)):
if 10 <= int(num_list[i - 1]) * 10 + int(num_list[i]) <= 25:
dp[i] = dp[i - 1] + dp[i - 2]
else:
dp[i] = dp[i - 1]
return dp[-1]
礼物的最大价值
description
面试题47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 200
0 < grid[0].length <= 200
solution
动态规划
class Solution(object):
def maxValue(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
dp = []
for i in range(len(grid)):
# col = []
dp.append([])
for j in range(len(grid[0])):
val = grid[i][j]
if i- 1 >= 0 and j - 1 >= 0:
val += max(dp[i - 1][j], dp[i][j - 1])
elif i - 1 >= 0:
val += dp[i - 1][j]
elif j - 1 >= 0:
val += dp[i][j - 1]
dp[i].append(val)
return dp[-1][-1]
最长不含重复字符的子字符串
description
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
solutions
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = maxLength = 0
strmap = {}
for i in range(len(s)):
if s[i] in strmap and strmap[s[i]] >= start:
start = strmap[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
strmap[s[i]] = i
return maxLength
丑数
description
264. 丑数 II
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
264. Ugly Number II
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Example:
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:
1 is typically treated as an ugly number.
n does not exceed 1690.
solution
k[1 ] = min( k[0]x2, k[0]x3, k[0]x5). The answer is k[0]x2. So we move 2’s pointer to 1. Then we test:
k[2 ] = min( k[1 ]x2, k[0]x3, k[0]x5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
res = [1 ]
i2 ,i3 ,i5 = 0 ,0 ,0
for i in range(1691):
num = min(res[i2] *2, res[i3] *3, res[i5] *5)
if len(res) == n:
break
if num == res[i2] *2:
i2 += 1
if num == res[i3] *3:
i3 += 1
if num == res[i5] *5:
i5 += 1
# print(num, i2, i3, i5,res)
res.append(num)
# print(res)
return res[-1]
第一个只出现一次的字符
description
387. 字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
注意事项：您可以假定该字符串只包含小写字母。
387. First Unique Character in a String
Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
Examples:
s = "leetcode"
return 0.
s = "loveleetcode",
return 2.
Note: You may assume the string contain only lowercase letters.
solutions
class Solution(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: str
"""
letters='abcdefghijklmnopqrstuvwxyz'
indexs = [s.index(l) for l in letters if s.count(l) == 1]
return s[min(indexs)] if indexs else " "
class Solution1(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: str
"""
hash_map = {}
import collections
counter = collections.Counter(s)
for c in s:
if counter[c] == 1:
return c
return " "
class Solution2(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
key_dict = {}
for key in s:
if key in key_dict:
key_dict[key] += 1
else:
key_dict[key] = 1
for i in range(len(s)):
if key_dict[s[i]] == 1:
return i
return -1
数组中的逆序对
description
面试题51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
solution
归并排序
class Solution(object):
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# count = 0
# for i in range(len(nums)):
# for j in range(i+1, len(nums)):
# if nums[j] < nums[i]:
# count += 1
# return count
# self.count = 0
# def quick_sort(arr):
# if len(arr) < 2:
# return arr
# left, right = [], []
# for ar in arr[1:]:
# if ar <= arr[0]:
# left.append(ar)
# else:
# self.count += 1
# right.append(ar)
# return quick_sort(left) + [arr[0]] + quick_sort(right)
# quick_sort(nums)
# return self.count
self.count = 0
def merge_sort(l, r):
if r - l <= 1:
return
mid = ( l +r) // 2
# print(l, r, mid)
merge_sort(l, mid)
merge_sort(mid, r)
i, j = l, mid
tmp = []
while j < r and i < mid:
if nums[i] > nums[j]:
self.count += mid - i
tmp.append(nums[j])
j += 1
else:
tmp.append(nums[i])
i += 1
while j < r:
tmp.append(nums[j])
j += 1
while i < mid:
tmp.append(nums[i])
i += 1
nums[l:r] = tmp
return
merge_sort(0, len(nums))
return self.count
两个链表的第一个公共节点
description
160. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
160. Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
solution
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
headA_ = headA
headB_ = headB
while headA_ != headB_:
headA_ = headA_.next if headA_ else headB
headB_ = headB_.next if headB_ else headA
return headA_
在排序数组中查找数字 I
description
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
34. Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
solutions
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
i = 0
j = len(nums) - 1
res = [-1, -1]
while i <= j:
print(i, j, nums[i], nums[j])
mid = (i + j) / 2
if nums[mid] == target:
l = r = mid
while l-1 >=0 and nums[l-1] == target:
l -= 1
while r+1 <= len(nums) -1 and nums[r+1] == target:
r += 1
res = [l, r]
break
elif nums[mid] < target:
i = mid + 1
elif nums[mid] > target:
j = mid - 1
return res
class Solution1(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left, right = -1, -1
i, j = 0, len(nums) - 1
while i < j:
mid = (i + j) / 2
if nums[mid] < target:
i = mid + 1
else:
j = mid
if i >= len(nums) or nums[i] != target:
return [-1, -1]
left = i
i, j = 0, len(nums) - 1
while i <= j:
mid = (i + j) / 2
if nums[mid] > target:
j = mid - 1
else:
i = mid + 1
right = i - 1
return [left, right]
0～n-1中缺失的数字
description
面试题53 - II. 0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制：
1 <= 数组长度 <= 10000
solutions
有序的数组首先想到二分法
二分法
class Solution1(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# return sum(range(len(nums)+1)) - sum(nums)
i, j = 0, len(nums) -1
while i <= j:
mid = (i+j) / 2
if nums[mid] == mid:
i = mid + 1
else:
j = mid - 1
return i
变形—-无序
description
268. Missing Number
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
268. 缺失数字
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例 2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
solutions
# 求和
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return len(nums) *(len(nums) + 1) / 2 - sum(nums)
# 位运算，异或
class Solution2:
def missingNumber(self, nums):
missing = len(nums)
for i, num in enumerate(nums):
missing ^= i ^ num
return missing
def missingNumber(self, nums):
n = len(nums)
return functools.reduce(operator.xor, nums) ^ [n, 1, n+1, 0][n % 4]
def missingNumber1(self, nums):
return (set(range(len(nums)+1)) - set(nums)).pop()
数组中数字出现的次数(72.6%-中等)
数组中数字出现的次数 II(78.9%-中等)
和为s的两个数字(65.2%-简单)
description
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1 ] = 2 + 7 = 9
所以返回 [0, 1]
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1 ] = 2 + 7 = 9,
return [0, 1].
solutions
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hash_map = {}
for i in range(len(nums)):
if nums[i] not in hash_map:
hash_map[target - nums[i]] = i
else:
return [hash_map[nums[i]], i]
和为s的连续正数序列(68.5%-简单)
description
面试题57 - II.和为s的连续正数序列
LCOF
English
description is not available
for the problem.Please switch to Chinese.
面试题57 - II.和为s的连续正数序列
输入一个正整数
target ，输出所有和为
target
的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例
1：
输入：target = 9
输出：[[2, 3, 4], [4, 5]]
示例
2：
输入：target = 15
输出：[[1, 2, 3, 4, 5], [4, 5, 6], [7, 8]]
限制：
1 <= target <= 10 ^ 5
solution
class Solution(object):
def findContinuousSequence(self, target):
"""
:type target: int
:rtype: List[List[int]]
"""
max = (target + 1) / 2 + 1
i, j = 1, 1
sum_ = 0
res = []
# for j in range():
while i <= max:
# sum_ = (i + j) * (j - i + 1) / 2
if sum_ == target:
res.append([k for k in range(i, j)])
i += 1
j += 1
sum_ += j
sum_ -= i
if sum_ > target:
sum_ -= i
i += 1
if sum_ < target:
sum_ += j
j += 1
return res
翻转单词顺序(41.8%-简单)
description
151. Reverse Words in a String
Given an input string, reverse the string word by word.
Example 1:
Input: "the sky is blue"
Output: "blue is sky the"
Example 2:
Input: " hello world! "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.
Example 3:
Input: "a good example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
Note:
A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.
Follow up:
For C programmers, try to solve it in-place in O(1) extra space.
151. 翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶：
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。
solutions
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return " ".join([i for i in s.strip().split(" ")[::-1] if i])
左旋转字符串(84.6%-简单)
description
面试题58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
solutions
class Solution(object):
def reverseLeftWords(self, s, n):
"""
:type s: str
:type n: int
:rtype: str
"""
length = len(s)
n = n % length
return s[n:]+s[:n]
滑动窗口的最大值(43.9%-简单)
239. 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
239. Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Follow up:
Could you solve it in linear time?
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
solutions
暴力破解
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or not k:
return []
res = []
for i in range(len(nums)-k+1):
res.append(max(nums[i:i+k]))
return res
单调队列
class Solution1(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or not k:
return []
res = []
q = []
maxs = []
for i in range(len(nums)):
num = nums[i]
q.append(num)
while maxs and num > maxs[-1]:
maxs.pop()
maxs.append(num)
# print(maxs)
if len(q) >= k:
res.append(maxs[0])
val = q.pop(0)
if val == maxs[0]:
maxs.pop(0)
return res
队列的最大值(48.4%-中等)
n个骰子的点数(53.3%-简单)
扑克牌中的顺子(43.7%-简单)
圆圈中最后剩下的数字(61.2%-简单)
股票的最大利润(63.4%-中等)
description
121. Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
solutions
dp[i]=max(dp[i−1],prices[i]−minprice)
动态规划
class Solution1(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
k = 1
cash, asset = [float('-inf')] * (k + 1), [0] * (k + 1)
for price in prices:
for i in range(1, k + 1):
cash[i] = max(cash[i], asset[i - 1] - price)
asset[i] = max(asset[i], cash[i] + price)
return asset[-1]
solution2
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
def max_profit(arr):
min_price = arr[0] if arr else 0
profit = 0
for i in arr:
min_price = min(i, min_price)
profit = max(i-min_price, profit)
return profit
return max_profit(prices)
求1+2+…+n(85.9%-中等)
description
面试题64. 求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3
输出: 6
示例 2：
输入: n = 9
输出: 45
限制：
1 <= n <= 10000
solution
class Solution(object):
def sumNums(self, n):
"""
:type n: int
:rtype: int
"""
if not n:
return 0
return n + self.sumNums(n-1)