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

''' 这道题对我来说有点难......等我做出来再更新，有懂得小伙伴交流一下，谢谢！ '''