题目

解析

同 733. 图像渲染

代码

DFS

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

void dfs(vector<vector<char>>& grid, int x, int y)
{
    int next[4][2] = { {0, 1}, {1, 0},  {0, -1}, {-1, 0} };
    grid[x][y] = '0';
    for(int i = 0; i < 4; i++) {
        int nx = x + next[i][0];
        int ny = y + next[i][1];
        if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == '1')
            dfs(grid, nx, ny);
    }

}

int numIslands(vector<vector<char>>& grid) {
    if(grid.empty() || grid[0].empty())
        return 0;
    int res = 0;
    int m = grid.size(), n = grid[0].size();
    for(int i = 0; i < m; i++) 
        for(int j = 0; j < n; j++) 
            if(grid[i][j] == '1') {
                res++;
                dfs(grid, i, j);
            }

    return res;
}

BFS

RE?

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

int numIslands(vector<vector<char>>& grid) {
    if(grid.empty() || grid[0].empty())
        return 0;
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    int landCount = 0;
    for(int i = 0; i < grid.size(); i++) {
        for(int j = 0; j < grid[0].size(); j++) {

            if(grid[i][j] == '1') {
                landCount++;
                queue<pair<int, int> > q;
                q.push(pair<int, int> (i, j));
                while(q.size()) {
                    pair<int, int> t = q.front();
                    q.pop();
                    grid[t.first][t.second] = '0';
                    for(int k = 0; k < 4; k++) {
                        int ni = t.first + next[k][0], nj = t.second + next[k][1];
                        if(ni >= 0 && ni < grid.size() && nj >= 0 && nj < grid[0].size() && grid[ni][nj] == '1')
                            q.push(pair<int, int> (ni, nj));
                    }
                }
            }
        }
    }
    return landCount;
}

题目

解析

类型：BFS

步骤：

1. 首先，把要求的数分为多个数相加，比如：10 = 1 + 9 = 1 + 4 + 4 + 1 = 1 + 1 + …… + 1
2. 但是，由于使用的循环，所以肯定是1 + 9先出现
3. 所以，依次类推，直到找到要求的数

• PS：
  1. BFS就是一层找一层，找到的肯定是最近的；
  2. 比如：4就是 0 + 4，只有一个数，设为第一层；同理，9 = 0 + 9，也只有一个数，同样为第一层
  3. 当遍历完0后，开始遍历第一层的数，那么找到的就是两个数的，即为第二层
  4. 依次类推

代码

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

int numSquares(int n) {
    queue<int> q;
    q.push(0);
    vector<int> dist(n + 1, INT_MAX);
    dist[0] = 0;
    while(q.size()) {
        int t = q.front();
        q.pop();
        if(t == n) {
            return dist[t];
        }
        for(int i = 1; i * i + t <= n; i++) {
            int j = i * i + t;
            if(dist[j] > dist[t] + 1) {
                dist[j] = dist[t] + 1;
                q.push(j);
            }
        }
    }
    return 0;
}

