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