LeetCode题解——数组(二)

你的名字 2023-02-24 08:30 129阅读 0赞

### 文章目录 ###

*   *  优美的排列 II
     *   *  解法
     *  数组的度
     *   *  解法
     *  托普利茨矩阵
     *   *  解法
     *  数组嵌套
     *   *  解法
     *  最多能完成排序的块
     *   *  解法
         *   *  推荐阅读

## 优美的排列 II ##

给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：
    
    ① 如果这个数组是 [a1, a2, a3, ... , an] ，那么数组 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数；.
    
    ② 如果存在多种答案，你只需实现并返回其中任意一种.
    
    示例 1:
    
    输入: n = 3, k = 1
    输出: [1, 2, 3]
    解释: [1, 2, 3] 包含 3 个范围在 1-3 的不同整数， 并且 [1, 1] 中有且仅有 1 个不同整数 : 1
     
    
    示例 2:
    
    输入: n = 3, k = 2
    输出: [1, 3, 2]
    解释: [1, 3, 2] 包含 3 个范围在 1-3 的不同整数， 并且 [2, 1] 中有且仅有 2 个不同整数: 1 和 2
     
    
    提示:
    
     n 和 k 满足条件 1 <= k < n <= 104.

### 解法 ###

让前 k+1 个元素构建出 k 个不相同的差值，序列为：1 k+1 2 k 3 k-1 … k/2 k/2+1.

class Solution {
        
        public int[] constructArray(int n, int k) {
        
            int[] res = new int[n];
            res[0] = 1;
            for (int i = 1, interval = k; i <= k; i++, interval--) {
        
                res[i] = i % 2 == 1 ? res[i - 1] + interval : res[i - 1] - interval;
            }
            for (int i = k + 1; i < n; i++) {
        
                res[i] = i + 1;
            }
            return res;
        }
    }

## 数组的度 ##

给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1:
    
    输入: [1, 2, 2, 3, 1]
    输出: 2
    解释: 
    输入数组的度是2，因为元素1和2的出现频数最大，均为2.
    连续子数组里面拥有相同度的有如下所示:
    [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
    最短连续子数组[2, 2]的长度为2，所以返回2.
    示例 2:
    
    输入: [1,2,2,3,1,4,2]
    输出: 6
    注意:
    
    nums.length 在1到50,000区间范围内。
    nums[i] 是一个在0到49,999范围内的整数。

### 解法 ###

class Solution {
        
        public int findShortestSubArray(int[] nums) {
        
            Map<Integer, Integer> numsCount = new HashMap<>();
            Map<Integer, Integer> numsLastIndex = new HashMap<>();
            Map<Integer, Integer> numsFirstIndex = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
        
                int num = nums[i];
                numsCount.put(num, numsCount.getOrDefault(num, 0) + 1);
                numsLastIndex.put(num, i);
                if (!numsFirstIndex.containsKey(num)) {
        
                    numsFirstIndex.put(num, i);
                }
            }
            int maxCount = 0;
            for (int num : nums) {
        
                maxCount = Math.max(maxCount, numsCount.get(num));
            }
            int result = nums.length;
            for (int num : nums) {
        
                int count = numsCount.get(num);
                if (count != maxCount) {
        
                    continue;
                }
                result = Math.min(result, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
            }
            return result;
        }
    }

## 托普利茨矩阵 ##

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。

给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。

示例 1:
    
    输入: 
    matrix = [
      [1,2,3,4],
      [5,1,2,3],
      [9,5,1,2]
    ]
    输出: True
    解释:
    在上述矩阵中, 其对角线为:
    "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
    各条对角线上的所有元素均相同, 因此答案是True。
    示例 2:
    
    输入:
    matrix = [
      [1,2],
      [2,2]
    ]
    输出: False
    解释: 
    对角线"[1, 2]"上的元素不同。
    说明:
    
     matrix 是一个包含整数的二维数组。
    matrix 的行数和列数均在 [1, 20]范围内。
    matrix[i][j] 包含的整数在 [0, 99]范围内。
    进阶:
    
    如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？
    如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？

### 解法 ###

class Solution {
        
        public boolean isToeplitzMatrix(int[][] matrix) {
        
            for (int i = 0; i < matrix[0].length; i++) {
        
                if (!check(matrix, matrix[0][i], 0, i)) {
        
                    return false;
                }
            }
            for (int i = 1; i < matrix.length; i++) {
        
                if (!check(matrix, matrix[i][0], i, 0)) {
        
                    return false;
                }
            }
            return true;
        }
        private boolean check(int[][] matrix, int expectValue, int row, int col) {
        
            if (row >= matrix.length || col >= matrix[0].length) {
        
                return true;
            }
            if (matrix[row][col] != expectValue) {
        
                return false;
            }
            return check(matrix, expectValue, row + 1, col + 1);
        }
    }

![format_png][]

## 数组嵌套 ##

索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }且遵守以下的规则。
    
    假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元素。
    
    示例 1:
    
    输入: A = [5,4,0,3,1,6,2]
    输出: 4
    解释: 
    A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
    
    其中一种最长的 S[K]:
    S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
     
    
    提示：
    
    N是[1, 20,000]之间的整数。
    A中不含有重复的元素。
    A中的元素大小在[0, N-1]之间。

### 解法 ###

class Solution {
        
        public int arrayNesting(int[] nums) {
        
            int max = 0;
            for (int i = 0; i < nums.length; i++) {
        
                int count = 0;
                for (int j = i; nums[j] != -1; ) {
        
                    count++;
                    int t = nums[j];
                    nums[j] = -1;
                    j = t;
                }
                max = Math.max(count, max);
            }
            return max;
        }
    }

## 最多能完成排序的块 ##

数组arr是\[0, 1, …, arr.length - 1\]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:
    
    输入: arr = [4,3,2,1,0]
    输出: 1
    解释:
    将数组分成2块或者更多块，都无法得到所需的结果。
    例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
    示例 2:
    
    输入: arr = [1,0,2,3,4]
    输出: 4
    解释:
    我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
    然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
    注意:
    
    arr 的长度在 [1, 10] 之间。
    arr[i]是 [0, 1, ..., arr.length - 1]的一种排列。

### 解法 ###

class Solution {
        
        public int maxChunksToSorted(int[] arr) {
        
            if (arr == null) {
        
                return 0;
            }
            int result = 0;
            int right = arr[0];
            for (int i = 0; i < arr.length; i++) {
        
                right = Math.max(right, arr[i]);
                if (right == i) {
        
                    result++;
                }
            }
            return result;
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png 1][]

[format_png]: /images/20230209/c7f20d8692df498c9bb13b1a98f9d1c4.png
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png 1]: /images/20230209/95c502acb45444ff8b6ffc3503f0724c.png