Leetcode1 全排列、全排列II、旋转数组

主要总结做过的四道题目：

全排列，全排列II，寻找旋转数组中的最小值，搜索旋转数组

全排列这道题主要需要明确排列过程中的递归树的结构，递归树的结构是这样：

虽然这道题也可以通过交换数组下标对应的元素实现不同的组合，不过我觉得这种事方式不容易理解也不容易拓展。 这种递归树的思想主要是尝试每一种可能的元素分别放在字符串的第0到第n-1个下标，同时需要记录哪些字符已经被放置。这样就可以写出代码：

在全排列II中需要找出不同的字符组合。因为假设存在相同的字符，有些组合会进行重复的尝试。为了避免进行重复的尝试，需要观察递归树

如果C和B相同，则不需要走C的分支。为了让这种判断更加自然和方便，我们首先需要将数组排序，这样相同的字符会接近，如果已经试探过，则直接跳过。 这样在全排列I的基础上，我们需要加一条额外判断：

其实这个条件中!visited[j-1]是最值得玩味的。在我们递归结构中，当访问完成的时候会恢复现场，visited，perms都会恢复状态，当visited[j-1] = false时，说明前一个字符的后续组合已经被记录了，就像上图中的AB节点和其子树。

寻找旋转数组的最小值：

当数组经过了若干次旋转，可能的情况有三种：

上图中（1）此时，通过左右下标构成的子数组是递增序列，最小值在【中】的左边，收缩右边

上图中（2）此时通过“断崖”分割的左边整体会高于断崖的右边，最小值在中间的左边，收缩右边

上图中（3）和上面类似，最小值在【中】的右边，收缩左边。

从上面三种情况看来，情况1、2都可以通过对比【中】和【右】进行界定，两者可以合并。

下面具体来分析为什么这个代码可以这么写：

  因为使用mid = left + (rigth - left) / 2，会使得mid的值更接近left 。

当数组长度等于1时，left = mid = right，left和right都保存了数组的最小值

当数组长度等于2时，left = mid = right-1 ，若nums[mid] < nums[right] right = mid=left，退出循环；其他情况时，left = mid + 1 = right，退出循环，left和right都保存了最小值的下标。

对于搜索旋转数组中的最小值，直接找到数组的最小值下标，划分成两个数组就可以解决了。