题目

解析

同 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;
}

题目

解析

1. 最小路径就是和相邻的两行有关系
2. 由于，从上往下有些麻烦，所以，从下往上
3. 首先，把最后一行的数据，存入 vector<int> f 中，并且 vector<int> g 保存：两行中，上面一行与下面相邻两个元素相加之和的最小数组
4. 比如：以最后两行为例
5. f 此时为 [4, 1, 8, 3]
   g 此时为 [0, 0, 0, 0]
6. 然后，g 就更新为 [7, 6, 10, 0]
7. f 也就更新为 g，即为： [7, 6, 10, 0]
8. 依次类推
9. 最后，f[0]就是，第一个数，与下面最小的数相加的和，即为最短路径

Note

1. 如果不懂，就自己调试一下吧
2. 这里是动态规划，更新的是g和f（首先更新g，接着将g赋值给f）
3. 其中f，总是为最后一行最小数的数组：
   1. 比如：一开始为 [4, 1, 8, 3] ，后来状态转移为：[7, 6, 10, 0]
   2. 那么 [7, 6, 10, 0] 可以看成最后一行（替换后面两行，依次类推）

代码

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

int minimumTotal(vector<vector<int> > &triangle)
{
   int n = triangle.size();
   vector<int> f(triangle[n - 1].begin(), triangle[n - 1].end()), g(n);
   for(int i = n - 2; i >= 0; i--) {
      for(int j = 0; j <= i; j++) {
            g[j] = min(f[j], f[j + 1]) + triangle[i][j];
      }
      f = g;
   }
   return f[0];
}

简化

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

int minimumTotal(vector<vector<int>>& triangle) {
   int n = triangle.size();
   vector<int> f(triangle[n - 1].begin(), triangle[n - 1].end());

   for(int i = n - 2; i >= 0; i--) {
         for(int j = 0; j <= i; j++) {
            f[j] = min(f[j], f[j + 1]) + triangle[i][j];
         }

   }
   return f[0];
}

Note

1. 相比于上面的代码，下面的代码删除了 g
2. 原因：因为 f[j] 改变，对 f[j + 1] 并没有影响，所以就不需要 g 了。

题目

解析

类型：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$，具体性质详见 位运算的知识点以及常用技巧