剑指Offer思路简记版

本文对剑指offer的每道题进行了思路的总结，可以经常没事看看记一下，这样在面试的过程中如果碰到就会很快有思路。

1.二维数组的查找

二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

从数组右上角开始查找，如果该数字大于要查找的数字，剔除这个数字所在的行，如果该数字小于要查找的数字，剔除这个数字所在的列。

2.替换空格

请实现一个函数，把字符串中的每个空格替换成”%20”，例如“We are happy.”，则输出“We%20are%20happy.”。

可以直接调用Java的replace函数，或者先便利字符串计算出需要的总长度，然后从头一个一个填进去

3.从尾到头打印链表

整个链表压入栈中或者递归先访问下一节点，再输出

4.重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如：前序遍历序列｛ 1, 2, 4, 7, 3, 5, 6, 8｝和中序遍历序列｛4, 7, 2, 1, 5, 3, 8，6}，重建二叉树并输出它的头结点。

递归，首先从前序遍历中找到根节点（第一个节点），然后在中序中找到左右子树长度，然后根据长度确定前序中左右子树的根节点返回（这里递归），最后返回根节点。

这道题有好几种解法：可以利用list的sublist进行递归，或者利用hashmap记录前序在中序里面的位置。

5.两个栈实现队列

栈1用于存储元素，栈2用于弹出元素，出队时若栈2发现为空，把栈一的全部弹出到栈二。

6.旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾， 我们称之数组的旋转。输入一个递增排序的数组的一个旋转， 输出旋转数组的最小元素。例如数组{3,4,5,1,2 ｝为｛ 1,2,3,4,5}的一个旋转，该数组的最小值为1。

首尾指针，类似二分法，中间值大于等于第一个元素时赋给首位，小于等于最后一个元素时赋给尾位，若三数字相等，从头寻找

7.斐波那契数列

循环或者递归

8.二进制数中1的个数

输入一个整数，输出该数二进制表示中1的个数。

循环右移，每次和1&运算相加即可/循环让n-1&n

9.打印1到最大的n位数

输入数字n，按顺序打印出从1到n位最大十进数的数值。比如输入3，则打印出1、2、3一直到最大三位数即999。

使用n位数组，每次输出，模拟进位即可

10.在O(1)的时间内删除链表节点

给定单向链表的一个头指针和节点指针，定义一个函数在O(1)时间删除该节点。

把该节点的值替换为下一个节点的值，同时让该节点直接指向下一个节点的下一个节点。

11.调整数组顺序

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位予数组的后半部分。

首尾指针向中间移动，首部只招偶数，尾部只招奇数，找到之后交换，直到首位相遇

12.链表倒数第k个节点（遍历一遍）

定义两个节点，从头出发，一个先走k-1步，然后两个一起走，第一个走到尾的时候第二个走到倒数k个节点

13.反转链表

遍历。将指向下一个节点的指针指向上一个节点。

14.合并两个排序链表

比较两个链表的头结点，让较小的头结点作为新链表的头结点，直到有一个链表没有节点，然后将新链表的最后一个节点直接指向剩余链表的节点。

15.树的子结构

输入两棵二叉树A 和B，判断B 是不是A 的子结构。

第一步在树A 中找到和B 的根结点的值一样的结点R， 第二步再判断树A中以R 为根结点的子树是不是包含和树B 一样的结构（多层递归）

16.二叉树镜像

先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子结点。当交换完所有非叶子结点的左右子结点之后，就得到了树的镜像。

17.顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次扫印出每一个数字。

暴力输出，注意上下标和最后边界处理

18.包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小数的min 函数。在该栈中，调用min、push 及pop的时间复杂度都是O(1)。

把每次的最小元素（之前的最小元素和新压入战的元素两者的较小值）都保存起来放到另外一个辅助栈里。如果每次都把最小元素压入辅助栈， 那么就能保证辅助栈的栈顶一直都是最小元素．当最小元素从数据栈内被弹出之后，同时弹出辅助栈的栈顶元素，此时辅助栈的新栈顶元素就是下一个最小值

19.栈的压入弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

20.层次遍历二叉树

队列+while+for循环（打印层号）

21.二叉树的后序遍历

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。

递归，在后序遍历得到的序列中， 最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分： 第一部分是左子树结点的值，它们都比根结点的值小： 第二部分是右子树结点的值，它们都比根结点的值大。

22.二叉树中和为某一值的路径

输入一棵二叉树和一个整数， 打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

前序遍历，当用前序遍历的方式访问到某一结点时， 我们把该结点添加到路径上，并累加该结点的值。如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数， 则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是从根结点到父结点的路径。

23.复杂链表的复制

