供暖器

题面

leetcode题目

冬季已经来临。你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋\(houses\)和供暖器\(heaters\)的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

example

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

随机翻转矩阵

题面

leetcode题目

给你一个 \(m \times n\) 的二元矩阵 \(matrix\) ，且所有值被初始化为 \(0\) 。请你设计一个算法，随机选取一个满足 \(matrix[i][j] == 0\) 的下标 \((i, j)\) ，并将它的值变为 \(1\) 。所有满足 \(matrix[i][j] == 0\) 的下标 \((i, j)\) 被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现 Solution 类：

• Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
  
• int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
  
• void reset() 将矩阵中所有的值重置为 0

example

输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip(); // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip(); // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip(); // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip(); // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

数据范围

• \(1 \leq m, n \leq 10^4\)
• 每次调用flip 时，矩阵中至少存在一个值为 \(0\) 的格子。
• 最多调用 \(1000\) 次 \(flip\) 和 \(reset\) 方法。

键值映射

题面

leetcode题目

实现一个 MapSum 类，支持两个方法，insert 和 sum：

MapSum() 初始化 MapSum 对象
void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

example

输入：

1
2

["MapSum", "insert", "sum", "insert", "sum"]  
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]  

输出：

1

[null, null, 3, null, 5]

解释：

1
2
3
4
5

MapSum mapSum = new MapSum();  
mapSum.insert("apple", 3);    
mapSum.sum("ap");           // return 3 (apple = 3)  
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

通配符匹配

题面

leetcode题目

给定一个字符串 \(s\) 和一个字符模式 \(p\) ，实现一个支持 '?$ 和 \('*'\) 的通配符匹配。

\('?'\) 可以匹配任何单个字符。
\('*'\) 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:
* \(s\) 可能为空，且只包含从 \(a-z\) 的小写字母。
* \(p\) 可能为空，且只包含从 \(a-z\) 的小写字母，以及字符 \(?\) 和 \(*\)。

example-1

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

example-2

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

K个逆序对数组

题面

leetcode题目

给出两个整数 \(n\) 和 \(k\)，找出所有包含从 \(1\) 到 \(n\) 的数字，且恰好拥有 \(k\) 个逆序对的不同的数组的个数。

逆序对的定义如下：对于数组的第\(i\)个和第\(j\)个元素，如果满\(i < j\)且 \(a[i] > a[j]\)，则其为一个逆序对；否则不是。

由于答案可能很大，只需要返回 答案 mod \(10^9 + 7\) 的值。

example-1

输入: \(n = 3\), \(k = 0\)
输出: \(1\)
解释:
只有数组 \([1,2,3]\) 包含了从1到3的整数并且正好拥有 \(0\) 个逆序对。

example-2

输入: \(n = 3\), \(k = 1\)
输出: \(2\)
解释:
数组 \([1,3,2]\) 和 \([2,1,3]\) 都有 \(1\) 个逆序对。

正则表达式匹配

题面

leetcode题目

给你一个字符串 \(s\) 和一个字符规律 \(p\)，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖整个字符串\(s\)的，而不是部分字符串。

example-1

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

example-2

输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

猜数字游戏

题面

leetcode题目

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls", 公牛）， 有多少位属于数字猜对了但是位置不对（称为 "Cows", 奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。 给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，\(x\) 是公牛个数， \(y\) 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

example

输入: secret = "1807", guess = "7810"
输出: "1A3B"
解释: 数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。

1
2
3

"1807"
  |
"7810"

直线上最多的点数

题面

leetcode题目

给定一个初始元素全部为 \(0\)，大小为 \(m\times n\) 的矩阵 \(M\) 以及在 \(M\) 上的一系列更新操作。

操作用二维数组表示，其中的每个操作用一个含有两个正整数 \(a\) 和 \(b\) 的数组表示，含义是将所有符合 \(0 \leq i < a\) 以及 \(0 \leq j < b\) 的元素 \(M[i][j]\) 的值都增加 \(1\)。

在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。

数据范围

• \(m\) 和 \(n\) 的范围是 \([1,40000]\)。
• \(a\) 的范围是 \([1,m]\)，\(b\) 的范围是 \([1,n]\)。
• 操作数目不超过 \(10000\)。

题解

总体思路

脑内想象一下把所有操作的范围画在原矩阵上，可以看出所有的操作都是以原点开始的一个个叠加的子矩阵。

由于每一次操作都是固定的行为\(+1\)，所以最大的整数一定出现在叠加次数最多的部分，也就是\(min(a_1, a_2, a_3,\cdots,a_n) \times min(b_1, b_2, b_3,\cdots,b_n)\)

!!! note 注意 最终结果不能超过原矩阵的大小，此corner case出现在没有任何操作输入的时候。

代码

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

#include <iostream>
#include <vector>
using namespace std;

#define _DEBUG
#define MAX 40000
int min(int x, int y)
{
    return x < y ? x : y;
}

class Solution
{
public:
    int maxCount(int m, int n, vector<vector<int>> &ops)
    {
        int minm, minn;
        minm = minn = MAX + 1;
        for (auto iter = ops.begin(); iter != ops.end(); iter++)
        {
            int a = (*iter)[0];
            int b = (*iter)[1];
            minm = min(minm, a);
            minn = min(minn, b);
        }

        int count = minm * minn;
        int max = m * n;
        return min(count, max);
    }
};
// for test
int main()
{
    Solution s;
    vector<vector<int>> test1{{2, 2}, {3, 3}};
    cout << s.maxCount(3, 3, test1) << endl;
    vector<vector<int>> test2{};
    cout << s.maxCount(3, 3, test2) << endl;

    return 0;
}

直线上最多的点数

题面

leetcode题目

给你一个数组 \(points\) ，其中 \(points[i] = [xi, yi]\) 表示 \(X-Y\) 平面上的一个点。求最多有多少个点在同一条直线上。

example-1

输入：\(points = [[1,1],[2,2],[3,3]]\)
输出：\(3\)

example-2

输入：\(points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]\)
输出：\(4\)

最小好进制

题面

leetcode题目

对于给定的整数 \(n\), 如果\(n\)的\(k\) （ \(k\geq 2\)）进制数的所有数位全为\(1\)，则称 \(k\) （ \(k\geq 2\)）是 n 的一个好进制。

以字符串的形式给出 \(n\), 以字符串的形式返回 \(n\) 的最小好进制。

example

输入："13"
输出："3"
解释：13 的 \(3\) 进制是 \(111\)。