一、题目

给定两个有序数组arr1和arr2，再给定一个整数k，返回来自arr1和arr2的两个数相加和最大的前k个，两个数必须分别来自两个数组。按照降序输出。[要求]时间复杂度为O(klogk)。

1
2

arr1=[1,2,3,4,5], arr2=[3,5,7,9,11], k=4
返回数组 [16, 15, 14, 14]

二、分析

这道题目本身比较简单，就是写起来比较麻烦

注意 K 这个参数，我们需要调整，如果 arr1 的数量和 arr2 的数量之积，小于 K，则 K 取此积。

一、题目

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以 按任意顺序 返回答案。

1
2

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Leetcode：https://leetcode.cn/problems/permutations/

二、分析

回溯法 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

之字形打印矩阵

一、题目

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

也就是按照 “之” 字形的方式打印这个矩阵

1
2

mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

二、思路

我们可以看到其实就是按照对角线来打印。我们选取两个坐标。

在数组中找到一个局部最小的位置

一、题目

定义局部最小的概念。arr 的长度为 1 时，arr[0] 是局部最小。arr 的长度为 N (N > 1) 时，如果 arr[0] < arr[1]，那么 arr[0] 是局部最小；如果 arr[N-1] < arr[N-2]，那么 arr[N-1] 是局部最小；如果 0 < i < N-1，既有 arr[i] < arr[i-1]，又有 arr[i] < arr[i+1]，那么 arr[i] 是局部最小。

给定无序数组 arr，已知 arr 中任意两个相邻的数都不相等。写一个函数，只需返回 arr 中任意一个局部最小出现的位置即可。

二、思路

首先把几个极端条件列举出来给 pass 掉。当数组为空时，直接返回 -1；如果数组中只有一个数时，直接返回 0 位置；然后判断数组的最左边，如果 arr[0] < arr[1] 时，返回位置 0 即可；接下来判断数组的最右边，如果 arr[N-1] > arr[N-2]，返回位置 N-2 即可。

这时，一定存在局部最小值，因此通过 arr[0] < arr[1] 和 arr[N-1] > arr[N-2] 这两个条件不成立，就已经证明了数组不是有序的。所以一定存在局部最小值。

对于其他平常情况，我们采用二分查找的办法。定义 left 为 1，right 为 N-2；因为 位置 0 和位置 N-1 位置都已经尝试过了。遍历数组，条件是 left < right，取 mid = left + (right-left) / 2，当 arr[mid] > arr[mid-1] 时，说明左边肯定有局部最小值，让 right = mid-1，然后遍历左边子数组。当 arr[mid] > arr[mid+1] 时，说明右边肯定有局部最小值，让 left = mid+1。当这两个条件都不满足的时候，说明 mid 就是局部最小值的位置，直接返回 mid 位置即可。

在行列都排好序的矩阵中找指定值

一、题目

在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

现有矩阵 matrix 如下：

1
2
3
4
5
6
7

[
  [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。

一、给多个无序数组，求这些数组中元素的交集。

因为数组无序，所以我们必须要遍历所有数组所有元素。

1. 统计每个整数的出现次数

我们用 N 表示二维数组 nums 的长度。如果一个元素在每个数组中都出现过，则他出现的次数一定等于 N。因此我们用哈希表维护每个整数的出现次数，随后我们遍历二维数组所有元素，并更新到这个哈希表。

最终，我们遍历哈希表，其中出现次数等于 N 的元素即为交集。

这种方法，在最坏情况下，二维数组中所有元素都没有交集的情况下。哈希表非常大，会存储所有元素。而且数组中不能出现重复元素，如果有重复元素，使用出现次数就不准确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> intersection(const vector<vector<int>>& nums) {
        int n = nums.size();
        unordered_map<int, int> freq;
        for (const auto& arr: nums) {
            for (int num: arr) {
                ++freq[num];
            }
        }
        vector<int> res;
        for (const auto& [k, v]: freq) {
            if (v == n) {
                res.push_back(k);
            }
        }
        return res;
    }
};

子数组的最大累乘积

一、题目

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

leetcode：https://leetcode.cn/problems/maximum-product-subarray/

二、思路

我们按照动态规划的思路来做，我们以 arr[i] 为底，有变量 max 表示 arr[0 ... i] 的最大值，变量 min 表示 arr[0 ... i] 的最小值。当我们遍历到 i+1 位置时，我们求以 i+1 为底的子数组的最大累乘积，所以一定要用到 arr[i+1] 这个值。

一、题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

1
2
3
4
5
6
7

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

Leetcode：https://leetcode.cn/problems/number-of-islands

子矩阵的最大累加和

一、题目

给定一个矩阵，这个矩阵中的值有正、负、0。返回子矩阵的最大累加和。如下例子

1
2
3
4
5

matrix{{-90, 48, 78}, {64, -40, 64}, {-81, -7, 66}};
返回 209，子矩阵如下：
48   78
-40  64
64   66

二、思路

首先我们先看一个矩阵都有哪些子矩阵。假设一个 3 行的矩阵，我们先不管列，暂止列的数据全部用上，那么有这么多子矩阵

子数组的最大累加和

一、题目

给定一个数组，返回数组的最大累加和

1
2

arr = {1, -2, 3, 5, -2, 6, -1}
子数组 {3, 5, -2, 6} 可以累加出最大的和为 12

二、思路

这个数组中有正数、负数。既然只是要求最大累加和。那么我们使用 cur 记录当前子数组的累加和，用 max 来记录子数组的最大累加和。

遍历这个数组，每次给 cur 加上当前这个数。如果 cur 大于 0，我们更新一下 max 的值；如果 cur 小于 0，我们给 cur 赋 0。为什么这么做呢？因为 cur 大于 0，为正数，那么肯定可以作为子数组的一部分。如果 cur 为负数了，那么它就不能作为子数组的一部分。牢记子数组是连续的，而且我们也已经用 max 再每次遍历中记录了子数组的累加和。