154. Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.
• Would allow duplicates affect the run-time complexity? How and why?

这一题在LeetCode Find Minimum in Rotated Sorted Array的基础上，增加了元素可能重复的约束，此时二分判断时，会出现中间元素和边缘元素相等的情况，此时就不能判断应该丢弃哪半部分了。比如[3,3,1,3]，中间元素3和右边元素3相等，其实应该丢弃左半部分；又比如[1,3,3]，中间元素3和右边元素3相等，其实应该丢弃右半部分。所以遇到中间元素和边缘元素相等时，无法做决定，那么我们只能移动边缘元素，不断的缩小范围，直到中间元素和边缘元素不等。最坏情况是，所有元素都相等时，退化为线性查找了，所以时间复杂度变为了O(n)。
完整代码如下：

class Solution {
public:
    int findMin(vector<int>& nums)
    {
        int l = 0, r = nums.size() – 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[r])
                l = mid + 1;
            else if (nums[mid] < nums[r])
                r = mid;
            else
                –r;
        }
        return nums[l];
    }
};

本代码提交AC，用时6MS。

二刷。依然是更加鲁邦容易理解的代码，当nums[mid]==nums[r]时，退化为线性查找。

class Solution {
public:
	int findMin(vector<int>& nums) {
		int l = 0, r = nums.size() - 1;
		int ans = nums[0];
		while (l <= r) {
			if (r - l <= 1) {
				return min(nums[l], nums[r]);
			}
			int mid = l + (r - l) / 2;
			if (nums[mid] > nums[r]) {
				l = mid;
			}
			else if (nums[mid] == nums[r]) {
				--r;
			}
			else {
				r = mid;
			}
		}
		return nums[l];
	}
};

本代码提交AC，用时16MS。

153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

一个已按升序排列的数组，被循环旋转了若干次，现在要找到其最小值。第一观测题目中的例子，因为数组是按升序排列的，但是旋转的分界点（7,0）却是降序，所以我们可以遍历数组，找到这个分界点，那么小的数就是最小值。为了防止旋转之后和未旋转是一样的，预先设置结果为第一个元素。代码如下：

class Solution {
  public: int findMin(vector < int > & nums) {
    int ans = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] < nums[i– 1]) return nums[i];
    }
    return ans;
  }
};

本代码提交AC，用时3MS。

但是这个代码的最坏复杂度是O(n)的，和一个乱序的数组求最小值遍历一次的复杂度是一样的，本解法并没有利用到数组是已排序这个特点。
要想达到比O(n)更好的复杂度，自然的思路是二分查找的O(lgn)。数组4,5,6,7,0,1,2，中间元素为7，7>2，说明旋转分界点在右半部分，令l=mid+1，此时数组变为0,1,2，中间元素为1，1<2，说明右半部分是正常的，令r=mid。如此循环，直到不满足l<r。完整代码如下：

class Solution {
  public: int findMin(vector < int > & nums) {
    int l = 0, r = nums.size()– 1;
    while (l < r) {
      int mid = (l + r) / 2;
      if (nums[mid] > nums[r]) l = mid + 1;
      else r = mid;
    }
    return nums[l];
  }
};

本代码提交AC，用时3MS。

三刷。二分的代码其实很难写得bug free，尤其是上面的代码和正常的二分搜索不太一样。实际上，我们依然可以套用常规二分的方法，只不过需要做两点改动：

1. 更新l或r时，只更新为mid，而不是mid+1或者mid-1。常规二分搜索是要找target，所以当target!=nums[mid]时，可以直接跳过mid，到mid+1或者mid-1，但是这里需要找最小值，那么，mid就有可能是最小值，所以不能把mid跳过。
2. 不跳过mid又可能出现死循环的问题，比如[3,1,2]，nums[mid]<nums[r]，所以r=mid，之后的循环中l和mid都一直等于0，出现死循环。解决的办法也很简单，当r-l<=1时，说明此时最多只有两个数字，简单取min就可以得到最小值了。

这种修改方法解释起来逻辑很清楚，也很容易记忆，完整代码如下：

