先放代码： class Solution { public: bool hasPath(vector<vector<char> >& matrix, string word) { int n = matrix.size(), m = matrix[0].size(); int vis[205][205]; //对vis矩阵进行初始化 memset(vis, 0, sizeof(vis)); for(int i=0; i<n; i++){ for(...

解题思路： 有序的序列进行查找，优先想到二分查找，那先复习一下二分查找： 二分查找的条件： 查找的内容在逻辑上来说是有序的； 查找的数量只能是一个。 二分查找的过程： 首先确定查找元素的中间的位置mid=(left+right)/2； 如果中间的元素与要查找的元素target相同，说明找到了，返回中间元素的坐标； 如果中间元素的值小于要查找元素的值，因为有序，所以target在中间元素的左边是不可能，target只可能在中间元素的右边，所以将查找范围缩小到[mid+1,right]; 如果中间元素的值大于要查找元素的值，target只可能出现在中间元素的左边，所以将查找范围缩小到[lef...

解题思路：使用递归实现斐波那契数列。 时间复杂度：O(2^n)，执行次数最多不超过高度为n的满二叉树的节点数（2^n-1）； 空间复杂度：O(n)，递归使用的栈的大小; 补充：在递归计算的过程中，有很多节点是重复计算的，而且重复的节点数会随着n的增大而急剧增加，这意味这计算量会随着n的增大而急剧增大。 递归的缺点：递归由于是函数调用自身，而函数调用是有时间和空间的消耗的，每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间；除了效率之外，递归还存在调用栈溢出的问题，需要为每一次函数调用在内存栈中分配空间，而每个进程的栈容量是有限的，当递...

基于c++实现： 官方给的： class Solution { public: void push(int node) { stack1.push(node); } int pop() { int temp; if(!stack2.empty()){ temp = stack2.top(); stack2.pop(); }else{ while(!stack1.empty()){ stack2.push(sta...

解题思路：分两种情况来处理，1.如果该节点有右子树，则中序遍历的下一个节点是该节点右子树的左到不能左的节点；2.如果该节点没有右子树，则看该节点的父节点；如果该节点是它父节点的左子节点，那么中序遍历的下一个节点就是该节点的父节点；3.如果该节点既没有右子树，并且它还是它父节点的右子节点，那么这个情况就比较复杂，需要沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这个节点的父节点就是我们要找的中序遍历的下一个节点。 时间复杂度：O(n) 空间复杂度：O(1) 基于C++实现的： class Solution { public: TreeL...

解题思路：在二叉树的前序遍历序列中，第一个数字总是树的根节点的值。但是在树的中序遍历中，根节点的值在序列的中间，左子树的节点的值位于根节点的值的左边，而右子树的节点的值位于根节点的值的右边。因此根据先序遍历第一个值为根节点的值，扫描中序遍历，找到根节点的值的位置，位于根节点位置的左边的是左子树的节点，位于根节点位置右边的是右子树的节点。在扫描完之后，我们分别找到了左右子树先序和中序的遍历，我们就可以用同样的方法分别构建左子树和右子树，接下来的事情可以用递归来实现。 时间复杂度：O(n)，在遍历的过程都是O(n)的数量级； 空间复杂度：O(n)，递归使用的栈的最大深度不超过n; 基于C++实现：...

解体思路：链表遍历的顺序是从头到尾，可是输出的顺序是从尾到头。也就是说，第一个遍历遍历到的节点最后一个输出，而最后一个遍历的节点第一个输出，这是典型的“后进先出”，所以想到用栈这种数据结构来实现。每遍历一个节点的时候，把该节点入栈；当遍历完整个链表后，再从栈顶开始逐个输出节点的值，此时的节点的顺序已经反过来了。这样就实现了从尾到头打印链表。 时间复杂度：O(n)，n为链表的长度，每个节点仅遍历了一次； 空间复杂度：O(n)，为递归使用栈的大小，为链表长度n； 代码由C++来实现： class Solution { public: vector<int> printListF...

解题思路1：从后往前来对有空格的地方插入'%20',首先查看字符串中空格出现的次数，然后对字符串进行扩容（在原字符串长度的基础上添加空格数✖2的长度），然后按照下面的操作来进行。(1)p1指向原来字符串的末尾，p2指向扩容之后字符串的末尾，即新字符串的末尾；(2)从p1开始，将对应位置的字符复制给p2，然后p1--，p2--直到遇到空格；(3)当遇到空格时，在p2位置依次插入'0','2','%'（因为我们是从后往前复制的），此时p2的位置向前移动了三位，不要忘记p1--;(4)当p1=0并且p1>p2时,结束循环，输出新的字符串。 时间复杂度：O(n)，所有的字符串只复制了一次； 空间...

解题思路：首先选取数组右上角的数字。如果该数字等于要查找的数字，则查找过程结束，返回True；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。也就是说，如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围内剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找的范围为空。 时间复杂度：O(m+n)，m为行数，n为列数，最坏的情况下是m+n; 空间复杂度：O(1) 基于python3实现： class Solution: def Find(self , target: int, array: Lis...

解体思路：在原来的数组的基础上重排这个数组。从头到尾依次扫描数组numbers中的每一个数字m，先将数字m与其对应的坐标i进行比较，如果相等继续看下一个数字；如果不相等，则将数字m与numbers[m]对应的数字进行比较，如果m==numbers[m]，则存在重复的数字，返回m；如果不相等，则将numbers[i]与numbers[m]进行交换，然后继续扫描numbers[i]。 该方法的时间复杂度为O(n)，空间复杂度为O(1). 基于python3实现的： class Solution: def duplicate(self , numbers: List[int]) -&...