8.30 leetcode刷题（1）
栈和队列：
20 有效的括号
class Solution {
public:
bool isValid(string s) {
if(s.empty())
return true;
int n=s.size();
stack<char> st;
for(int i=0;i<n;i++){
if(s[i]=='('||s[i]=='['||s[i]=='{')
st.push(s[i]);
else{
if(st.empty())
return false;
char el=st.top();
if( s[i]==')' && el != '(' || s[i]==']' && el!='[' || s[i]=='}' && el!='{')
return false;
st.pop();
}
}
return st.empty();
}
};
思路：
利用栈去做匹配，定义好哪种情况入栈，哪种情况出栈。最后还要判断一下栈是否为空
bug经验：
[Error] lvalue required as left operand of assignment
可能是把== 写成=
练习：150 71
144 前序遍历 94 145
递归
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(root){
ret.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
return ret;
}
private:
vector<int> ret;
};
循环
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<pair<TreeNode *,int>> st;
vector<int> ret;
if(root!=nullptr){
st.push(make_pair(root->right,0));
st.push(make_pair(root->left,0));
st.push(make_pair(root,1));
}
while(!st.empty()){
int flag=st.top().second;
TreeNode *node=st.top().first;
st.pop();
if(flag==1){
ret.push_back(node->val);
}
else{
if(node!=nullptr){
st.push(make_pair(node->right,0));
st.push(make_pair(node->left,0));
st.push(make_pair(node,1));
}
}
}
return ret;
}
};
递归转循环的实现思路：
- 利用循环不变式的思想（往往与递归是2种不同的逻辑）
- 利用栈这个数据结构（代码会比递归复杂，且逻辑从代码层面上看也不再清晰）
循环思路：
利用了栈这个数据结构，因为栈是先入后出，为了保障循环符合递归的顺序，我们需要保障出栈的顺序符合我们的需求（根左右），所以入栈顺序是右左根，其中我设计了一个int变量来标记是记录数值还是递归操作
练习：341
队列：
应用：广度优先搜索 ，广度优先搜索解决的是遍历和最短路径问题。
而最短路径问题之所以能被bfs解决，是因为bfs在遍历的过程中可以记录层数，而层数恰好对应了遍历元素的路径长度。即利用了bfs中的层数这个信息可以解决最短路径问题，不利用层数信息的话则只可以解决遍历问题。
102 二叉树的层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ret;
if(root==nullptr)
return ret;
queue<pair<TreeNode *,int>> qu;
qu.push(make_pair(root,0));
while(!qu.empty()){
int level=qu.front().second;
TreeNode *node=qu.front().first;
qu.pop();
if(ret.size()==level)
ret.push_back(vector<int>());
ret[level].push_back(node->val);
if(node->left)
qu.push(make_pair(node->left,level+1));
if(node->right)
qu.push(make_pair(node->right,level+1));
}
return ret;
}
};
思路：
层序遍历其实就是树结构上的广度优先搜索，需要借用队列（广度优先搜索的模板需要记住）这个数据结构。本题还要求分出层次来，所以我考虑了pair结构，用TreeNode *来提取必要的信息，用int来标记层数，第一层用0而不是1来标记，是因为容器的第一个元素下标是0，用0的话方便后续操作
练习：103 199
279 完全平方数
class Solution {
public:
int numSquares(int n) {
vector<bool> used(n+1,false);
queue<pair<int,int>> qu;
qu.push(make_pair(n,0));
while(!qu.empty()){
int num=qu.front().first;
int step=qu.front().second;
qu.pop();
for(int i=1;i*i<=num;i++){
int dig=num-i*i;
if(dig==0)
return step+1;
if(used[dig]==false){
used[dig]=true;
qu.push(make_pair(dig,step+1));
}
}
}
return -1;
}
};
思路：
利用广度优先搜索的思想把本题由一个分数数字的题目转换成了求最短路径的题目。
思路是这样的，首先把符合要求的平方数选出来，然后让当前数字减去平方数，求得差值，然后再对这些差值进行处理，其实本质上是一种遍历，遍历的层数就相当于原始数字由几个平方数组成的个数，第一次找到0时，对应的层数就是个数。
练习：127 126
优先队列：堆
cpp利用priority_queue这个容器来实现
prioriry_queue<T,vector<T>,cmp> pq
pq.top()
pq.push()
pq.pop()
struct cmp{
bool operator ()(T t1,T t2){
//不交换位置
return true;
//swap the locations
return false;
}
}
cmp是自定义的比较方法，我通常用struct结构体来实现。需要记住返回值是bool，返回真时，2个元素不交换位置，返回false时2个元素交换位置。
347 前k个高频元素
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> ret;
int n=nums.size();
if(n==0)
return ret;
unordered_map<int,int> rec;
for(int i=0;i<n;i++){
if(rec.find(nums[i])==rec.end())
rec.insert(make_pair(nums[i],1));
else
rec[nums[i]]++;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
for(auto i=rec.begin();i!=rec.end();i++){
pq.push(*i);
if(pq.size()==k+1)
pq.pop();
}
while(!pq.empty()){
ret.push_back(pq.top().first);
pq.pop();
}
return ret;
}
private:
struct cmp{
bool operator ()(pair<int,int> a,pair<int,int> b){
return a.second>=b.second;
}
};
};
练习：23
二叉树和递归：
因为二叉树的定义本身就是递归定义的，所以二叉树的许多操作用递归去解决
104 二叉树的最大深度
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root){
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return 1+max(left,right);
}
else
return 0;
}
};
111 二叉树的最小深度
class Solution {
public:
int minDepth(TreeNode* root) {
if(root){
int left=minDepth(root->left);
int right=minDepth(root->right);
if(left==0)
return 1+right;
if(right==0)
return 1+left;
return 1+min(right,left);
}
else
return 0;
}
};
思路：
本题的难点在于度为1的节点的处理，如果仍按节点是否为空去处理，那么结果会错误，因为程序会把度为1的节点看作叶子节点而返回错误答案。
因此需要让程序去忽略高度为0的节点。
具体的解决方案：
首先判断当前节点是否为空，为空返回0.
若不为空，递归求解左右子树。获取左子树和右子树的最小高度（设计递归的思想之一就是假想已经实现了函数功能，通过f(n-1)和操作el(n)最终求得f(n)）
根据左子树和右子树的最小高度来判断以当前节点为根节点的树的高度（注意处理子树高度为0的情况，为0说明子树为空树，只有1者为零说明当前节点的度为1，需进行处理）
226 翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root){
TreeNode *left=invertTree(root->left);
TreeNode *right=invertTree(root->right);
root->right=left;
root->left=right;
}
return root;
}
};
练习：100 101 222 110
112 路径总和
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(root){
if(root->left==nullptr && root->right==nullptr)
return root->val==sum;
else{
bool left=hasPathSum(root->left,sum-root->val);
bool right=hasPathSum(root->right,sum-root->val);
return left||right;
}
}
else
return false;
}
};
思路：
利用递归思想，递归思路的设计原则就是假设已经实现了递归函数的功能，操作f(n-1)和操作el(n) f(n)
首先判断根节点是否为空，若为空则说明是非法输入，返回false
根节点不为空，则可以开始考虑设计递归，找到递推关系，比较明显的一个关系就是 递归2棵子树，若有1棵能够凑成 sum-root->val，则说明为真。
最后要设计递归终止条件，最终的终止条件是当前节点是叶节点，且值与sum相等（递归终止条件要放在递归函数开头处）
练习：404
257 二叉树的所有路径
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ret;
if(root==nullptr)
return ret;
if(root->left==nullptr && root->right==nullptr)
{
ret.push_back(to_string(root->val));
return ret;
}
if(root->left){
vector<string> leftS=binaryTreePaths(root->left);
int n1=leftS.size();
for(int j=0;j<n1;j++)
ret.push_back(to_string(root->val)+"->"+leftS[j]);
}
if(root->right){
vector<string> rightS=binaryTreePaths(root->right);
int n2=rightS.size();
for(int j=0;j<n2;j++)
ret.push_back(to_string(root->val)+"->"+rightS[j]);
}
return ret;
}
};
思路：
首先设计递归思路。
递归思路是假设已经实现了路径功能，对于树来讲，就是递归2棵子树，然后根据根节点来求解需求的结果，很明显，把根节点的值拼接上去就可以。
主逻辑梳理清楚后，接下来就要设计终止条件，终止条件就是一旦根节点是叶子节点，直接放入容器返回即可
另外，根节点是空节点也明显是非法条件，需要做出处理。
练习：113 129
437 路径总和3
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if(root==nullptr)
return 0;
int ret=getPath(root,sum);
int leftS=pathSum(root->left,sum);
int rightS=pathSum(root->right,sum);
return ret+leftS+rightS;
}
private:
int getPath(TreeNode *root,int sum){
int ret=0;
if(root==nullptr)
return ret;
if(root->val==sum)
ret++;
int leftS=getPath(root->left,sum-root->val);
int rightS=getPath(root->right,sum-root->val);
return ret+leftS+rightS;
}
};
思路：
因为不要求从根节点开始，也不要求在叶节点结束。我们的思路是先设计一个算法getPath求出从某节点node处出发，遍历所有路径，看能找出几条符合要求的路径；然后再通过getPath和递归，实现主算法
getPath的设计：
主逻辑
先假设我们已经实现了该函数，通过求取2棵子树的符合条件的路径，以及判断根节点本身是否符合，从而汇总出从root节点出发的所有符合条件的路径个数。
迭代
2棵子树自身实现了迭代
终止条件
因为不要求在叶节点结束，那么只要当前节点为空时，才会终止递归
非法条件
无
pathSum的设计：
主逻辑
先假设递归函数已经实现了功能，那么递归求取2棵子树的所有路径，再利用getPath求取从根节点开始的所有路径，汇总即所得
二分搜索树：
235 二分搜索树的最近公共祖先
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr || root==p || root==q)
return root;
if(root->val < p->val && root->val < q->val)
return lowestCommonAncestor(root->right,p,q);
if(root->val > p->val && root->val > q->val)
return lowestCommonAncestor(root->left,p,q);
return root;
}
};
思路：
递归，判断逻辑是若pq都在左侧，去考虑左子树的情况；都在右侧，就去考虑右子树的情况；一边一个，那么当前节点就是
练习 98 450 108 230 236
236
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr||root==p||root==q)
return root;
TreeNode *left=lowestCommonAncestor(root->left,p,q);
TreeNode *right=lowestCommonAncestor(root->right,p,q);
if(left==nullptr)
return right;
if(right==nullptr)
return left;
return root;
}
};
