TODO:
- 左旋转字符串，余数的方法可以再看看
- 重做 二叉树中和为某一值的路径（就是一道典型递归)
剑指 Offer 58 - II. 左旋转字符串(简单)
确实简单，但是感觉这样做面试的时候会不Okay。
reverse函数功能是逆序（或反转），多用于字符串、数组、容器。头文件是#include <algorithm>。
reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数无返回值。
class Solution {
public:
string reverseLeftWords(string s, int n) {
if(s.empty() || n>s.size()) return s;
if(n == s.size()) { reverse(s.begin(),s.end()); return s;}
reverse(s.begin(),s.begin()+n);
reverse(s.begin()+n,s.end());
reverse(s.begin(),s.end());
return s;
}
};
然后又去看题解
感觉取余数的方法就很妙
class Solution {
public:
string reverseLeftWords(string s, int n) {
string res = "";
for(int i = n; i < n + s.size(); i++){
res += s[i%s.size()];
}
return res;
}
};
剑指 Offer 55 - I. 二叉树的深度(简单)
超级简单的两行递归。在于树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。
动画演示
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
剑指 Offer 34. 二叉树中和为某一值的路径(中等)
做了好久,大概四十多分钟？然而效果不怎么好，可能因为我是值传递？
image.png
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> pathSum(TreeNode* root, int target) {
if(root == nullptr)return{};
vector<int> temp;
dfs(root,target,temp);
return res;
}
void dfs(TreeNode* root, int target,vector<int> temp){
if(root == nullptr) return ;
else{
target = target-root->val;
temp.push_back(root->val);
}
if((root->left ==nullptr) && target ==0 && (root->right ==nullptr) ){
res.push_back(temp);
return ;
};
dfs(root->left, target,temp);
dfs(root->right,target,temp);
}
};
改良版:⭐
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int target) {
if(root == nullptr)return{};
dfs(root,target);
return res;
}
void dfs(TreeNode* root, int target){
if(root == nullptr) return ;
target = target-root->val;
path.push_back(root->val);
if((root->left ==nullptr) && target ==0 && (root->right ==nullptr) ){
res.push_back(path);
path.pop_back();//注意这个pop_back()；因为return会导致不能pop_back();从而影响回溯
return ;
};
dfs(root->left, target);
dfs(root->right,target);
path.pop_back();
}
};
