最长的可整合子数组的长度

一、题目

先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数的差的绝对值都为1，或者该数组长度为1，则该数组为可整合数组。例如，[5, 3, 4, 6, 2]排序后为[2, 3, 4, 5, 6]，符合每相邻两个数差的绝对值都为1，所以这个数组为可整合数组

给定一个数组arr, 请返回其中最大可整合子数组的长度。例如，[5, 5, 3, 2, 6, 4, 3]的最大可整合子数组为[5, 3, 2, 6, 4]，所以请返回5

二、思路

我们首先需要获取到这个数组中的所有子数组，然后在判断这个子数组是否为可整合的。判断可整合可以按照这样的思路，这个子数组必须是没有重复元素，并且最大值减去最小值，再加一的结果等于元素的个数。也即：(max - min + 1 == 元素个数)。那么这个子数组就是可整合数组。

没有重复元素可以使用 set 来做判断

找到这个数组中所有子数组的时间复杂度是 O(N2)，检验是否为可整合的为 O(1)。整体的时间复杂度为 O(N2)。

数组排序后相邻数的最大差值

一、题目

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

Leetcode：https://leetcode.cn/problems/maximum-gap/

二、思路

利用桶排序的思路，以下思路步骤

先获取到数组的最大值 max、最小值 min、以及数组的长度 N。用于确定桶的区间范围。接下来我们申请一个桶，桶的长度为 N+1。然后将数组中的元素填充到桶中。因为桶的个数为 N+1，所以必定有一个以上的空桶。

未排序正数数组中累加和为给定值的最长子数组长度

一、题目

给定一个数组 arr，该数组无序，但每个值均为正数，再给定一个正数 k，求 arr 的所有子数组中所有元素相加和为 k 的最长子数组长度

1
2

例如，arr = [1, 2, 1, 1, 1], k = 3
累加和为 3 的最长子数组为 [1, 1, 1], 所以结果返回 3

二、思路

数组中全部为正数，我们有如下几个变量，len 初始为 0，表示子数组的长度。left 初始为 0，表示子数组的左边界，right 初始为 0，表示子数组的右边界。 sum 初始值为 arr[0]，表示 arr[left ... right] 之间求和。

我们开始遍历，条件是 right < arr.size() 。

一、题目

给定一个无序数组 arr，其中元素可正、可负、可 0，求arr所有的子数组中累加和小于或等于k的最长子数组长度。

1

arr = [3, -2, -4, 0, 6]，k = -2，相加和小于或等于-2的最长子数组为[3, -2, -4, 0]，所以结果返回4。

• 如果要返回最长子数组的左右下标呢？

未排序数组中累加和为给定值的最长子数组系列问题

一、题目

未排序数组中累加和为给定值的最长子数组系列问题

1. 给定一个无序数组 arr，其中元素可正、可负、可 0。给定一个整数 k，求 arr 所有的子数组中累加和为 k 的最长子数组长度
2. 给定一个无序数组 arr，其中元素可正、可负、可 0。求 arr 所有的子数组中正数与负数个数相等的最长子数组长度
3. 给定一个无序数组 arr，其中元素只是 1 和 0。求 arr 所有子数组中 0 和 1 个数相等的最长子数组长度

自然数数组的排序

一、题目

给定一个长度为 N 的整形数组 arr，其中有 N 个互不相等的自然数 1 – N。请实现 arr 的排序，但是不要把下标0 – N−1 位置上的数通过直接赋值的方式替换成1 – N

二、思路

此题目比较简单。数组长度为 N，存储的元素是 1 – N，但是是乱序的。我们想要的结果是：

arr[i] = i+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
27
28
29
30
31
32

#include <vector>
#include <iostream>
#include <algorithm>

class Solution {
public:
    void sort_01(std::vector<int>& arr) {
        int i = 0;
        for (; i < arr.size();) {
            if (arr[i] == i+1) {
                i++;
            } else {
                std::swap(arr[i], arr[arr[i]-1]);
            }
        }
    }
};

void print_arr(const std::vector<int>& arr) {
    for (const auto x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    Solution s;
    std::vector<int> arr{2,1,4,5,3};
    s.sort_01(arr);
    print_arr(arr);
    return 0;
}

一、题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

Leetcode：https://leetcode.cn/problems/first-missing-positive/description/

二、分析

对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1, N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数。

我们的流程为：

矩阵的最短通路值

一、题目

用一个整形矩阵 matrix 表示一个网络，1 代表有路，0 代表无路，每一个位置只要不越界，都有上下左右 4 个方向，求从最左上角到最右下角的最短通路值

如下举例：

1
2
3
4
5
6
7

matrix = {
    {1, 0, 1, 1, 1},
    {1, 0, 1, 0, 1},
    {1, 1, 1, 0, 1},
    {0, 0, 0, 0, 1},
}
通路只有一条，由 12 个 1 构成，返回 12

二、思路

这道题目我们可以使用广度优先遍历这个矩阵。我们新创建一个矩阵 map 用来记录最短的通路值，用一个队列来记录广度搜索的坐标。

转圈打印矩阵

一、题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

例子：

1
2

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

Leetcode：https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/

需要排序的最短子数组的长度

一、题目

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

1
2
3

zui输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

Leetcode：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray