## Leetcode-70 爬楼梯问题（DP）

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.

$stairs(n) = stairs(n-1) + stairs(n-2)$，只需要初始化好退出递归的条件就算写完了。

class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 1:
return 1
if n == 2:
return 2
return self.climbStairs(n - 1) + self.climbStairs(n - 2)


class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
refs = dict() # 建立字典类型备忘录
def rec(n):
# 初始条件写入备忘录
if n <= 1:
refs[n] = 1
return 1
if n == 2:
refs[n] = 2
return 2
# 存在于字典的直接输出
if n in refs:
return refs[n]
else:
refs[n] = rec(n - 1) + rec(n - 2)
return refs[n]
return rec(n)


class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
res = [1, 1, 2] #初始化
if n >=3:
for i in range(3, n + 1):
res.append(res[i - 1] + res[i - 2])
return res[n]


class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 1:
return 1
if n == 2:
return 2
if n >= 3:
first, second = 1, 2
for i in range(3, n + 1):
third = first + second
first = second
second = third
return second


## leetcode-242 重排校验

Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true

class Solution:
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
origin = sorted(list(s))
current = sorted(list(t))
return origin == current


from collections import Counter
class Solution:
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
return Counter(s) == Counter(t)


## leetcode-104 二叉树最大深度

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Given binary tree [3,9,20,null,null,15,7],return its depth = 3.

max(0, None) = 0


class Solution:
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1


## leetcode-160 链表交集

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

A:          a1 → a2
↘
c1 → c2 → c3
↗
B:     b1 → b2 → b3


begin to intersect at node c1.

1. 指针顺序遍历，解决一个问题就是2个链表长度不同，所以第一步要遍历得到2个链表的长度（这块可能空间复杂度开销比较大）。将长链表向前移动至剩余链表长度与短链表一致。
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
return None
len_a, len_b = 0, 0
# 赋值计算长度
while p:
p = p.next
len_a += 1
while q:
q = q.next
len_b += 1

# 赋值截断到相同长度
if len_a > len_b:
for i in range(len_a - len_b):
p = p.next
else:
for i in range(len_b - len_a):
q = q.next

while p != q:
p = p.next
q = q.next
return p

1. 最大的障碍是2个链表长度不同，所以有一个巧妙的办法来补齐。就是当一个链表先行到达链表尾部时，将Next指针去指向另一个链表的头部，同理另一个链表也同样如此，这样就保证了在O（m+n）内一定能找到结果。举个例子：
ListNodeA = 0, 9, 1, 2, 4
LIstNodeB = 3, 2, 4
Path of A -> B = 0, 9, 1, 2, 4, 3, 2, 4
Path of B -> A = 3, 2, 4, 0, 9, 1, 2, 4
这样只需要遍历一次，如果遍历结束2个指针仍然不同都指向None，也就没有交集.
class Solution(object):

"""
:rtype: ListNode
"""

while p != q:
p = headB if p is None else p.next
q = headA if q is None else q.next
return p


## Leetcode-204 质数个数

Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

import math
class Solution:
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
import math
count = 0

# 一个判断是否为质数的方法
def judge_prime(w):
sqrt_w = int(math.sqrt(w))
# 迭代相除直到sqrt(w)
# 注意传入2时，sqrt(2) + 1 = 2， range(2, 2)不会执行，因此还是会返回1
# 不然边界条件太乱了。
for i in range(2, sqrt_w + 1):
if x % i == 0:
return 0

return 1

for x in range(2, n):
count = count + judge_prime(x)

return count


def countPrimes(self, n):
if n < 3:
return 0
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
return sum(primes)


1. 创建一个数组，长度为n个True，第0，1个位置设置为False，即0和1不是质数。
2. 从2开始（True，初始化），用2举例，以2*2作为起点开始迭代，迭代的终点是n，步长为2，将满足的都标记为False。
3. 同理3，4由于已经被2标记了跳过，5同理，6被标记，7同理，循环的终点就是$\sqrt{n}$。这里解释一下，因为一共有n个数，每次的起点是i*i，这是因为避免了重复的计算，比如3是从3*3开始的，因为3*2已经计算过了，$\sqrt{n} * \sqrt{n}$作为终点也是保证了不重复计算。总的遍历从2到$\sqrt{n}$，次数下降了指数级别。
4. 这里又借助了python list的可以设置变步长的性质 [i*i : n : i]，也不需要额外开辟更大的空间，可以说是时间复杂度和空间复杂度都做到了极致。
5. AC了，但是凭空我肯定是想不到的。

