ARTS第二十周（2020年2月3日~9日）

2020-02-03

Algorithm

编号	难度	题目	我的解答	执行用时	内存消耗	排名
106	中等	从中序与后序遍历序列构造二叉树	200203-1.cpp	12 ms	17 MB	97.54%
107	简单	二叉树的层次遍历 II	200203-1.cpp	24 ms	14.1 MB	8.47%
108	简单	将有序数组转换为二叉搜索树	200203-1.cpp	20 ms	21.3 MB	74.94%
109	中等	有序链表转换二叉搜索树	200204-1.cpp	36 ms	24.7 MB	59.19%
110	简单	平衡二叉树	200204-1.cpp	16 ms	17.7 MB	73.15%
111	简单	二叉树的最小深度	200204-1.cpp	24 ms	19.8 MB	13.75%
112	简单	路径总和	200205-1.cpp	16 ms	20.1 MB	62.22%
113	中等	路径总和 II	200205-1.cpp	24 ms	33.3 MB	43.71%
114	中等	二叉树展开为链表	200205-1.cpp	4 ms	9.9 MB	96.03%
115	困难	不同的子序列	200206-1.cpp	8 ms	9.4 MB	85.41%
116	中等	填充每个节点的下一个右侧节点指针	200206-1.cpp	12 ms	19.3 MB	99.58%
117	中等	填充每个节点的下一个右侧节点指针 II	200206-1.cpp	24 ms	20.4 MB	55.31%
118	简单	杨辉三角	200207-1.cpp	0 ms	8.8 MB	100.00%
119	简单	杨辉三角 II	200207-1.cpp	0 ms	9.1 MB	100.00%
120	中等	三角形最小路径和	200207-1.cpp	4 ms	10.7 MB	96.41%
121	简单	买卖股票的最佳时机	200207-1.cpp	1068 ms	9.6 MB	16.18%
122	简单	买卖股票的最佳时机 II	200208-1.cpp	12 ms	9.8 MB	25.46%
123	困难	买卖股票的最佳时机 III	200208-3.cpp	1872 ms	9.8 MB	5.04%
124	困难	二叉树中的最大路径和	200208-1.cpp	920 ms	64.4 MB	5.10%
125	简单	验证回文串	200208-1.cpp	4 ms	9.6 MB	98.81%
126	困难	单词接龙 II	200209-1.cpp	1816 ms	52.5 MB	10.04%
127	中等	单词接龙	200209-1.cpp	1592 ms	23.4 MB	11.60%
129	中等	求根到叶子节点数字之和	200209-1.cpp	4 ms	12.8 MB	84.55%
130	中等	被围绕的区域	200209-1.cpp	40 ms	14.2 MB	47.82%

Review

1. 如何写git commit的注释信息

文章链接：How to Write a Git Commit Message

从技术上说，git commit允许任意写注释信息，但为了便于后续浏览和查询，最好能够遵循一定的惯例。这篇文章给出了几条建议及其原因：

标题和正文之间空一行（Separate subject from body with a blank line）
标题不应超过50字符（Limit the subject line to 50 characters）
标题首字母大写（Capitalize the subject line）
标题末尾不带句号（Do not end the subject line with a period）
标题使用祈使句型（Use the imperative mood in the subject line）
正文做手工折行使每行不超过72字符（Wrap the body at 72 characters）
正文解释详细的原因及方法（Use the body to explain what and why vs. how）

Tip

1. 在Linux下扩容存储

文章链接：Linux extend file system after resize disk volume

存储硬件设备扩大容量，经常发生在磁盘阵列、虚拟机、云端设备上。由于业务的需要，这些设备扩容往往能够在线完成。当硬件扩容后，在Linux系统中，需要运行相应的命令，让操作系统能够正确匹配扩容后的新容量。这篇文章给出了相应的操作步骤及命令，主要包括：

1
2
3


sudo growpart /dev/sdb 1   # 扩展分区信息
sudo xfs_growfs /backup1/  # 扩展xfs文件系统
sudo resize2fs /dev/sdb1   # 扩展ext文件系统

2. Bash中的变量扩展