请实现函数ComplexListNode clone(ComplexListNode head),复制一个复杂链表。在复杂链表中，每个结点除了有一个next 域指向下一个结点外，还有一个sibling 指向链表中的任意结点或者null。

在不用辅助空间的情况下实现O(n)的时间效率。第一步：仍然是根据原始链表的每个结点N 创建对应的N’。把N’链接在N的后面。第二步：设置复制出来的结点的sibling。假设原始链表上的N的sibling指向结点S，那么其对应复制出来的N’是N的next指向的结点，同样S’也是S的next指向的结点。第三步：把这个长链表拆分成两个链表。把奇数位置的结点用next . 链接起来就是原始链表，把偶数位置的结点用next 链接起来就是复制 出来的链表。

24.二叉搜索树转化为双向链表

由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每一个结点， 这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每一个结点。当遍历到根结点的时候，我们把树看成三部分：根结点，左子树，右子树。根据排序链表的定义，根结点将和它的左子树的最大一个结点链接起来，同时它还将和右子树最小的结点链接起来。

25.字符串的排列

DFS深度优先，step步数递归+for循环+book数组

26.数组中出现次数超过一半

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

排序，找中间那个数

27.最小的k个数

输入n个整数，找出其中最小的k个数。

维持一个list，和长度k，每次添加时进行操作，或者使用优先队列（小顶堆）

28.连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

记录当前和，若大于0，则一直加，若小于零则等于当前值，每次更新最大值

29.1-n中1的个数

暴力判断，不解释

30.数组排列成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

定义排序大小，两个数字m 和n能拼接成数字m和m。如果mn < nm，那么我们应该打印出m，也就是m 应该排在n 的前面，我们定义此时m 小于n：反之，如果nm < mn，我们定义n小于m。如果mn=nm,m 等于n。在下文中，符号“<”、“>”及“＝”表示常规意义的数值的大小关系，而文字“大于”、“小于”、“等于”表示我们新定义的大小关系。然后排序算法排即可，定义compare函数，然后array.sort()即可

按照字符串比较，否则越界

31.丑数

我们把只包含因子2、3 和5 的数称作丑数（Ugly Number）。求从小到大的顺序的第1500个丑数。

放置三个index，分别记录乘以235刚好超过当前丑数的数，然后每次取乘以235最小的那个数即可。

32.第一个只出现一次的字符。

在字符串中找出第一个只出现一次的字符。

第一次扫描，次数放hashmap，第二次扫描，找第一次次数为1的

33.数组中的逆序对

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

归并算法，每次merge之前先找当前数组的逆序次数返回，然后merge将数组排序，消除逆序对

34.两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共结点。

都先遍历找到长度，然后一个先走差值步数，然后两个一起走比较

35.排序数组中出现的次数

统计一个数字：在排序数组中出现的次数。

举例说明

例如输入排序数组｛ 1, 2, 3, 3, 3, 3, 4, 5｝和数字3 ，由于3 在这个数组中出现了4 次，因此输出4 。

二分查找，找到数字之后两头扩撒找到次数

36.二叉树的深度

递归，当前节点为0返回0，否则返回左右大的那个加一

37.判断平衡二叉树

输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1 ，那么它就是一棵平衡二叉树。

后序遍历，在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度）若为-1则返回-1，若子树均不为-1判断两个只差是否满足，若不满足返回-1，满足返回两个大值+1，我们就可以一边遍历一边判断每个结点是不是平衡的。

38.数组中只出现一次的数

一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

全部异或，得到两单独数字的异或结果，结果肯定有某一位为1，找到第一个为1的位数n，将数组分为两个，一类位数n为1，然后全部异或得到一个数字，一类位数为0，然后全部异或得到另一个数字

39.和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。

头尾指针，向中间移动，每次判断大小，大了就降低尾指针，小了就增加头指针

40.和为s的连续正数序列

输入一个正数s，打印出所有和为s 的连续正数序列（至少两个数）。例如输入15，由于1+2+3+4+5=4＋5+6＝7+8=15，所以结果打出3 个连续序列1～5、4～6 和7～8。

考虑用两个数small 和big 分别表示序列的最小值和最大值。首先把small 初始化为1, big 初始化为2。如果从small 到big 的序列的和大于s，我们可以从序列中去掉较小的值，也就是增大small 的值。如果从small 到big 的序列的和小于s，我们可以增大big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加small 到(1+s)/2 为止。

41.翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字的顺序不变。为简单起见，标点符号和普通字母一样处理。

举例说明

例如输入字符串”I am a student. ”，则输出”student. a am I”。