## Leetcode-17 Letter Combinations of a Phone Number 字母组合

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

(letters = {‘2’: ‘abc’, ‘3’: ‘def’, ‘4’: ‘ghi’, ‘5’: ‘jkl’,
‘6’: ‘mno’, ‘7’: ‘pqrs’, ‘8’: ‘tuv’, ‘9’: ‘wxyz’})
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
letters = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}

def dfs(res, index):
new_lts = [i for i in letters[input[index]]]
res = [i + j for i in res for j in new_lts] # 拼接生成最新的结果
index += 1
# 递归结束标志
if index > len(input) - 1:
return res
else:
return dfs(res, index) 每次传入当前结果，以及下一个新的数字键

input = list(digits)
如果输入为空，则返回空。
if len(input) < 1:
return []
# 初始化从1开始
initial = [i for i in letters[input[0]]]
idx = 1
if len(input) == 1:
return initial

return dfs(initial, idx)


class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
letters = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}

input = list(digits)
if len(input) < 1:
return []

comb = [i for i in letters[input[0]]]
for num in input[1:]:
comb = [i + j for i in comb for j in letters[num]]
return comb


$$comb(n) = F(\ comb(n-1),\ curr(n)\ )$$

class Solution:
# @param {string} digits
# @return {string[]}
def letterCombinations(self, digits):
mapping = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
if len(digits) == 0:
return []
if len(digits) == 1:
return list(mapping[digits[0]])
prev = self.letterCombinations(digits[:-1])
return [s + c for s in prev for c in additional] #生成新的组合


Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 2:
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

class Solution:
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
#先检查边界
if len(g) == 0 or len(s) == 0:
return 0
count = 0

for ck in s:
tmp = ck
for px in g:
if ck >= px and (ck - px <= tmp):
tmp = ck - px
if tmp == 0: #等于0，立刻跳出开始下一个
count += 1
g.remove(px)
break
if tmp < ck and tmp != 0:
g.remove(ck - tmp)
count += 1
return count


class Solution:
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
#先检查边界
if len(g) == 0 or len(s) == 0:
return 0
count = 0
g.sort()
s.sort()
for ck in s:
for px in g:
if ck >= px:
count += 1
g.remove(px)
break
return count


AC了，也可以借助双指针，主指针是饼干，从动的那个指针是小孩，这样就可以省去异常值也放进去循环了，差不多的思想，排序之后其实优化方法还有很多，感觉排序就是一个能让天空放晴的办法，借助while和指针，大概写了一下：

class Solution:
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
#先检查边界
if len(g) == 0 or len(s) == 0:
return 0

g.sort()
s.sort()
ckp, chp = 0, 0

while ckp < len(s) and chp < len(g):
if s[ckp] >= g[chp]:
chp += 1
ckp += 1

return chp


## Leetcode-416 Partition Equal Subset Sum 分割相等子集

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

• 首先，题目要求2个子数组和相等，因此，只有大数组的和为偶数，才可能使得2个子数组和是相等，所以一旦和为奇数就可以立即排除输出False
• 其次对于和为偶数的情况，可以将总和除2作为每个子数组的目标和，所以问题就转化为找出子数组和为$target = sum / 2$。
• DP问题就是要借助DP的思想，就要写一下状态转移方程，作为写代码的指导思想。动态规划都是借助一个2维或者1维的表格来建立整个过程，于是我们借一个例子来画一下表格：
	0	1	2	3	4	5	6	8	9	10	11
0	1	0	0	0	0	0	0	0	0	0	0
1	1	1	0	0	0	0	0	0	0	0	0
5	1	1	0	0	0	1	1	0	0	0	0
5	1	1	0	0	0	1	1	0	0	0	1


]处已经满足，那加上nums[i]也同样会满足，显示了DP的递推性。这样主体就搭建好了。

class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if sum(nums) % 2 == 1:
return False
target = sum(nums) // 2

# dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
dp = [[False for i in range(target + 1)] for j in range(len(nums) + 1)]
dp[0][0] = True
for i in range(1, len(nums) + 1):
for j in range(1, target + 1):
dp[i][j] = dp[i-1][j]
if j >= nums[i-1] and dp[i-1][j-nums[i-1]]:
dp[i][j]  = True
return dp[-1][-1]


