经典回溯问题。选择使用循环+递归的方式进行回溯。在一个循环内遍历矩阵中的结点，以该点为起点调用寻路函数在寻路函数中，先判断当前字符串是否满足要求，若是则返回true，否则将其周围四个点拼接至当前字符串尾部，递归调用寻路函数。为了避免一个字符被多次使用，引入一个visited数组，用于记录被访问过的点。为了对递归进行剪枝，当当前要拼接的字符与要求的字符串中对应位置的字符不等时，直接返回false。当要访问的结点位置越界时直接返回false。当当前字符串长度大于要求字符串时直接返回false。这里面在构造visited数组时复习了一下vector的初始化方法。 vector<bool>...

看到题目第一时间没有想用递归，想直接用两个指针遍历两个字符串来解。但是写到后面发现判断结构太过复杂，太过冗余，故回到递归的方法来。字符串处理的题目，细节必定特别多。要把每一步想的特别透彻才能做对。本题主要的难点就是'*'的处理，遇到这个符号，可以不匹配，也可以匹配多个，处理这一问题的判断就是下面这个关键的递归语句。 return match(str.substr(1), pattern) || match(str, pattern.substr(2)) || match(str.substr(1), pattern.substr(2)); 返回的这三种递归调用，分别对应了匹配多个字符，不匹配...

