供暖器

题面

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\le m,n\le {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$ ，实现一个支持 '?$ 和 ${}^{\prime }{\ast }^{\prime }$ 的通配符匹配。

${}^{\prime }{?}^{\prime }$ 可以匹配任何单个字符。
${}^{\prime }{\ast }^{\prime }$ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

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

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\le i<a$ 以及 $0\le 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

示例1

example-2

示例2

最小好进制

题面

leetcode题目

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

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

example

输入："13"
输出："3"
解释：13 的 $3$ 进制是 $111$。