class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if sum(nums) % 2 == 1:
return False
target = sum(nums) // 2

# dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
dp = [False for i in range(target + 1)]
dp[0] = True
for i in range(0, len(nums)):
for j in range(target, nums[i] - 1, -1):
dp[j] = dp[j] | dp[j - nums[i]]
return dp[-1]



## Leetcode-215 第K个最大的数

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums.sort(reverse=True)
return nums[k - 1]


class Solution:
def findKthLargest(self, nums, k):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[j] > nums[i]:
nums[i], nums[j] = nums[j], nums[i]
return nums[k-1]


class Solution:
def findKthLargest(self, nums, k):
for index in range(len(nums)):
tmp = index
for j in range(index + 1, len(nums)):
if nums[j] > nums[tmp]:
tmp = j
nums[index], nums[tmp] = nums[tmp], nums[index]
return nums[k - 1]


class Solution:
def findKthLargest(self, nums, k):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] < key:
# 只要key比已排序好的数大，先对原数进行移位操作，腾出空间。
nums[j + 1] = nums[j] #会有个重复
j -= 1
# while条件不满足时，这里nums[j + 1]其实是(j - 1) + 1 = j，将key置于上步腾出的那个位置
nums[j + 1] = key
return nums[k-1]


class Solution:
# 2. 再对left和right作归并排序
def merge_sort(self, left, right):
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
# 1. 先拆分，运用递归
def divide_merge(self, nums):
if len(nums) <= 1:
return nums
num = len(nums) // 2
left = self.divide_merge(nums[:num])
right = self.divide_merge(nums[num:])
return self.merge_sort(left, right)

def findKthLargest(self, nums, k):
res = self.divide_merge(nums)
return res[-k]


class Solution:
def findKthLargest(self, nums, k):
pivot = nums[0]
left  = [l for l in nums if l < pivot]
equal = [e for e in nums if e == pivot]
right = [r for r in nums if r > pivot]

if k <= len(right):
return self.findKthLargest(right, k)
elif (k - len(right)) <= len(equal):
return equal[0]
else:
return self.findKthLargest(left, k - len(right) - len(equal))


## Leetcode-46 Permutations 排列

Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
def helper(nums, visited):
if len(visited) == len(nums):
res.append(visited[:])

for item in nums:
# 如果已经存在就不再记入
if item in visited:
continue
visited.append(item)
helper(nums, visited)
visited.pop()
helper(nums, [])
return res


AC了，看到另外的解法，避免了在循环中进行判断，而是在传入下层递归的时候，就只传入除去当次循环的那个元素后的剩余元素，要巧妙的多。

class Solution(object):
# DFS
def permute(self, nums):
res = []
self.dfs(nums, [], res)
return res

def dfs(self, nums, path, res):
if not nums:
res.append(path)
# return # backtracking
for i in range(len(nums)):
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)


## Leetcode-647 Palindromic Substrings 回文子串个数

Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:
Input: “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

class Solution:
def __init__(self):
self.count = 0

def countSubstrings(self, s):
"""
:type s: str
:rtype: int
"""
def move_check(input, i, j):
if i < 0 or j >= len(input):
return

if input[i] == input[j]:
self.count += 1
else: # 不满足及时跳出，有效减少无效递归。
return

i -= 1
j += 1
move_check(input, i, j)

index = 0
while index < len(list(s)):
move_check(list(s), index, index) #奇数
move_check(list(s), index - 1, index) #偶数
index += 1
return self.count


AC了，看了个大神的方法，用了for嵌套while的结构，看着还是挺清楚的，我承认我之前非要写个递归，其实就是想自己练练写递归，也没什么特别的道理哈哈。这里用了一个技巧来一步实现奇数偶数的判断，left = center / 2, right = center / 2 + center % 2. 实现如下：

class Solution:
def countSubstrings(self, S):
N = len(S)
ans = 0
for center in range(2*N - 1):
left = center // 2
right = left + center % 2
while left >= 0 and right < N and S[left] == S[right]:
ans += 1
left -= 1
right += 1
return ans


## Leetcode-230 Kth Smallest Element in a BST BST树中第k个最小值

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:
Input: root = [3,1,4,null,2], k = 1. Output: 1
3
/
1 4