第一步翻转句子中所有的字符。比如翻转“I am a student. ”中所有的字符得到”.tneduts a m a I”，此时不但翻转了句子中单词的顺序，连单词内的字符顺序也被翻转了。第二步再翻转每个单词中字符的顺序，就得到了”student. a am I”。

42.左旋字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。

举例说明

比如输入字符串”abcdefg”和数字2，该函数将返回左旋转2 位得到的结”cdefgab”。

以”abcdefg”为例，我们可以把它分为两部分。由于想把它的前两个字符移到后面，我们就把前两个字符分到第一部分，把后面的所有字符都分到第二部分。我们先分别翻转这两部分，于是就得到”bagfedc”。接下来我们再翻转整个字符串， 得到的”cdefgab”就是把原始字符串左旋转2 位的结果。

43.n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s 的所有可能的值出现的概率。
1.现在变量有：骰子个数，点数和。当有c个骰子，点数和为k时，出现次数记为dp(c,k)。那与c-1个骰子阶段之间的关系是怎样的？
2.当我有c-1个骰子时，再增加一个骰子，这个骰子的点数只可能为1、2、3、4、5或6。那k个骰子得到点数和为n的情况有：
(c-1,k-1)：第c个骰子投了点数1
(c-1,k-2)：第c个骰子投了点数2
(c-1,k-3)：第c个骰子投了点数3
….
(c-1,k-6)：第c个骰子投了点数6
在c-1个骰子的基础上，再增加一个骰子出现点数和为k的结果只有这6种情况！
所以：dp(c,k)=dp(c-1,k-1)+dp(c-1,k-2)+dp(c-1,k-3)+dp(c-1,k-4)+dp(c-1,k-5)+dp(c-1,k-6)(注意当k<6时的处理越界问题)
3.有1个骰子，dp(1,1)=dp(1,2)=dp(1,3)=dp(1,4)=dp(1,5)=dp(1,6)=1。
因此状态转移方程为
dp(c,k)=sum（dp(c-1)(k-m)）(1<=m<=6&&m<k)

44.扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

排个序 计算前面0的个数zeros
然后zeros - (顺子差的数)
若zeros最后 >= 0 说明用大小王补够用 否则不行
还要判断一下只要有相同的牌直接返回false

45.约瑟夫环问题

0, 1, … , n-1 这n个数字排成一个圈圈，从数字0开始每次从圆圏里删除第m个数字。求出这个圈圈里剩下的最后一个数字。

创建list，模拟过程，每次找第m个的时候，下标记得模list的大小

46.不用加减乘除做加法

两个数进行^运算，这相当于没有进位的加法，然后两个数&得到要向前进位的数，左移一位，将这个数与前面的没有进位加法得到结果相加，一直循环这个过程，直到进位为0

47.字符串转化为整数

没啥技巧，主要是考虑情况比较多，考虑要全面

48.树中两个节点的最低公共祖先

求树中两个结点的最低公共祖先，此树不是二叉树，并且没有指向父节点的指针。

遍历两次，前序遍历，找到根节点到两个节点的路径，然后求路径上的相同的那一段就行了

49.数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

举例说明

例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

先排序，或者哈希表，或者扫描数组，先判断a[i]和i是否相等，相等继续扫描，不相等，将a[a[i]]与a[i]交换，每次比较a[a[i]]和a[i]，若相等，则找出一个相同值返回，若交换之后a[i] = i了，那么继续下一个扫描

50.构建乘积数组

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1],不能使用除法。

先计算下三角的连乘，再计算上三角的连乘

51.正则表达式匹配

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

当模式中的第二个字符不是“*”时：
1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
2、如果 字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第二个字符是“*”时：
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
1、模式后移2字符，相当于星号被忽略；
2、字符串后移1字符，模式后移2字符；
3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为星号可以匹配多位

52.表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

例如，字符串“+100”，“5e2”，“-123”，“3.1416”及”-1E-16”都表示数。但“12e”,”1a3.14”,”1.2.3”,”+-5”及“12e+5.4”都不是。

没什么技巧，主要注意判断，循环每个字符，每次判断以下所有，e后面一定要接数字；不能同时存在两个e；第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后；第二次出现+-符号，则必须紧接在e之后；e后面不能接小数点，小数点不能出现两次；记得判断不合法字符

53.字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。

举例说明

例如，当从字符流中只读出前两个字符“Go”时，第一个只出现一次的字符是‘g’。当从该字符流中读出前六个字符“google”时，第一个只出现1次的字符是”l”。

用一个大小为256的数组存储，这正好是char字符的大小，使用hash存储的方式，把字符的index存储进数组中，如果出现两次就置为-2，起始全部置为-1，然后 最后找数组中大于0的那个最小值即index最小的那个ch即可。

