迫于从某厂离职，每个月白嫖的300CNY良心云额度不复存在，考虑到之前的博客维护都比较的古老，趁机也做一波升级。

在这次维护之前，博客的本体存放在我的NAS上，并通过FRP暴露出去外接一个良心云cdn用来分发，也顺便做了备案，这一套之前跑起来没啥问题，就是每次 generate 之后还需要手动 copy 产物到某个特定的文件夹，非常的不现代化。 由于整体的环境都在本地，所以其实可维护性很低。

更新的思路大概如下:

• 对博客项目进行梳理，清理掉不规范的配置
• 博客的本体部分由 github actions 生成并推送到 Azure Static Web App
• 对境内而言，还是走CDN分发，分发回源地址由之前的 FRP 暴露的地址改为 Azure Static Web App 生成的地址
• 境外部分，dnspod支持分线路解析，直接通过 Custom domain 功能分发即可

GitHub actions 写起来也是挺简单的，改了改模板就能直接用。

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
46
47
48
49
50
51
52

name: Azure Static Web Apps CI/CD

on:
  push:
    branches:
      - main

jobs:
  build_and_deploy_job:
    runs-on: ubuntu-latest
    name: Build and Deploy Job
    steps:
      - name: Setup NodeJS
        uses: actions/setup-node@v3
        with:
          node-version: 19
      - uses: actions/checkout@v2
        with:
          submodules: true
      - name: Install pandoc
        run: sudo apt-get update -y && sudo apt-get install pandoc -y
      - name: Install hexo-cli
        run: npm install hexo-cli -g
      - name: Npm install
        run: npm install
      - name: Hexo generate
        run: hexo g
      - name: Deploy
        id: builddeploy
        uses: Azure/static-web-apps-deploy@v1
        with:
          azure_static_web_apps_api_token: ${{ secrets.AZURE_STATIC_WEB_APPS_API_TOKEN_GREEN_STONE_0480A0D00 }}
          repo_token: ${{ secrets.GITHUB_TOKEN }} # Used for Github integrations (i.e. PR comments)
          action: "upload"
          ###### Repository/Build Configurations - These values can be configured to match your app requirements. ######
          # For more information regarding Static Web App workflow configurations, please visit: https://aka.ms/swaworkflowconfig
          app_location: "/public" # App source code path
          api_location: "" # Api source code path - optional
          output_location: "" # Built app content directory - optional
          ###### End of Repository/Build Configurations ######

#  close_pull_request_job:
#    if: github.event_name == 'pull_request' && github.event.action == 'closed'
#    runs-on: ubuntu-latest
#    name: Close Pull Request Job
#    steps:
#      - name: Close Pull Request
#        id: closepullrequest
#        uses: Azure/static-web-apps-deploy@v1
#        with:
#          azure_static_web_apps_api_token: ${{ secrets.AZURE_STATIC_WEB_APPS_API_TOKEN_GREEN_STONE_0480A0D00 }}
#          action: "close"

这次迁移遗留几个问题待解决:

• 图库目前是在良心云 COS 上，需要迁走
• 境外的图片访问仍需要路由回国内
• 考虑到科学上网已经是基本技能，境内的加速是否存在必要？

供暖器

题面

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\)