剑指 Offer 04. 二维数组中的查找
题目描述：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 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
由于存在矩阵每行和每列的数据都是递增的，所以我们可以从最小的元素所在的位置或是最大的元素所在的位置，即二维数组的左下角或是右上角开始查找。若当前位置的元素小于查找的数时，行数加1；否则列数加1。如下所示：
下三角寻找：
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if matrix is None or matrix == []: return False
rows, cols = len(matrix), len(matrix[0])
row, col = rows - 1, 0
while row >= 0 and col <= cols - 1:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
row -= 1
else:
col += 1
return False
上三角寻找：
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if matrix is None or matrix == []: return False
rows, cols = len(matrix), len(matrix[0])
row, col = 0, cols - 1
while col >= 0 and row <= rows - 1:
if matrix[row][col] == target:
return True
elif matrix[row][col] < target:
row += 1
else:
col -= 1
return False
440. 字典序的第K小数字
给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
示例 :
输入:
n: 13 k: 2
输出:
10
解释:
字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
补充题2. 圆环回原点问题
91. 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2:
输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
dp[i]表示到第i-1位时解码的方法数
两种情况：
1.s[i-1]单独解码，方法数为dp[i-1]
2.s[i-2:i]拼接成双字符解码，若10<=s[i-2:i]<26，双字符合格，解码的方法数位dp[i-2]，否则为0
综合两种情况，得到状态转移矩阵：
dp[i] = dp[i-1] + (dp[i-2] if 双字符合格 else 0)
为什么dp[i]表示的使i-1位？
例如 216，在判断第二位‘1’时，i-2<0了，状态转移矩阵不能用了，故在前加一位，即dp[0]为1
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1 if s[0]!='0' else 0
for i in range(2,n+1):
if s[i-1]!='0':
dp[i] = dp[i-1]
if 9< int(s[i-2:i])<27:
dp[i] += dp[i-2]
return dp[-1]
230. 二叉搜索树中第K小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
代码
# 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 kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
inorder = list()
self.inorderTra(root, inorder)
print inorder
return inorder[k-1]
def inorderTra(self, node, path):
if not node:
return
self.inorderTra(node.left, path)
path.append(node.val)
self.inorderTra(node.right, path)
572. 另一个树的子树
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
示例 1:
给定的树 s:
3
/ \
4 5
/ \
1 2
给定的树 t：
4
/ \
1 2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
示例 2:
给定的树 s：
3
/ \
4 5
/ \
1 2
/
0
给定的树 t：
4
/ \
1 2
返回 false。
思路：深度优先搜索
在这里，先分析题意：
一个二叉树若为另一个树的子树，则它含有与另外一个树的子树相同结构和节点值。
根据示例 2 可知，判断是否为子树，必须有完全相同结构和节点值。
以下 s、t 表示两个二叉树，题目要求判断 t 是否是 s 的子树
现在将题意转换为可实现代码书写的思路，判断两个树是否相等，那么下面的条件必须同时成立：
当前两个树根节点值相同；
s 的左子树与 t 的左子树相同；
s 的右子树与 t 的右子树相同。
根据上面的思路，本篇幅考虑使用深度优化搜索的方法，枚举 s 的每个节点，判断这个点的子树是否与 t 相等。使用深度优先搜索检查，从根出发，同步移动遍历两个树，判断相应的位置是否相等。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
return self.dfs(s, t)
def dfs(self, c, t):
# c 子树为空时，返回 False
if not c:
return False
return self.is_same(c, t) or self.dfs(c.left, t) or self.dfs(c.right, t)
def is_same(self, c, t):
# 两个树都为空时，也认为是相同
if (not c) and (not t):
return True
# 当其中一个树为空，但另外一个树不为空时，此时则为不同
if (not c and t) or (c and not t):
return False
# 两个树都不为空，若值不同，也为不同
if (c.val != t.val):
return False
# 上面的情况都不符合时，继续向下检查
return self.is_same(c.left, t.left) and self.is_same(c.right, t.right)
114. 二叉树展开为链表
# 递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def unflod(node):
if not node:
return None
unflod(node.left)
unflod(node.right)
# 后序遍历
if node.left:
pre = node.left
# 找到左子树的最右子节点，用以连接根的右子树
while pre.right:
pre = pre.right
# 当找到左子树的最右子节点，令其指向根的右子树
pre.right = node.right
# 然后令根的右子树指向根的左子树，令根的左子树为空
node.right = node.left
node.left = None
# 循环
node = node.right
unflod(root)
# 非递归
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
while root:
if root.left:
pre_node = root.left
# 同样先找到左子树的最右节点
while pre_node.right:
pre_node = pre_node.right
# 最右节点指向根节点的右子树
pre_node.right = root.right
# 根的右子树指向根的左子树，同时置空左子树
root.right = root.left
root.left = None
root = root.right
剑指 Offer 62. 圆圈中最后剩下的数字
445. 两数相加 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverse(self, head): # 链表反转
pre = head
cur = head.next
pre.next = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
l1 = self.reverse(l1)
l2 = self.reverse(l2)
h = ListNode((l1.val + l2.val) % 10) # 额外记下头结点，方便后续反转链表
flag = (l1.val + l2.val) // 10
p = h
l1 = l1.next
l2 = l2.next
while l1 or l2 or flag:
if l1 and l2:
node = ListNode((l1.val + l2.val + flag) % 10)
flag = (l1.val + l2.val + flag) // 10
l1 = l1.next
l2 = l2.next
elif l1:
node = ListNode((l1.val + flag) % 10)
flag = (l1.val + flag) // 10
l1 = l1.next
elif l2:
node = ListNode((l2.val + flag) % 10)
flag = (l2.val + flag) // 10
l2 = l2.next
elif flag:
node = ListNode(flag)
flag = 0
p.next = node
p = node
return self.reverse(h)
295. 数据流的中位数
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是
输入：x = 121
输出：true
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数
def isPalindrome(x: int) -> bool:
"""不满足进阶要求"""
if x < 0:
return False
if 0 <= x <= 9:
return True
if x % 10 == 0:
return False
rev_x = int(''.join(list(str(x))[::-1]))
if rev_x == x:
return True
else:
return False
