1.旋转字符串–KMP

题目地址
KMP字符串匹配算法，找出$p_0...p_{j-1}$中前缀子串和后缀子串相同的最大值。
KMP算法，包括改进后的next数组

代码如下

class Solution {
public:bool rotateString(string s, string goal) {if(s.size()!=goal.size())return false;vector<int> next(goal.size());getnext(next,goal);string str=s+s;int pos=0;for (int i = 0; i < str.size(); ) {//匹配while(i<str.size()&&pos<goal.size()&&str[i]==goal[pos]){pos++;i++;}if(pos==0)i++;else if(pos==goal.size())return true;elsepos=next[pos];}return false;}void getnext(vector<int> next,string s){//next数组next[0]=-1;int k=-1;for(int i=1;i<s.size();){if(k==-1||s[i]==s[k]){k++;next[i]=k;i++;}else{k=next[k];}}}
};

2.二叉树前中后遍历的迭代写法

前序遍历

//前序遍历
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;if(root==NULL)return ans;stack<TreeNode* > s;s.push(root);while(!s.empty()){auto temp=s.top();s.pop();ans.push_back(temp->val);if(temp->right!=NULL)s.push(temp->right);if(temp->left!=NULL)s.push(temp->left);}return ans;}
};

中序遍历

//中序遍历
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {if(root==nullptr)return {};vector<int> ans;stack<TreeNode* > s;while(!s.empty()||root!=nullptr){while(root!=nullptr){s.push(root);root=root->left;}root = s.top();s.pop();ans.push_back(root->val);root=root->right;}return ans;}
};

后序遍历

//后序遍历
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {if(root==nullptr)return {};vector<int> ans;stack<TreeNode* > s;TreeNode* cur = nullptr;while(!s.empty()||root!=nullptr){while(root!=nullptr){s.push(root);root=root->left;}root=s.top();if(root->right==nullptr||root->right==cur){cur=root;ans.push_back(root->val);root=nullptr;s.pop();}else{root=root->right;}}return ans;}
};