欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Leetcode 探索算法面试题汇总(一)

程序员文章站 2022-04-19 23:24:31
写在前面:所有题目都是用python写的,有一些题目懒得重头写,直接用python自带的功能或库造好的“*” 一、开始之前 1、只出现一次的数字 说明: 示例 1: 示例 2: 2、求众数 示例 1: 示例 2: 3、搜索二维矩阵 II 示例: 现有矩阵 matrix 如下: [ [1, 4, 7 ......

 写在前面:所有题目都是用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

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