劍指 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 Falserows, cols = len(matrix), len(matrix[0])row, col = rows - 1, 0while row >= 0 and col <= cols - 1:if matrix[row][col] == target:return Trueelif matrix[row][col] > target:row -= 1else:col += 1return False上三角尋找：
class Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:if matrix is None or matrix == []: return Falserows, cols = len(matrix), len(matrix[0])row, col = 0, cols - 1while col >= 0 and row <= rows - 1:if matrix[row][col] == target:return Trueelif matrix[row][col] < target:row += 1else:col -= 1return False440. 字典序的第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] = 1dp[1] = 1 if s[0]!='0' else 0for 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 = Noneclass Solution(object):def kthSmallest(self, root, k):""":type root: TreeNode:type k: int:rtype: int"""inorder = list()self.inorderTra(root, inorder)print inorderreturn 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 子樹為空時，返回 Falseif not c:return Falsereturn 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 Noneunflod(node.left)unflod(node.right)# 后序遍歷if node.left:pre = node.left# 找到左子樹的最右子節點，用以連接根的右子樹while pre.right:pre = pre.right# 當找到左子樹的最右子節點，令其指向根的右子樹pre.right = node.right# 然后令根的右子樹指向根的左子樹，令根的左子樹為空node.right = node.leftnode.left = None# 循環node = node.rightunflod(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.leftroot.left = Noneroot = 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 = headcur = head.nextpre.next = Nonewhile cur:tmp = cur.nextcur.next = prepre = curcur = tmpreturn predef 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) // 10p = hl1 = l1.nextl2 = l2.nextwhile l1 or l2 or flag:if l1 and l2:node = ListNode((l1.val + l2.val + flag) % 10)flag = (l1.val + l2.val + flag) // 10l1 = l1.nextl2 = l2.nextelif l1:node = ListNode((l1.val + flag) % 10)flag = (l1.val + flag) // 10l1 = l1.nextelif l2:node = ListNode((l2.val + flag) % 10)flag = (l2.val + flag) // 10l2 = l2.nextelif flag:node = ListNode(flag)flag = 0p.next = nodep = nodereturn 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 Falseif 0 <= x <= 9:return Trueif x % 10 == 0:return Falserev_x = int(''.join(list(str(x))[::-1]))if rev_x == x:return Trueelse:return False
)
