力扣高频|算法面试题汇总(一）：开始之前_力扣算法面试题

力扣高频|算法面试题汇总(一）：开始之前
力扣高频|算法面试题汇总(二）：字符串
力扣高频|算法面试题汇总(三）：数组
力扣高频|算法面试题汇总(四）：堆、栈与队列
力扣高频|算法面试题汇总(五）：链表
力扣高频|算法面试题汇总(六）：哈希与映射
力扣高频|算法面试题汇总(七）：树
力扣高频|算法面试题汇总(八）：排序与检索
力扣高频|算法面试题汇总(九）：动态规划
力扣高频|算法面试题汇总(十）：图论
力扣高频|算法面试题汇总(十一）：数学&位运算

力扣高频|算法面试题汇总(一）：开始之前

力扣链接
目录：

• 1.只出现一次的数字
• 2.多数元素
• 3.搜索二维矩阵 II
• 4.合并两个有序数组
• 5.鸡蛋掉落

1.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4

特别要求：线性时间复杂度+不使用额外空间。
因此使用做差法，即异或，相同的数字经过异或运算后结果为0，除单独出现一次的数字外，其他数字都是出现两次的，那么这些数字经过异或运算后结果一定是0。而任何数字与0进行异或运算都是该数字本身。
C++

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 使用异或操作
        int num = 0;
        for(auto itear = nums.cbegin(); itear < nums.cend(); ++itear)
            num ^= *itear;
        return num;
    }
};
1
2
3
4
5
6
7
8
9
10

Python:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num
        return res
1
2
3
4
5
6

2.多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

方法一：
使用哈希表，用哈希表来快速统计每个元素出现的次数。一边循环，一边记录数字重复的最大次数和最大值，保证时间复杂度$O(n)$。
C++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
            map<int, int> idCount;
            int majorityNum = 0;// 记录出现次数最多的数字
            int count = 0;  // 记录出现的次数
            for(int i = 0; i < nums.size(); ++i){
                ++idCount[nums[i]];
                if(idCount[nums[i]] > count){
                    count = idCount[nums[i]];
                    majorityNum = nums[i];
                }
            }

            return majorityNum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Python

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        idHash = {}.fromkeys(nums,0) # 全部初始化为0
        maxCount = 0
        maxCountNum = 0
        for num in nums:
            idHash[num] += 1
            if idHash[num] > maxCount:
                maxCount = idHash[num]
                maxCountNum = num
        
        return maxCountNum
1
2
3
4
5
6
7
8
9
10
11
12

或者：

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)
1
2
3
4

方法二：
排序，如果某个数字超过半数，那么在排序之后，索引为$n/2$必定为出现次数过半的哪个数字。
C++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 排序
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};
1
2
3
4
5
6
7
8

Python

class Solution:
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)//2]
1
2
3
4

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。

因为矩阵的行和列是排序的（分别从左到右和从上到下），所以在查看任何特定值时，我们可以修剪$O(m)$或$O(n)$元素。如以左下角（或者右上角）为起点，与target进行比较，如果小于target，则减少行数，如果大于target则增加列数，以右上角为起点类似，整个时间复杂度为$O(m+n)$
C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows, cols;
        if(matrix.empty())
            return false;
        rows = matrix.size();
        cols = matrix[0].size();

        // 因为矩阵是有序的，所以从左小角开始判断
        int row = rows-1;
        int col = 0;
        while(row >= 0 && col < cols){
            if(matrix[row][col] == target){
                return true;
            }else if(matrix[row][col] > target){
                --row;
            }else{
                ++col;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Python:

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        
        row = rows - 1
        col = 0
        while row >= 0 and col < cols:
            if matrix[row][col] < target:
                col += 1
            elif matrix[row][col] > target:
                row -= 1
            else:
                return True
        
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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]

直接对两个数组按着判断即可。
C++

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums1Copy = nums1; // 拷贝nums1
        int p1 = 0;
        int p2 = 0;
        int count = 0;
        while(p1 < m && p2 < n){
            if(nums1Copy[p1] <= nums2[p2]){
                nums1[count] = nums1Copy[p1];
                ++p1;
            }else{
                nums1[count] = nums2[p2];
                ++p2;
            }
            ++count;
        }
        while(p1 < m){
            nums1[count] = nums1Copy[p1];
            ++p1;
            ++count;
        }
        while(p2 < n){
            nums1[count] = nums2[p2];
            ++p2;
            ++count;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Python：

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1Copy = nums1.copy()
        p1 = 0
        p2 = 0 
        count = 0
        while p1 < m and p2 < n:
            if nums1Copy[p1] <= nums2[p2]:
                nums1[count] = nums1Copy[p1]
                p1 += 1
            else:
                nums1[count] = nums2[p2]
                p2 += 1
            count += 1
        
        while p1 < m:
            nums1[count] = nums1Copy[p1]
            p1 += 1
            count += 1
        while p2 < n:
            nums1[count] = nums2[p2]
            p2 += 1
            count += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
提示：
1 <= K <= 100
1 <= N <= 10000

这里参考一个博主的解析。
总结一下：

• 1.这个题有两个关键值：鸡蛋个数K或者eggsCount，楼层数N，需要解的是需要多少次(remainTestCount)扔鸡蛋就可以确定关键楼层F，并且可以不考虑鸡蛋去往任意楼层的时间。
• 2.如果你只有一个鸡蛋eggsCount，那么你只能从第一层往上时，比如从第一层扔下去，如果碎了，则F=0，可以确定的楼层数N=1；如果没有碎，则F>1,可以继续在更上面的楼层扔掉，直到可以扔的次数remainTestCount用完，或者鸡蛋碎掉。也就是当鸡蛋的个数只有一个时，可以确定的楼层getConfirmFloors的最大值，只与remainTestCount相关。
• 3.如果只允许你扔一次，即remainTestCount=1，那么你只能确定的楼层数只能从第1层扔，如果鸡蛋碎了，那么F=1，否则F>1。
• 4.本题问的是你确定 F 的值的最小移动次数是多少？其实就是考虑在最坏的情况下需要移动 多少次以确定 F 是多少
• 5.定义一个函数getConfirmFloors( remainTestCount, eggsCount)，即表示有remainTestCount次扔鸡蛋的机会和手上有eggsCount个鸡蛋能够确定的楼层数，当能确定的楼层数>N，即大于本题给的楼层数时，remainTestCount即为确定 F 的值的最小移动次数
• 6.当在某一层m时，你有remainTestCount次机会和eggsCount鸡蛋，你可以确定的楼层数为getConfirmFloors( remainTestCount, eggsCount)，你扔下去，如果鸡蛋碎了，那么你还可以确定的楼层数为：getConfirmFloors( remainTestCount- 1, eggsCount-1)，如果没有碎，那么你还可以确定的楼层数为：getConfirmFloors( remainTestCount- 1, eggsCount)，但是无论你鸡蛋碎不碎，当前层m你是可以确定的。则可以得到等式：getConfirmFloors( remainTestCount, eggsCount) = getConfirmFloors( remainTestCount-1, eggsCount-1) + getConfirmFloors( remainTestCount-1, eggsCount) + 1。

C++

class Solution {
public:
    int superEggDrop(int K, int N) {
        int remainTestCount = 1;
        while(getConfirmFloors(remainTestCount, K)<N)// 第5点，通过remainTestCount次数可以确定的楼层数
            ++remainTestCount;						 // 如果确定的楼层数大于N，remainTestCount为解
        
        return remainTestCount;
    }
    int getConfirmFloors(int remainTestCount, int eggsCount){
        if(remainTestCount == 1 || eggsCount ==1){	// 第2点和第3点
            return remainTestCount;
        }
        return getConfirmFloors(remainTestCount - 1, eggsCount) +	//第6点
            getConfirmFloors(remainTestCount - 1, eggsCount - 1) + 
            1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Python

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        remainCounts = 1
        while self.getConfirmFloors(remainCounts, K) < N:
            remainCounts += 1
        return remainCounts
    
    def getConfirmFloors(self,  remainCounts,  K) -> int:
        if remainCounts == 1 or K == 1:
            return remainCounts
        return self.getConfirmFloors(remainCounts-1, K) + \
                self.getConfirmFloors(remainCounts-1, K-1) +\
                1
1
2
3
4
5
6
7
8
9
10
11
12
13