这个月的月初学习了一发牛客网的课程，左程云的算法课，把一些笔记和思路记录下来，以便于分享和回顾。
1，二叉树的层次打印：
有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。
给定二叉树的根结点
root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。
引用下别人的总结:
两个变量用于记录打印的位置和结果
1.初始化时，last=1，把1放入队列；
2.将1出队，把1的子孩子2,3放入队列，更新nlast=3；
3.nlast更新完之后，打印上一次出队的1，并和last比较，如果相同就打印换行，并更新last=nlast=3;
4.将2出队，把2的子孩子4放入队列，更新nlast=4;
5,nlast更新完以后，打印上一次出队的2，并和last（3）比较，不相同，continue；
6.将3出队，将3的子孩子5，6放入队列，更新nlast=6;
7.nlast更新完以后，打印上一次出队的3，并和last（3）比较， 相同就打印换行，并更新last=nlast=6;
…………
总结就是如下循环：（初始化last=根节点）
1.将A出队，并将A的子孩子入队，更新nlast=A最后入队的子孩子；
2.打印上次出队的家伙A，并和last比较， 如果相同就打印换行，并更新last=nlast，如果 不相同，则continue
AC代码:
class TreePrinter {
public:
vector<vector<int> > printTree(TreeNode* root) {
vector<vector<int> > res; //一共要打印的点集合
vector<int> templist;//每一行要打印
TreeNode * last; TreeNode* nlast; //核心思路两个变量分别记录 当前行最右边的节点 与下一行最右边的节点
if(root==NULL)
return res;
queue<TreeNode*>que;
que.push(root);
last = nlast = root;
while(!que.empty()){
TreeNode* temp = que.front();
que.pop();
templist.push_back(temp->val);
if(temp->left){
que.push(temp->left);
nlast = temp->left;
}
if(temp->right){
que.push(temp->right);
nlast = temp->right;
}
if(temp == last){//核心步骤，让
当前的打印的节点 和 上次存储后的最右边的节点比较
res.push_back(templist); //换行操作
last = nlast;
templist.clear();
}
}
return res;
}
};
,2，
两串旋转练习题
如果对于一个字符串A，将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A="12345",A的旋转词有"12345","23451","34512","45123"和"51234"。对于两个字符串A和B，请判断A和B是否互为旋转词。
给定两个字符串
A
和
B
及他们的长度
lena
，
lenb
，请返回一个bool值，代表他们是否互为旋转词。
测试样例：
"cdab",4,"abcd",4
返回：true
说下核心的思路：
1，第一个观察结果是 一个字符串拼接两次的结果里面包含了 所有该字符串旋转的结果的所有可能 （以子串的形式存放）
2， 由1可得知，判断两个子串是否互为旋转结果既可以转化为字符串匹配问题（在AA中找和B的匹配的子串），KMP算法即可。
难点有两个：
1，思路1需要进行观察和推测
2，如何手撸KMP算法(如果面试官不让用类似于库函数：string：find实现的话)
给出简单的版本： 网上写题目时必须要会的
class Rotation {
public:
bool chkRotation(string A, int lena, string B, int lenb) {
// write code here
if(lena!=lenb) return false;
string C =A+A;
return C.find(B) != string::npos;
}
};
手撸版本（next数组的求解很麻烦）：
class Rotation {
public:
bool chkRotation(string A, int lena, string B, int lenb) {
string big = A + A;
if(lena!=lenb)
return false;
return KMP(big,B);
}
const vector<int> * kmp_next(string &m) //找到待匹配串的next数组
{
static vector<int> next(m.size());
next[0]=0;
int temp;
for(int i=1; i<next.size(); i++)
{
temp=next[i-1];
while(m[i]!=m[temp]&&temp>0)
{
temp=next[temp-1];
}
if(m[i]==m[temp])
next[i]=temp+1;
else next[i]=0;
}
return &next;
}
bool KMP(string text,string m) //匹配串
{
const vector<int> * next=kmp_next(m);
int tp=0;
int mp=0;
for(tp=0; tp<text.size(); tp++)
{
while(text[tp]!=m[mp]&&mp) //遇到不匹配时情况
mp=(*next)[mp-1];
if(text[tp]==m[mp])
mp++;
if(mp==m.size())
{
return true;
}
}
return false;
}
};
试听第一章结束