2

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
vals = [] # 初始化一个数组
def ldr(node):
if node is None:
return
dfs(node.left)
vals.append(node.val)
dfs(node.right)
ldr(root)
return vals[k - 1]


class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
stack = []  # stack以栈来放置node，到达放入，结束后弹出
node = root # node用来表示当前的节点
res = []    # 存放排序结果
while node or stack:
while node:
stack.append(node) # 插入当前节点
node = node.left
node = stack.pop() # 弹出最底层的节点
res.append(node.val)
node = node.right
return res[k - 1]


class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
self.k = k
self.res = None
self.helper(root)
return self.res

def helper(self, node):
if not node:
return
self.helper(node.left)
self.k -= 1 # 计数并精准返回
if self.k == 0:
self.res = node.val
return
self.helper(node.right)


## Leetcode-69 Sqrt(x) 开根号

Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:
Input: 4
Output: 2

class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0:
return 0

def calculate(i, j, x):
if i * i == x:
return i
if j * j == x:
return j
if j - i <= 1:
return i
mid = (i + j) // 2
if mid * mid > x:
return calculate(i, mid, x)
else:
return calculate(mid, j, x)
return calculate(1, x, x)


class Solution:
def mySqrt(self, x):
l, r = 0, x
while l <= r:
mid = l + (r-l)//2
if mid * mid <= x < (mid+1)*(mid+1):
return mid
elif x < mid * mid:
r = mid
else:
l = mid + 1


## Leetcode-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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return None
# tmp = root.left
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root


class Solution:
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root:
invert = self.invertTree
root.left, root.right = invert(root.right), invert(root.left)
return root


## Leetcode-435 Non-overlapping Intervals 不重复交集

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:
You may assume the interval’s end point is always bigger than its start point.
Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.

Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
def eraseOverlapIntervals(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
if len(intervals) <= 1:
return 0
intervals.sort(key = lambda x: x.end)
start, current_end = intervals[0].start, intervals[0].end
count = 0
for item in intervals[1:]:
if item.start >= current_end:
current_end = item.end
else:
count += 1
return count


AC了，这个题没什么特别的，就是要一开始想清楚。

## Leetcode-51 N-Queens N皇后

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example:
Input: 4
Output: [
[“.Q…”, // Solution 1
“…Q”,
“Q…”,
“…Q.”],
[“…Q.”, // Solution 2
“Q…”,
“…Q”,
“.Q…”]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

• 判断模块，3个情况，不在同一行，不在同一列，不在同一个斜线。这里的斜线要考虑2个方向：abs(r1-r2) == abs(c1 - c2)以及 r1+c1 == r2+c2 （checkValid()）。
• 主模块，递归加遍历，这里我比较优先采用DFS来收集(dfs())。
• 打印结果模块 (trans_print())。
class Solution:
def __init__(self):
self.res = []

def checkValid(self, current, visited):
if not visited:
return True
curr_row = len(visited)
# 三个情况的判断
for idx, item in enumerate(visited):
if abs(item - current) == abs(idx - curr_row) or (idx + item) == current + curr_row or current == item:
return False
return True

def dfs(self, visited, n):
if len(visited) == n:
self.res.append(visited) # 结果收集
return
for col in range(n):
if self.checkValid(col, visited):
self.dfs(visited + [col], n) #！这里需要格外注意，只有visited +
#[col]这样可以支持程序回退

def trans_print(self, res, n):
if not res:
return []
final_res = []
for r in res: # 结果打印
res_list = []
for num in r:
temp = ['.'] * n
temp[num] = 'Q'
res_list.append(''.join(temp))
final_res.append(res_list)
return final_res

def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.dfs([], n)
return self.trans_print(self.res, n)


def solveNQueens(self, n):
def DFS(queens, xy_dif, xy_sum):
p = len(queens)
if p==n:
result.append(queens)
return None
for q in range(n):
if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])
result = []
DFS([],[],[])
return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]


## Leetcode-19 Remove Nth Node From End of List 末尾移除节点

Given a linked list, remove the n-th node from the end of list and return its head.
Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
"""
:type n: int
:rtype: ListNode
"""
mark = n
while mark > 0:
mark -= 1
behind = behind.next
behind.next = behind.next.next


## Leetcode-235 Lowest Common Ancestor of a Binary Search Tree BST最低公共祖先

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

