数组：其他

睡不醒的鲤鱼 2021-10-03 每日一题 LeetCode

# 0004. 寻找两个正序数组的中位数 (opens new window)

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

1
2
3

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

1
2
3

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

解析

本题可以抽象为：给定两个数组 A、B，如何找到从小到大排列的第 $k$ 个数？

只要让 $k$ 取值 $(n + m) / 2$ ，就可以得到中位数。令 $k_1 = k / 2$ ， $k_2 = k - k / 2$ ，则：

当 $A[k_1] < B[k_2]$ 时，去掉 $A[\le{k_1}]$ 的元素；
当 $A[k_1] > B[k_2]$ 时，去掉 $B[\le{k_2}]$ 的元素；
当 $A[k_1] = B[k_2]$ 时，去掉 $A[\le{k_1}]$ 或 $B[\le{k_2}]$ 的元素。

综上，可以将其转化为一个递归的问题，每次 $k$ 的规模都减少一半，而 $k$ 取值 $(n + m) / 2$ ，因此时间复杂度为 $O(log(m+n))$ 。

代码

# 0036. 有效的数独 (opens new window)

题目

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

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

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

解析

使用一个布尔数组记录每个数字是否出现，分别判断行、列和 3x3 宫内即可。

代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool ex[9];

        // 判断行
        for (int i = 0; i < 9; i++) {
            memset(ex, 0, sizeof(ex));
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int t = board[i][j] - '1';
                if (ex[t]) return false;
                ex[t] = true;
            }
        }

        // 判断列
        for (int i = 0; i < 9; i++) {
            memset(ex, 0, sizeof(ex));
            for (int j = 0; j < 9; j++) {
                if (board[j][i] == '.') continue;
                int t = board[j][i] - '1';
                if (ex[t]) return false;
                ex[t] = true;
            }
        }

        // 判断 3x3 宫内
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                memset(ex, 0, sizeof(ex));
                for (int x = 0; x < 3; x++) {
                    for (int y = 0; y < 3; y++) {
                        if (board[i + x][j + y] == '.') continue;
                        int t = board[i + x][j + y] - '1';
                        if (ex[t]) return false;
                        ex[t] = true;
                    }
                }
            }
        }

        return true;
    }
};

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
33
34
35
36
37
38
39
40
41
42
43
44
45

# 0089. 格雷编码 (opens new window)

题目

n 位格雷码序列是一个由 2n 个整数组成的序列，其中：

每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现不超过一次
每对相邻整数的二进制表示恰好一位不同，且
第一个和最后一个整数的二进制表示恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列。

解析

递推构造，n 位的格雷码序列可以划分成两部分，由 n - 1 位的格雷码镜像构成，只需要在最后一位分别补上 0 和 1 即可。

代码

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        while (n--) {
            for (int i = ans.size() - 1; i >= 0; i--) {
                ans[i] <<= 1;
                ans.push_back(ans[i] + 1);
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 0118. 杨辉三角 (opens new window)

题目

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

解析

每个数字由上一行的当前列数字和上一行的左侧数字相加得到，模拟这个过程就可以得到每一行的结果了。

代码

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        for (int i = 0; i < numRows; i++) {
            vector<int> cur(i + 1, 1);
            for (int j = 1; j < i; j++) {
                cur[j] = ans[i - 1][j - 1] + ans[i - 1][j];
            }
            ans.push_back(cur);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 0119. 杨辉三角 II (opens new window)

题目

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

解析

由 0118. 杨辉三角可知，每个数字只和前一行的数字有关，所以可以通过滚动数组来对结果迭代更新，这样可以把空间复杂度优化到 $O(n)$ 。

代码

class Solution {
public:
    vector<int> getRow(int n) {
        vector<vector<int>> ans(2, vector<int>(n + 1, 1));
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                ans[i % 2][j] = ans[(i - 1) % 2][j - 1] + ans[(i - 1) % 2][j];
            }
        }
        return ans[n % 2];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

# 0128. 最长连续序列 (opens new window)

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

解析

使用一个哈希表来记录数组中的数字，然后来遍历哈希表，找到每个连续片段的起点，计算长度即可。

代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int ans = 0;
        for (int num: st) {
            if (!st.count(num - 1)) {
                int x = num + 1;
                while (st.count(x)) x++;
                ans = max(ans, x - num);
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 0134. 加油站 (opens new window)

题目

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

解析

枚举起始点，只要有剩余油量，就不断向后行驶，直到到达起始点。

同时可以进行如下优化：

假设可以从 i 行驶到 j，但不能到达 j+1，那么从 i 到 j 之间任意点都不能到达 j+1。

代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int i = 0; i < n; ) {
            int j = 0, left = 0;
            while (j < n) {
                int k = (i + j) % n;
                left += gas[k] - cost[k];
                if (left < 0) break;
                j++;
            }
            if (j == n) return i;
            i = i + j + 1;
        }
        return -1;
    }
};

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

数组：数学定理二分查找：基础

鲤鱼笔记

Choose mode

数组：其他

数组：其他

# 0004. 寻找两个正序数组的中位数 (opens new window)

# 0036. 有效的数独 (opens new window)

# 0089. 格雷编码 (opens new window)

# 0118. 杨辉三角 (opens new window)

# 0119. 杨辉三角 II (opens new window)

# 0128. 最长连续序列 (opens new window)

# 0134. 加油站 (opens new window)