剑指 Offer 38. 字符串的排列（中等）
还需要再做做。注意这里用了一个set是为了处理有相同字母的情况的。
比如,aab,如果不用set,那aab,第一个a放在第一位和aab,第二个a放在第一位,就会是两个结果。
class Solution {
public:
vector<string> permutation(string s) {
dfs(s,0);
return res;
}
private:
vector<string> res;
void dfs(string s, int x){
if(x == s.size()-1){
res.push_back(s);
return ;
}
set<char> hi;
for(int i = x; i< s.size();i++){
if(hi.count(s[i])){continue;}
hi.insert(s[i]);
swap(s[i],s[x]);
dfs(s,x+1);
swap(s[i],s[x]);
}
}
};
剑指 Offer 07. 重建二叉树
不大会，还需要再做做
1. 递归
这个方法比较简单，可以先建立个中序遍历的hash表，方便找到前序遍历每个节点在中序中的对应位置。递归的中止条件就是前序遍历递归结束。对于前序遍历，我们可以找到中序遍历数组中，[left,root] [root,right]结点的范围。
class Solution {
private:
unordered_map<int,int> ids;
public:
TreeNode* tree(vector<int>& preorder, vector<int>&inorder, int preleft, int preright, int inleft, int inright){
if(preleft > preright) return nullptr;
int root_val = preorder[preleft];//in中顺序
TreeNode* t = new TreeNode(root_val);
int size_tree = ids[root_val] - inleft;
t->left = tree(preorder, inorder, preleft+1, preleft+size_tree,inleft,ids[root_val]-1);
t->right = tree(preorder,inorder,preleft+size_tree+1,preright,ids[root_val]+1,inright);
return t;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int i =0;
for(auto it:inorder){
ids[it] = i++;
}
return tree(preorder,inorder,0,preorder.size()-1,0,preorder.size()-1);
}
};
2. 迭代
这个方法，模拟了好一会。似懂非懂，但是好巧妙哦。
前序： 左 中 右
中序： 中 左 右
对于前序而言：
[...,a,b,c,d,...]
b 只有两种可能，①a的左孩子，②a或者a父节点的右孩子
如何确定b是左孩子还是右孩子呢，遍历前序的时候，构建树。(对照着中序值不一样，相当于都是左边的），当遇到中序和前序某结点一样时说明来了个右孩子。出栈对比，前序出栈的顺序就是....
what.jpg
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if(preorder.size() <= 0) return nullptr;
TreeNode* node = new TreeNode(preorder[0]);
stack<TreeNode*> s;
s.push(node);
int in_index = 0;
for(int i =1; i<preorder.size(); i++){
TreeNode* root = s.top();
int preval = preorder[i];
if(root->val != inorder[in_index]){
root->left = new TreeNode(preval);
s.push(root->left);
}else{
while(!s.empty() && s.top()->val == inorder[in_index]){
root = s.top();
s.pop();
in_index++;
}
root->right = new TreeNode(preval);
s.push(root->right);
}
}
return node;
}
};
剑指 Offer 29. 顺时针打印矩阵(简单)
简单题，但是为什么才击败7%呢。其实没有必要用if判断，只要有一个不符合就不用继续下去了。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int n = matrix.size();
if(n == 0) return {};
int m = matrix[0].size();
if(m == 0) return {};
int count = n*m;
int left =0, right =m-1, top = 0, bottom = n-1;
vector<int> res(count);
int i = 0;
while(i< count){
//从左向右
if(top <= bottom){ //❗可以改变成，再top = top+1后判断if(top>right) 则break
for(int k = left; k <= right; k++){
res[i++] = matrix[top][k];
}
top = top +1;}
//从上向下
if(right>=left){
for(int k = top; k<=bottom; k++){
res[i++] = matrix[k][right];
}
right = right-1;}
//从右向左
if(bottom>=top){
for(int k = right; k >= left; k--){
res[i++] = matrix[bottom][k];
}
bottom = bottom-1;}
//从下向上
if(left<=right){
for(int k = bottom; k >= top; k--){
res[i++] = matrix[k][left];
}
left++;
}
}
return res;
}
};
改动了一点,击败67%
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int n = matrix.size();
if(n == 0) return {};
int m = matrix[0].size();
if(m == 0) return {};
int left =0, right =m-1, top = 0, bottom = n-1;
vector<int> res;
while(true){
//从左向右
for(int k = left; k <= right; k++){
res.push_back(matrix[top][k]);
}
top = top +1;
if(top > bottom) break;
//从上向下
for(int k = top; k<=bottom; k++){
res.push_back(matrix[k][right]);
}
right = right-1;
if(right < left) break;
//从右向左
for(int k = right; k >= left; k--){
res.push_back(matrix[bottom][k]);
}
bottom = bottom-1;
if(bottom < top) break;
//从下向上
for(int k = bottom; k >= top; k--){
res.push_back(matrix[k][left]);
}
left++;
if(left > right)break;
}
return res;
}
};
网友评论