# 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 lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
max_num = max(p.val, q.val)
min_num = min(p.val, q.val)
if root.val >= min_num and root.val <= max_num:
return root
if root.val > max_num:
return self.lowestCommonAncestor(root.left, p, q)
else:
return self.lowestCommonAncestor(root.right, p, q)


def lowestCommonAncestor(self, root, p, q):
a, b = sorted([p.val, q.val])
while not a <= root.val <= b:
root = (root.left, root.right)[a > root.val]
return root


## Leetcode-207 Course schedule

There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:
Input: 2, [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.

Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.

# out(出顶点) -> in(入顶点)
{
0: [1, 2],
1: [3],
2: [3]
}

# in(入顶点) -> out(出顶点)
{
1: [0],
2: [0],
3: [1, 2]
}


1. 入度为0的顶点的集合（每次遍历图，如果图顶点的后继节点不存在，那就移入入度为0的集合）
2. 遍历过已经放入的结果集（遍历过的放入结果中）
3. 当前图（字典，当移除入度为0的顶点，同步也要将图中的边进行更新，同步移除包含该入度为0顶点对应的边，再进行判断，如果移除后顶点本身同样没有进入的边了即值为空数组，便也要将其更新到入度为0顶点的集合中，以便继续遍历结束）。

class Solution:
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""

ordered = [] # 存结果

graph = collections.defaultdict(list) #表示图
for out, into in prerequisites:
graph[into].append(out)

zero_in_degree = [i for i in range(numCourses) if i not in graph] # 存入度为0的顶点集合

for item in zero_in_degree:
for key, val in graph.items():
if item in val: # 图中含有该节点准备删除
val.remove(item)  # 移除该顶点
if len(val) == 0: # 该顶点入度为0，则将该节点插入到0 degree 集合 下次继续遍历
zero_in_degree.append(key)
ordered.append(item)
return len(ordered) == numCourses


class Solution:
def canFinish(self, n, prerequisites):
G = [[] for i in range(n)] #表示图
degree = [0] * n
for j, i in prerequisites:
G[i].append(j)
degree[j] += 1

bfs = [i for i in range(n) if degree[i] == 0]
for i in bfs:
for j in G[i]:
degree[j] -= 1
if degree[j] == 0:
bfs.append(j)
return len(bfs) == n


def canFinish(self, numCourses, prerequisites):
graph = [[] for _ in xrange(numCourses)]
visit = [0 for _ in xrange(numCourses)]
for x, y in prerequisites:
graph[x].append(y)
def dfs(i):
if visit[i] == -1:
return False
if visit[i] == 1:
return True
visit[i] = -1
for j in graph[i]:
if not dfs(j):
return False
visit[i] = 1
return True
for i in range(numCourses):
if not dfs(i):
return False
return True


## Leetcode-309 Best Time to Buy and Sell Stock with Cooldown 股票买卖

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

Input: [1,2,3,0,2]
Output: 3

1. hold[i] = max(hold[i-1], reset[i-1] - price[i])
持有状态的价值 = max(前一时刻持有的价值，当前时刻买入的价值)，由于买入之前一定要有cooldown，所以会产生第二种状态转变，注意买入的话是花钱，所以是减去当前股价。
2. sold[i] = hold[i-1] + price[i]
卖出状态的价值 = 前一时刻的持有和当前卖出加钱的和，这里hold[i-1]因为是买入花钱，就一定是负数，所以是求和。
3. rest[i] = max(rest[i-1], sold[i-1])
空仓状态的价值 = max(前一时刻空仓价值，卖出之后的价值）。因为卖出后必须要cooldown，所以这里的sold[i-1]也可以理解了。

class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
hold = [float('-inf')] * (len(prices) + 1)
sold = [0] * (len(prices) + 1)
rest = [0] * (len(prices) + 1)
prices.insert(0, None)

for i in range(1, len(prices)):
hold[i] = max(hold[i-1], rest[i-1] - prices[i])
sold[i] = hold[i-1] + prices[i]
rest[i] = max(rest[i-1], sold[i-1])

return max(sold[-1], rest[-1])


## Leetcode-64 Minimum Path Sum 最小路径和

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

$$route[i][j] = pos[i][j] + min(route[i-1][j], route[i][j-1])$$

class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
mem = {} # 备忘录
# route[i][j] = pos[i][j] + min(route[i-1][j], route[i][j-1])

def route(i, j):
if i < 0 or j < 0: # 超出边界时，我会主动返回一个正无穷给min()去做判断
return float('inf')

if i == 0 and j == 0:
return grid[i][j]

if (i, j) in mem:
return mem[(i, j)]
else:
mem[(i, j)] = grid[i][j] + min(route(i-1, j), route(i, j-1))
return mem[(i, j)]

if not len(grid) or not len(grid[0]):
return 0
return route(len(grid) - 1, len(grid[0]) - 1)


def minPathSum(self, grid):
m = len(grid)
n = len(grid[0])
# 补齐首行和首列
for i in range(1, n):
grid[0][i] += grid[0][i-1]
for i in range(1, m):
grid[i][0] += grid[i-1][0]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]


## Leetcode-763 Partition Labels 分割字符

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:
Output: [9,7,8]

Explanation:
The partition is “ababcbaca”, “defegde”, “hijhklij”.
This is a partition so that each letter appears in at most one part.
A partition like “ababcbacadefegde”, “hijhklij” is incorrect, because it splits S into less parts.

import collections
class Solution(object):
def partitionLabels(self, S):
"""
:type S: str
:rtype: List[int]
"""
last_pos = {}
for idx, item in enumerate(list(S)):
last_pos[item] = idx

res = []
start, end = 0, 0

for index, item in enumerate(S):
if last_pos[item] > end:
end = last_pos[item]
# 到达切割点
if index == end:
res.append(end - start + 1)
start = end + 1
return res


## Leetcode-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

class MyQueue:
def __init__(self):
self.s1 = []
self.s2 = []

def push(self, x):
while self.s1:
self.s2.append(self.s1.pop())
self.s1.append(x)
while self.s2:
self.s1.append(self.s2.pop())

def pop(self):
return self.s1.pop()

def peek(self):
return self.s1[-1]

def empty(self):
return not self.s1


## Leetcode-975 Odd Even Jump 奇偶跳

You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, …) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:
During odd numbered jumps (ie. jumps 1, 3, 5, …), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, …), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
(It may be the case that for some index i, there are no legal jumps.)
A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