• AT 计划在计算机上运行的命令和程序。
• ATTRIB 显示或更改文件属性。
• BREAK 设置或清除扩展式 CTRL+C 检查。
• CACLS 显示或修改文件的访问控制列表(ACLs)。
• CALL 从另一个批处理程序调用这一个。
• CD 显示当前目录的名称或将其更改。
• CHCP 显示或设置活动代码页数。
• CHDIR 显示当前目录的名称或将其更改。
• CHKDSK 检查磁盘并显示状态报告。
• CHKNTFS 显示或修改启动时间磁盘检查。
• CLS 清除屏幕。
• CMD 打开另一个 Windows 命令解释程序窗口。
• COLOR 设置默认控制台前景和背景颜色。
• COMP 比较两个或两套文件的内容。
• COMPACT 显示或更改 NTFS 分区上文件的压缩。
• CONVERT 将 FAT 卷转换成 NTFS。您不能转换当前驱动器。
• COPY 将至少一个文件复制到另一个位置。
• DATE 显示或设置日期。
• DEL 删除至少一个文件。
• DIR 显示一个目录中的文件和子目录。
• DISKCOMP 比较两个软盘的内容。
• DISKCOPY 将一个软盘的内容复制到另一个软盘。
• DOSKEY 编辑命令行、调用 Windows 命令并创建宏。
• ECHO 显示消息，或将命令回显打开或关上。
• ENDLOCAL 结束批文件中环境更改的本地化。
• ERASE 删除至少一个文件。
• EXIT 退出 CMD.EXE 程序(命令解释程序)。
• FC 比较两个或两套文件，并显示不同处。
• FIND 在文件中搜索文字字符串。
• FINDSTR 在文件中搜索字符串。
• FOR 为一套文件中的每个文件运行一个指定的命令。
• FORMAT 格式化磁盘，以便跟 Windows 使用。
• FTYPE 显示或修改用于文件扩展名关联的文件类型。
• GOTO 将 Windows 命令解释程序指向批处理程序中某个标明的行1. 。
• GRAFTABL 启用 Windows 来以图像模式显示扩展字符集。
• HELP 提供 Windows 命令的帮助信息。
• IF 执行批处理程序中的条件性处理。
• LABEL 创建、更改或删除磁盘的卷标。
• MD 创建目录。
• MKDIR 创建目录。
• MODE 配置系统设备。
• MORE 一次显示一个结果屏幕。
• MOVE 将文件从一个目录移到另一个目录。
• PATH 显示或设置可执行文件的搜索路径。
• PAUSE 暂停批文件的处理并显示消息。
• POPD 还原PUSHD保存的当前目录的上一个值。
• PRINT 打印文本文件。
• PROMPT 更改Windows命令提示符。
• PUSHD 保存当前目录，然后对其进行更改。
• RD 删除目录。
• RECOVER 从有问题的磁盘恢复可读信息。
• REM 记录批文件或CONFIG.SYS中的注释。
• REN 重命名文件。
• RENAME 重命名文件。
• REPLACE 替换文件。
• RMDIR 删除目录
• SET 显示、设置或删除Windows环境变量。
• SETLOCAL 开始批文件中环境更改的本地化。
• SHIFT 更换批文件中可替换参数的位置。
• SORT 对输入进行分类。
• START 启动另一个窗口来运行指定的程序或命令。
• SUBST 将路径跟一个驱动器号关联。
• TIME 显示或设置系统时间。
• TITLE 设置CMD.EXE会话的窗口标题。
• TREE 以图形模式显示驱动器或路径的目录结构。
• TYPE 显示文本文件的内容。
• VER 显示Windows版本。
• VERIFY 告诉Windows 是否验证文件是否已正确写入磁盘。
• VOL 显示磁盘卷标和序列号。
• XCOPY 复制文件和目录树。
• appwiz.cpl 添加删除程序
• control userpasswords2 用户帐户设置
• cleanmgr 垃圾整理
• CMD 命令提示符可以当作是Windows的一个附件
• Ping，Convert这些不能在图形环境下使用的功能要借助它来完成。
• cmd jview察看Java虚拟机版本。
• command.com 调用的则是系统内置的NTVDM，一个DOS虚拟机。它完全是一个类似VirtualPC的虚拟环境，和系统本身联系不大。当我们在命令提示符下运行 DOS程序时，实际上也是自动转移到NTVDM虚拟机下，和CMD本身没什么关系。
• calc 启动计算器
• chkdsk.exe Chkdsk磁盘检查
• compmgmt.msc 计算机管理
• conf 启动netmeeting
• control userpasswords2 User Account 权限设置
• devmgmt.msc 设备管理器
• diskmgmt.msc 磁盘管理实用程序
• dfrg.msc 磁盘碎片整理程序
• drwtsn32 系统医生
• dvdplay 启动Media Player
• dxdiag DirectX Diagnostic Tool
• gpedit.msc 组策略编辑器
• gpupdate /target:computer /force 强制刷新组策略
• eventvwr.exe 事件查看器
• explorer 打开资源管理器
• logoff 注销命令
• lusrmgr.msc 本机用户和组
• msinfo32 系统信息
• msconfig 系统配置实用程序
• net start (servicename) 启动该服务
• net stop (servicename) 停止该服务
• notepad 打开记事本
• nusrmgr.cpl 同control userpasswords，打开用户帐户控制面板
• Nslookup IP地址侦测器
• oobe/msoobe /a 检查系统是否激活
• perfmon.msc 计算机性能监测程序
• progman 程序管理器
• regedit 注册表编辑器
• regedt32 注册表编辑器
• regsvr32 /u *.dll 停止dll文件运行
• route print 查看路由表
• rononce -p 15秒关机
• rsop.msc 组策略结果集
• rundll32.exe rundll32.exe %Systemroot%System32shimgvw.dll,ImageView_Fullscreen 启动一个空白的Windows图片和传真查看器
• secpol.msc 本地安全策略
• services.msc 本地服务设置
• sfc /scannow 启动系统文件检查器
• sndrec32 录音机
• taskmgr 任务管理器（适用于2000／xp／2003）
• tsshutdn 60秒倒计时关机命令
• winchat XP自带局域网聊天
• winmsd 系统信息
• winver 显示About Windows窗口
• wupdmgr Windows Update
• mspaint:打开画图
• calc:打开计算器
• winver:检查window版本
• mstsc:远程桌面连接
• write:写字板
• mem.exe:显示内存的使用情况
• notepad:打开记事本