解决这题的突破口是找到递推规律。根据题目给出的条件，从水平方向看，可以知道，我们竖着摆放21矩形时，必须一次至少摆两个，而横着摆放时，则可以一次摆一个。所以我们对2n的大矩形，在第一次摆放时，有两种选择，要么摆放一个横着的小矩形，要么一次摆放两个竖着的小矩形。这样就可以得到递推式f(n)=f(n-1)+f(n-2)。从而得知，本题的递归公式与斐波那契数列一致，属于斐波那契数列的变种。在面对这种递推题目时，理清思路，找准递推公式是关键。 class Solution { public: int rectCover(int number) { if(!number){ ...

使用和跳台阶一样的思路。模拟跳的过程，将n阶台阶分为第一次跳1阶，第一次跳2阶，...，第一次跳n阶。这样就得到了一个类似于原始跳台阶的公式，f(n)=f(1)+f(2)+...+f(n-1)+1，f(n)表示n阶台阶的跳法数。最后不是加f(n)而是加1，是因为一次跳n个台阶就直接跳完了，只有一种跳法。如果加f(n)的话会使等式不成立，使递归无出口。这个最后加1在代码中体现为返回++sum。由于在循环中调用递归，所以时间复杂度在O(n^2)，是比较大的，算法还有进一步优化的空间。 class Solution { public: int jumpFloorII(int number) ...

基础斐波那契数列，基础递归方法。 class Solution { public: int Fibonacci(int n) { if(n == 1 || n == 2){ return 1; } else{ return Fibonacci(n-1) + Fibonacci(n - 2); } } };

题目中要求时间复杂度O(logn)，所以直接用二分查找。 总体思路是通过二分查找找到要找的数，然后在查找该数周围相同的数，最后返回累计计数。复杂度满足题目要求。因为写完一次过了，所以代码结构还有较大调整空间。 class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int count = 0; int index; int left = 0; int right = data.size() - 1; while(r...

刚看到题其实稍微有点蒙，不过看了题目配的图就很简单了。图里已经给出了一种解题思路。按顺序遍历遍历字符串，对每一个字符都调换它以及大于等于它的下标的字符，将新得到的字符串压栈，并对新字符串也执行该操作，直到遍历完整个字符串。由于调用的层数比较深，这里选择递归的方法来实现。传入参数中的index为开始交换的下标。第一次写完代码测试时，发现"aab"的调用结果会出现6个，其中有三个重复的，所以正确结果应该是3个。为了解决重复元素造成的重复结果这一问题，选择先将得到的数组变为集合，再将集合变回数组的方式解决。 class Solution { public: vector<string&...

这题常规使用二分查找来解，这里先皮一下，直接用set初始化函数排序，两行代码秒解。同理也可以直接用sort函数排序，也是两行解。ps: 使用set函数初始化的运行速度和使用sort排序的时间基本一致，都是超过95%www。空间复杂度上当然sort更优。 class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { set<int> s(rotateArray.begin(),rotateArray.end()); return *s.b...

模拟窗口滑动的过程，用一个数组来记录滑动窗口内的值，一个数组来记录最大值。每次窗口滑动都将最大值数组的队尾压入结果栈，最后返回结果栈。 这题要做出来并不难，难在追求优秀的时间复杂度和空间复杂度。感觉这个代码还有较大改进空间。欢迎讨论。 class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> result; if(size == 0 || size >...

难度较低的题目。在经历了前面的字符串处理地狱之后，这种题目我看过之后心里毫无波澜，甚至还有点想笑w。言归正传，总体的思路是：将string作为char[]遍历，遇到空格则切词，并将切下的词入栈。最后按出栈顺序将字符串拼好即可。需要注意空格的处理方式，这里我的做法是每次切词都加上空格，对头尾特殊处理。 class Solution { public: string ReverseSentence(string str) { stack<string> stk; string temp = ""; string result = ...

审题后从输入序列和输出序列入手，发现规律：当两个元素在输入序列中的先后顺序与在输出序列中一致时，在这两个数之后输入的数必不可能在这两个数之前输出。围绕这一发现，设计算法逻辑：用一个辅助数组seq来储存输入序列的元素在输出序列中的位置，如seq[0]则表示输入序列中第一个元素在输出序列中的位置。遍历seq，seq中某两个元素的值的大小关系与其序号的大小关系一致时，则这两个元素输入输出的先后顺序一致，进而判断seq中在这两个元素之后的元素。若之后的元素中有比这两个元素的值小的，则可知有在其后输入的元素在其前输出了，返回false。否则继续，直至遍历seq中所有数对。 class Solution ...

需求是在基本栈的功能上增加一个min的功能。 这里选择增加一个栈用于维护最小值，暂且称它为最小栈。 每次push时检查最小栈，为空则直接入最小栈，否则将入原始栈元素与栈顶元素比较，若入原始栈元素小于等于最小栈栈顶元素，则也将其入最小栈。之所以等于时也要入最小栈，是因为相等说明前面有一个同样数据的结点已经入原始栈，当原始栈执行pop操作时，若pop了其中一个最小值，那么最小栈中也会同样将其pop，而此时原始栈中还有一个和该值同样的值，所以最小值不应该改变。 每次pop时检查最小栈栈顶元素是否与pop的出的元素想等，想等则最小栈也pop。 top操作直接调用top即可。 每次min时直接返回最小栈...

一面 set的底层结构，单核机器多线程加不加锁，洗牌算法，经典烧香，线程和进程的区别，线程通信，时间片切换怎么处理，malloc free new delete，对称加密和非对称加密，为什么udp快，三次握手 四次挥手，shared_ptr怎么实现，iterator的有效性。 二面 堆排，hash和红黑树，可靠udp，类的函数表，malloc和free的伪代码，多重继承的虚函数表怎么安排，参数压栈的顺序。

这道题本身挺简单的，但是坑是真的多，给我整破防了。 先说一下大概的思路，直接用层序遍历来序列化。序列化的时候使用一个队列来辅助将结点值拼接到字符串上，节点为空则拼接#。反序列化时同理，使用队列来辅助反序列化，创建好的节点先入队，并且查看队头结点的情况，若其左结点为空，则将该结点设为队头结点的左结点，若队头结点右结点为空，则将该结点设为队头节点右结点，并将队头出队。 在最开始写好时，两个测试用例无事通过，信心满满，点击提交，用例未通过{100,50,##,50}，噩梦开始。 因为最初审题不细致，没看到结点取值为0<=val<=100，我默认值是在0-9之间的个位数了。虽然这对整个程序...