（对于某些索引 i，可能无法进行合乎要求的跳跃。）

odd[i] = even[j]
even[i] = odd[j]

odd[i] = even[odd_next[i]]
even[i] = odd[even_next[i]]

class Solution:
def oddEvenJumps(self, A):
"""
:type A: List[int]
:rtype: int
"""
odd = [False] * len(A)
even = [False] * len(A)

# 最后一个元素一定是满足的
odd[-1], even[-1] = True, True

oddNext = [None] * len(A)
evenNext = [None] * len(A)

# 用一个stack来存储最优值（最大或者最小）
# 返回出对应原数组的index, stack也是装的index
stack = []
for item, index in sorted([[item, index] for index, item in enumerate(A)]):
while stack and index > stack[-1]:
oddNext[stack.pop()] = index
stack.append(index)

stack = []
for item, index in sorted([[-item, index] for index, item in enumerate(A)]):
while stack and index > stack[-1]:
evenNext[stack.pop()] = index
stack.append(index)

for i in reversed(range(len(A) - 1)):
if oddNext[i] is not None:
odd[i] = even[oddNext[i]]
if evenNext[i] is not None:
even[i] = odd[evenNext[i]]
return sum(odd)


## Leetcode-486 Predict the Winner 预测胜者

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.

Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
1 5 233 8

$$solve(nums) = max(nums[0] - solve(nums[1:]), nums[-1] - solve(nums[:-1]))$$

