【探索初级算法】LeetCode数组篇（6 - 11题）

旧城等待， 2022-04-01 06:27 186阅读 0赞

# 两个数组的交集 II #

给定两个数组，编写一个函数来计算它们的交集。

**示例 1:**

输入: nums1 = [1,2,2,1], nums2 = [2,2]
    输出: [2,2]

**示例 2:**

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出: [4,9]

**说明：**

*  输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
 *  我们可以不考虑输出结果的顺序。

**进阶:**

*  如果给定的数组已经排好序呢？你将如何优化你的算法？
 *  如果 *nums1 *的大小比 *nums2 *小很多，哪种方法更优？
 *  如果 *nums2 *的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

**解题思路：**

先用Arrays.sort()方法对两个数组进行排序，之后遍历这两个数组，这里遍历的话，我们使用while循环，条件以最小的数组长度为准。对比 nums2\[0\] 和 nums1\[0\] 的值，如果大于其中 i++ ，反之小于 j++，最后等于那这个就是其中的交集，我们添加到集合中存储起来，同时记得 i++ 和 j++ 进入下个数组下标。if 判断的时候可以交换 num2 和 num1的位置，同时记得切换 i 和 j ，这是不影响的。

**解题代码：**

class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            Arrays.sort(nums1);
            Arrays.sort(nums2);
    
            List<Integer> tmp = new ArrayList<>();
    
            int i = 0;
            int j = 0;
            while (i < nums1.length && j < nums2.length) {
                if (nums2[j] > nums1[i]) {
                    i++;
                } else if (nums2[j] < nums1[i]) {
                    j++;
                } else {
                    tmp.add(nums1[i]);
                    i++;
                    j++;
                }
            }
    
            int[] result = new int[tmp.size()];
            for (int k = 0; k < result.length; k++) {
                result[k] = tmp.get(k);
            }
            return result;
        }
    }

条条大路通罗马，欢迎评论区留下你的解题思路及代码。

# 加一 #

给定一个由**整数**组成的**非空**数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

**示例 1:**

输入: [1,2,3]
    输出: [1,2,4]
    解释: 输入数组表示数字 123。

**示例 2:**

输入: [4,3,2,1]
    输出: [4,3,2,2]
    解释: 输入数组表示数字 4321。

**解题思路：**

这题有点类似之前我在leetcode做过的一道题目，就是个位加一，然后判断是否会变成十位数，如果变成十位数，则向前进一位，然后之前的数在加上1，在判断是否要进一位以此类推。

如何判断是否相加变成了个位，我们可以用相加之后的值除以10

相加为十位数的数，怎么得到个位，我们可以通过取模的方式。

**解题代码：**

class Solution {
        public int[] plusOne(int[] digits) {
            int carry = 1;
    
            for (int i = digits.length - 1; i >= 0; i--) {
                if (carry == 0) {
                    return digits;
                }
                int tmp = digits[i] + carry;
                carry = tmp / 10;
                digits[i] = tmp % 10;
            }
    
            if (carry != 0) {
                int[] result = new int[digits.length + 1];
                result[0] = 1;
                return result;
            }
    
            return digits;
        }
    
    }

条条大路通罗马，欢迎评论区留下你的解题思路及代码。

# 移动零 #

给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。

**示例:**

输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]

**说明**:

1.  必须在原数组上操作，不能拷贝额外的数组。
2.  尽量减少操作次数。

**解题思路：**

代码不难，不过想进一步优化，就陷入苦思冥想当中了。

根据题目解读出需求，只要将0放到数组后面，那么就是说，遍历数据时，遇到0，那么就将后续的数字往前面挪移一位，然后覆盖掉0这个位置，同时在数组的最后位置设置为0，一直遍历完该数组，那么就可以得到需要输出的数组了。

**解题代码：**

class Solution {
        public void moveZeroes(int[] nums) {
            int index = 0;
            for (int i = 0; i < nums.length - index; ) {
                if (nums[i] == 0) {
                    move(i, nums);
                    index++;
                }else{
                    i++;
                }
            }
    
        }
    
        private void move(int index, int[] nums) {
            for (int j = index; j < nums.length - 1; j++) {
                nums[j] = nums[j + 1];
            }
            nums[nums.length - 1] = 0;
        }
    }

条条大路通罗马，欢迎评论区留下你的解题思路及代码。

# 两数之和 #

给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那 **两个** 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**示例:**

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

**解题思路：**

用 target 的数组减去数组中的数字，差值是否等于数组剩余的数字，因为只对应一种答案，如果等于，所以直接返回它俩的位置就可以了。

**解题代码：**

class Solution {
        public int[] twoSum(int[] nums, int target) {
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (target - nums[i] == nums[j]) {
                        return new int[]{i, j};
                    }
                }
            }
            return null;
        }
    }

条条大路通罗马，欢迎评论区留下你的解题思路及代码。

# 有效的数独 #

判断一个 9x9 的数独是否有效。只需要**根据以下规则**，验证已经填入的数字是否有效即可。

1.  数字 `1-9` 在每一行只能出现一次。
2.  数字 `1-9` 在每一列只能出现一次。
3.  数字 `1-9` 在每一个以粗实线分隔的 `3x3` 宫内只能出现一次。

![250px-Sudoku-by-L2G-20050714.svg.png][]

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 `'.'` 表示。

**示例 1:**