一、DFS和BFS的区别和优势

说明：

1. BFS（宽度有限搜索）
2. DFS（深度有限搜索）

优劣势：

1. BFS   需要把下一层所有的方案都存下来，需要很大的空间，空间是指数级别的；
   DFS   需要的空间只与路径的长度有关系。
2. BFS优势：有可以寻找最小的优势 （最小性）
3. DFS：一条路走到黑
4. DFS劣势：
   1. 空间复杂度和深度成正比
   2. C++的限制：栈空间默认只有4M
   3. DFS搜索时，系统栈分到栈空间里面的，当搜索层数太多时，系统栈就会爆掉，就是RE，大概搜索 10万 层时就会RE
   4. 所以说，如果层数深的话，尽量用BFS，避免爆栈

区别

BFS：

1. 空间是指数级别的，比较大！！！
2. 不会有爆栈的风险
3. 能搜索：最短，最小……

DFS：

1. 空间和深度成正比，比较小！！！
2. 有爆栈的风险，比如树的深度最坏可能有100000层，此时会爆栈
3. 不能搜：最短，最小……

题目

解析

1. 解析图：
2. 首先，如果是Null，那么，便返回0
3. 然后，看左子树深度和右子树的深度
4. 接着，如果有左子树或者右子树的深度为0，那么返回另一个深度+1
5. 最后，如果左右子树的深度都不为0，那么返回最小值+1

代码

1
2
3
4
5
6
7
8
9

int minDepth(TreeNode* root) {
    if(!root)
        return 0;
    int leftNum = minDepth(root -> left);
    int rightNum = minDepth(root -> right);
    if(!leftNum || !rightNum)
        return (leftNum + rightNum + 1);
    return min(leftNum, rightNum) + 1;
}

题目

解析

1. 以第k位为例
2. 假设所有数字的第k位为：1 0 1 0
3. 汉明距离与 0 1的个数有关
4. 第k位汉明距离总和为 $num_0 * num_1$

【其中】：
1. $num_0$：数字0的个数
2. $num_1$：数字1的个数

代码

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

int totalHammingDistance(vector<int>& nums) {
    int res = 0;
    for(int i = 0; i < 31; i++) {
        int ones = 0;
        for(auto x : nums) {
            if(x >> i & 1)
                ones++;
        }
        res += ones * (nums.size() - ones);
    }
    return res;
}

题目

解析

1. 与&只要有一个为0，则与的所有数为0
2. 对每个 位 分别判断是否有0
3. 首先判断m的第i位是否为0
4. 然后判断第i位为0，且$>$m的最小的数是否大于n，如果大于，则这些都为1

代码

1
2
3
4
5
6
7
8
9
10

int rangeBitwiseAnd(int m, int n) {
    int res = 0;
    for(int i = 0; (1ll << i) <= m; i++) {
        if(m >> i & 1) {
            if(((m & ~((1ll << i) - 1)) + (1ll << i)) > n)
                res += (1 << i);
        }
    }
    return res;
}

题目描述

解析

1. 利用异或运算的性质
   1. x ^ x = 0
   2. x ^ 0 = x
2. 对所有数字异或运算
   1. $x_1$ ^ $x_2$ ^ …… ^ $x_n$ = 只出现过一次的数
3. 程序

   1 2 3 4 5 6

   int singleNumber(vector<int>& nums) { int res = 0; for(auto x : nums) res ^= x; return res; }

题目

解析

1. 所有元素只有两个出现一次，其余的出现两次，那么对所有的元素求异或和，那么最后求出来的肯定是出现过一次元素的异或和
2. 接着，因为这两个元素不同，所以，这两个数字的异或和肯定有一位为1，假设第k位为1
3. 那么将第k位为1的分为一堆，其余的分为另一堆
4. 接下来的问题就是 列表中只有一个出现一次的数字，其余的出现两次这个问题了

【释】：这两堆肯定是第k位为1的为一堆，该堆中只有一个出现过一次，其余的数出现两次，最后，对这两堆分别求异或和就可以求出来了

代码1

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

vector<int> singleNumber(vector<int>& nums) {
    int s = 0;
    for(auto x : nums)
        s ^= x;
    int k = 0;
    while( !(s >> k & 1) )
        k++;
    int s1 = 0, s2 = 0;
    for(auto x : nums)
        if(x >> k & 1)
            s1 ^= x;
        else
            s2 ^= x;
    return vector<int>({s1, s2});
}

