力扣_中级算法_树和图_4~6题_和_回溯算法_第1题
风吹夏天 2020-07-18
一位C++小白的力扣刷题_成长记录_welcome to visit ^_^
树和图_第4题：填充每个节点的下一个右侧节点指针
题目描述：
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
举例 （反正，我是没看懂它这个例子 害.....）
示例：
输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。提示：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
解题思路：搜索二叉树。这里又要用到递归。分两种情况来建立 next 关系。（详见代码）
学习心得：我先前想用一个队列，加一个vector容器来做，方法有点类似于昨天做的那个“二叉树的锯齿形
层次遍历”，但是有个地方一直有问题，用 VS2010 调试，还是没查出问题，后来去看题解，学习了前辈的
厉害的算法。二叉树，递归，嗯，两者紧密难分。
实现：（C++）
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if( root==NULL||root->left==NULL ) return root; //第二个条件“root->left==NULL”别忘了呦。因为本题的前提是“完美二叉树”嘛，left、right都可以
root->left->next=root->right; //细品
if( root->next!=NULL ) //这个是一环搭一环的“连”下去的。用草稿纸来画一画就一目了然了。
root->right->next=root->next->left;
connect( root->left ); //递归递归~这条语句和下面一条顺序不能换。因为next建立的关系是 从左至右 的
connect( root->right );
return root;
}
};
运行结果：
代码执行结果：
我的输入
[1,2,3,4,5,6,7]
我的答案
[1,#,2,3,#,4,5,6,7,#]
预期答案
[1,#,2,3,#,4,5,6,7,#]
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树和图_第5题：二叉搜索树中第K小的元素
题目描述：
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
举例：
示例 1:
输入: root = [3,1,4,null,2], k = 1 3 / 1 4 2 输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ 3 6
/ 2 4
/
1
输出: 3进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
解题思路：这道题做出来不难，用昨天学得的那个 迭代算法+一个队列+一个移动指针 来完成。
学习心得：这道题不难，但是想把 空间复杂度和时间复杂度 降低，还不时间松活事。我现在的目标就是
正确地把它做出来，其实我没用到那个，二叉搜索树的特征。虽然只打败了5%的人......嘻嘻。
实现：（C++）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
vector<int> vec; //容器，储存最后的数组
queue<TreeNode*> q;
TreeNode* fp; //定义一个“树”上的“移动”指针
q.push(root); //把“树根”放入队列
while( !q.empty() ) //只要队列里还有元素，继续循环
{
fp=q.front();
q.pop();
vec.push_back( fp->val );
if( fp->left ) //细品，作了图就好理解了
q.push(fp->left);
if( fp->right ) //细品+1
q.push(fp->right);
}
sort( vec.begin(),vec.end() ); //排序
return vec[k-1]; //排序后就好找了
}
};
运行结果：
我的输入
[3,1,4,null,2] 1
我的答案
1
预期答案
1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树和图_第6题：岛屿数量
题目描述：
给你一个由 ‘1‘（陆地）和 ‘0‘（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
举例：
示例 1:
输入: [ [‘1‘,‘1‘,‘1‘,‘1‘,‘0‘], [‘1‘,‘1‘,‘0‘,‘1‘,‘0‘], [‘1‘,‘1‘,‘0‘,‘0‘,‘0‘], [‘0‘,‘0‘,‘0‘,‘0‘,‘0‘] ] 输出: 1
示例 2:
输入: [ [‘1‘,‘1‘,‘0‘,‘0‘,‘0‘], [‘1‘,‘1‘,‘0‘,‘0‘,‘0‘], [‘0‘,‘0‘,‘1‘,‘0‘,‘0‘], [‘0‘,‘0‘,‘0‘,‘1‘,‘1‘] ] 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
解题思路：“标记法”，我把它叫做标记法。就是 把出现 “1” 的上下左右换成另外一种字符。下次检索到 “1”（但被更换了的）时，就跳过。这个要结合递归函数。
力扣题解里，我看评论，看到一个很贴切的 名字 ，叫做 “感染函数” ，我觉得很应景。
学习心得：做这道题，让我明白了 ：在递归函数中，其终止条件一般放在最开始，而且这个 终止条件 一定
要做好。这道题 思维易理解，但是其 细节 需要我们 细品。
实现：（C++）
class Solution {
public:
void infect( vector<vector<char>>& g,int i,int j )
{
if( i<0||j<0||i>=g.size()||j>=g[0].size()||g[i][j]!=‘1‘) return ; //最后一个 终止小条件“ g[i][j]!=‘1‘ ”可别忘了
g[i][j]=‘*‘; //换个符号，做个标记
infect( g,i-1,j ); //递归 左边
infect( g,i,j+1 ); //递归 上边
infect( g,i+1,j ); //递归 右边
infect( g,i,j-1 ); //递归 下边
return ;
}
int numIslands(vector<vector<char>>& grid) {
if( grid.size()==0 ) return 0;
int row=grid.size(),col=grid[0].size();
int i,j,res=0;
for( i=0;i<row;i++ )
for( j=0;j<col;j++ )
{
if( grid[i][j]==‘1‘ )
{
res++; //有一个‘1‘，其岛屿数就加1
infect( grid,i,j );
}
}
return res;
}
};
运行结果：
代码执行结果：
我的输入
[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
我的答案
1
预期答案
1
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
回溯算法_第1题： 电话号码的字母组合
题目描述：
注意:
你可以假设树中没有重复的元素。
举例：
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
解题思路： 我先想的的使用队列，但不好想。后来结合了 递归+哈希表 ，灵活运用下标，解决了。
学习心得：这道题把递归这个东西，再一次地体现得淋漓尽致。 哈希表的功能在这一道题也展现了
强大的功能。
实现：（C++）
class Solution {
public:
vector<string> vec;
string temp; //临时存储字符串
map<char,string> table= //注意是 char ！哈希表的构建，注意字符串有 “ ”包起哈。
{
{‘2‘,"abc"},
{‘3‘,"def"},
{‘4‘,"ghi"},
{‘5‘,"jkl"},
{‘6‘,"mno"},
{‘7‘,"pqrs"},
{‘8‘,"tuv"},
{‘9‘,"wxyz"}
};
void DFS(int index,string digits) //DFS函数，用于递归。DFS：深度优先搜索算法
{
if( index == digits.size() ) //当 digits的下标 和 digits的有效长度一样时，执行下面操作。（ 终止条件）
{
vec.push_back( temp );
return ;
}
int i;
for( i=0;i<table[ digits[index] ].size();i++ ) //举个栗子： table[ digits[0] ] = table[ ‘2‘ ] = "abc" 。（这里假设的digits[0] 为 ‘2’ ）
{
temp.push_back( table[ digits[index] ][i] );
DFS( index+1,digits ); //递归点在这里
temp.pop_back(); //字符串末尾弹出一个字符
}
//temp.pop_back(); //这句话是多余的，写出来，警醒自己。因为第一遍敲时，没注意到
return ;
}
vector<string> letterCombinations(string digits) {
if( digits.size()==0 ) return vec;
DFS( 0,digits );
return vec;
}
};
运行结果：
代码执行结果：
我的输入
"23"
我的答案
["ad","ae","af","bd","be","bf","cd","ce","cf"]
预期答案
["ad","ae","af","bd","be","bf","cd","ce","cf"]