输入:
    [
      ["5","3",".",".","7",".",".",".","."],
      ["6",".",".","1","9","5",".",".","."],
      [".","9","8",".",".",".",".","6","."],
      ["8",".",".",".","6",".",".",".","3"],
      ["4",".",".","8",".","3",".",".","1"],
      ["7",".",".",".","2",".",".",".","6"],
      [".","6",".",".",".",".","2","8","."],
      [".",".",".","4","1","9",".",".","5"],
      [".",".",".",".","8",".",".","7","9"]
    ]
    输出: true

**示例 2:**

输入:
    [
      ["8","3",".",".","7",".",".",".","."],
      ["6",".",".","1","9","5",".",".","."],
      [".","9","8",".",".",".",".","6","."],
      ["8",".",".",".","6",".",".",".","3"],
      ["4",".",".","8",".","3",".",".","1"],
      ["7",".",".",".","2",".",".",".","6"],
      [".","6",".",".",".",".","2","8","."],
      [".",".",".","4","1","9",".",".","5"],
      [".",".",".",".","8",".",".","7","9"]
    ]
    输出: false
    解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
         但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

**说明:**

*  一个有效的数独（部分已被填充）不一定是可解的。
 *  只需要根据以上规则，验证已经填入的数字是否有效即可。
 *  给定数独序列只包含数字 `1-9` 和字符 `'.'` 。
 *  给定数独永远是 `9x9` 形式的。

**解题思路：**

先从第一个要求来，排除每一行每一列中没有重复的数字，首先利用双重循环可以遍历二维数组的每一个数字，那么我们可以再通过 HashSet 集合来进行排重，它有一个 contains（） 方法，作用为检查集合中是否已经有数字了。如果有我们之间返回 false，整个方法结束，如果没有那么就把这个数添加到 set 集合中。这里可以用两个 set 同时进行，注意 index 和 i 的位置，不要弄混了。

第二个要求，每个小的九宫格中没有重复的数组，我们可以把大的九宫格看做是九个小的九宫格，每次循环得到每个小宫格的左上角第一块，那么就利用一个双重循环遍历，每次循环之后 +3 ，跳到下个小宫格的。

到这里可以得到 ![20190104181418156.png][] 这样的一组数字，就是每个小九宫格的第一块位置我们得到了。那么接下来只要在这个双重循环里面分别遍历这九个小的九宫格就可以了，同样是利用双重循环和 HashSet 集合，可以参考第一个要求的解题思路。

**解题代码：**

class Solution {
        public boolean isValidSudoku(char[][] board) {
            for (int i = 0; i < board.length; i++) {
                if (!isRowAndColumn(i, board)) {
                    return false;
                }
            }
            if(!isNineGongGe(board)){
                return false;
            }
            return true;
        }
    
        private boolean isRowAndColumn(int index, char[][] board) {
            HashSet isRowHashSet = new HashSet();
            HashSet isColumnHashSet = new HashSet();
            for (int i = 0; i < board.length; i++) {
                if (isRowHashSet.contains(board[index][i]) ||
                        isColumnHashSet.contains(board[i][index])) {
                    return false;
                } else {
                    if (board[index][i] != '.') {
                        isRowHashSet.add(board[index][i]);
                    }
    
                    if (board[i][index] != '.') {
                        isColumnHashSet.add(board[i][index]);
                    }
                }
            }
            return true;
        }
    
        private boolean isNineGongGe(char[][] board) {
            for (int i = 0; i < board.length; i += 3) {
                for (int j = 0; j < board.length; j += 3) {
                    HashSet hashSet = new HashSet();
                    for (int n = i; n < i + 3; n++) {
                        for (int m = j; m < j + 3; m++) {
                            if(hashSet.contains(board[n][m])){
                                return false;
                            }else{
                                if (board[n][m] != '.') {
                                    hashSet.add(board[n][m]);
                                }
                            }
                        }
                    }
                }
            }
            return true;
        }
    }

条条大路通罗马，欢迎评论区留下你的解题思路及代码。

# 旋转图像 #

给定一个 *n *× *n* 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

**说明：**

你必须在**[原地][Link 1]**旋转图像，这意味着你需要直接修改输入的二维矩阵。**请不要**使用另一个矩阵来旋转图像。

**示例 1:**

给定 matrix = 
    [
      [1,2,3],
      [4,5,6],
      [7,8,9]
    ],
    
    原地旋转输入矩阵，使其变为:
    [
      [7,4,1],
      [8,5,2],
      [9,6,3]
    ]

**示例 2:**

给定 matrix =
    [
      [ 5, 1, 9,11],
      [ 2, 4, 8,10],
      [13, 3, 6, 7],
      [15,14,12,16]
    ], 
    
    原地旋转输入矩阵，使其变为:
    [
      [15,13, 2, 5],
      [14, 3, 4, 1],
      [12, 6, 8, 9],
      [16, 7,10,11]
    ]

**解题思路：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrcDE2MDM2NDU3NTY_size_16_color_FFFFFF_t_70][]

**解题代码：**

class Solution {
        public void rotate(int[][] matrix) {
            int n = matrix.length;
    
            for (int i = 0; i < n / 2; ++i) {
                for (int j = i; j < n - 1 - i; ++j) {
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[n - 1 - j][i];
                    matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                    matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                    matrix[j][n - 1 - i] = tmp;
                }
            }
        }
    }

条条大路通罗马，欢迎评论区留下你的解题思路及代码。

[250px-Sudoku-by-L2G-20050714.svg.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png
[20190104181418156.png]: /images/20220401/f2c086cff83f45adabf97c414e0a5655.png
[Link 1]: https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrcDE2MDM2NDU3NTY_size_16_color_FFFFFF_t_70]: /images/20220401/bc5afa2111b14feba3a50fc45f3e78bf.png