专题模板

1.哨兵

• 参考CSDN (opens new window)
• sentry，哨兵
• 哨兵，顾名思义，是用来解决国家之间边界问题的，不直接参与生产活动。
• 同样，计算机科学中提到的哨兵，也用来解决边界问题。
  A sentinel is a dummy object that allows us to simplify boundary conditions. 哨兵是用来简化边界问题的虚设对象
  比如：我们在判断链表是否为空，加不加一个头结点，就能看见代码的改善与否。

2.数组和链表专题

2.1.数组和链表专题

排序数组中的搜索问题，首先想到 二分法 解决。

排序数组使用双指针也是高频选项

2.2.指针的题目

• 1）首先记得想，会不会是NULL（顺路也考虑了程序的健壮性）
• 2）指针的题目，就是不断的移动指针达到题目要求

2.3.链表的常见技巧

3.树专题

树和链表都是递归结构，很多树的问题可以使用递归来处理。

几种遍历，

其中，主要考察，我们对递归的实现？

但是其实有非递归的实现，（面试可能考！！！）

树—常考题型之一

• 完全二叉树 (opens new window)共有700结点，该二叉树有多少个叶子结点？

3.1关于递归到底好不好？

• 可能以前在做ACM题目的时候，个人对递归有偏见
• 但是面试以来，递归是很好的，它能保证递归有足够的空间去，一般不会爆栈！！！！
• 此外面试的时候是有时间控制的，你需要做的是『精简代码、快速解答』
• 110平衡二叉树+剑指offer55 借助做过的求树的高度的题目进行递归 其实自己都不知道为什么AC了，但是获得了经验

1、递归不一定只是递归本身。可以几个不同函数一起递归，分解问题

3.2.树的层序遍历（BFS）

​ 牛客上，没有return最终结果，竟然还能出现内存超限的情况。

​ 我在LeetCode上，有用过两个vector模拟队列，但是在这，我用len控制了遍历的节点数。就能只用一个队列。

3.3.树的三大遍历

3.3.1.递归写法

• 递归写法（习惯递归这种技巧，强化） 前序、中序、后序遍历，一套框架（伪代码）

void DFS( TreeNode * root )
{

    if( nullptr==root )
    {
        return ;
    }

    //前序遍历visit
    DFS( root->left );
    //中序遍历visit
    DFS( root->right );
    //后序遍历visit
}

3.3.2.栈模拟写法（非递归）

• 非递归写法一（重点掌握，防止爆内存栈）——借助栈实现

1、前序遍历

原理： 根-》左-》右 变为 先访问根

stack先入右边，后入左边，这样，出栈遍历就OK

vector<int> preorderTraversal(TreeNode* root) 
{
        
    vector<int> ret;//返回值
    if( nullptr==root )
    {
        return ret;
    }

    stack<TreeNode *> st;
    st.push( root );

    while( !st.empty() )
    {
        TreeNode * temp=st.top();
        st.pop();

        if( nullptr==temp )
        {
            continue;
        }

        ret.push_back( temp->val );//先访问根节点val

        //下面是核心代码：先右后左，这样就能在出栈的时候保证，左子树先被遍历
        st.push( temp->right );
        st.push( temp->left );
    }

    return ret;
}

2、后序遍历

原理：借鉴了前序的，想办法，将两者的写法尽量统一！ 前序遍历为root->left->right 后序遍历为left->right->root 我们如果可以修改前序遍历为root->right->left 显然就可以用STL的reverse算法反转就OK了

vector<int> postorderTraversal(TreeNode* root) 
{

    vector<int> ret;
    if( nullptr==root )
    {
        return ret;
    }

    stack<TreeNode * > st;
    st.push(root);

    while( !st.empty() )
    {
        TreeNode * temp=st.top();
        st.pop();

        if( nullptr==temp )
        {
            continue;
        }

        ret.push_back( temp->val );
        st.push( temp->left );
        st.push( temp->right );
    }

    //反转
    reverse( ret.begin(), ret.end() );
    return ret;
    }

3、中序遍历

• 1、这个的理解和前面两个不一样，这个需要借助DFS的角度来看
• 2、可以借助《算法笔记》中DFS走迷宫来理解代码。

