Leetcode 探索演算法面試題彙總（一）

 寫在前面：所有題目都是用python寫的，有一些題目懶得重頭寫，直接用python自帶的功能或庫造好的“輪子”

一、開始之前

1、只出現一次的數字

給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

說明：

你的演算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎？

示例 1:

輸入: [2,2,1]

輸出: 1

示例 2:

輸入: [4,1,2,1,2]

輸出: 4

def singleNumber(nums):
    tmp = []
    for num in nums:
        if num in tmp:
            tmp.remove(num)
        else:tmp.append(num)
    return tmp[0]

2、求眾數

給定一個大小為 n 的數組，找到其中的眾數。眾數是指在數組中出現次數大於 ⌊ n/2 ⌋ 的元素。

你可以假設數組是非空的，並且給定的數組總是存在眾數。

示例 1:

輸入: [3,2,3]

輸出: 3

示例 2:

輸入: [2,2,1,1,1,2,2]

輸出: 2

'''
    先將對應的數目存為字典
    找到 values 中最大的值
    再遍歷字典返回 key
'''
def majorityElement(nums):
    dic = {}
    for num in nums:
        dic[num] = dic.get(num, 0) + 1
    max_num = max(dic.values())
    for key in dic.keys():
        if dic[key] == max_num:
            return key

3、搜索二維矩陣 II

編寫一個高效的演算法來搜索 m x n 矩陣 matrix 中的一個目標值 target。該矩陣具有以下特性：

每行的元素從左到右升序排列。
每列的元素從上到下升序排列。

示例:

現有矩陣 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。

def searchMatrix(matrix, target):
    """
    遞歸，先定位到右上角的數 x
    若 target < x 則往左移一格
    若 target > x 則往下移一格
    註意遞歸的出口
    """
    if matrix == []:
        return False
    m = 0
    n = len(matrix[0]) - 1
    return f(matrix, m, n, target)

def f(matrix, m, n, target):
    if n < 0:
        return False
    if m == len(matrix):
        return False
    if target == matrix[m][n]:
        return True
    if target < matrix[m][n]:
        return f(matrix, m, n-1, target)
    if target > matrix[m][n]:
        return f(matrix, m+1, n, target)
    return False

4、合併兩個有序數組

給定兩個有序整數數組 nums1 和 nums2，將 nums2 合併到 nums1 中，使得 num1 成為一個有序數組。

說明:

初始化 nums1 和 nums2 的元素數量分別為 m 和 n。

你可以假設 nums1 有足夠的空間（空間大小大於或等於 m + n）來保存 nums2 中的元素。

示例:

輸入:

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],     n = 3

輸出: [1,2,2,3,5,6]

# 不想重覆造輪子，簡單粗暴的做法
def merge(nums1, m, nums2, n):
    """
    Do not return anything, modify nums1 in-place instead.
    """
    nums1[m:] = nums2[:n]
    nums1.sort()

5、雞蛋掉落

你將獲得 K 個雞蛋，並可以使用一棟從 1 到 N  共有 N 層樓的建築。

每個蛋的功能都是一樣的，如果一個蛋碎了，你就不能再把它掉下去。

你知道存在樓層 F ，滿足 0 <= F <= N 任何從高於 F 的樓層落下的雞蛋都會碎，從 F 樓層或比它低的樓層落下的雞蛋都不會破。

每次移動，你可以取一個雞蛋（如果你有完整的雞蛋）並把它從任一樓層 X 扔下（滿足 1 <= X <= N）。

你的目標是確切地知道 F 的值是多少。

無論 F 的初始值如何，你確定 F 的值的最小移動次數是多少？

示例 1：

輸入：K = 1, N = 2 輸出：2 解釋： 雞蛋從 1 樓掉落。如果它碎了，我們肯定知道 F = 0 。 否則，雞蛋從 2 樓掉落。如果它碎了，我們肯定知道 F = 1 。 如果它沒碎，那麼我們肯定知道 F = 2 。 因此，在最壞的情況下我們需要移動 2 次以確定 F 是多少。

示例 2：

輸入：K = 2, N = 6 輸出：3

示例 3：

輸入：K = 3, N = 14 輸出：4

''' 這道題對我來說有點難......等我做出來再更新，有懂得小伙伴交流一下，謝謝！ '''