題目描述1：53.在排序數組中查找數字 難度：簡單
統計一個數字在排序數組中出現的次數。
示例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: 2
示例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: 0
解題思路：
暴力方法，直接遍歷
二分法查找
Python代碼：
class Solution: def search(self, nums: List[int], target: int) -> int: count = 0 for i in nums: if i == target: count += 1 return count class Solution: def search(self, nums: List[int], target: int) -> int: i, j = 0, len(nums)-1 while i <= j: m = (i + j) // 2 if nums[m] <= target:i = m + 1 else:j = m - 1 right = i if j >= 0 and nums[j] != target: return 0 i = 0 while i <= j: m = (i + j) // 2 if nums[m] < target:i = m + 1 else: j = m - 1 left = j return right - left - 1class Solution: def search(self, nums: List[int], target: int) -> int: def find(target): i, j = 0, len(nums)-1 while i <= j: m = (i + j) // 2 if nums[m] <= target:i = m + 1 else:j = m - 1 return i return find(target) - find(target-1)
題目描述2：34.在排序數組中查找元素的第一個和最後一個位置 難度：中等
給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
如果數組中不存在目標值 target，返回 [-1, -1]。
進階：
你可以設計並實現時間複雜度為 O(log n) 的算法解決此問題嗎？
示例 1：
輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]
示例 2：
輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]
示例 3：
輸入：nums = [], target = 0
輸出：[-1,-1]
解題思路：
同上
Python代碼：
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: res = [-1,-1] tmp = [] for i in range(len(nums)): if nums[i] == target: tmp.append(i) if tmp: res[0], res[1] = tmp[0], tmp[-1] return resclass Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: def find(target): i, j = 0, len(nums)-1 while i <= j: m = (i + j) // 2 if nums[m] <= target:i = m + 1 else:j = m - 1 return i res = [-1,-1] if (find(target) - find(target-1)) != 0: res[0] = find(target-1) res[1] = find(target) - 1 return res
題目描述3：53.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
解題思路：
Python代碼：
class Solution: def missingNumber(self, nums: List[int]) -> int: i, j = 0, len(nums) - 1 while i <= j: m = (i + j) // 2 if nums[m] == m: i = m + 1 else: j = m - 1 return i class Solution: def missingNumber(self, nums: List[int]) -> int: for i in range(len(nums)): if i != nums[i]: return i return len(nums)
題目描述4：54.二叉搜索樹的第k大節點 難度：簡單
給定一棵二叉搜索樹，請找出其中第k大的節點。
示例 1:
輸入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
輸出: 4
示例 2:
輸入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
輸出: 4
解題思路：
中序遍歷
Python代碼：
class Solution: def kthLargest(self, root: TreeNode, k: int) -> int: res = [] def dfs(root): if not root:return dfs(root.left) res.append(root.val) dfs(root.right) dfs(root) return res[-k]
題目描述5：55.二叉樹的深度 難度：簡單
輸入一棵二叉樹的根節點，求該樹的深度。從根節點到葉節點依次經過的節點（含根、葉節點）形成樹的一條路徑，最長路徑的長度為樹的深度。
例如：
給定二叉樹 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
解題思路：
遞歸
Python代碼：
class Solution: def maxDepth(self, root: TreeNode) -> int: if not root:return 0 L = self.maxDepth(root.left) R = self.maxDepth(root.right) return max(L, R) + 1
題目描述6：55.平衡二叉樹 難度：簡單
輸入一棵二叉樹的根節點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意節點的左右子樹的深度相差不超過1，那麼它就是一棵平衡二叉樹。
示例 1:
給定二叉樹 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
給定二叉樹 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
解題思路：
遞歸
Python代碼：
class Solution: def isBalanced(self, root: TreeNode) -> bool: self.flag = True def dfs(root): if not root:return 0 L = dfs(root.left) R = dfs(root.right) if abs(L - R) > 1: self.flag = False return max(L, R) + 1 dfs(root) return self.flag
題目描述7：136.只出現一次的數字 難度：簡單
給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。
說明：
你的算法應該具有線性時間複雜度。你可以不使用額外空間來實現嗎？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
解題思路：
位運算
Python代碼：
class Solution: def singleNumber(self, nums: List[int]) -> int: res = 0 for i in nums: res ^= i return res
題目描述8：137.只出現一次的數字 難度：中等
給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現了三次。找出那個只出現了一次的元素。
說明：
你的算法應該具有線性時間複雜度。你可以不使用額外空間來實現嗎？
示例 1:
輸入: [2,2,3,2]
輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
解題思路：
如下圖所示，考慮數字的二進位形式，對於出現三次的數字，各 二進位位 出現的次數都是 3 的倍數。
因此，統計所有數字的各二進位位中 1 的出現次數，並對 3 求餘，結果則為只出現一次的數字。
Python代碼：
class Solution: def singleNumber(self, nums: List[int]) -> int: counts = [0] * 32 for num in nums: for j in range(32): counts[j] += num & 1 num >>= 1 res, m = 0, 3 for i in range(32): res <<= 1 res |= counts[31 - i] % m return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)
題目描述9：56.數組中數字出現的次數 難度：中等
一個整型數組 nums 裡除兩個數字之外，其他數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間複雜度是O(n)，空間複雜度是O(1)。
示例 1：
輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]
示例 2：
輸入：nums = [1,2,10,4,1,4,3,3]
輸出：[2,10] 或 [10,2]
解題思路：
Python代碼：
class Solution: def singleNumbers(self, nums: List[int]) -> List[int]: res = 0 #所有數字異或的結果 a = 0 b = 0 for i in nums: res ^= i h = 1 while (res & h == 0): h <<= 1 for i in nums: if (i & h) == 0: a ^= i else: b ^= i return [a,b]
題目描述10：645.錯誤的集合 難度：簡單
集合 S 包含從1到 n 的整數。不幸的是，因為數據錯誤，導致集合裡面某一個元素複製了成了集合裡面的另外一個元素的值，導致集合丟失了一個整數並且有一個元素重複。
給定一個數組 nums 代表了集合 S 發生錯誤後的結果。你的任務是首先尋找到重複出現的整數，再找到丟失的整數，將它們以數組的形式返回。
示例 1:
輸入: nums = [1,2,2,4]
輸出: [2,3]
解題思路：
方法1：使用字典存放整數出現的次數
如果一個整數在字典中沒出現，說明是缺失的值
如果一個整數在字典中出現了兩次，說明是重複的值方法2：位移
Python代碼：
class Solution: def findErrorNums(self, nums: List[int]) -> List[int]: class Solution: def findErrorNums(self, nums: List[int]) -> List[int]: dicts = {} res = [] for i in nums: dicts[i] = dicts.setdefault(i,0) dicts[i] += 1 for i in range(1,len(nums) + 1): if i not in dicts: res.append(i) elif dicts[i] == 2: res.insert(0,i) elif len(res) == 2: break return res lass Solution: def findErrorNums(self, nums: List[int]) -> List[int]: ret = 0 a = 0 b = 0 for n in nums: ret ^= n for i in range(1, len(nums) + 1): ret ^= i h = 1 while(ret & h == 0): h <<= 1 for n in nums: //數組的一半 if (h & n == 0): a ^= n else: b ^= n for n in range(1, len(nums) + 1): //數組的另一半 if (h & n == 0): a ^= n else: b ^= n for num in nums: if a == num: return [a, b] if b == num: return [b, a]
題目描述11：57.和為s的兩個數字 難度：簡單
輸入一個遞增排序的數組和一個數字s，在數組中查找兩個數，使得它們的和正好是s。如果有多對數字的和等於s，則輸出任意一對即可。
示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[2,7] 或者 [7,2]
示例 2：
輸入：nums = [10,26,30,31,47,60], target = 40
輸出：[10,30] 或者 [30,10]
解題思路：
利用 HashMap 可以通過遍歷數組找到數字組合，時間和空間複雜度均為 O(N) ；
注意本題的 numsnums 是 排序數組 ，因此可使用 雙指針法 將空間複雜度降低至。
Python代碼：
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dics = {} for i in nums: if i in dics: return [i,dics[i]] else: dics[target - i] = i
題目描述12：57.和為s的連續正數序列 難度：簡單
輸入一個正整數 target ，輸出所有和為 target 的連續正整數序列（至少含有兩個數）。
序列內的數字由小到大排列，不同序列按照首個數字從小到大排列。
示例 1：
輸入：target = 9
輸出：[[2,3,4],[4,5]]
示例 2：
輸入：target = 15
輸出：[[1,2,3,4,5],[4,5,6],[7,8]]
解題思路：
滑動窗口
數學公式法（求根法）
Python代碼：
class Solution:
class Solution: def findContinuousSequence(self, target: int) -> List[List[int]]: i, j = 0, 0 nums = [x for x in range(1,target//2 + 2)] #15、16 res = [] while j <= len(nums): cur_sum = sum(nums[i:j]) if j != i and cur_sum == target: res.append(nums[i:j]) j += 1 if cur_sum > target: i += 1 if cur_sum < target: j += 1 return resclass Solution: def findContinuousSequence(self, target: int): res = [] for y in range(1,target//2 + 2): x = (1/4 + y**2 + y - 2 * target) ** (1/2) + 0.5 if type(x) != complex and x - int(x) == 0: res.append(list(range(int(x),y+1))) return res
題目描述13：58.翻轉單詞順序 難度：簡單
輸入一個英文句子，翻轉句子中單詞的順序，但單詞內字符的順序不變。為簡單起見，標點符號和普通字母一樣處理。例如輸入字符串"I am a student. "，則輸出"student. a am I"。
示例 1：
輸入: "the sky is blue"
輸出: "blue is sky the"
示例 2：
輸入: " hello world! "
輸出: "world! hello"
解釋: 輸入字符串可以在前面或者後面包含多餘的空格，但是反轉後的字符不能包括。
示例 3：
輸入: "a good example"
輸出: "example good a"
解釋: 如果兩個單詞間有多餘的空格，將反轉後單詞間的空格減少到只含一個。
解題思路：
方法一：分割+倒置
方法二：雙指針
Python代碼：
class Solution: def reverseWords(self, s: str) -> str: s = s.strip() i = j = len(s) - 1 res = [] while i >= 0: while i >=0 and s[i] != ' ':i -= 1 res.append(s[i + 1:j + 1]) while s[i] == ' ':i -= 1 j = i return ' '.join(res)
參考資料：
1.https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/mian-shi-ti-53-i-zai-pai-xu-shu-zu-zhong-cha-zha-5/
2.https://leetcode-cn.com/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/
3.https://leetcode-cn.com/problems/single-number-ii/solution/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/
4.https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/zhi-chu-xian-yi-ci-de-shu-xi-lie-wei-yun-suan-by-a/
來源：LeetCode
連結:
1.https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
2.https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
3.https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
4.https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
5.https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
6.https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
7.https://leetcode-cn.com/problems/single-number/
8.https://leetcode-cn.com/problems/single-number-ii/
9.https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/
10.https://leetcode-cn.com/problems/set-mismatch/
11.https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/
12.https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
13.https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/