Skip to content

Commit b38805d

Browse files
committed
update 79
1 parent 6d03495 commit b38805d

2 files changed

Lines changed: 20 additions & 16 deletions

File tree

README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ LeetCode solution (C++ and Python)
2525
062 [Unique Paths](https://leetcode-cn.com/problems/unique-paths/ ) | [Python](https://github.com/codename1995/leetcodehub/blob/master/python/62_Unique_Paths.py) | 1. DP
2626
064 [Minimum Path Sum](https://leetcode-cn.com/problems/minimum-path-sum/) | [C++](https://github.com/codename1995/leetcodehub/blob/master/cpp/64_Minimum_Path_Sum/64_Minimum_Path_Sum.cpp) | 1. DP|
2727
070 [Climbing Stairs](https://leetcode-cn.com/problems/climbing-stairs/ ) | [C++](https://github.com/codename1995/leetcodehub/blob/master/cpp/70_Climbing_Stairs/70_Climbing_Stairs.cpp) | 1. DP|
28+
| 079 [Word Search](https://leetcode-cn.com/problems/word-search/) | [C++](https://github.com/codename1995/LeetCodeHub/blob/master/cpp/79_Word_Search/79_Word_Search.cpp) | 1. DFS+Backtracking
2829
091 [Decode Ways](https://leetcode-cn.com/problems/decode-ways/)| [C++](https://github.com/codename1995/leetcodehub/blob/master/cpp/91_Decode_Ways/91_Decode_Ways.cpp) | 1. DP
2930
105 [Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)| [C++](https://github.com/codename1995/LeetCodeHub/blob/master/cpp/105_Construct_Binary_Tree_from_Preorder_and_Inorder/105_Construct_Binary_Tree_from_Preorder_and_Inorder.cpp)| 1. 根据前序的第一个元素中序中确定根的位置,从而得到左右子树的元素数量,于是将前序和中序分为左右子树。再对左右子树递归此过程
3031
121 [Best Time To Buy And Sell Stock](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/submissions/ ) | [C++](https://github.com/codename1995/leetcodehub/blob/master/cpp/121_Best_Time_To_Buy_And_Sell_Stock/121_Best_Time_To_Buy_And_Sell_Stock.cpp) | 1. DP <br> 2. 遍历数组时维护最小价格,并判断价差是否产生更大收益|
@@ -63,7 +64,7 @@ Most of leetcode links are based on @yanring's [REPO](https://gist.github.com/ya
6364
| 09_02 用两个队列实现栈 | 225 [Implement Stack using Queue](https://leetcode-cn.com/problems/implement-stack-using-queues/) | [C++](https://github.com/codename1995/LeetCodeHub/blob/master/cpp/225_Implement_Stack_using_Queue/225_Implement_Stack_using_Queue.cpp) <u>**两个栈实现队列,一个队列实现栈!!!**</u> |
6465
| 10 斐波那契数列 |509 [Fibonacci Number](https://leetcode-cn.com/problems/fibonacci-number/ ) | [C++](https://github.com/codename1995/leetcodehub/blob/master/cpp/509_Fibonacci_Number/509_Fibonacci_Number.cpp) |
6566
| 10_02 青蛙跳台阶 | 70 [Climbing Stairs](https://leetcode-cn.com/problems/climbing-stairs/ ) | [C++](https://github.com/codename1995/leetcodehub/blob/master/cpp/70_Climbing_Stairs/70_Climbing_Stairs.cpp) |
66-
| 11 旋转数组中的最小数字 | 153 [Find Minimum in Rotated Sorted Array](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/) | [C++](https://github.com/codename1995/LeetCodeHub/blob/master/cpp/153_Find_Minimum_in_Rotated_Sorted_Array/153_Find_Minimum_in_Rotated_Sorted_Array.cpp) |
67+
| 11 旋转数组中的最小数字 | 153 [Find Minimum in Rotated Sorted Array](https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/) | [C++](https://github.com/codename1995/LeetCodeHub/blob/master/cpp/153_Find_Minimum_in_Rotated_Sorted_Array/153_Find_Minimum_in_Rotated_Sorted_Array.cpp) 核心是比较nums[m]与nums[r]|
6768
| 12 矩阵中的路径 | 79 [Word Search](https://leetcode-cn.com/problems/word-search/) | [C++](https://github.com/codename1995/LeetCodeHub/blob/master/cpp/79_Word_Search/79_Word_Search.cpp) |
6869
| 13 机器人的运动范围 | | 可参考1219 黄金矿工,也是二维矩阵dfs搜索的问题,而且更难一些 |
6970
| 14 剪绳子 | 343 [Interger Break](https://leetcode-cn.com/problems/integer-break/) | [C++](https://github.com/codename1995/LeetCodeHub/blob/master/cpp/343_Interger_Break/343_Interger_Break.cpp) |

cpp/79_Word_Search/79_Word_Search.cpp

Lines changed: 18 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,10 @@
1-
int dr[] = { -1,1,0,0 };
1+
#include<iostream>
2+
#include<cstring>
3+
#include<vector>
4+
5+
using namespace std;
6+
7+
int dr[] = { -1,1,0,0 };
28
int dc[] = { 0,0,-1,1 };
39
class Solution {
410
public:
@@ -9,22 +15,19 @@ class Solution {
915
bool dfs(int r, int c, int cnt) {
1016
if (r >= 0 && r < nr && c >= 0 && c < nc && cnt < w.size() && b[r][c] == w[cnt]) {
1117
if (cnt == w.size() - 1) return true;
12-
else
13-
{
14-
bool flag = false;
15-
char ch = b[r][c];
16-
b[r][c] = '#';
17-
for (int i = 0; i != 4; i++) {
18-
if (dfs(r + dr[i], c + dc[i], cnt + 1))
19-
{
20-
// cout<< r << c << endl;
21-
flag = true;
22-
break;
23-
}
18+
bool flag = false;
19+
char ch = b[r][c];
20+
b[r][c] = '#';
21+
for (int i = 0; i != 4; i++) {
22+
if (dfs(r + dr[i], c + dc[i], cnt + 1))
23+
{
24+
// cout<< r << c << endl;
25+
flag = true; // 不能直接返回true,必须在将visited数组复位之后返回结果。
26+
break;
2427
}
25-
b[r][c] = ch;
26-
return flag;
2728
}
29+
b[r][c] = ch;
30+
return flag;
2831
}
2932
return false;
3033
}

0 commit comments

Comments
 (0)