vector<int> inorderTraversal(TreeNode* root) 
{
    vector<int> ret;
    if( nullptr == root )
    {
        return ret;
    }

    stack<TreeNode * > st;

    TreeNode * cur=root;
    //注意是或
    while( nullptr!=cur || (!st.empty()) )
    {
        //DFS之一条路走到最左的
        while( nullptr!=cur )
        {
            st.push( cur );
            cur=cur->left;
        }

        TreeNode * temp=st.top();
        st.pop();

        ret.push_back( temp->val );//放入输出的数组
        //注意是变成temp的右边
        cur= temp->right;//开始到当前节点的右边去遍历，如果没有，显然会先经过根
    }

    return ret;
}

3.3.3.Morris遍历、化树为链表（非递归）

1、中序遍历

特点，改变了二叉树结构，将二叉树变成了“链表”

• 时间复杂度：$O(n)$ $O(n)$，其中 nn 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 $O(2n)$=$O(n)$$O(2n)$=$O(n)$。
• 空间复杂度：$O(1)$ $O(1)$。

讲解： 1、Leecode动画演示 (opens new window)

2、讲解算法

思路与算法
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源：力扣（LeetCode）

• 代码

vector<int> inorderTraversal(TreeNode* root) 
{
    vector<int> rt;
    TreeNode * preNode=nullptr;

    while( nullptr!=root )
    {
        //1.链表的左边，要先遍历的
        if( nullptr!=(root->left) )
        {
            //（1）第1步，preNode节点就是当前 root 节点向左走一步，
            //然后一直向右走至无法走为止（理解）
            preNode=root->left;

            while( nullptr!= (preNode->right)  && (preNode->right) != root )
            {
                preNode=preNode->right;
            }


            //（2）第2步，如果，这个preNode的右边节点是nullptr
            //显然我还没有改变成链表
            if( nullptr==(preNode->right) )
            {
                //改变为“链表”
                preNode->right=root;
                //局部改变之后，我们移动root，准备下一次的改变成链表
                root=root->left;
            }
            else
            {
                //（2）第2步，如果，preNode->right == root
                //说明左子树已经访问完了，我们可以直接开始遍历了
                //此外我们需要断开链接？？
                rt.push_back( root->val );
                preNode->right=nullptr;//断开？？？这步需要吗？
                root=root->right;
            }


        }
        else
        {
            //2.没有左孩子，则直接访问右孩子
            rt.push_back( root->val );
            root=root->right;//不断看被改成的链表右侧
        }

    }   

    return rt;
}

3.3.4.线索化二叉树（非递归）

实际做OJ的时候，这种解法可能有局限，毕竟要修改结构体。 新增两个指针。

3.4.重建二叉树『模板』

3.4.1.需要熟练的树的代码

• 效果：手到码出
• 递归：前、中、后序遍历
• 迭代：前、中、后序遍历

3.4.2.重建二叉树『模板』

有2个新名词：

• 1、序列化：必须保存1个中序遍历的结果，然后外加1个前序or后序遍历的结果
• 2、反序列化：根据2次遍历生成的结果恢复二叉树

1、中序+前序->二叉树『树无重复元素』

• 105. 从前序与中序遍历序列构造二叉树 (opens new window)
• 剑指 Offer 07. 重建二叉树 (opens new window)

（1）递归模板

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

TreeNode * solve
(
    vector<int>::iterator preBegin, vector<int>::iterator preEnd, 
    vector<int>::iterator inBegin, vector<int>::iterator inEnd 
)
{
    if( preBegin==preEnd || inBegin==inEnd )
    {
        return nullptr;
    }

    TreeNode * root= new TreeNode( *preBegin );
    //不记得下面这个函数，也可以用for循环自行查找。
    vector<int>::iterator it= find( inBegin, inEnd, root->val );
    int num=(it-inBegin);

    //递归，左闭右开『注意事项』
    root->left=solve( preBegin+1, preBegin+1+num, inBegin,inBegin+num);
    root->right=solve( preBegin+1+num, preEnd, inBegin+num+1, inEnd);
    return root;
}

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        return solve
        ( 
            preorder.begin() , preorder.end() , 
            inorder.begin() , inorder.end()
        );
    }
};

2、中序+后序->二叉树『树无重复元素』

• 106. 从中序与后序遍历序列构造二叉树 (opens new window)
• PTA甲级1020 Tree Traversals (opens new window)

