202005leetcode刷题记录 3. 无重复字符的最长子串 9. 回文数 15. 三数之和 21. 合并两个有序链表 25. K 个一组翻转链表 26. 删除排序数组中的重复项 45. 跳跃游戏 II 50. Pow(x, n) 53. 最大子序和 61. 旋转链表 69. x 的平方根 98. 验证二叉搜索树 102. 二叉树的层序遍历 136. 只出现一次的数字 141. 环形链表 155. 最小栈 202. 快乐数 221. 最大正方形 236. 二叉树的最近公共祖先 287. 寻找重复数 344. 反转字符串 560. 和为K的子数组 572. 另一个树的子树 922. 按奇偶排序数组 II 983. 最低票价 1417. 重新格式化字符串 1431. 拥有最多糖果的孩子 面试题 17.04. 消失的数字 面试题29. 顺时针打印矩阵 面试题46. 把数字翻译成字符串 面试题64. 求1+2+…+n
题目要求：
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
思路：
用左指针和右指针指向子串的开头和结尾，开始时两个指针都指向字符串的开头。每次右指针加一，判断新加入的字符是否在子串中，如果在子串中，左指针加一；否则右指针加一，并更新最长子串的长度。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
ans = left = right = 0
while right < n:
if s[right] in s[left:right]:
left += 1
else:
right += 1
ans = max(ans, right - left)
return ans
9. 回文数
题目要求：
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
class Solution:
def isPalindrome(self, x: int) -> bool:
s = str(x)
n = len(s)
left, right = 0, n - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
15. 三数之和
题目要求：
给你一个包含 n 个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a + b + c = 0？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
思路一：
暴力法。python上没法通过，倒数第三个测试用例一直超时。可能是用了not in导致速度很慢，要考虑其他去重方法。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
if n < 3:
return ans
nums.sort()
for i in range(0, n - 2):
if nums[i] > 0:
break
target = -nums[i]
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
if nums[j] + nums[k] == target and [nums[i], nums[j], nums[k]] not in ans:
ans.append([nums[i], nums[j], nums[k]])
return ans
思路二：
双指针。遍历数组，对每个元素之后的数组用双指针求和。
class Solution:
def threeSum(self, nums: [int]) -> [[int]]:
nums.sort()
ans = []
n = len(nums)
for i in range(n - 2):
# 排序后，若当前元素大于 0 ，那么三数之和不可能为 0
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
j, k = i + 1, n - 1
while j < k:
s = nums[i] + nums[j] + nums[k]
if s < 0:
j += 1
while j < k and nums[j] == nums[j - 1]:
j += 1
elif s > 0:
k -= 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
else:
ans.append([nums[i], nums[j], nums[k]])
j += 1
k -= 1
while j < k and nums[j] == nums[j - 1]:
j += 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
return ans
21. 合并两个有序链表
题目要求：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：
五一节的每日一题这么快乐的吗？
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
head = l3 = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
l3.next = l1
l1, l3 = l1.next, l3.next
else:
l3.next = l2
l2, l3 = l2.next, l3.next
l3.next = l1 if l1 else l2
return head.next
25. K 个一组翻转链表
题目要求：
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
思路：
以上图为例，要怎么翻转A-->B-->C呢？按本题的要求，最终得到的结果应该是：
首先断开A-->B的指针，将A的指针指向D。可以写出如下的伪代码：
ANext = A.next
A.next = D
# 为下一个循环做准备
D = A
A = B
那么翻转子链表就不难写出了。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverse(self, head: ListNode, tail: ListNode):
q = tail.next
p = head
while q != tail:
pNext = p.next
p.next = q
q = p
p = pNext
return tail, head
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
L = ListNode(0)
L.next = head
pre = L
while head:
tail = pre
# 找出长度为k的子链表的头尾指针
for i in range(k):
tail = tail.next
if not tail:
return L.next
tNext = tail.next
head, tail = self.reverse(head, tail)
# 此时子链表的tail已经连好了，要将head与原链表连上
pre.next = head
pre = tail
head = tail.next
return L.next
26. 删除排序数组中的重复项
题目要求：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。
思路：
划重点：已排序，而且得原地修改数组，本以为只要返回新数组的长度就行了。那就可以用两个指针lo和hi，遇到两个位置的元素相等就跳过，否则就修改。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
lo = hi = 0
while hi < n:
if nums[lo] == nums[hi]:
hi += 1
else:
lo += 1
nums[lo] = nums[hi]
hi += 1
return lo + 1
45. 跳跃游戏 II
题目要求：
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。
思路一：
可以用贪心算法，每一步都跳到可以到达的最远位置，第一步能跳到的最远位置即nums[0]，之后能跳到的最远位置是max(maxPos, nums[i] + i)。pos为当前位置，每当遍历到当前位置时，就跳到能达到的最远位置。返回前加一个判断，如果已经可以到达最后那个位置，就返回，以防止多计数一次。
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0
pos = 0 # 当前所在位置
maxPos = nums[0] # 能跳到的最远位置
cnt = 0
for i in range(n):
maxPos = max(maxPos, nums[i] + i)
if i == pos:
pos = maxPos
cnt += 1
if pos > n - 2:
return cnt
思路二：
每次去找索引最小且能到达最后一个位置的元素，相当于倒着走，最终走到第一个位置。这个方法个人认为比较好理解，但是在最差的情况下会退化到(O(n^2))，Python下会超时。
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
pos = n - 1
cnt = 0
while pos > 0:
for i in range(pos + 1):
if i + nums[i] >= pos:
pos = i
cnt += 1
break
return cnt
50. Pow(x, n)
题目要求：
实现pow(x, n)，即计算 x 的 n 次幂函数。
思路：
对于(x^n)，我们可以将 n 写为其二进制形式((i_m, i_{m-1}, ..., i_0)_2)，则有
而我们知道，对于一个二进制的数字来说，每个位上的数不是 0 就是 1 ，也就是说只有对应的二进制表示的位上是 1 的对于求(x^n)才有贡献。例如 77 的二进制表示为1001101，(x^{77} = x*x^4*x^8*x^{64})，恰好对应了二进制的每一个 1。
class Solution:
def myPow(self, x: float, n: int) -> float:
def quickMul(N):
ans = 1.0
x_pow = x
while N > 0:
if N % 2 == 1:
# 如果 N 是奇数，就需要多乘一次 x
ans *= x_pow
x_pow *= x_pow
N //= 2
return ans
return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)
53. 最大子序和
题目要求：
给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
进阶:
如果你已经实现复杂度为O(n)的解法，尝试使用更为精妙的分治法求解。
思路一：
这是一个经典的动态规划问题。可以计算以第i个元素为末尾的子序列的最大子序和，有两种情况：
- 如果
nums[i] > num[i] + 以第i - 1个元素为末尾的子序列的最大子序和，那么当前的最大子序和就是nums[i]； - 否则就等于
num[i] + 以第i - 1个元素为末尾的子序列的最大子序和
然后只需取这之中最大的就行。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxSum = nums[0]
dp = 0
for x in nums:
dp = max(x, dp + x)
maxSum = max(dp, maxSum)
return maxSum
61. 旋转链表
题目要求：
给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。
思路：
先把链表的首尾连起来，然后从head开始找到新的头结点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head or not k or not head.next:
return head
ptr = head
n = 1
# 把指针移动到最后一个结点，顺便看看数组有多长
while ptr.next:
ptr = ptr.next
n += 1
ptr.next = head
cnt = (n - k) % n
# 找新的头结点
while cnt > 0:
head = head.next
ptr = ptr.next
cnt -= 1
ptr.next = None
return head
69. x 的平方根
题目要求：
实现int sqrt(int x)函数。
计算并返回x的平方根，其中x是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
思路：
二分查找。显然int sqrt(int x)在0到x之间，所以可以使用二分查找。
class Solution:
def mySqrt(self, x: int) -> int:
if x <= 1:
return x
left = 1
right = x - 1
while left <= right:
mid = left + (right - left) // 2
square = mid ** 2
if square > x:
right = mid - 1
else:
left = mid + 1
return right
98. 验证二叉搜索树
题目要求：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
思路一：
中序遍历BST可以得到一个升序的序列，利用这个性质就可以直接对它进行中序遍历，判断是否可以得到升序的序列。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
if not root:
return True
stack = []
value = float('-inf')
while root or stack:
while root:
stack.append(root)
root = root.left
if stack:
root = stack.pop()
# 注意要用<=来判断
if root.val <= value:
return False
value = root.val
root = root.right
return True
思路二：
用一个辅助递归函数，用于判断当前节点的值val是否在上下界的范围内。当val不在上下界范围内时，显然就不是二叉搜索树；如果val在范围内，则判断左右孩子的值是否在范围内，左孩子的上界是val，右孩子的下界是val（与二叉搜索树的性质相对应）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
def helper(node, lo, hi):
if not node:
return True
val = node.val
if not lo < val < hi:
return False
return helper(node.left, lo, val) and helper(node.right, val, hi)
return helper(root, float('-inf'), float('inf'))
102. 二叉树的层序遍历
题目要求：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。
（即逐层地，从左到右访问所有节点）。
思路：
用队列辅助。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
ans = []
if not root:
return ans
from collections import deque
que = deque()
que.append(root)
while que:
temp = []
n = len(que)
for _ in range(n):
node = que.popleft()
temp.append(node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
ans.append(temp)
return ans
136. 只出现一次的数字
题目要求：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
思路：
这题花里胡哨的做法好像很多，我直接用的异或。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for x in nums:
ans ^= x
return ans
141. 环形链表
题目要求：
给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是-1，则在该链表中没有环。
思路：
用一个快指针和一个慢指针，快指针一次走两步，慢指针一次走一步，如果是环形的，那么他们一定会相遇。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head:
return False
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
155. 最小栈
题目要求：
设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
-
push(x)—— 将元素 x 推入栈中。 -
pop()—— 删除栈顶的元素。 -
top()—— 获取栈顶元素。 -
getMin()—— 检索栈中的最小元素。
思路一：
设一辅助栈。每次入栈操作时，同时保证辅助栈中的栈顶元素是当前栈中的最小元素：
- 若 x 比辅助栈的栈顶元素还要小，则将 x 入栈；
- 否则将辅助栈的栈顶元素再次入栈。
出栈操作时对两个栈都进行出栈处理即可。而获取最小元素只要返回辅助栈的栈顶元素即可。
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [math.inf]
def push(self, x: int) -> None:
self.stack.append(x)
self.min_stack.append(min(x, self.min_stack[-1]))
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
思路二：
不设辅助栈，用栈本身来记录每次最小值的变化。维护一个min_val变量记录当前的最小值。每次入栈操作时：
- 若 x 小于
min_val，则先将min_val入栈，再将 x 入栈，并把 x 赋值给min_val； - 否则直接将 x 入栈。
出栈时，如果发现当前的栈顶元素与min_val相等，就意味着这是记录了之前的最小值的地方，就需要出栈两次，把第二次出栈的元素赋值给min_val。
class MinStack:
def __init__(self):
self.stack = []
self.min_val = float('inf')
def push(self, x: int) -> None:
if self.min_val >= x:
self.stack.append(self.min_val)
self.min_val = x
self.stack.append(x)
def pop(self) -> None:
if self.stack.pop() == self.min_val:
self.min_val = self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_val
202. 快乐数
题目要求：
编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
如果n是快乐数就返回True；不是，则返回False。
思路一：
暴力法冲啊！把每次算出来的n丢到集合里面，后面在遇到就说明循环了。
class Solution:
def isHappy(self, n: int) -> bool:
nums = set() # 出现过的数字
while n not in nums:
nums.add(n)
sqSum = 0
for s in str(n):
sqSum += int(s) ** 2
if sqSum == 1:
return True
else:
n = sqSum
return False
思路二：
环形链表。用类似141题的算法，快指针一次走两步，慢指针一次一步，如果它们相等说明有循环。
class Solution:
def isHappy(self, n: int) -> bool:
def nextN(num):
sqSum = 0
for s in str(num):
sqSum += int(s) ** 2
return sqSum
slow = n
fast = nextN(n)
while fast != 1 and slow != fast:
slow = nextN(slow)
fast = nextN(nextN(fast))
return fast == 1
221. 最大正方形
题目要求：
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
思路一：
暴力法。遇到1时，同时横向和纵向拓展，要保证拓展的每个元素都是1。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
if m == 0 or n == 0:
return 0
maxSide = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
maxSide = max(maxSide, 1)
maxPos = min(m - i, n - j) # 此时可能的最大边长
for k in range(1, maxPos):
flag = True
if matrix[i + k][j + k] == '0':
break
for s in range(k):
if matrix[i + k][j + s] == '0' or matrix[i + s][j + k] == '0':
flag = False
break
if flag:
maxSide = max(maxSide, k + 1)
else:
break
return maxSide ** 2
思路二:
动态规划，下次一定写。
236. 二叉树的最近公共祖先
题目要求：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
思路：
递归后序遍历。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# 如果左右子树的遍历结果都为空
# 说明p,q不在左右子树中，返回空值
if not left and not right:
return
# 如果左右子树有一个为空
# 说明p,q在同一子树中
if not left:
return right
if not right:
return left
# 如果都不空
# 说明p,q分别在root的左右子树中
return root
287. 寻找重复数
题目要求：
给定一个包含 n + 1 个整数的数组nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
思路：
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
n = len(nums)
# 每个数都在[left, right]中
left = 1
right = n - 1
while left < right:
mid = (left + right) // 2
cnt = 0
for num in nums:
if num <= mid:
cnt += 1
if cnt > mid:
right = mid
else:
left = mid + 1
return left
344. 反转字符串
题目要求：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
n = len(s)
left, right = 0, n - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
560. 和为K的子数组
题目要求：
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
思路一：
前缀和。时间复杂度(O(n^2))，超时了。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
cnt, n = 0, len(nums)
pre = [0] * (n + 1)
for i in range(1, n + 1):
pre[i] = pre[i - 1] + nums[i - 1]
for i in range(1, n + 1):
for j in range(i, n + 1):
if pre[j] - pre[i - 1] == k:
cnt += 1
return cnt
思路二：
前缀和加哈希表优化。事实上，我们不需要关心前缀和到底对应了哪里到哪里的和，我们只关心它的值和它出现的次数。用一个字典来保存前缀和出现的次数，如果pre - k在字典中，意味着已存在之前的某个前缀和，使得pre - pre_i == k。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
hashmap = {0 : 1} # 如果pre == k，就直接 +1
pre = cnt = 0
for x in nums:
pre += x
if pre - k in hashmap:
cnt += hashmap[pre - k]
if pre in hashmap:
hashmap[pre] += 1
else:
hashmap[pre] = 1
return cnt
572. 另一个树的子树
题目要求：
给定两个非空二叉树s和t，检验s中是否包含和t具有相同结构和节点值的子树。s的一个子树包括s的一个节点和这个节点的所有子孙。s也可以看做它自身的一棵子树。
思路：
这题要求s中的子树与t完全相同，用一个辅助递归函数，判断s中以当前结点为根结点的子树与t是否相同。主函数中同样也用递归判断，如果以当前结点为根结点的子树与t不相同，则判断它的左右孩子。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
def identical(A, B):
if not A and not B:
return True
elif A and B:
return A.val == B.val and
identical(A.left, B.left) and
identical(A.right, B.right)
else:
return False
if not s:
return False
if identical(s, t):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
922. 按奇偶排序数组 II
题目要求：
给定一个非负整数数组A，A中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当A[i]为奇数时，i也是奇数；当A[i]为偶数时，i也是偶数。你可以返回任何满足上述条件的数组作为答案。
思路：
一个奇数指针，一个偶数指针，对不上的就交换。
class Solution:
def sortArrayByParityII(self, A: List[int]) -> List[int]:
n = len(A)
odd, even = 1, 0
while odd < n and even < n:
if A[odd] % 2 == 0 and A[even] % 2 == 1:
A[odd], A[even] = A[even], A[odd]
if A[odd] % 2 == 1:
odd += 2
if A[even] % 2 == 0:
even += 2
return A
983. 最低票价
题目要求：
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为days的数组给出。每一项是一个从1到365的整数。
火车票有三种不同的销售方式：
- 一张为期一天的通行证售价为
costs[0]美元； - 一张为期七天的通行证售价为
costs[1]美元； - 一张为期三十天的通行证售价为
costs[2]美元。
通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在给定的列表days中列出的每一天的旅行所需要的最低消费。
思路：
这题啊，这题是动态规划，然而还是想了半天。如果当前的日期不是出行的日期，那么dp[i] = dp[i - 1]，因为没出门就没必要买票；如果是出行的日期，那么就要看一天、七天、三十天前的票价加上相应的票价哪个是最少的。这样会把之前的花费加到后面去，但是不影响，因为最后的结果是dp[-1]。
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
ptr = 0 # 指向days数组处理到哪一天
dp = [0] * (days[-1] + 1)
for i in range(1, len(dp)):
if i != days[ptr]:
dp[i] = dp[i - 1]
else:
dp[i] = min(dp[max(0, i - 1)] + costs[0],
dp[max(0, i - 7)] + costs[1],
dp[max(0, i - 30)] + costs[2])
ptr += 1
return dp[-1]
1417. 重新格式化字符串
题目要求：
给你一个混合了数字和字母的字符串s，其中的字母均为小写英文字母。请你将该字符串重新格式化，使得任意两个相邻字符的类型都不同。也就是说，字母后面应该跟着数字，而数字后面应该跟着字母。
请你返回重新格式化后的字符串；如果无法按要求重新格式化，则返回一个空字符串 。
思路：
用两个辅助数组，如果是数字就丢进数字组，字母就丢进字母组，最后轮流输出。
class Solution:
def reformat(self, s: str) -> str:
numbers = []
letters = []
for i in s:
if 'a' <= i <= 'z':
letters.append(i)
else:
numbers.append(i)
n, m = len(numbers), len(letters)
if abs(n - m) > 1:
return ''
res = []
if n >= m:
while numbers:
res.append(numbers.pop())
if letters:
res.append(letters.pop())
else:
while letters:
res.append(letters.pop())
if numbers:
res.append(numbers.pop())
return "".join(res)
1431. 拥有最多糖果的孩子
题目要求：
给你一个数组candies和一个整数extraCandies，其中candies[i]代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的extraCandies个糖果分配给孩子们之后，此孩子有最多的糖果。注意，允许有多个孩子同时拥有最多的糖果数目。
class Solution:
def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
maxC = max(candies)
ans = [candies[i] + extraCandies >= maxC for i in range(len(candies))]
return ans
面试题 17.04. 消失的数字
题目要求：
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
思路一：
跟41题有点像，可以用同一个做法。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
if(not nums):
return 1
n = len(nums)
# 不用额外建立哈希表，利用本身的索引即可
for i in range(n):
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if(nums[i] != i+1):
return i + 1
return n + 1
思路二：
又又又又看了评论区，发现可以直接用等差数列的和算，还真没有想起来。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
sum_ = sum(nums)
return n * (n + 1) // 2 - sum_
思路三：
什么？又是异或。异或满足以下性质：
- (a igoplus 0 = a)
- (a igoplus a = 0)
利用这两个性质可知，将数组中的元素与0 ~ n取异或就得到缺少的那个数字。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
for i in range(n):
ans ^= i
ans ^= nums[i]
# 还少个n没有取异或
ans ^= n
return ans
面试题29. 顺时针打印矩阵
题目要求：
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
思路：
要记住上下左右的边界，这样每次遍历完一行或者一列，就缩小边界。
class Solution:
def spiralOrder(self, matrix:[[int]]) -> [int]:
ans = []
if not matrix:
return ans
l, r, t, b = 0, len(matrix[0]) - 1, 0, len(matrix) - 1
while True:
for i in range(l, r + 1):
ans.append(matrix[t][i])
t += 1
if t > b:
break
for i in range(t, b + 1):
ans.append(matrix[i][r])
r -= 1
if l > r:
break
for i in range(r, l - 1, -1):
ans.append(matrix[b][i])
b -= 1
if t > b:
break
for i in range(b, t - 1, -1):
ans.append(matrix[i][l]) # bottom to top
l += 1
if l > r:
break
return ans
面试题46. 把数字翻译成字符串
题目要求：
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成“z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
思路：
整体思路与91. 解码方法有点类似，还是用动态规划来求解。不同的地方在于，0也可以单独解码，不用特殊考虑。
class Solution:
def translateNum(self, num: int) -> int:
s = str(num)
n = len(s)
dp = [1] * (n + 1)
for i in range(2, n + 1):
if s[i - 2] == '1' or
(s[i - 2] == '2' and s[i - 1] < '6'):
dp[i] = dp[i - 2] + dp[i - 1]
else:
dp[i] = dp[i - 1]
return dp[-1]
面试题64. 求1+2+…+n
题目要求：
求1+2+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
思路：
用于迭代的关键字都不能用，那就只能用递归。但是条件判断语句也不能使用，只好康康别人的题解利用用and运算的短路机制，即前面的语句如果返回的是False就不管后面的了。
class Solution:
def __init__(self):
self.ans = 0
def sumNums(self, n: int) -> int:
n > 1 and self.sumNums(n - 1)
self.ans += n
return self.ans