class Solution(object):
def PredictTheWinner(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
if len(nums)%2 == 0 or len(nums) == 1:
return True

cache = dict()

def solve(nums):

tnums = tuple(nums)
if tnums in cache:
return cache[tnums]
cache[tnums] = max(
nums[0] - solve(nums[1:]),
nums[-1] - solve(nums[:-1])
)
return cache[tnums]
return solve(nums) >= 0


## Leetcode-551 Student Attendance Record I 学生出席率

You are given a string representing an attendance record for a student. The record only contains the following three characters:
‘A’ : Absent.
‘L’ : Late.
‘P’ : Present.
A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:
Input: “PPALLP”
Output: True
Example 2:
Input: “PPALLL”
Output: False

class Solution(object):
def checkRecord(self, s):
"""
:type s: str
:rtype: bool
"""
count_a = 0
count_l = 0
max_l = 0
for item in list(s):
if item == 'A':
count_a += 1
count_l = 0
elif item == 'L':
count_l += 1
if count_l > max_l: max_l = count_l
else:
count_l = 0
return count_a < 2 and count_l < 3


class Solution(object):
def checkRecord(self, s):
"""
:type s: str
:rtype: bool
"""
count_a = 0
count_l = 0
for item in list(s):
if item == 'A':
count_a += 1
if item == 'L':
count_l += 1
else: count_l = 0
if count_a > 1 or count_l > 2:
return False
return True


## Leetcode-1 2SUM 2数求和

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].

class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
mem = dict()

for index, item in enumerate(nums):
if item in mem:
return [mem[item], index]
else:
mem[target - item] = index


class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
sn = sorted((num, i) for i, num in enumerate(nums))
i, j = 0, len(nums) - 1
print(sn)
while i < j:
n, k = sn[i]
m, l = sn[j]
if n + m < target:
i += 1
elif n + m > target:
j -= 1
else:
return [k, l]


## Leetcode-15 3SUM 3数求和

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
nums.sort()
# 外层第1个指针
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
# 第2第3个指针从i往后开始
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l +=1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
# 这里判断直到找到下一个不同于上一个的值
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1; r -= 1 # 这里把最终移动放到最后
return res


## Leetcode-18 4SUM 4数求和

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

4数求和啦，一路从2个做到4个，这里也是一样的意思，4数就是4个指针喽（噗~(oﾟ▽ﾟ)o）。一样也是会遇到很恶心的重复问题，我这里先自己丑陋的实现了一遍，思路是外层2个指针，内部做2SUM，去重我借助了一个字典，因为重复的情况很多很复杂，所以借助字典可以照顾到所有的情况，内外一旦发现重复，就启动指针的移位，最后输出结果中的每一个都先排了个序，再set去重，再转成list输出，哈哈哈，发现居然AC了。代码如下：

class Solution:

def writeDict(self, mem, key, value):
print(value)
if key in mem:
mem[key].append(value)
else:
mem[key] = [value]

def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
mem = dict()
nums.sort()
res = []

for prior1_idx in range(len(nums)-2):
for prior2_idx in range(prior1_idx + 1, len(nums)-1):
sum_prior = nums[prior1_idx] + nums[prior2_idx]
prior = (nums[prior1_idx], nums[prior2_idx])

if sum_prior in mem and prior in mem[sum_prior]:
continue

sum_post = target - sum_prior
temp = nums.copy()
temp.remove(nums[prior1_idx])
temp.remove(nums[prior2_idx])
l, r = 0, len(temp) - 1
while l < r:
if temp[l] + temp[r] < sum_post:
l += 1
elif temp[l] + temp[r] > sum_post:
r -= 1
else:
post = (temp[l], temp[r])
if sum_post in mem and post in mem[sum_prior]:
l += 1
r -= 1
continue
else:
# 写入字典
self.writeDict(mem, sum_prior, prior)
self.writeDict(mem, sum_post, post)
single = list(prior) + list(post)
single.sort()
res.append(single)
l += 1
r -= 1
return list(set(tuple(i) for i in res))


class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
num.sort()
def ksum(num, k, target):
i = 0
result = set()
if k == 2:
j = len(num) - 1
while i < j:
if num[i] + num[j] == target:
i += 1
elif num[i] + num[j] > target:
j -= 1
else:
i += 1
else:
while i < len(num) - k + 1:
newtarget = target - num[i]
subresult = ksum(num[i+1:], k - 1, newtarget)
if subresult:
result = result | set( (num[i],) + nr for nr in subresult)
i += 1

return result

return [list(t) for t in ksum(num, 4, target)]


result = result | set( (num[i],) + nr for nr in subresult)


## Leetcode-77 Combination 组合

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
res = []

def dfs(array, k, path):
if k == 0:
res.append(path)
return
else:
for i in range(len(array)):
dfs(array[i+1:], k-1, path + [array[i]])
dfs(range(1, n+1), k, [])
return res


class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
res = []
if k==0 or n<1:
return res

def backtracking(n, k, path, index):
if len(path) == k:
res.append(path[:])
return

