剑指 Offer 记录
这是毕业找工作时看《剑指 Offer》的记录，记录一下有帮助的题目。
面试题11:旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如,数组｛3,4,5, 1,2｝为｛1,2, 3, 4, 5｝的一个旋转,该数组的最小值为1。
思路
二分。如何判断是否要继续看子数组，看首尾的大小关系。
面试题49:丑数
我们把只包含因子2、3和5的数称作丑数(Ugly Number)。求按从小到大的顺序的第1500个丑数。例如，6、8都是丑数，但14不是，因为它包含因子7。
思路
我感觉非常好的题目，这本书印象最深的题目。这个视频讲的很好：https://b23.tv/oVSKYjM
文字说明：定义数组 \(dp\)，其中 \(dp[i-1]\) 表示第 \(i\) 个丑数，定义 \(3\) 个指针 \(p_2\), \(p_3\) 和 \(p_5\)，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都指向 \(dp[0]\)。更新 \(dp[i]=\min(dp[p_2] \times 2, dp[p_3] \times 3, dp[p_5] \times 5)\)，然后分别比较 \(dp[i]\) 与 \(dp[p_2] \times 2\), \(dp[p_3] \times 3\), \(dp[p_5] \times 5\) 是否相等，若是，则对应的指针加 \(1\)。
面试题23：链表中环的入口节点
如果一个链表中包含环，如何找出环的入口节点。
思路
标准的快慢指针应用。放在这里也是提醒一下快慢指针这个东西。设置快慢指针，快指针每次走一步，慢指针每次走两步，假如链表中有环，它们一定在环中相遇。