（1）递归模板

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
TreeNode * solve
(
    vector<int>::iterator inBegin, vector<int>::iterator inEnd,
    vector<int>::iterator postBegin, vector<int>::iterator postEnd
)
{
    if( inBegin==inEnd || postBegin==postEnd )
    {
        return nullptr;
    }

    TreeNode * root=new TreeNode( *(postEnd-1) );
    vector<int>::iterator it;
    for( it=inBegin; it<inEnd; ++it)
    {
        if( *it==root->val )
        {
            break;
        }
    }
	//注意：左闭右开
    int num=it-inBegin;
    root->left=solve( inBegin, inBegin+num, postBegin, postBegin+num );
    root->right=solve( inBegin+num+1, inEnd, postBegin+num, postEnd-1 );
    return root;
}
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

        return solve( inorder.begin(), inorder.end(), postorder.begin(), postorder.end() );
    }
};

3、中序+层序->二叉树

• 这个结论，是在『算法笔记』上看到的，我们写出下面的模板代码
• 注意：区间的开闭

参考博客 (opens new window)

4、前序+后序->二叉树『不唯一』

（显然树不唯一）

889. 根据前序和后序遍历构造二叉树 (opens new window)

4.『贪心』解决过桥问题

4.1.题面

• N个人在晚上想通过桥。每次最多过去2个人，需要有手电筒。现在只有1个手电筒。每个人过桥的速度都不一样，过桥的时间以慢的为准。你的工作是找到最少的过桥的方法;

  输入:
  首先是n,然后n行是过桥的时间。
  人数不超过1000，而且没有人过桥的时间超过100秒;
  输出:
  首先输出总共所需最少时间;下面表示过桥的过程(见样例)，如果有多种过桥方案，输出其中一种。

• 来源：IBM面试题，一道标准的贪心题目

样例输入：
输入样例
4 	//4个人
1
2
5
10
样例输出：
输出样例
17
1 2			//1和2先过去
1			//1回来
5 10		//5和10过去
2			//2回来
1 2		    //1 2 过去

4.2.解法

算法复杂度在于排序

样例：
4
1 2 5 10

1）贪心第1部分——贪心策略1（表述不如，算法清晰）

• 1）每次过桥2个人， 希望一起过去的人时间相差最小 ，选领近的两个，所以采用贪心技术。（第1个要贪心的）
• 理解：比如，上面的最大的10是肯定没有办法避免的，但是我就希望这个5就不要在出现在我的和式里面了 时间相差最小：比如，时间最多的人和时间次多的人一起过，这样我们最大的那个时间10就只出现一次 怎么办？所以，我希望在过桥的时候，是5和10一起过
• 2）而且返回的时间要少，所以用时间最少的人返回;往回送手电筒的人，时间要少（第2个贪心）

2）贪心策略1的算法：

预处理：我们将过桥的时间从小到大排好序，标记为T1,T2,T3..Tn

• 1.首先让时间最少的两人过去，T1，T2（这2个人的使命是：用来往回送手电筒的）
• 2.然后，返回T1和T2中的哪一个呢？ -- Q：难道返回任何一个都没有关系？ -- A：T1不是这次返回的话，反正下次还是要返回的 但是，请看这个样例：如果只有3个人，1 2 3，显然如果要T2回去送，返回的时候会长一点点，会影响时间
• 3.让Tn和Tn-1一起过去，我们希望在时间的总和里面，Tn出现，但是比他稍微小一点的Tn-1就不用再出现了
• 4.然后余下的T2返回

显然，观察容易知道，经过以上4个步骤会出现： T1和T2又回到了最初的位置，Tn和Tn-1却过河了 这样，我们就从n个人转换为了n-2个人过河 来回2趟，送过去2个人，得到一个部分最优解。 在这个基础上，不断的分解

3）贪心第2部分——贪心策略2

Q：先前的策略是，时间最小的2个人来送手电筒，那么能否只让时间最小的1个人来送手电筒？ A：不能，因为从数学上可以证明

显然，我们上面的样例中，那个时间5会加到我们的总和中去，

广义的数学证明这个贪心策略不行：

抽象从小到大的4个数，T1，T2，Tn-1，Tn

贪心策略1：
比如，Tn-1不会出现在最终和式中
T1 T2过去 （T2）
T1回来		（T1）
Tn-1和Tn过去	（Tn)
T2回来		(T2)
sum1=Tn+2*T2+T1;

贪心策略2：
Tn,Tn-1啥的都会出现在最终和式
T1 Tn过去  （Tn）
T1回来		（T1）
T1和Tn-1过去	（Tn-1)
T1回来		(T1)
sum2=Tn+T（n-1）1+2*T1

显然 sum2-sum1<0的时候，需要满足Tn-1< 2*T2-T1才能使用 比如这个样例