class Solution {
public:
	int findMin(vector<int>& nums) {
		int l = 0, r = nums.size() - 1;
		int ans = nums[0];
		while (l <= r) {
			if (r - l <= 1) {
				return min(nums[l], nums[r]);
			}
			int mid = l + (r - l) / 2;
			if (nums[mid] > nums[r]) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
		return nums[l];
	}
};

本代码提交AC，用时0MS。

四刷。上述解法还是有点怪，为什么是比较nums[mid]和nums[r]呢，而不是比较nums[mid]和nums[l]呢？后者是否可行，事实上是可行的。

基本思想：如果数组没有旋转，则应该满足nums[l]<nums[m]<nums[r]。上述思路是，如果数组选择了，则找到的m可能不满足上述条件，如果不满足nums[m]<nums[r]，即上述if(nums[mid]>nums[r])，说明右半部分违反顺序，最小值应该在右半部分l=mid。这种解法是找违反顺序的，然后在违反顺序的区间进一步查找。

另一种思路是，找不违反顺序的，比如如果满足nums[l]<nums[r]，则说明左半部分满足顺序，所以最小值应该在右边，同样有l=mid。但是这里有一个问题，就是如果数组旋转之后和没旋转是一样的，比如是[1,2,3]，则左边没违反顺序，在右边找最小值，只能找到2，答案错误。所以需要在开头加一个判断，即如果数组头<尾，则说明数组旋转前后是一样的，直接输出头元素为最小值。完整代码如下：

class Solution {
public:
    int findMin(vector<int>& numbers)
    {
        int n = numbers.size();
        int l = 0, r = n - 1;
        if (numbers[l] < numbers[r])
            return numbers[l]; // 注意这一句
        while (l <= r) {
            if (r - l <= 1)
                return min(numbers[l], numbers[r]);
            int m = l + (r - l) / 2;
            if (numbers[l] < numbers[m]) { // 左边有序，在右边找
                l = m;
            }
            else { // 左边无序，在左边找
                r = m;
            }
        }
        return 0;
    }
};

本代码提交AC，用时4MS。

LeetCode Elimination Game There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list. Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers. We keep repeating the steps again, alternating left to right and right to left, until a single number remains. Find the last number that remains starting with a list of length n. Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6

LeetCode Repeated Substring Pattern Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000. Example 1:

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Input: "aba"
Output: False

Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

LeetCode Flatten Nested List Iterator Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a list — whose elements may also be integers or other lists. Example 1: Given the list [[1,1],2,[1,1]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1]. Example 2: Given the list [1,[4,[6]]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

89. Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

格雷码是这样一种编码：第一个数为0，后面每个数和前一个数在二进制位上只相差一位。现在给定二进制编码为n位，要求输出一串格雷码。
在不了解格雷码的情况下，可以单纯根据上面格雷码的定义来列出这一串格雷码，我们需要尝试依次翻转n位中的每一位，如果翻转之后得到的编码之前没有出现过，则翻转成功，接着进入下一次尝试，直到产生所有格雷码。
假设一个二进制数为x，则翻转其第i位之后的二进制数为(x&(~(1 << i))) | (~x)&(1 << i)，还是有点复杂的。
这种思路可以用递归的方法实现，完整代码如下：

class Solution {
public:
    void work(vector<int>& ans, unordered_set<int>& codes, int gray, int n)
    {
        for (int i = 0; i < n; ++i) {
            int new_gray = (gray & (~(1 << i))) | (~gray) & (1 << i); // flip i-th bit
            if (codes.find(new_gray) == codes.end()) {
                codes.insert(new_gray);
                ans.push_back(new_gray);
                work(ans, codes, new_gray, n);
                break;
            }
        }
    }
    vector<int> grayCode(int n)
    {
        vector<int> ans = { 0 };
        if (n == 0)
            return ans;
        unordered_set<int> codes = { 0 };
        work(ans, codes, 0, n);
        return ans;
    }
};

本代码提交AC，用时6MS。
查看格雷码的维基百科，有好多种方法都可以生成格雷码序列，其中一种很有意思，可以根据二进制长度为n-1的格雷码序列生成二进制长度为n的格雷码序列，如下图所示，这种方法叫做镜射排列。

仔细观察会发现，n长的格雷码序列的前一半序列和n-1长的格雷码序列，在十进制数上是完全一样的，二进制数上也只是多了一个前导零；而后半序列是n-1长的格雷码序列镜面对称之后，加上一位前导1得到的。所以很容易可以写出镜射排列的代码：

class Solution {
public:
    vector<int> grayCode(int n)
    {
        vector<int> ans = { 0 };
        if (n == 0)
            return ans;
        ans.push_back(1);
        for (int i = 2; i <= n; ++i) {
            int sz = ans.size();
            while (sz–) {
                ans.push_back(ans[sz] | (1 << (i – 1)));
            }
        }
        return ans;
    }
};

本代码提交AC，用时3MS。

LeetCode Linked List Random Node Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen. Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space? Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

LeetCode Decode String Given an encoded string, return it’s decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer. You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4]. Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c][/c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

LeetCode Convert a Number to Hexadecimal Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used. Note:

1. All letters in hexadecimal (a-f) must be in lowercase.
2. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.
3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
4. You must not use any method provided by the library which converts/formats the number to hex directly.

Input:
26
Output:
"1a"

Input:
-1
Output:
"ffffffff"