54.链表中环的入口节点

快慢指针，先找到环的长度n，然后找两个指针一个先走n步，然后两个一起走，当两个第一次相等的时候就是入口节点

55.删除链表中重复的节点

在一个排序的链表中，如何删除重复的结点？

例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

没技巧，遍历一遍，判断删除即可

56.二叉树的下一个节点

给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父节点的指针。

如果一个结点有右子树，那么它的下一个结点就是它的右子树中的左子结点。也就是说右子结点出发一直沿着指向左子结点的指针，我们就能找到它的下一个结点。接着我们分析一个结点没有右子树的情形。如果结点是它父节点的左子结点，那么它的下一个结点就是它的父结点。如果一个结点既没有右子树，并且它还是它父结点的右子结点，这种情形就比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。

57.对称的二叉树

请实现一个函数来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

递归，先判断左右子节点是否相等，或者同为空，然后返回左子树的左节点和右子树的右节点的比较结果和左子树的右节点和右子树的左节点的结果

或者层次遍历，每一层的节点从头尾操作比较一下就行了

58.层次输出二叉树（带层号）

队列+while+for循环（队列的size）+层号即可

59.之字形打印二叉树

队列+while+for循环（队列的size）+奇数行左右顺序入队列，偶数行右左顺序入队列即可

60.二叉搜索树的第k个节点

给定一棵二叉搜索树，请找出其中的第k大的结点。

中序遍历，递归实现，每次访问当前节点时，判断当前节点是不是第k个，如果是则返回。注意每次判断一下左右子树返回的节点是不是空，如果不是空则已经搜索到了，直接返回即可。

或者执行中序遍历，用数组存储遍历结果，然后直接取k-1下标的值

61.数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

• 先用java集合PriorityQueue来设置一个小顶堆和大顶堆

• 主要的思想是：因为要求的是中位数，那么这两个堆，大顶堆用来存较小的数，从大到小排列；
  小顶堆存较大的数，从小到大的顺序排序，显然中位数就是大顶堆的根节点与小顶堆的根节点和的平均数。

• ⭐保证：小顶堆中的元素都大于等于大顶堆中的元素，所以每次塞值，并不是直接塞进去，而是从另一个堆中poll出一个最大（最小）的塞值

• ⭐当数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中；

• ⭐当数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中；

• ⭐取中位数的时候，如果当前个数为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当前个数为奇数，显然是取小顶堆的根节点

  //小顶堆
     private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
     //大顶堆
     private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() {
         @Override
         public int compare(Integer o1, Integer o2) {
             return o2 - o1;
         }
     });

62.滑动窗口的最大值

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
举例说明
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小为3，那么一共存在6个滑动窗口，它们的最大值分别为{4,4,6,6,6,5}。

用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较，把所有比他小的值丢掉

注意，当i大于滑动窗口的数组大小时才能开始输出

使用ArrayDeque，基于数组的双端队列。

63.矩阵中的路径

回溯算法
这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。
当矩阵中坐标为（row,col）的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下标为pathLength+1的字符。
如果4个相邻的格子都没有匹配字符串中下标为pathLength+1的字符，表明当前路径字符串中下标为pathLength的字符在矩阵中的定位不正确，我们需要回到前一个字符(pathLength-1)，然后重新定位。
一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置

64.机器人的运动范围

地上有个m行n列的方格。一个机器人从坐标(0,0)的格子开始移动，它每一次可以向左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。
举例分析
例如，当k为18时，机器人能够进入方格(35,37)，因为3+5+3+7=18.但它不能进入方格(35,38)，因为3+5+3+8=19.请问该机器人能够达到多少格子？

这个方格也可以看出一个m*n的矩阵。同样在这个矩阵中，除边界上的格子之外其他格子都有四个相邻的格子。
机器人从坐标(0,0)开始移动。当它准备进入坐标为(i,j)的格子时，通过检查坐标的数位和来判断机器人是否能够进入。如果机器人能够进入坐标为(i,j)的格子，我们接着再判断它能否进入四个相邻的格子(i,j-1)、(i-1,j),(i,j+1)和(i+1,j)。

65.剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

下面是分析：
首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
当然也可能有4，但是4=2x2，我们就简单些不考虑了。
5<2 x 3,6<3 x 3,比6更大的数字我们就更不用考虑了，肯定要继续分。
其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2x2x2<3x3，那么题目就简单了。**
**直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。**
**由于题目规定m>1，所以2只能是1x1，3只能是2x1，这两个特殊情况直接返回就行了。
乘方运算的复杂度为：O(log n)，用动态规划来做会耗时比较多。