if k-len(path) > n - index + 1:
return

for num in range(index, n+1):
if num not in path:
path += [num]
backtracking(n, k, path, num+1)
path.pop()
backtracking(n, k, [], 1)
return res


## Leetcode-39 组合之和

[
[7],
[2,2,3]
]

[
[2,2,2,2],
[2,3,3],
[3,5]
]

class Solution:
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
candidates.sort()
# path记录遍历过的数字
def dfs(array, gap, path):
if gap == 0:
res.append(path)
return

if gap < min(array):
return

for index, item in enumerate(array):
dfs(array[index:], gap - item, path + [item])

dfs(candidates, target, [])
return res


## Leetcode-40 Combination Sum III 组合之和2

[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

[
[1,2,2],
[5]
]

class Solution:
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
res = []

def dfs(array, gap, path):
if gap == 0:
res.append(path)
return

if len(array) >0 and gap < array[0]:
return

for index, item in enumerate(array):
dfs(array[index+1:], gap - item, path + [item])

dfs(candidates, target, [])
return [list(tupl) for tupl in {tuple(item) for item in res }]


class Solution:
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
res = []

def dfs(array, start, target, path):
if target == 0:
res.append(path)
return
if target < 0:
return
for index in range(start, len(array)):
if index > start and array[index] == array[index-1]:
continue
dfs(array, index+1, target - array[index], path + [array[index]])

dfs(candidates, 0, target, [])
return res


## Leetcode-216 Combination Sum III 组合之和3

class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
nums = list(range(1, 10))
res = []

def dfs(array, target, path, k):
if target == 0 and k == 0:
res.append(path)
return
if target < 0 or k < 0:
return

for index in range(len(array)):
dfs(array[index+1:], target - array[index], path + [array[index]], k-1)
dfs(nums, n, [], k)
return res


## Leetcode-328 奇偶链表

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
return None

while even and even.next:
odd.next=odd.next.next
odd=odd.next
even.next=even.next.next
even=even.next



## Leetcode-322 找零钱 coin change

$$F ( S ) = \left{ \begin{array} { l l } { 0 , } & { \text { if } S = 0 } \ { \min _ { i = 0 , \cdots , n - 1 } F \left( S - c _ { i } \right) + 1 , } & { \text { if } S - c _ { i } \geq 0 } \ { - 1 } & { \text { other } } \end{array} \right.$$

dp[0] = 0
dp[1] = 1
dp[2] = min{dp[2-1]}+1
dp[3] = min{dp[3-1],dp[3-2]}+1
dp[4] = min{dp[4-1],dp[4-2]}+1
...
dp[11] = min{dp[11-1],dp[11-2],dp[11-5]}+1


class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
n = len(coins)
# dp[i]表示amount=i需要的最少coin数
dp = [float("inf")] * (amount+1)
dp[0] = 0
for i in range(amount+1):
for j in range(n):
# 只有当硬币面额不大于要求面额数时，才能取该硬币
if coins[j] <= i:
dp[i] = min(dp[i], dp[i-coins[j]]+1)
# 硬币数不会超过要求总面额数，如果超过，说明没有方案可凑到目标值
return dp[amount] if dp[amount] <= amount else -1


## Leetcode-146 LRU缓存机制

1. get 操作：如果哈希表中有这个 key，则返回这个 key 的值，并且由于是最近使用的，所以需要将其移动至双向链表的头部；没有则返回-1
2. put 操作：将（key，value）的一个 pair 加入到双向链表中，这边就存在 2 种情况：如果有则直接修改值，并且移动至链表头部；如果没有值，则新建链表节点，移动至头部，并且需要检查总的长度是否超过 LRU 总的容量，超过则要删除链表中最后一个节点，并且在哈希表里也要弹出这个节点对应的 key。

class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None

class LRUCache:
def __init__(self, capacity: int):
self.cache = {}
self.capacity = capacity
self.size = 0

node.next.prev = node

def removeNode(self, node):
print(node.key)
print(node.value)
print(node.next)
node.prev.next = node.next
node.next.prev = node.prev

self.removeNode(node)

def removeTail(self):
node = self.tail.prev
self.removeNode(node)
return node

def get(self, key: int) -> int:
if key not in self.cache:
return -1
# 如果 key 存在，先通过哈希表定位，再移到头部
node = self.cache[key]
return node.value

def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.value = value