技术交流QQ群:，欢迎你的加入！

欢迎关注我的微信公众号：CurryCoder的程序人生

1.滑动窗口的最大值（剑指offer原59题）

• 解题思路：其实是一个队列的问题，用一个队列去维护当前窗口中的所有元素；首先将超出窗口中的队头元素先删掉，然后将新的元素插入当前窗口中，插入时要判断新插入的元素与队尾元素的大小，如果队尾元素较小，则先删除队尾元素再插入。

2.n个骰子的点数，这里求的是扔n次骰子，n次中骰子点数之和是s的，所有方案可能的数！(与剑指offer60题有点差别！)

• 解题思路：每次扔骰子，最小值是1，最大值是6；所以扔n个骰子在地上后的，最小值就是n，最大值就是6*n。dfs()算法的思路： // dfs方法来解决：注意两点，第一是状态的表示是什么(从输出中来)？第二是按照什么顺序来计算第一步中的状态？ res += dfs(n - 1, sum - i); // 热狗法：最后一次骰子点数已经确定时，则只需要计算前面投了n-1次骰子，总和是s-i的情况下，一共有多少种方案。
• 动态规划算法dp的思路： // dp方法来解决：注意三点，第一是状态的表示是什么(从输出中来)？第二是如何计算第一步中的状态？第三是边界问题

• 解题思路：模拟人的想法，先将除去了大小王之外的牌拿过来，如果有相同元素，则一定不是顺子！如果没有任何两个元素相同，看一下牌中最小值与最大值的差距是否在4以内。如果满足条件，则可以将缺失的部分用大小王来进行填补。 // 从扑克牌中随机抽5张牌，判断是不是一个顺子。

4.圆圈中最后剩下的数字(剑指offer原62题)----约瑟夫环问题

• 解题思路：f(n,m)表示总共n个数字，每次报到数字m时，就将此数字从环中删除,最后剩下的数字。f(n-1,m)表示从剩下的n-1个数字中，每次报到数字m时，就将此数字从环中删除，最后剩下的数字。观察f(n,m)与f(n-1,m)之间的关系，可知f(n,m) = (f(n-1,m) + m) % n,其中边界条件是f(n==1, m) = 0;

5.股票的最大利润（剑指offer原63题）

• 解题思路：找出前i天的最小值，利用一个变量minValue来存储。第i天卖出的价格是nums[i]，最大利润res是等于第i天卖出价格与前i天中价格最低时买入的价格之差，此时获得的利润是最大的。

6.求1+2+3+...+n，不能使用乘除法和各种循环、判断语句(剑指offer原64题)

• 解题思路：使用递归的思路来写，但是将当中的if语句，改成&&运算符。

7.不用加减乘除做加法(剑指offer原65题)

• 解题思路：模拟计算机中的加法A + B，结果是CD。其中C是十位，D是个位。A和B对应位上的取值有四种(0 0、0 1、1 0、1 1)，C上的结果是(0 0 0 1),D上的结果是(0 1 1 0)。可以将C上的结果看出(A对应位上的取值 & B对应位上的取值)；将D上的结果看出(A对应位上的取值 ^ B对应位上的取值)。因此，可以将多位数相加A + B可以看出是A + B=

8.构建乘积数组(剑指offer原66题)[不能用除法、只能开一个数组]

9.把字符串转换成整数(剑指offer原67题)

• 解题思路：处理好各种边界问题！ // 忽略完行首的空格后，可能有-/+的符号

10.树中两个结点的最低公共祖先(剑指offer原68题)

• 解题思路：给出的两个结点的位置可能有两种情况，一种是两个结点出现在一个结点的左右两个子树上；另一种是一个给定的结点出现最低公共祖先节点上，另一个给定的结点出现在左子树或右子树上！
  具体的方法是：先遍历左子树，检查是否有给定的两个结点p、q；再遍历右子树，检查是否有给定的两个结点p、q。如果左右子树中同时出现了p、q，则当前结点就是需要返回的就是最低公共祖先结点；如果只在左子树或右子树中出现p、q，则返回值就是p、q的最低公共祖先。