代码2

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

vector<int> singleNumber(vector<int>& nums) {
    int s = 0;
    for(auto x : nums)
        s ^= x;
    int k = 0;
    while( !(s >> k & 1) )
        k++;
    int s1 = 0;
    for(auto x : nums)
        if(x >> k & 1)
            s1 ^= x;
    return vector<int>({s1, s ^ s2});
}

【释】：因为 $s_1$ ^ $s_2$ = s，那么 s ^ $s_1$ = $s_2$，具体性质详见 位运算的知识点以及常用技巧

init

1

$ hexo init [folder]

folder: 文件夹名字，或者说是博客名字。

新建一个网站。如果没有设置 folder ，Hexo 默认在目前的文件夹建立网站。

new

1

$ hexo new [layout] <title>

新建一篇文章。如果没有设置 layout 的话，默认使用 _config.yml 中的 default_layout 参数代替。如果标题包含空格的话，请使用引号括起来。

1

$ hexo new "post title with whitespace"

默认情况下，Hexo 会使用文章的标题来决定文章文件的路径。对于独立页面来说，Hexo 会创建一个以标题为名字的目录，并在目录中放置一个 index.md 文件。你可以使用 --path 参数来覆盖上述行为、自行决定文件的目录：

1

hexo new page --path about/me "About me"

以上命令会创建一个 source/about/me.md 文件，同时 Front Matter 中的 title 为 "About me"

注意！title 是必须指定的！如果你这么做并不能达到你的目的：

1

hexo new page --path about/me

此时 Hexo 会创建 source/_posts/about/me.md，同时 me.md 的 Front Matter 中的 title 为 "page"。这是因为在上述命令中，hexo-cli 将 page 视为指定文章的标题、并采用默认的 layout。

generate

1

$ hexo generate

生成静态文件。

该命令可以简写为

1

$ hexo g

publish

1

$ hexo publish [layout] <filename>

发表草稿。

server

1

$ hexo server

启动服务器。默认情况下，访问网址为： http://localhost:4000/或 http://127.0.0.1:4000/。

deploy

1

$ hexo deploy

部署网站。

该命令可以简写为：

1

$ hexo d

render

1

$ hexo render <file1> [file2] ...

渲染文件。

migrate

1

$ hexo migrate <type>

从其他博客系统 迁移内容。

clean

1

$ hexo clean

清除缓存文件 (db.json) 和已生成的静态文件 (public)。

在某些情况（尤其是更换主题后），如果发现您对站点的更改无论如何也不生效，您可能需要运行该命令。

list

1

$ hexo list <type>

列出网站资料。

version

1

$ hexo version

显示 Hexo 版本。

选项

安全模式

1

$ hexo --safe

在安全模式下，不会载入插件和脚本。当您在安装新插件遭遇问题时，可以尝试以安全模式重新执行。

调试模式

1

$ hexo --debug

在终端中显示调试信息并记录到 debug.log。当您碰到问题时，可以尝试用调试模式重新执行一次，并 提交调试信息到 GitHub。

简洁模式

1

$ hexo --silent

隐藏终端信息。

自定义配置文件的路径

1
2
3
4
5

# 使用 custom.yml 代替默认的 _config.yml
$ hexo server --config custom.yml

# 使用 custom.yml 和 custom2.json，其中 custom2.json 优先级更高
$ hexo generate --config custom.yml,custom2.json,custom3.yml

自定义配置文件的路径，指定这个参数后将不再使用默认的 _config.yml。
你可以使用一个 YAML 或 JSON 文件的路径，也可以使用逗号分隔（无空格）的多个 YAML 或 JSON 文件的路径。例如：

1
2
3
4
5

# 使用 custom.yml 代替默认的 _config.yml
$ hexo server --config custom.yml

# 使用 custom.yml, custom2.json 和 custom3.yml，其中 custom3.yml 优先级最高，其次是 custom2.json
$ hexo generate --config custom.yml,custom2.json,custom3.yml

当你指定了多个配置文件以后，Hexo 会按顺序将这部分配置文件合并成一个 _multiconfig.yml。如果遇到重复的配置，排在后面的文件的配置会覆盖排在前面的文件的配置。这个原则适用于任意数量、任意深度的 YAML 和 JSON 文件。

显示草稿

1

$ hexo --draft

显示 source/_drafts 文件夹中的草稿文章。

自定义 CWD

1

$ hexo --cwd /path/to/cwd

自定义当前工作目录（Current working directory）的路径。