剑指offer11~21题

11. 旋转数组的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路：
题目中的“非减”的意思就是说前一个数要小于或者等于后一个数，不要理解成“非递减”了。
二分法思想：
在一个有序数组中查找一个元素可以用二分查找，二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度都为 O(logN)。

本题可以修改二分查找算法进行求解：

当 nums[m] <= nums[h] 的情况下，说明解在 [l, m] 之间，此时令 h = m；
否则解在 [m + 1, h] 之间，令 l = m + 1。

上面的解法如果遇到一个特殊情况还是可能会出问题，例如对于数组 {1,1,1,0,1}，满足nums[l] == nums[m] == nums[h]，l、m 和 h 指向的数都为 1，此时无法知道最小数字 0 在哪个区间。（解释：相当于右边的逐渐向上的最高峰等于左边的逐渐向上的最高峰这种特殊情况时）

12. 矩阵中的路径（笔者对这个题也有一些疑问）

题目描述：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。（解释：只要存在这样的路径包含我们输入的字符串全部字符，就说明存在，否则不存在）路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

例如下面的矩阵包含了一条 bfce 路径。

详情参考：
https://github.com/CyC2018/CS-Notes/blob/master/notes/剑指 offer 题解.md#12-矩阵中的路径

14. 剪绳子

解释：为什么尽量拆分成3呢，因为3很特殊，4的话可以拆成22，5的话可以拆成32，更大的数也是可以不断地拆下去。
下图代码是先尽可能的拆出3来，然后再尽可能避免1的出现，拿多出来的1和其中一个3来组成2*2的结果

小疑问：这题还有动态规划法，笔者目前也不是很明白这道题如何进行动态规划?
详情参考;https://github.com/CyC2018/CS-Notes/blob/master/notes/剑指 offer 题解.md#14-剪绳子

15. 二进制中 1 的个数

16. 数值的整数次方

解释：他这个递归解法的时间复杂度是O(logN),因为n每次减小一半，也许有人想说暴力解法，for循环每次乘以x，乘n次不就行了嘛。是的，但是这样的话时间复杂度就不是O(logN)而是O（N）了！

17. 打印从 1 到最大的 n 位数

18.1 在 O(1) 时间内删除链表节点

综上，如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N ~ 2，因此该算法的平均时间复杂度为 O(1)。

18.2 删除链表中重复的结点

题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

19. 正则表达式匹配

小疑问：本题意思没搞明白，感觉题目描述的有问题

20. 表示数值的字符串

题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"±5"和"12e+4.3"都不是。

21. 调整数组顺序使奇数位于偶数前面

题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变