4
1 4 5 10
贪心策略1：
10+2*4+1=19
贪心策略2：
10+5+2*1=17

所以，我们使用贪心策略1还是2的时候，需要判别Tn-1< 2*T2-T1的成立与否

3、结合两种贪心策略的最终代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=1000+5;
int test[maxn];




//伪代码，时间复杂度是O（n）
void solve()
{

	//t表示的意识是
	t=2*T2- T1 （最小的T1，次小的T2）

	//2个人来回送手电筒贪心策略
	for(int i=n-l; (s[i-l]>t)&(i>2) ;i-=2)
	{
		printf ("%d %d\n",s[0],s[1]);
		printf ("%d\n",s[0]);
		printf ("%d %d\n",s[i-1],s[i]);
		printf ("%d\n",s[1]);
	}

	//Tn-1< 2*T2-T1才能使用
	//1个人来回送手电筒贪心策略
	for(int j=i; j>l ; --j)
	{
		printf("%d %d\n", s[0],s[j]);
		printf("%d\n", s[0]);
	}
}



//真实代码
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		for(int i=0;i<n;++i)
		{
			scanf("%d",&test[i]);
		}

		sort(test,test+n);//将所有的时间排序是贪心法的预备工作

	}

	return 0;
}

5.『分治』算法

很显然，递归这种『编码技巧』，就是分治算法的完美体现之一

1、使用情况

问题规模比较大的时候，难以求解 想办法减少

贪心，DP，分治，减治 减治，由于时间的关系，我们就不举例子了。

分治： 我们用得比较多的也是二分法，或者三分法

2、分治法-到底如何分解问题

到底如何分解问题，其实我一直很迷惑，9.2号。我突然想到一个好像不错的方法：

1）找到最大的问题
2）找到最简化的问题（最小的问题）
3）分析如何从最大的问题一步步转换为最小的问题

我后面，自己找了一个3人，3鬼的方法验证
3人3鬼过河，人的数目要比鬼多，否则鬼会吃掉人

3、最大问题

人人人 鬼鬼鬼|  |

4、最小问题

人 鬼|	|
这个容易解决，一次性过去。

5、中等问题

人人鬼鬼| |

显然，中等问题要成功，最后的状态要是

人鬼|  |人鬼

或者

鬼| |人人鬼

转换关系

最大要转换为

人人鬼鬼|（船在这）  |人鬼

中等问题要转换为

人鬼|（船在这） |人鬼

6.面试—字符串

• 参考文章：一个模板刷遍所有字符串句子题目 (opens new window)！（归纳总结+分类模板+题目分析）
  • 注意点：字符串的遍历，记得“擦屁股”—也就是收拾最后的残局

7.KMP算法

#include<bits/stdc++.h>
using namespace std;


class KMP
{
public:
    void getNext( vector<int> & next, string s )
    {
        //我的理解，getNext其实本质也是个strStr的函数，
        //其中，文本串是『后缀XXX』，needle__也就是s是『前缀XXX』

        int prefixPos=0;//初始化『前缀末尾位置』
        next[0]=0;//初始化next[0]的回退位置

        //i意义1：表示『后缀末尾的位置』,初始化next[i]
        //意义2：此外，i还代表当前XXX
        for (int suffixPos = 1; suffixPos < s.size(); ++suffixPos)
        {

            //易错，不能是if，因为可能借助next多次回退
            while( prefixPos>0 && s[prefixPos]!=s[suffixPos] )
            {
                prefixPos=next[prefixPos-1];
            }

            if( s[prefixPos]==s[suffixPos] )
            {
                ++prefixPos;
            }

            //初始化next
            next[suffixPos]=prefixPos;
        }

    }


    int strStr( string haystack, string needle )
    {
        if( 0==needle.size() )
        {
            return 0;
        }

        vector<int> next( needle.size() );
        getNext( next, needle );

        int j=0;//needle串，当前需要测试匹配性的位置
        for(int i=0; i<haystack.size(); ++i)
        {
            //易错：不能用if，因为可能多次借助next数组回退
            while( j>0 && haystack[i]!=needle[j] )
            {
                j=next[j-1];
            }

            //如果匹配了1个字符，显然会后移
            if( haystack[i]==needle[j] )
            {
                ++j;
            }

            //完全匹配
            if( j==needle.size() )
            {
                //注意，因为i还来不及+1，所以，返回前要+1然后才能减掉
                return ( i+1-needle.size() );
            }
        }

        return -1;//匹配失败
    }
}

int main()
{

    return 0;
}