11.数字在排序数组中出现的次数(剑指offer原53题--题目一）

• 解题思路：二分法解决！就是此数字第一次出现的位置与此数字最后一次出现的位置，两者之间的数的个数就是该数字出现的次数！

• 题目要求的是：长度为n的数组,将其中的一个数删掉，只剩下n-1个数了。将剩下的n-1个数作为程序的输入，找出被删除的那个数！
• 解题思路：先计算0到n-1中的n个数的和，再减去当前序列中的每个数，也就可以得到答案了。

13.数组中数值和下标相等的元素(剑指offer原53题---题目三)

• 解题思路：因为给定的数组nums具有单调递增的性质，可以使用二分查找，时间复杂度是O(logn)。考察数组nums[i]-i是否具有单调性。即（nums[i]-i >= nums[i-1] - (i-1)是否成立？）

14.二叉搜索树的第K个大的结点(剑指offer原54题)

• 解题思路：先对二叉搜索树进行中序遍历，每遍历到一个结点后，就对K进行减一操作。直到k减小到0后，就已经找到了第K个大的结点。

• 解题思路：深度就是找出从根结点到叶子节点的路径最长长度！具体就是找出根节点的左右子树两者中更长者的深度+1，即二叉树的深度。左右子树的深度用递归的方法来求解，当递归到叶子节点时，递归停止！

• 解题思路：利用上一题的思路，求出左右子树的深度之差是否是大于1的，如果所有点的深度差都不大于1的话，则是平衡二叉树；如果任意一个结点的左右子树深度之差大于1，则一定是非平衡二叉树!

17.数组中只出现一次的两个数字(剑指offer原56题)

• 原题是：一个数组中除了两个数字之外，其他数字都出现了2次。利用程序找出这两个只出现一次的数字！
• 先考虑一种简单的情况，数组中除了一个数字只出现一次外，其余数字都出现了2次，找出这个只出现一次的数字。利用异或运算的特点，所有出现两次的数字异或时都被消成0，再将异或结果与只出现一次的数字进行异或，结果就是我们要找的数字。
• 本题中只出现一次的数字有两个，如何找出这两个只出现一次的数呢?利用上面一样的操作，对所有的数字执行异或操作，得到的结果是两个只出现一次的数字的异或，由于两个数字都只出现一次。因此，最终的异或结果肯定不等于0。因为两个只出现一次的数字的异或的结果不等于0，所以异或结果的二进制表示中肯定有一位是1。假设异或结果中的第3位是1，则两个只出现一次的数字二进制表示的第3位一定是不相同的。此时，将原始数组中所有数字划分成两个集合，划分的依据就是看数组中每个数字的第3位是0还是1。因此，两个只出现一次的数字一定不在同一个集合中！所有出现两次的数字一定在同一个集合中！此时，两个集合中的数字就转化成最开始讨论的一种简单情况的例子。

18.数组中唯一只出现一次的数字(剑指offer原56题--题目2)

• 原题目：一个数组中除了一个数字只出现一次外，其他数字都出现了三次，找出那个只出现一次的数字。
• 解题思路：有限状态机原理，初始的状态是(ones=0,twos=0);输入的数字的二进制表示中某一位是1时，状态转移成(1,0),接着数字的二进制表示中某一位仍然是1时，状态转移成(0,1),接着数字的二进制表示中某一位继续是1时，状态转移成(0,0)。也就是每三个状态构成一个循环；当输入的数字的二进制表示中某一位是0时，从初始的状态是(ones=0,twos=0)转移至自身(0,0)；当所有的输入数字中某一位出现次数是%3余1时，状态就转移到(1,0)；当所有的输入数字中某一位出现次数是%3余0时，状态就转移到(0,0)状态。ones就代表了上面两种情况的结果。数组中唯一只出现一次的数字。

• 解题思路1：暴力解法，先依次遍历每个数字，遍历到某个数字时，固定这个数字。再依次判断数组中其余的n-1个数字与它的和是否等于target。
• 解题思路2：对第二重循环进行优化，第二重循环的目的是判断对于j < i这个范围内，是否存在一个数字nums[j]使得target - nums[i] == nums[j]成立。因此，可以使用哈希表来统计数字nums[j]是否出现从而来优化，使得时间复杂度变成O(n)。

• 原题：输入一个正数s,输出所有和为s的连续正数序列，序列中至少含有两个数。
• 解题思路：暴力方法是给出区间的起点i,再给出区间的终点j。利用求和公式计算出区间[i,j]中数字的和是否为s，时间复杂度是O(n2)。改进的方法是：假设区间[i,j]中数字的和是s，当区间左端点i向右移动到i1时，区间的右端点j也会向右移动到j1，如果右端点j向左移动到j2，则区间[i1,j2]中的数字之和一定是小于s的**。总结起来就是使用双指针算法，时间复杂度变成O(n)。

• 原题：输入一个句子，翻转句子中单词的顺序，但每个单词内的字母顺序不变。
• 解题思路：先用双指针i和j，将整个句子的每个单词以字母为单位进行翻转；然后对句子的每个单词进行翻转。

• 原题是：将字符串中的前面的前n位移动到字符串的尾部。
• 解题思路：和上一题一样的思路，先对整个字符串进行翻转。然后将翻转后的结果分成两个部分：前str.size() - n个字符和倒数n个字符，然后分别对上面的两部分进行翻转即可。

23.数字序列中某一位的数字(剑指offer原44题)

• 2.确定是几位数的第几个数
• 3.确定那个数的第几位
• 详细过程：首先要确定第n位对应的数字在什么范围内，也就是确定第n位对应的数字是几位数。因为一位数有10个，占10位，两位数有90个，占180位，三位数有900个，占2700位。假设输入的是第1000位，则第1000位对应的应该是一个三位数（因为 = 720 < 2700）；然后确定第1000位对应的是哪个三位数上的某一位。因为经过上一步的分析可知，输入的第1000位出现在两位数之后的第720位，因为三位数每个数占3位，所以输入的第1000位对应的应该是第240个三位数中的某一位！由于三位数从100开始，所以第240个三位数是100 + 240 - 1 = 339；最后确定对应是339中的哪一位（因为720 / 3 = 240，所以应该对应339的最后一位9） // 确定n对应是几位数 // 确定是几位数中的哪个数 // 确定那个数的第几位

24.把数组排成最小的数(剑指offer原45题)

• 解题思路：首先在数组中定义两个数字之间的小于<关系：即a < b等价于ab < ba。然后将原始的输入数组按照定义的小于关系重新排序，一次拼接派好序后的数组中的数字即可。

25.把数字翻译成字符串(剑指offer原46题)

• 解题思路：大部分计数的问题，可以看成是动态规划的问题。问题的关键是a.状态表示 b.状态如何计算 c.边界怎么定义。f(i)表示前i位数字一共有多少种翻译方式，f(i)
  如何计算？如果将第i位数字单独翻译成一个字母，则f(i)可表示为前i-1位数字一共有多少种翻译方式；如果将第i位和第i-1位数字翻译成两个个字母，则f(i)可表示为前i-2为数字一共有多少种翻译方式。综合上述两种情况,f(i) = f(i-1) + f(i-2)。注意第二种情况：f(i-2)是将第i和第i-1位数字联合起来翻译成字母，因此必须有约束,范围是[10,25]之间。最后，考虑边界f(0) = 1。

• 解题思路：经典的边界问题，还是要考虑三个问题，状态怎么表示；状态的计算问题；怎么定义边界。f[i,j]表示从左上角出发，到达当格子获得的最大价值。状态计算[i, j] = max(f[i-1, j],f[i, j-1]) + gifts[i,j]；边界f[i,0] = f[0, j] = 0。所要求的答案是f[n,m]。

27.最长不含重复字符的子字符串(剑指offer原48题)

• 解题思路：双指针i、j算法，当j指针每向后移动一位时，判断i到j中是否有重复字符，如果出现了重复字符，就将i指向的重复字符删除，同时i指针向后移动一次。当j移动到字符串末尾时，j-i+1的距离就是不含重复字符的子字符串。

• 解题思路：丑数：一个数的质因子中只包含2 3 5的数！首先将1加入丑数集合中去，然后分别用三个i,j,k指针指向1.。其中i表示2，j表示3，k表示5；然后用1分别与i、j、k三个指针相乘，取相乘后所有结果中的最小值放在1的下一个位置。同时，将指针向后移动一个位置。当有多个相等的最小值出现时，需要将多个指针分别向后移动一个位置。依次循环下去，就可以找到整个丑数组成的集合了。（实际上是3路归并排序，将包含因子2的排好序丑数放入一个数组、包含因子3的排好序丑数放入一个数组、包含因子5的排好序丑数放入一个数组；前面的三个数组中，是不包含因子1。然后将三个数组分别除以数字2 数字3 数字5得到的结果仍然是一个丑数序列，将得到的3个丑数序列合并后进行判重处理，就得到了最终结果）

29.字符串中第一个只出现一次的字符(剑指offer原50题---题目一)

• 解题思路：先定义一个hash表，统计每个字符出现多少次，然后从前往后遍历hash表，扫描到第一个值是1对应的key，也就是最终的结果

30.字符流中第一个只出现一次的字符(剑指offer原50题---题目二)

• 解题思路：每次输入字符时，将输入的字符流中出现次数大于1的字符删除。使用队列的数据结构来存储插入的字符！ // 插入字符到一个队列queue中 // 利用hash表判断当前正在插入的字符是否出现在当前的队列中

31.数组中的逆序对(剑指offer原51题）

• 解题思路：暴力做法的时间复杂度是O(n**2)，考虑能否使用归并排序的方法来优化算法为O(nlogn)。首先分别对统计同时在左右两个子序列中一共有多少个逆序对（递归方法）；然后计算逆序对不在同一个子序列时，对第二个序列中的每一个数a[j]，计算第一个序列中一共有多少个数a[i]比a[j]要大。因此一共有r-i+1个数比a[j]]要大！最后的结果是上面三个部分的和。

32.两个链表的第一个公共结点(剑指offer原52题）

• 思路：使用两个指针p和q，p指针指向第一个链表的头结点，q指针指向第二个链表的头结点。当p指针遍历到第一个链表的末尾时，接着回到第二链表的头结点位置；当q指针遍历到第二个链表的末尾时，接着回到第一链表的头结点位置。注意两个指针所走的总距离是相等的！当进行了多次循环后，两个指针一定会在某个结点处相遇，即公共结点。

33.二叉搜索树的后序遍历序列(剑指offer原33题)

• 题目：给定一个数组，判断此数组是否是某二叉搜索树的后序遍历结果！
• 解题思路：先找出数组中的最后一个元素作为树根root，然后找到二叉搜索树的左子树的最后一个位置（左子树中的结点值均小于root，右子树的结点值均大于root）。接着找到二叉搜索树的右子树的最后一个位置。判断结点的值是否满足二叉搜索树的定义！

34.二叉树中和为某一值的路径(剑指offer原34题)

• 解题思路：直接遍历一遍二叉树，当遍历到叶节点时，判断从根节点到当前节点的路径上的节点值之和是否等于给定值。如果等于的话，就记录当前的路径。 // 如果当前节点的左右子树都是空的，则当前节点是叶子节点 // 递归处理左右子树

• 解题思路：第一步将每个节点复制出来，然后将当前节点的next指针指向复制出来的节点；第二步将原先节点p的random指针指向第3个节点；那么，被复制出来的p节点是p->next，其random指针即p->next->random指向p->random->next节点。最后将复制出来的节点全部连接起来！ // 第一步复制所有的节点，并将当前节点指向复制出来的节点 // 第三步将所有复制出来的节点连接起来

36.二叉搜索树与双向链表(剑指offer原36题)

• 解题思路：首先获取根节点；然后分别递归左右子树，左右子树分别返回一个首尾节点(即当前子树中最左边的节点和当前子树中最右边的节点)；接着将三部分拼接起来；最后将左子树的最左侧和右子树的最右侧节点返回就是最后的答案。

• 题目：确保二叉树可以序列化为字符串；并且可以将此字符串反序列化为原始树结构。
• 解题思路：利用二叉树的前序遍历实现从二叉树到字符串的序列化操作；反序列化实现的是从字符串到二叉树的转换，注意将字符串类型的数字转成整数的方法！ // 前序遍历实现序列化

• 题目：输入一组数字(可能包含重复数字)，输出其所有的全排列
• 解题思路：先对输入的数字进行排序，然后开辟与输入一组数字相同长度的数组，接着从输入数字中按顺序取一个数字放在数组的任意一个位置上。接下来，取第二个数字放在数组中剩下空间的任意一个位置上，如果第二个数字与第一个数字值是相同的，则规定第二个数字只能放在第一个数字的后面的位置，依次将输入的数字放入数组中，直到数组的各位都已经占满为止。 // u:当前枚举的位置 start: 当前这个数应该从哪个位置开始枚举？（即上一个数的后一个位置开始枚举） // state: 存储的是状态，表示哪些数被用过

39.数组中出现次数超过一半的数字（寻找数组中的众数）(剑指offer原39题)

• 解题思路：初始化一个计数变量count = 0，然后遍历数组中的每个元素，当val等于第一个元素时，count加1。接着遍历第二个元素，如果第二个元素的值与第一个元素的值相同时，则count加1；如果第二个元素的值与第一个元素的值不同时，count减1；最后遍历完整个数组后，最终结果存储在val变量中。摩尔投票法原理

• 解题思路：维护一个大顶堆，当最小的k个数存放在大顶堆中。遍历输入数组中的每个元素，然后将每个元素与大顶堆中的堆顶元素进行比较，如果比堆顶元素小，就更新堆顶元素。

• 题目：如果从数据流中读出奇数个数值，则中位数就是所有数值排序后位于中间的数值；如果从数据流中读出偶数个数值，则中位数就是所有数值排序之后中间两个数的平均值。
• 解题思路：将当前所有的数维护成两个集合，第一个集合是一个小顶堆，存的是比较大的那一部分数；第二个集合是一个大顶堆，存的是比较小的那一部分数。可以发现，大顶堆的堆顶元素和小顶堆的堆顶元素实际就是输入数据流中间的两个数。规定，数据流中读出的是奇数个数值时，大顶堆比小顶堆中的元素多一个。如何维护这个结构？每次插入一个新的元素到大顶堆中，如果下面大顶堆的堆顶元素比上面小顶堆的堆顶元素的大（即逆序了），则交换；如果下面大顶堆中的元素太多了，就要直接转移当中的一个元素到小顶堆中。

42.连续子数组的最大和(剑指offer原42题)

• 解题思路：s表示遍历到当前数x前一个位置为结尾的子数组的和最大值，s如何更新？当s > 0时，s = s + x；当s <= 0时，s = x；

• 解题思路：假设输入13015，则万位上的1个数：共3016个；千位上的1个数：000-11999，一共有2000个；百位上的1个数：情况有很多种！十位上的1个数：情况有很多种！总结出的一般规律：输入的数字是abcedf，第一种情况：假设c位置上的数字是1，则ab位置上的取值范围是00到ab-1；def位置上的取值范围是000到999，则总方案数是ab*1000。第二种情况：最高位恰好取到ab时，分两种情况讨论。1.c位等于0时，就只有0个1；2.c位等于1时，则def的取值范围是0到def，一共有def+1种方案；3.c大于1时，def位置上的取值范围是000到999，则总方案数是1000！ // 取出n中的每位数字放入number中

• 解题思路：因为反转的是一个单向链表，所以无法直接遍历当前节点的前驱结点，因此利用一个变量pre记录当前节点的前驱结点。然后从头开始遍历给定的单向链表，直到遍历到空结点为止。

45.合并两个排序的链表(剑指offer原25题)

• 解题思路：归并排序的方法来实现即可！ auto cur = dummy; // 因为往合并后的链表中添加元素时，是尾部插入的。因此，需要一个cur指针来记录当前链表的尾结点在哪。 // 将两个链表中更长者中剩余的部分链接到已合并链表的末尾

• 解题思路：类比字符串匹配的方法，从根结点root开始枚举，看一下树根root是否是子树的根节点；不是的话，判断树的左孩子结点是否是子树的树根结点；不是的话，判断树的右孩子结点是否是子树的树根结点。然后利用前序遍历树和子树即可。

• 解题思路：所有结点的左右孩子结点都交换了一下，遍历树中的所有结点，每次遍历完后，将每个结点的左右孩子结点交换一下就可以了。

• 解题思路：除了根节点之外，其他的每个结点它的左边的结点和右边的结点是对应的！并且左边结点的左孩子和右边结点的右孩子是对称的，左边结点的右孩子和右边结点的左孩子是对称的！

• 解题思路：顺时针定义四个方向：右 下 左 上；先按右的方向走，走到不能走为止；然后向下移动一个位置，按下的方向走，走到不能走为止；再向左移动一个位置，按左的方向走，走到不能走为止；最后向上移动一个位置，按上的方向走，走到不能走为止！直到总完nm步就完成了！不能走的定义是：要么走出了边界，要么你已经走过了这个格子了*。

• 题目：设计一个支持push pop top等操作并可以在O(1)的时间复杂度内检索出最小元素的堆栈。
• 解题思路：利用一个辅助栈(单调栈)来操作。单调栈：即栈中的元素是单调的！维护一个单调栈，单调栈中的元素大小是单独变化的，当插入一个新的元素到主栈中时，将其与单调栈中的栈顶元素进行比较，当插入的元素比单调栈中的栈顶元素大，则不会将新的元素插入到主栈中；当插入的元素比单调栈中的栈顶元素小或者与单调栈中的栈顶元素相等时，则将新的元素插入到主栈中去。

51.栈的压入与弹出序列(剑指offer原31题)

• 解题思路：模拟一遍整个过程，每次往栈里面加一个元素，加完后判断当前栈顶元素是否是当前弹出序列的元素。如果是，则将栈顶元素弹出。当栈里面已经是空时，弹出序列就是合法的，否则就是不合法的!

52.不分行从上往下打印二叉树[层序遍历](剑指offer原32题---题目一)

• 解题思路：宽度优先搜索BFS，利用队列这个数据结构来实现

53.分行从上往下打印二叉树(剑指offer原32题---题目二)

• 解题思路：在队列中增加一个null标记，表示当前层的结点已经全部遍历结束。 if(!t) // t为空时，表示已经遍历完一层

• 解题思路：在上一题的基础上增加一个布尔类型的变量zigzag，当zigzag为true时，表示从右到左打印；zigzag为false时，表示从左到右打印！ if(!t) // t为空时，表示已经遍历完一层

• 解题思路：一般考虑使用宽度优先遍历BFS，不建议使用深度优先遍历DFS。因为深度优先遍历在数据范围比较大时，可能会出现栈溢出！从(0,0)点开始遍历，每次将符合要求的格子加入到队列中去。最后一共遍历完多少个合法的格子，就是我们最终的结果。 // 算出一个数字的各个位置上的数字之和 // 算出一个格子中的各个位置上数字之和

• 题目：给定一个正整数，将此整数划分成若干个更小的正整数的和
  使得划分出来的若干个正整数的乘积最大
• 解题思路：目标：假设输入的正整数是N，拆分成尽可能多的3！。分下面几种情况：1.如果N % 3 == 0，则拆分成若干个3；2.如果N % 3 == 1，则先将N拆分成两个2，剩下的全部拆分成3；3.如果N % 3 == 2，则先将N拆分成一个2，剩下的全部拆分成3；
2。由前面的1和2得到拆分出来的数字一定不包含4和大于等于5的数字；因此可知所有拆分出来的ni不是2就是3。接下来证明拆分出来的数字中，最多只有两个2（因为2*2*2 < 3*3）。

• 解题思路：s += n & 1是先统计n中个位上是数字1的个数，n>>1则是统计完n中个位的结果后，移除n的个位上的数字来进行更新。

• 解题思路：注意处理次方是负数的情况即可！

59.在O(1)的时间复杂度内删除链表结点（剑指offer原18题--题目一）

• 解题思路：此题不能使用常规方法！因为要删除的结点不是链表的最后一个结点，所以下一个结点一定不是空结点。删除的方法是：用下一个结点的值去覆盖当前结点的值，然后将下一个结点的值删掉。这种方法就不需要用到前驱结点了。

60.删除链表中重复的结点（剑指offer原18题--题目二）

• 解题思路：建议凡是可能会把头结点删掉的链表问题，一般来说都会增加一个虚拟头结点来简化代码。使用两个指针，第一个指针p指向上一次保留的结点的最后一个位置，q指向的是下一段的第一个结点，q用来扫描下一段的所有结点。

61.正则表达式的匹配（剑指offer原19题）

• 题目：实现一个函数用来匹配包括.和*的正则表达式。字符.表示任意一个字符；字符*表示它前面的字符可以出现任意次（含0次）。

62.表示数值的字符串（剑指offer原20题）

• 解题思路：分各种情况讨论 // 删除字符串s中的前后空格

63.调整数组顺序使奇数位于偶数前面（剑指offer原21题）

• 题目：输入一个数组，实现数组中数字的顺序，使得所有的奇数位于数组的前半部分；所有的偶数位于后半部分。
• 解题思路：使用双指针，一个指针从前往后，另一个指针从后往前。保证第一个指针前面全部是奇数，第二个指针前面全部是偶数。

64.链表中倒数第k个节点（剑指offer原22题）

• 解题思路：由于单链表不能从后往前遍历的，只能从前往后遍历。因此首先求出整个链表的长度n，求倒数第k个节点相当于求正序的n-k+1个节点，然后从前往后遍历到n-k+1个节点就可以了。

65.链表中环的入口节点（剑指offer原23题）

• 解题思路：使用快慢指针算法，用两个指针first和second分别从起点开始走，first每次走一步，second每次走两步。如果过程中second走到null，则说明不存在环；否则当first和second相遇后，让first返回起点，second待在原地不动，然后两个指针每次分别走一步，当相遇时，相遇点就是环的入口。

66.找出数组中重复的数字（剑指offer原3题---题目一）

• 解题思路：从前往后遍历整个数组中的每个元素，如果元素的取值不在0到n-1范围内，就直接返回-1；如果元素的取值在0到n-1范围内时，检查数组下标是取值为该元素时的数组位置上存储的是哪个数字；如果存储的数字与其在数组中对应的下标相等，则找出了重复的数字，否则将两个位置上的数字进行交换，重复此步骤，直到存储的数字与其在数组中对应的下标相等为止。

67.不修改数组，找出数组中重复的数字（剑指offer原3题---题目二）

• 解题思路：根据抽屉原理，至少有2个数字会重复！利用递归的思想，将这个数组一分为二，分别计算左右子数组两边的长度和元素的个数，至少有一边元素的个数会大于子数组的长度。递归上面的过程即可！

68.二维数组中的查找（剑指offer原4题）

• 解题思路：从二维数组右上角的位置开始查找，如果要查找的目标数字比右上角的数字要大，则目标数字出现在二维数组的右下角位置；如果要查找的目标数字比右上角的数字要小，则目标数字出现在二维数组的左上角位置。

69.替换空格（剑指offer原5题）

• 解题思路：开一个新的字符串，遍历原始的字符串，如果遇到空格字符，就将20%存储在新字符串中；否则，直接存储在新字符串中。

70.从尾到头打印链表（剑指offer原6题）

• 解题思路：先将整个链表遍历一遍，然后将整个链表翻转一下即可。

71.重建二叉树（根据前序遍历和中序遍历来重建二叉树）（剑指offer原7题）

• 解题思路：首先，根据前序遍历确定当前区间的根节点是哪个；然后，根据已经确定的根节点，从中序遍历中找到根节点的位置在哪，从而确定二叉树的左右子树中分别包含的数字；最后，在已经确定的左右子树中递归执行前面的两个步骤，即可重建二叉树。

72.二叉树的下一个节点（剑指offer原8题）

• 题目：给定二叉树中的一个节点，找出中序遍历序列的下一个节点
• 解题思路：分情况进行讨论，情况1：如果给定的节点是存在右子树的，则下一个节点是右子树中最左边的节点；情况2：如果给定的节点是不存在右子树的，又分两种情况讨论：a.如果给定的节点存在父节点，并且给定的节点是父节点的左儿子的话，则下一个节点是给定节点的父节点；b.如果给定的节点存在父节点，并且给定的节点是父节点的右儿子的话，此时沿着父节点向上找，直到找到第一个节点是当前父节点的左儿子时停止，返回父节点。

73.用两个栈实现一个队列（剑指offer原9题）

• 解题思路：先将元素依次压入栈1中，然后逐个弹出栈1中的元素，将每个元素依次压入栈2中。此时，栈2中的栈顶元素就是栈1中的栈底元素，再依次弹出栈2中的元素时，就实现了队列的先进先出功能（最先进入栈1中的元素，最先从栈2中弹出）。

74.斐波那契数列数列（剑指offer原10题）

75.旋转数组的最小数字（剑指offer原11题）

2，两部分是单调的增加。首先将后半部分相同值删除，然后观察剩下的结果可知，所有的元素都比前半部分的第一个元素小。前半部分中后面的值都大于或等于第一个元素。下面就可以使用二分法，找出后半部分中第一个比前半部分第一个元素小的那个数字，就是我们要找的最小数字。

76.矩阵中的路径（剑指offer原12题）

• 解题思路：先枚举所有起点，然后枚举方向。直到走到不能走为止，这样就得到所有的路径。

一般来说，用scanf就得用多线程；不用scanf、非阻塞读取键盘缓冲区就不需要多线程。

当然，你也可以用select反复等待stdin可读，当select返回，就说明用户输入了信息，此时调用getch可以立即返回，不会造成阻塞。

但此时scanf行为可能受stdin缓冲模式（比如是遇到回车才返回可读还是敲一个字符就返回可读）以及scanf本身期望的模式字符串影响（比如用户敲了一个字符，你的scanf却期望他输入一个数字、一个逗号、另一个数字，回车；那么这时候肯定还是要卡住了）——总之，较为复杂的程序很少用scanf，因为它太机械了，和它设想的状况有一点点差异都会搅乱你的逻辑。

然后，需要每隔1s显示数字也很简单，select超时设置为1s就行了。

注意，你要检查select返回信息，确认真正的原因；具体可参考相关文档。

如果select返回原因是超时，那就dispatch到时间显示处理函数；如果返回原因是stdin可读，就dispatch到字符读取处理函数——注意此时在getch之后、重新调用select时要扣除上次显示输出到现在已经流逝的时间，否则时间间隔就不正确了。

当然，如果你搞正式项目的话，可以考虑著名的ncurses文本界面库。它直接内置了一整套机制，你自己就不用操心很多细节问题了。