参考链接：bash的man信息（“Expansion”部分）

示例代码：

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


WORD="abcdefg"
echo ${WORD}        # abcdefg          - 显示WORD当前值
echo ${WORD:-xyz}   # xyz              - 当WORD为空时，使用缺省值
echo ${WORD:+xyz}   # abcdefg          - 当WORD不为空时，使用缺省值
echo ${WORD:3}      # defg             - 截取3开始的子串
echo ${WORD:3:2}    # de               - 截取3开始、长度为2的子串
echo ${!W*}         # WINDOWPATH WORD  - 列出所有W开头的变量名
echo ${#WORD}       # 7                - 返回变量值的长度
echo ${WORD#ab}     # cdefg            - 去掉前缀
echo ${WORD%fg}     # abcde            - 去掉后缀
echo ${WORD/cd/xyz} # abxyzefg         - 替换
echo ${WORD^}       # Abcdefg          - 首字母大写
echo ${WORD^^}      # ABCDEFG          - 全部字母大写
echo ${WORD^^[CDG]} # abCDefG          - 匹配字母大写
WORD="ABCDEFG"
echo ${WORD,}       # aBCDEFG          - 首字母小写
echo ${WORD,,}      # abcdefg          - 全部字母小写
echo ${WORD,,[CDG]} # ABcdEFg          - 匹配字母小写

3. Linux下查看无线网卡信息

参考链接：8 Linux Commands: To Find Out Wireless Network Speed, Signal Strength And Other Information

包括如下命令：

1
2
3
4
5
6
7
8


lspci                                          # 列出所有pci设备
lspci | egrep -i --color 'wifi|wlan|wireless'  # 列出无线网卡
lspci -vvvs 03:00.0                            # 列出某个设备的详细信息
lshw -C network                                # 列出网络设备
iwconfig wlan0                                 # 列出无线网卡信息
nmcli connection show                          # 列出网络连接
cat /proc/net/wireless                         # 无线网络相关信息
wavemon                                        # 文本界面的监控工具

1. C++中的json类型实现

分享链接：

这是一个封装比较完美的C++类库，基于C++11（或更高版本标准）支持，只需要对头文件进行#include，即可非常便利地使用json类型。该封装类型可以如同原生内置类型（first class data type）一样使用，如：

 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


#include <nlohmann/json.hpp>
using json = nlohmann::json;

void foo() {
    json j;
    j["pi"] = 3.141;
    j["happy"] = true;
    j["name"] = "Niels";
    j["nothing"] = nullptr;
    j["answer"]["everything"] = 42;
    j["list"] = { 1, 0, 2 };
    j["object"] = { {"currency", "USD"}, {"value", 42.99} };

    json j2 = {
      {"pi", 3.141},
      {"happy", true},
      {"name", "Niels"},
      {"nothing", nullptr},
      {"answer", {
        {"everything", 42}
      }},
      {"list", {1, 0, 2}},
      {"object", {
        {"currency", "USD"},
        {"value", 42.99}
      }}
    };
}

若编译器支持C++17新标准，该类库甚至支持如下的使用字符串后缀的初始化：

1
2
3
4
5
6
7
8


json j = "{ \"happy\": true, \"pi\": 3.141 }"_json;

auto j2 = R"(
  {
    "happy": true,
    "pi": 3.141
  }
)"_json;

2. C++中的编译期正则表达式解析

分享项目：https://github.com/hanickadot/compile-time-regular-expressions

这是一个基于C++新标准实现的编译器做正则表达式解析的类库。其运算速度甚至能够明显优于各种被广泛使用的正则表达式库，很值得学习。

其C++17语法如下：

1
2
3
4
5


static constexpr auto pattern = ctll::fixed_string{ "h.*" };

constexpr auto match(std::string_view sv) noexcept {
	return ctre::match<pattern>(sv);
}

其C++20语法如下：

1
2
3


constexpr auto match(std::string_view sv) noexcept {
	return ctre::match<"h.*">(sv);
}

正则表达式的初始化，不再消耗运行时，而是在编译过程中直接完成，同时也完成相应的正则语法判断。