1. 基本思路

首先我们要决定要存储什么历史信息以及用什么数据结构来存储信息。然后是最重要的递推式，就是如从存储的历史信息中得到当前步的结果。最后我们需要考虑的就是起始条件的值。

题目

示例

解析

1. 令f[i][j]存储：从 (0, 0) 到 (i, j) 的路径个数
2. 而一步到 (i, j) 最多只有两个路径：从左面或者从上面
3. 那么，接下来判断，是否能从左面或者上面到 (i, j)，如果可以，那么 f(i, j) 加上左面或者上面的路径个数即可

代码

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

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    if(obstacleGrid[0][0])
        return 0;
    vector<vector<long long> > f(m, vector<long long>(n));
    f[0][0] = 1;
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++) {
            // if(i || j) f[i][j] = 0; （可有，可无，因为 ：f默认都是0）
            if(!obstacleGrid[i][j]) {
                if(i) f[i][j] += f[i - 1][j];
                if(j) f[i][j] += f[i][j - 1];
            }
        }
    return f[m - 1][n - 1];
}

疑问

f为int型， 为什么会报错 ？？？

Line 27: Char 65: runtime error: signed integer overflow: 1053165744 + 1579748616 cannot be represented in type 'int' (solution.cpp)

题目

解析

• DFS

  1. 首先判断是否为image是否为空，如果是，则返回image
  2. 然后，保存老的颜色值，即为 old，并判断 old 是否与 newColor 相同，如果是，则返回image
  3. 接着，对周围的这些点进行遍历，符合条件的，进入递归
  4. 最后，返回image

• BFS

  1. 首先判断是否为image是否为空，如果是，则返回image
  2. 然后，保存老的颜色值，即为 old，并判断 old 是否与 newColor 相同，如果是，则返回image
  3. 创建队列，类型为 pair<int, int> 类型，将image[sr][sc]入队；
  4. 对队列 q 进行遍历，将 q.front() 变为 newColor，然后，遍历周围的点，符合条件的入队
  5. 最后，返回image

代码

• DFS

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

vector<vector<int> > floodFill(vector<vector<int> >& image, int sr, int sc, int newColor) {
    if(image.empty() || image[0].empty())
        return image;
    int old = image[sr][sc];
    if(old == newColor)
        return image;
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    image[sr][sc] = newColor;
    for(int i = 0; i < 4; i++) {
        int nSr = sr + next[i][0], nSc = sc + next[i][1];
        if(nSr >= 0 && nSr < image.size() && nSc >= 0 && nSc < image[0].size() && image[nSr][nSc] == old)
            floodFill(image, nSr, nSc, newColor);
    }
    return image;
}

• BFS

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

vector<vector<int> > floodFill(vector<vector<int> >& image, int sr, int sc, int newColor) {
    if(image.empty() || image[0].empty())
        return image;
    int old = image[sr][sc];
    if(old == newColor) {
        return image;
    }
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    queue<pair<int, int> > q;
    q.push(pair<int, int>(sr, sc));
    while(q.size()) {
        pair<int, int> t = q.front();
        q.pop();
        image[t.first][t.second] = newColor;
        for(int i = 0; i < 4; i++) {
            int nx = t.first + next[i][0], ny = t.second + next[i][1];
            if(nx >= 0 && nx < image.size() && ny >= 0 && ny < image[0].size() && image[nx][ny] == old) {
                q.push(pair<int, int>(nx, ny));
            }
        }
    }
    return image;
}

题目

解析

同 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 保存：两行中，上面一行与下面相邻两个元素相加之和的最小数组
   1. 比如：以最后两行为例
   2. f 此时为 [4, 1, 8, 3]
      g 此时为 [0, 0, 0, 0]
   3. 然后，g 就更新为 [7, 6, 10, 0]
   4. f 也就更新为 g，即为： [7, 6, 10, 0]
   5. 依次类推
4. 最后，f[0]就是，第一个数，与下面最小的数相加的和，即为最短路径

• PS：

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

PS：

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

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

一、DFS和BFS的区别和优势

1. 说明：

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

2. 优劣势：

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

3. 区别

BFS：

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

DFS：

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