Leetcode

数组

☑ Maximum Gap 一个无序的数组，在线性时间内，找到排好序后，相邻两个元素之间差值的最大值。
- 讨论区题解思想是，得到最大值 maxv 和最小值 minv 后，可确定最大差值的下限为 L = (maxv - minv) / (N - 1) 。将[minv, maxv] 等距分割成 N - 1 段（或者更多的段，因为每段距离只要短于L，就不需要考虑段内的差值，因此对结果都不会有影响），记录每一段的最大值和最小值，最终比较某段的最小值与它前面一段的最大值之差，最大的差即为答案。
- 基数排序
- 如果是求差值的最小值呢？
- 脑洞：任意两个元素差值的最大值，也就是最大和最小值的差。可以用最大子数组的方法做。

代码

int maximumGap(std::vector<int> &num) {
	for(unsigned bit = 0; bit < 31; bit++)
	std::stable_partition(num.begin(), num.end(), [bit](int a){
		return !(a & (1 << bit));
	});
	int difference = 0;
	for(std::size_t i = 1; i < num.size(); i++) {
		difference = std::max(difference, num[i] - num[i-1]);
	}
	return difference;
}

☑ Search for a range 有序数组里的 lower_bound 和 upper_bound
- 突然发现自己好像还不会这个。想了一下也没想出来，应该是二分查找稍微变形一下
- 盯着代码看，就想出来了。找上下界与一般二分查找的不同之处是，在找到目标元素后是否还继续寻找。
- 此处的解释比较严谨，要搞明白！其实代码可以很简单，但是需要复杂的证明，说明为什么正确。相比之下我的代码更加直接，只是有些复杂。 Bug多多。

代码

class Solution {
	public:
		int lower_bound(int A[], int n, int target)
		{
			int lo = 0, hi = n - 1, mid;
			while(lo <= hi)
			{
				mid = lo + (hi - lo)/2;
				if(A[mid] == target)
				{
					if(mid == 0 || A[mid - 1] < A[mid])
					{
						return mid;
					}
					else
					{
						hi = mid - 1;
					}
				}
				else if(A[mid] > target)
				{
					hi = mid - 1;
				}
				else
				{
					lo = mid + 1;
				}
			}
			return -1;
		}
		int upper_bound(int A[], int n, int target)
		{
			int lo = 0, hi = n - 1, mid;
			while(lo <= hi)
			{
				mid = lo + (hi - lo)/2;
				if(A[mid] == target)
				{
					if(mid == n - 1 || A[mid + 1] > A[mid])
					{
						return mid;
					}
					else
					{
						lo = mid + 1;
					}
				}
				else if(A[mid] > target)
				{
					hi = mid - 1;
				}
				else
				{
					lo = mid + 1;
				}
			}
			return -1;
		}
		vector<int> searchRange(int A[], int n, int target) {
			vector<int> range;
			range.push_back(lower_bound(A, n, target));
			range.push_back(upper_bound(A, n, target));
			return range;
		}
};

☑ kth-largest-element-in-an-array 数组第ｋ大元素
基于partition的查找。可以自己实现，也可以直接调用 nth_element
基于堆排序。可以使用 priority_queue
基于 multiset ，也即二叉查找树。

代码

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
		int res;
		int n = nums.size();
		int lo = 0, hi = n - 1;
		int pos;
		while(lo < hi) {
			pos = lo;
			for (int i = lo; i < hi; ++i) {
				if(nums[i] > nums[hi]) {
					swap(nums[pos], nums[i]);
					++pos;
				}
			}
			swap(nums[pos], nums[hi]);
			if(pos - lo == k - 1) return nums[pos];
			else if(pos - lo < k - 1) {
				k -= (pos - lo + 1); // 必须排除pivot元素，否则会造成死循环。
				lo = pos + 1;
			}
			else {
				hi = pos - 1;
			}
		}
		assert(lo == hi);
		return nums[lo];
    }
};

✓ rotate-array 数组循环移位
- 方法一：使用额外的空间，B[(i + k) % n] = A[i]
- 方法二：三次反转。 reverse(A, 0, k); reverse(A, k, n); reverse(0, n);
- 方法三？

find-minimum-in-rotated-sorted-array 找到循环移位后的数组的最小值，数组元素无重复
- 二分查找的变形。
- 但还是有两种不同的思路：
  - 思路一：以A[0]为分界，如果A[mid] >= A[0] ，说明是在前段数组中，那么令lo = mid，即低指针始终在前段中；同样可以让高指针始终在后段中。当两个指针相差缩小到1的时候，高指针的位置就是最小元素。
    
    其中， if(num[mid] > num[len - 1]) 也可以和num[hi]比较，目的只是来判断num[mid]是在前半段还是后半段。用 num[0] num[hi]同样能达到目的。但是用num[lo]就会有问题，因为大于num[lo]并不能保证是在前半段，因为lo可能已经到了后半段的第一个元素了。
    
    例如 [2, 1] ，第一次查找，mid = 0，如果是判断 if(num[mid] > num[lo]) ，那么会有 hi = 0 ，最终返回 2 而不是 1。计算改为判断 if(num[mid] >= num[lo]) ，那么考虑测试用例: [3,4,5,1,2] ，(lo, hi, mid) 分别为 (0,4,2), (3,4,3), (4,4,3) ，第二次查找更新时，num[mid] = 1, num[lo] = 1，于是lo += 1，到了2，错过了正确答案。
  - 思路二：二分查找的目的是找到比其前一个数小的数。

思路一的代码

class Solution {
public:
    int findMin(vector<int> &num) {
		int len = num.size();
		int lo = 0, hi = len - 1, mid;
		if(num[0] < num[hi]) return num[0];
		while(lo < hi)
		{
			mid = lo + (hi - lo)/2;
			if(num[mid] > num[len - 1])  // 也可以和num[hi]比较，目的只是来判断num[mid]是在前半段还是后半段。用num[0]，num[hi]同样能达到目的。但是用num[lo]就会有问题，因为大于num[lo]并不能保证是在前半段，因为lo可能已经到了后半段的第一个元素了。
				lo = mid + 1;
			else
				hi = mid;
		}
		return num[lo]; // 也可以返回num[hi]，因为退出时，lo == hi。
    }
};

find-minimum-in-rotated-sorted-array-ii 找到循环移位后的数组的最小值，数组元素可以重复
- 还是同样的思想，但是需要做一步预处理，即首尾元素相同的情况下，可以先移动其中一个idx，使得首尾元素不同，才能继续后面的判断元素在哪一段中。
- 所有元素都相同的情况下，也要正确处理。

代码

class Solution {
public:
    int findMin(vector<int> &num) {
		int n = num.size();
		if(n == 0) return 0;
		int lo = 0, hi = n - 1, mid, t;
		if(num[0] == num[n - 1]) {
			while(num[lo] == num[0] && lo < hi) ++lo;
			//while(num[hi] == num[n - 1] && hi > lo) --hi; // 同时删掉两头相同的元素会有问题，考虑：[1,2,1]
		}
		while(lo < hi) {
			mid = lo + (hi - lo) / 2;
			if(num[mid] > num[n - 1]) {
				lo = mid + 1;
				// t = num[mid];
				// while(num[lo] == t && lo < hi) ++lo; // 找到下一个不等于num[mid]的元素，也可以不要
			}
			else hi = mid;
		}
		return num[lo];
    }
};

✓ search-in-rotated-sorted-array 在循环移位一次的数组中实现二分查找（数组元素无重复）
- A[0]是个分界点。如果 target > A[0]，需要在前一段已排序的数组中二分查找；如果 target < A[0] 则需要在后半段中查找。
- 可以先通过二分查找，确定分界点的位置。

move-zeroes 将数组中所有的0都移动到最后，其它元素的相对位置不变
- idx0 始终代表最前面的 0 的下标，idx1代表非零值的下标。idx1 遍历整个数组，当idx1 < idx0时，就交换两者，然后往后找下一个 idx0。复杂度是线性的。

代码

class Solution {
public:
	void moveZeroes(vector<int>& nums) {
		int n = nums.size();
		int idx0 = 0, idx1 = 0;
		while (idx0 < n && idx1 < n) {
			while (idx1 < n && nums[idx1] == 0) {
				idx1++;
			} // find next non-zero number.
			while (idx0 < n && nums[idx0] != 0) {
				idx0++;
			} // find next zero number.
			if (idx0 < idx1 && idx1 < n) {
				swap(nums[idx0], nums[idx1]);
			}
			idx1++; // look for next non-zero.
		}
	}
};

sort-colors 只包含0,1,2的数组，把0都放在前面，2都放在后面
- 排序是可以的。但是还有线性时间算法。
- 线性算法中，有two-pass的
  - 统计0，1，2的个数，然后重置数组。
  - 根据 move-zeroes 中的算法，把0放到前面，2放到后面。
- 但one-pass的算法也是有的。
  - 方法一：还是基于计数，但在计数的同时把filling的步骤做了，不是简单地设一个counter。假设当前有cnt0, cnt1, cnt2 个 0, 1, 2，如果有三个数组分别有cnt0 + cnt1 + cnt2 个 2，cnt0 + cnt1 个 1，cnt0 个 0 ，那么用后一个覆盖前一个，最后就得到了答案。这种方法可以推广到多个数的情况。
  - 方法二：基于交换。维护 idx0 和 idx2，下标 i 遍历整个数组，遇到 0 就与 idx0 位置处的元素交换，并更新idx0；而此时 i 位置上的新值仍有可能是 0 ，那么就继续此过程。idx2的情况类似。当 i < idx0 或者 i > idx2 时终止。

方法一

class Solution {
public:
	void sortColors(vector<int>& nums) {
		int n = nums.size();
		int n0 = 0, n1 = 0, n2 = 0;
		for(int i = 0; i < n; ++i) {
			if(nums[i] == 0) {
				nums[n2++] = 2; nums[n1++] = 1; nums[n0++] = 0;
			}
			else if(nums[i] == 1) {
				nums[n2++] = 2; nums[n1++] = 1;
			}
			else {
				nums[n2++] = 2;
			}
		}
		return;
	}
};

方法二

class Solution {
public:
	void sortColors(vector<int>& nums) {
		int n = nums.size();
		int idx0 = 0, idx2 = n - 1;
		for (int i = 0; i <= idx2;) {
			if(nums[i] == 0) {
				swap(nums[i++], nums[idx0++]); // 遇到0要i++，因为新的i值是从前面的元素换过来的，不会是0了。
			}
			else if(nums[i] == 2) {
				swap(nums[i], nums[idx2--]); // 遇到2时，不更新i，因为新的nums[i]还有可能是2。
			}
			else i++;
		}
		return ;
	}
};

majority-element 找出数组中出现次数不小于n/2的元素
- Boyer-Moore Majority Vote Algorithm
- 如果有两个元素出现次数相同怎么处理？leetcode上貌似没考虑这种情况。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        int curr = nums[0], cnt = 1;
        for(int i = 1; i < n; ++i) {
            if(nums[i] == curr) ++cnt;
            else if(cnt > 0) --cnt;
            else {
                cnt = 1;
                curr = nums[i];
            }
        }
        return curr;
    }
};

majority-element-ii 找到所有出现次数不少于n/3的元素
- 维护两个cnt，如果新元素不等于被统计的两个值，则两个cnt都减一。
- 如果存在出现次数不少于 n/3 的元素，则必为最后的 num1，num2中，但num1和num2不一定是答案，因此还需要一次遍历，确定是否真的符合条件。

代码

class Solution {
	public:
		vector<int> majorityElement(vector<int>& nums) {
			int n = nums.size();
			vector<int> res;
			if(n == 0) return res;
			int cnt1 = 0, cnt2 = 0;
			int num1, num2;
			for (int i = 0; i < n; ++i) {
				if(cnt1 && nums[i] == num1) ++cnt1;
				else if(cnt2 && nums[i] == num2) ++cnt2;
				else {
					if(cnt1 == 0) {
						num1 = nums[i];
						++cnt1;
					}
					else if(cnt2 == 0) {
						num2 = nums[i];
						++cnt2;
					}
					else {
						--cnt1;
						--cnt2;
					}
				}
			}
			cnt1 = 0; cnt2 = 0;
			for (int i = 0; i < n; ++i) {
				if(nums[i] == num1) ++cnt1;
				else if(nums[i] == num2) ++cnt2;
			}
			if(cnt1 > n / 3)res.push_back(num1);
			if(cnt2 > n / 3)res.push_back(num2);
			return res;
		}
};

链表操作

☑ Merge Two Sorted Lists 合并两个有序的链表。
- 算法很清楚，主要是看怎么实现。如果用p指向要返回的列表当前位置，注意每次更新的时候是先改变p→next，然后p=p→next。

代码

/********************************
	* Author:			bigeast
	* Time:			2015-03-14
	* Description:		AC.
	********************************/
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
	ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
		struct ListNode res(0), *p = &res;
		while(l1 != NULL && l2 != NULL)
		{
			if(l1->val < l2->val)
			{
				p->next = l1;
				l1 = l1->next;
			}
			else
			{
				p->next = l2;
				l2 = l2->next;
			}
			p = p->next;
		}
		if(l1 == NULL)
		{
			p ->next = l2;
		}
		else if(l2 == NULL)
		{
			p ->next = l1;
		}
		return res.next;
	}
};

☑ merge-k-sorted-lists 合并k个有序链表
- 较好的做法是，利用merge2，每次合并两个。例如，list0 到 list4，第一次先合并 list4→list0, list3→list1，然后现在只需要合并 list0, list1, list2
- 复杂度是 O(n logk)

代码

class Solution {
public:
	ListNode* merge2Lists(ListNode *l1, ListNode *l2) {
		if(!l1 && !l2) return NULL;
		else if(!l1) return l2;
		else if(!l2) return l1;
		ListNode res(0), *p = &res;
		while(l1 && l2) {
			if(l1->val < l2->val) {
				p->next = l1;
				l1 = l1->next;
			}
			else {
				p->next = l2;
				l2 = l2->next;
			}
			p = p->next;
		}
		if(!l1) p->next = l2;
		else p->next = l1;
		return res.next;
	}
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		int n = lists.size();
		if(n == 0) return NULL;
		while(n > 1) {
			for(int i = 0; i < n / 2; ++i) { // 注意这里的 n / 2
				lists[i] = merge2Lists(lists[i], lists[n - 1 - i]);
			}
			n = (n + 1) / 2; // 这里必须是 (n + 1) / 2，因为有可能剩下的是一个还未在该轮合并的链表。例如 0, 1, 2中的 1
		}
		return lists[0];
	}
};

sort-list 链表排序
归并方法比较容易实现。
没有想象中的复杂。宜信实习面试的时候遇到了这个问题，没有很好地解决，直接跪掉了。

class Solution {
public:

	ListNode* Merge(ListNode *la, ListNode *lb) {
		ListNode res(0), *p = &res;
		while(la && lb) {
			if(la->val < lb->val) {
				p->next = la;
				la = la->next;
			}
			else {
				p->next = lb;
				lb = lb->next;
			}
			p = p->next;
		}
		if(!la) p->next = lb;
		else p->next = la;
		return res.next;
	}
    ListNode* sortList(ListNode* head) {
		int len = 0;
		ListNode *fast = head, *slow = head;
		if(!head || !head->next) return head;
		fast = fast->next;
		while(fast->next && fast->next->next) {
			fast = fast->next->next;
			slow = slow->next;
		}
		ListNode *A = head, *B = slow->next;
		slow->next = NULL;
		return Merge(sortList(A), sortList(B));
    }
};

reverse-linked-list 链表反转
remove-linked-list-elements 删除列表中某个值的元素
- 标准的做法是设一个prev指针，开始是NULL。
- 二级指针的做法比较难理解，但是优雅。

代码

class Solution {
	public:
		ListNode* removeElements(ListNode* head, int val) {
			for(ListNode **curr = &head; *curr; ) {
				if((*curr)->val == val)
					*curr = (*curr)->next;
				else
					curr = &((*curr)->next);
			}
			return head;
		}
};

☑ reverse-linked-list-ii 将链表中给定范围内的一段进行反转

代码

/**************************************************
* Time: Sat 26 Sep 2015 05:31:40 PM CST
* Author: Bigeast
* Descriptions: 想好，就能写对
* Status: AC
**************************************************/

class Solution {
public:
	ListNode* reverseBetween(ListNode* head, int m, int n) {
		if(m >= n) return head;
		ListNode ahead(0);
		ahead.next = head;
		stack<ListNode *> stk;
		ListNode *ap = &ahead, *p;
		int i;
		for(i = 1; i < m && p; ++i) {
			ap = ap->next;
		}
		p = ap;
		for(; i <= n && p; ++i) {
			p = p->next;
			stk.push(p);
		}
		if(p) { // n is not larger than length.
			ListNode *btail = p->next;
			while(!stk.empty()) {
				ap->next = stk.top();
				stk.pop();
				ap = ap->next;
			}
			ap->next = btail;
		}
		return ahead.next;
	}
};

☑ swap-nodes-in-pairs 将链表中相邻两个节点交换

代码

class Solution {
	public:
		ListNode* swapPairs(ListNode* head) {
			ListNode *p1, *p2, *tmp;
			p1 = head;
			if(p1)p2 = p1->next;
			else return p1;
			if(p2)
			{
				tmp = p2->next;
				p2->next = p1;
				p1->next = swapPairs(tmp);
				return p2;
			}
			else return p1;
		}
};

☑ reverse-nodes-in-k-group 将链表每k个一组进行反转
- 自己的代码写得有点丑。
- 顺便看下Java中节点的定义：

代码

public ListNode reverseKGroup(ListNode head, int k) {
	ListNode curr = head;
	int count = 0;
	while (curr != null && count != k) { // find the k+1 node
		curr = curr.next;
		count++;
	}
	if (count == k) { // if k+1 node is found
		curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
		// head - head-pointer to direct part,
		// curr - head-pointer to reversed part;
		while (count-- > 0) { // reverse current k-group:
			ListNode tmp = head.next; // tmp - next head in direct part
			head.next = curr; // preappending "direct" head to the reversed list
			curr = head; // move head of reversed part to a new node
			head = tmp; // move "direct" head to the next node in direct part
		}
		head = curr;
	}
	return head;
}

ListNode

public class ListNode {
	int val;
	ListNode next;
	ListNode(int x) { val = x; }
}

☑ intersection-of-two-linked-lists 找到两个链表开始相交的地方。
- 方法就是先算出两个链表的长度，然后长的先走一点，与短的对齐，之后两个链表同步，如果有相交，这样一定会碰上。
- 有一点技巧就是，有时不能确定两个数组的长短，但是代码中又需要用到他们的长短关系，这时可以做一次判断，如果长短关系不满足假设，则交换参数的位置多调用一次。

代码

class Solution {
public:
	int listLength(ListNode *root) {
		int res = 0;
		while(root) {
			res++;
			root = root->next;
		}
		return res;
	}
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		int m = listLength(headA), n = listLength(headB);
		if(m < n) return getIntersectionNode(headB, headA);
		ListNode *pA = headA, *pB = headB;
		for(int i = 0; i < m - n; ++i) {
			pA = pA->next;
		}
		while(pA != pB) {
			pA = pA->next;
			pB = pB->next;
		}
		return pA;
	}
};

reorder-list 将链表排列成 1, n - 1, 2, n - 2, 3, n - 3… 的形式。
- 主要是要求常数级别的空间复杂度，而且必须实际对链表操作，而不能更换值。递归的方法每次都要遍历链表找到最后的数，复杂度是 O(n^2) ，会超时。

连续整数

☑ first-missing-positive
- 题目中要求是线性时间，常数空间。如果空间没有要求，可以使用桶排序类似的方法。
- 交换次数是线性的。
- 然而实际的运行时间并没有降低。。

代码

class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
	int n = nums.size();
	if(n == 0) return 1;
	for(int i = 0; i < n; ++i) {
		// 遇到一个元素就把它放到正确的位置。
		while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // 继续为新换到i位置的元素找到合适的位置。
			swap(nums[i], nums[nums[i] - 1]);
		}
	}
	for(int i = 0; i < n; ++i) {
		if(nums[i] != i + 1) {
			return i + 1;
		}
	}
	return n + 1;
}
};

☑ longest-consecutive-sequence
- 用哈希表存储元素，方便查找元素是否存在。 C++ 中使用 unordered_map 代替哈希表。
- 对与每个元素，向前和向后查找相邻的元素是否存在，若存在则从哈希表中删除（避免重复查找）。

子集和DFS

☑ two-sum 找出数组中两个和为target的数（答案唯一）
- 注意看数组是否是有序的。此题是无序，则暴力求解是平方级别的。排序后可以线性找出答案。
- 用HashMap可以达到线性时间复杂度。

☑ 3sum 找到数组中和为0的三元数组
- 先排序，然后枚举最小元素的值A，然后在剩下的数组中找出和为 -A 的两个数。复杂度 O(n^2) 。

☑ 3sum-closest 找到数组中和最接近target的三元数组（答案唯一）
- 与 3sum 思想类似。

☑ 4sum
- 与 3sum 类似，只是枚举的是前两个最小的元素，复杂度 O(n^3) 。注意判重，下标加一的时候看数值是否变化。

代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
		int i, j, k, l;
		int n = nums.size();
		int t;
		sort(nums.begin(), nums.end());
		vector<vector<int>> res;
		vector<int> ans(4, 0);
		for (int i = 0; i < n; ) {
			ans[0] = nums[i];
			for (int j = i + 1; j < n;) {
				ans[1] = nums[j];
				k = j + 1;
				l = n - 1;
				while(k < l) {
					ans[2] = nums[k];
					ans[3] = nums[l];
					t = ans[0] + ans[1] + ans[2] + ans[3];
					if(t == target) {
						res.push_back(ans);
						while(k < n && ans[2] == nums[k]) ++k;
						while(l >= 0  && ans[3] == nums[l]) --l;
					}
					else if(t < target) {
						while(k < n && ans[2] == nums[k]) ++k;
					}
					else {
						while(l >= 0  && ans[3] == nums[l]) --l;
					}
				}
				while(j < n  && ans[1] == nums[j]) ++j;
			}
			while(i < n  && ans[0] == nums[i]) ++i;
		}
		return res;
    }
};

☑ generate-parentheses 生成所有的n对括号序列
保证开括号个数始终大于闭括号。

代码

class Solution {
public:
	vector<string> res;
	int N;
	int dfs(string s, int can_in, int can_out) {
		if(s.size() == 2 * N) {
			res.push_back(s);
			return 0;
		}
		if(can_in > 0) dfs(s + '(', can_in - 1, can_out + 1);
		if(can_out > 0) dfs(s + ')', can_in, can_out - 1);
		return 0;
	}
    vector<string> generateParenthesis(int n) {
		N = n;
		dfs("", N, 0);
		return res;
    }
};

palindrome-partitioning 将字符串分成若干段，每段都是回文子串
- DFS

DP

palindrome-partitioning-ii 一个字符串最少分成多少段，可以使每段都是回文子串

longest-palindromic-substring 最长的回文子串
- O(n^2) ：枚举回文子串的中间位置，向两边扩张，直到不再回文。更新长度。注意奇偶的情况要分开做。
- 更高效的做法是，实时更新当前的最大长度maxLen，在新的字符加入时，只检查以该字符结尾的长度为 maxLen + 1 和 maxLen + 2 的串是否是回文的。

edit-distance 通过删除、替换、添加字符，把str1变为str2的最小操作步数
- f[i][j] 表示 str[1…i] 与 str2[1…j] 之间的最小编辑距离。（str下标从1开始）
- f[i][0] = i, f[0][j] = j;
- 如果str1[i] == str2[j], 则 f[i][j] = f[i - 1][j - 1]
- 如果删除str1[i]，则编辑距离 f[i][j] = f[i - 1][j] + 1
- 如果添加str2[j]，则编辑距离 f[i][j] = f[i][j - 1] + 1
- 如果替换str1[i]，则编辑距离 f[i][j] = f[i - 1][j - 1] + 1

maximal-rectangle MxN的0-1矩阵，求最大的矩形1块的面积
用f[i][j]代表以 m[i][j] 结尾的最大面积，问题转化为如何从 f[i - 1][j - 1], f[i - 1][j], f[i][j - 1] 得到 f[i][j]。
面积不能给出有用的状态转移信息。于是想到要保存最大矩形的宽和高。但是面积一定的情况下，宽高可以是不唯一的，而不同的宽高会影响到状态的转移结果。重新陷入僵局。

其它

word-ladder 起始单词到终止单词，每次只允许改一个字母，且中间单词必须在给定的字典中，求最少的变换次数
- O(n^2) 时间建立一个图。然后广搜。

☑ palindrome-number 判断是否是回文数字，不能使用额外的空间。

the-skyline-problem 柱状图的轮廓
- 记得有一种做法是把一个柱状图看作两个事件，起点和终点。
- 想起来了。

☑ container-with-most-water 一组整数，选择两个围成隔断，求装水最多的隔断
- 要想比首尾两个挡板围成的隔断面积大，宽度肯定不能更大了，需要寻找高度更高的挡板。
- 由于隔断高度 h = min{hl, hr} ，因此在寻找新的面积更大的隔断时，两段高度都要严格大于旧隔断的高度 h 。
- 两个挡板向中间靠拢，比 h 大就停一下，计算新的隔断面积。因为越早遇到的，宽度越大，必须纳入考虑。

代码

class Solution {
public:
	int maxArea(vector<int>& height) {
		int n = height.size();
		int lo = 0, hi = n - 1;
		int ans = 0, h;
		while(lo < hi) {
			h = min(height[lo], height[hi]);
			ans = max(h * (hi - lo), ans);
			while(height[lo] <= h) ++lo;
			while(height[hi] <= h) --hi;
		}
		return ans;
	}
};

☑ trapping-rain-water 一组高度为整数的bar，注水过后能保存多少水
- 思路：分别计算每个bar向前和向后的最大值，取两者中较小的一个，就是该bar上方水的高度。
- 一开始陷入的误区：找的是向前和向后第一次遇到比当前高的bar，但这是局部值，如果后面遇到更高的，这个就没用了。
- 不用考虑水域的连续性，一个bar一个bar来计算结果反而更简单。

代码

class Solution {
public:
	int trap(vector<int>& height) {
		int n = height.size();
		if(n == 0) return 0;
		vector<int> max_forward(n);
		vector<int> max_backward(n);
		max_forward[0] = 0;
		for (int i = 1; i < n; ++i) {
			max_forward[i] = max(height[i - 1], max_forward[i - 1]);
		}
		max_backward[n - 1] = 0;
		for (int i = n - 2; i > 0; --i) {
			max_backward[i] = max(height[i + 1], max_backward[i + 1]);
		}
		int t, res = 0;
		for (int i = 1; i < n - 1; ++i) {
			t = min(max_forward[i], max_backward[i]);
			res += max(t - height[i], 0);
		}
		return res;
	}
};

largest-rectangle-in-histogram 直方图所包含的最大矩形
思路一：f[n] 代表以 height[n] 结尾的矩形的最大面积。则：
- 初始条件：f[0] = height[0]
- 状态转移方程：
  - f[n + 1] = f[n] + hegiht[n + 1]，当 height[n + 1] >= height[n]；
  - f[n + 1] 要重新计算？所以这种状态设置似乎不可行
思路二：f[n] 代表截止 height[n] 所能形成的矩形的最大面积。则：
- 好像更不好做。
思路三：注意到，最终最大矩形肯定跟某个 height[i] 一样高，否则矩形的面积还可以增加。因此对于每个高度，计算以它为中心，高度不小于它的 height 有多少个。
奇怪vim-syntastic 当没有包含algorithm头文件时，vector会出现错误！

O(n^2)的算法,TLE

class Solution {
public:
	int largestRectangleArea(vector<int>& height) {
		int n = height.size();
		set<int> S;
		for(int i = 0; i < n; ++i) {
			S.insert(height[i]);
		}
		int res = 0;
		for(auto item: S) {
			int area = 0;
			int span, idx = 0;
			while(idx < n) {
				span = 0;
				while(item <= height[idx++]) {
					++span;
				}
				if(span * item > res) res = span * item;
			}
		}
		return res;
	}
};

☑ next-permutation 下一个排列
- STL中现成函数 next_permutation
- 手动实现时，额，方法又忘了。
- 步骤是：
  - 找到最后一段不增序列，设为[i, n - 1]
  - 在[i, n - 1]中找到最小的比 nums[i - 1] 大的一个数 nums[j]。
  - swap(num[i - 1], num[j]);
  - 对新的[i, n - 1]区间进行排序。
- 关键是查找nums[j]时，如何用二分方法？upper_bound貌似不能直接用！自己实现又容易出错。在数组递减排序时如何使用lower_bound和upper_bound呢？

代码

class Solution {
	public:
		void nextPermutation(vector<int> &num) {
			int i, j;
			for(i = num.size() - 1; i > 0 && num[i - 1] >= num[i]; --i);
			if(i > 0) {
				for(j = num.size() - 1; j > i && num[j] <= num[i - 1]; --j);
				swap(num[i - 1], num[j]);
			}
			sort(num.begin() + i, num.end());
		}
};

permutations 生成所有排列（元素各不相同，或者当有相同元素的时候，排列可以出现多次）
- 每次调用next_permutation。
- DFS

代码

class Solution {
public:
	void permute(vector<int> &nums, int pos, vector<vector<int>> &res) {
		if(pos == nums.size()) {
			res.push_back(nums);
			return ;
		}
		for (int i = pos; i < nums.size(); ++i) {
			swap(nums[i], nums[pos]);
			permute(nums, pos + 1, res);
			swap(nums[i], nums[pos]);
		}
		return ;
	}
    vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> res;
		permute(nums, 0, res);
		return res;
    }
};

permutations-ii 生成所有排列（元素可以相同）
- 除了调用next_permutation，也可以用DFS的方法，不过要先排序，然后每次找下一个不同的元素。

代码

// https://leetcode.com/discuss/25279/a-simple-c-solution-in-only-20-lines
class Solution {
public:
    void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
        if (i == j-1) {
            res.push_back(num);
            return;
        }
        for (int k = i; k < j; k++) {
            if (i != k && num[i] == num[k]) continue;
            swap(num[i], num[k]);
            recursion(num, i+1, j, res);
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> >res;
        recursion(num, 0, num.size(), res);
        return res;
    }
};

permutation-sequence 返回 1…n 的第k个排列

☑ median-of-two-sorted-arrays 两个有序数组的中值
- 需要有一种比较巧妙的方法来实现，不然会很麻烦。
- 假设两个数组 nums1 和 nums2 的长度分别是 m, n，且 m ⇐ n，则算法复杂度是 O(log m)
- 当 m + n 为奇数时，中位数下标是 (m + n + 1) / 2 ；当 m + n 为偶数时，中位数为 (m + n + 1) / 2 与 (m + n + 1) / 2 + 1 的均值。
- 将两个数组都分成两个部分，最终的中位数是由两个分界处的四个元素决定的。
- 例如设 nums1[0 … i - 1] 为nums1的第一部分，nums2[0 … j - 1] 为nums2的第一部分。则 m + n 为奇数时，如果 max{nums1[i - 1], nums2[j - 1]} 是中位数，充要条件是 i + j = (m + n + 1) / 2 ，且 max{nums1[i - 1], nums2[j - 1]} < min{nums1[i], nums2[j]} 。
- 边界条件好容易出错！！这个太难写对了。
- 答案说明
- 还有一种做法是用两个index分别指向两个数组，每次增加数值小的那个，复杂度O(k)。其实就是模拟归并排序。

代码

class Solution {
	public:
		double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
			int m = nums1.size(), n = nums2.size();
			if(m > n) return findMedianSortedArrays(nums2, nums1);
			//int lo = 0, hi = m - 1;
			int lo = 0, hi = m;
			int i, j; // i, j 分别代表 nums1 和 nums2 在合成数组中的前一半中所占的元素个数，注意不是下标！
			double res1 = 0, res2 = 0, res;
			while(lo <= hi) {
				i = lo + (hi - lo) / 2;
				j = (m + n + 1) / 2 - i;
				if(i > 0 && j < n && nums1[i - 1] > nums2[j]) // nums2 小了，需要减少 nums1 的长度使它增大。
					hi = i - 1;
				else if(j > 0 && i < m && nums2[j - 1] > nums1[i]) // nums1 小了，需要增大。
					lo = i + 1;
				else {
					if(i == 0) {
						res1 = nums2[j - 1];
					}
					else if(j == 0) {
						res1 = nums1[i - 1];
					}
					else {
						res1 = max(nums1[i - 1], nums2[j - 1]);
					}
					if((m + n) % 2 == 0) {
						if(i == m)
							res2 = nums2[j];
						else if(j == n)
							res2 = nums1[i];
						else
							res2 = min(nums1[i], nums2[j]);
					}
					break;
				}
			}
			res = ((m + n) & 1) ? res1 : (res1 + res2) / 2.0;
			return res;
		}
};

☑ combination-sum 从集合中找到和为target的所有子集，每个子集从小到大排序
- 很明显的DFS。
- 速度竟然也不慢。主要是先将集合排序，然后每次从某个下标开始搜索。

代码

class Solution {
public:
	vector<vector<int>> res;
	// 当前序列seq的基础上，目标是target, 新元素从cand[idx]开始
	int dfs(vector<int> &cand, vector<int> &seq, int target, int idx) {
		if(target < 0) return 1;
		else if(target == 0) {
			res.push_back(seq);
			return 0;
		}
		for(int i = idx; i < cand.size() && target >= cand[i]; ++i) {
			seq.push_back(cand[i]);
			dfs(cand, seq, target - cand[i], i);
			seq.pop_back();
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<int> item;
		sort(candidates.begin(), candidates.end());
		int n = candidates.size();
		dfs(candidates, item, target, 0);
		return res;
	}
};

☑ combinationSum-sum-ii 每个元素只能使用一次

代码

class Solution {
public:
	vector<vector<int>> res;
	set<vector<int>> S;
	// 当前序列seq的基础上，目标是target, 新元素从cand[idx]开始
	int dfs(vector<int> &cand, vector<int> &seq, int target, int idx) {
		if(target < 0) return 1;
		else if(target == 0) {
			S.insert(seq);
			return 0;
		}
		for(int i = idx; i < cand.size() && target >= cand[i]; ++i) {
			seq.push_back(cand[i]);
			dfs(cand, seq, target - cand[i], i + 1);
			seq.pop_back();
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<int> item;
		sort(candidates.begin(), candidates.end());
		int n = candidates.size();
		dfs(candidates, item, target, 0);
		for(auto item: S){
			res.push_back(item);
		}
		return res;
	}
};

☑ combination-sum-iii 从1 … 9 中选择 k 个数字，使得和为 n
思路一：由于只有9个数字，问题空间是 2^9 ，因此遍历所有 C(9, 3) 的组合然后看和是否为n即可。
思路二：用DFS，每次分支为选当前的数还是不选当前的数。
一个优化是，可以在开始的时候判断下是否无解。事实证明这是个很有必要的优化。

代码

class Solution {
public:
	vector<vector<int>> res;
	// 从start开始，选n个数，和为target
	void dfs(vector<int> &seq, int start, int n, int target) {
		if(target == 0 && n == 0) {
			res.push_back(seq);
			return ;
		}
		if(target < 0 || n < 0 || start > 9) return ;
		seq.push_back(start);
		dfs(seq, start + 1, n - 1, target - start); // 选第start个数
		seq.pop_back();

		dfs(seq, start + 1, n, target); // 不选第start个数
	}
	vector<vector<int>> combinationSum3(int k, int n) {
		int t = 0;
		for (int i = 0, s = 9; i < k && i < 9; ++i) {
			t += s--;
		}
		if(t < n) return res; // 最大的k个数之和也比n小，就不用搜索了
		vector<int> item;
		dfs(item, 1, k, n);
		return res;
	}
};

☑ minimum-window-substring 给出一个字符串S，一个字母表T，找出S中包含T中所有字符的最短的连续子串（假设最短的只有一个）
- 设T中的字母出现的次数分别为l1, l2, …, ln，设置n个队列，每个队列都最多保存li个元素，存的是字母出现位置的下标。遍历S中的元素，加入队列，当所有队列都满时，查找所有队列头的最小值，与当前S中的下标相减，更新最小窗口宽度。

☐ substring-with-concatenation-of-all-words 字典中单词的长度固定，求字符串中所有只由单词组成的子串

☐ sliding-window-maximum 长度为ｎ的数组，计算出所有k个连续元素中的最大值
- 堆的话，可以更新最大值，但是无法定位到滑出窗口的元素，因此也无法删除。
- 单调队列。队列单调递减，加入元素时，如果后出现的数比先出现的数大，则先出现的数不可能是最大值，故可以删除。因此只需将新元素放到从队尾到队头方向第一个比他大的数后面。要取最大值时，弹出队头元素，并检查其下标是否在窗口中。

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
		deque<int> Q;
		vector<int> res;
		int n = nums.size();
		for (int i = 0; i < n; ++i) {
			while(!Q.empty() && nums[Q.back()] <= nums[i])
				Q.pop_back();
			Q.push_back(i);
			if(i >= k - 1) {
				while(!Q.empty() && i - Q.front() >= k) {
					Q.pop_front();
				}
				res.push_back(nums[Q.front()]);
			}
		}
		return res;
    }
};

☑ minimum-size-subarray-sum 在数组中找到最短连续的子段，其和不小于给定值
- 二分答案的方法， O(nlogn)
- 线性怎么做？还是 Two Pointers ，先添加右端元素，使和大于s，然后从左端开始删掉元素，使和不小于s，更新子段长度，继续在右端添加。

find-the-duplicate-number n + 1个数字全部来自于1 … n，其中有且仅有一个数字出现了不止一次，找到这个数字。要求不能改变数组，不能使用额外空间，复杂度低于平方级别。
- 主要是要求太多：
  - You must not modify the array (assume the array is read only).
  - You must use only constant, O(1) extra space.
  - Your runtime complexity should be less than O(n2).
  - There is only one duplicate number in the array, but it could be repeated more than once.
- 不能改变数组，不能使用额外空间，也就是不能对其进行排序了。
- 也不能用Hash。
- 被我想到了算法！那只能是用二分查找了！注意数字大小也是n，跟数字规模一样大，所以这题的复杂度是基于数字大小的。二分枚举一个数字x，然后遍历数组看有多少个元素小于等于它，如果x小于目标元素，那么小于等于x的元素个数应该是x。否则小于等于x的元素个数就会大于x。
- 线性算法是，将数组看做链表，a_i = j，看做是第i个结点指向第j个节点。整个数组可能会形成很多环，但是没有元素指向最后一个元素，因此从最后一个元素出发，就不会再回来，即遇到了环，那么这个环的起点位置就是所求，因为至少有两个节点指向它。于是问题转换为求链表中环的开始位置。方法就是快慢指针，两者相交于环中的一个节点，然后让其中一个回到起点（节点n + 1），再让两个指针同时走，再次相交的位置就是答案。

☑ jump-game 数组中每个数字代表从该位置开始，能向下走的步数，求能否从第一个走到最后一个
- DFS 会超时。
- 线性的算法是，计算出从起点出发，能达到的最远距离，如果这个距离大于最后一个元素的位置，则可行。

代码

class Solution {
public:
    bool canJump(vector<int>& nums) {
		int n = nums.size(), maxlen = 0;
		for (int i = 0; i <= maxlen && i < n; ++i) {
			maxlen = max(maxlen, nums[i] + i);
		}
		return maxlen >= n - 1;
    }
};

jump-game-ii 求上题中，跳到最后一个元素时，中间节点最少的那个路径
- BFS超时了。没想到这题这么简单，不像Hard。
- 每步都会有一个最长距离，每次更新这个最长距离，看什么时候终点落在这个距离范围内。

代码

class Solution {
    public:
        int jump(vector<int>& nums) {
            int n = nums.size();
			int start = 0, end = 0;
			int maxv, steps = 0;
			while(end < n - 1) {
				maxv = start + nums[start];
				for (int i = start + 1; i <= end; ++i) {
					if(maxv < i + nums[i])
						maxv = i +nums[i];
				}
				start = end + 1;
				end = maxv;
				++steps;
			}
			return steps;
        }
};

Careercup

smallest-range k个有序数组，每个数组拿出一个数，如何使得取出的这k个数区间最小？即 max{a_k} - min{a_k} 最小
- k个idx，分别指向每隔数组的当前位置。每次把值最小的那个idx加1，然后更新区间。

两个数组之间的相同元素（集合的交集）

代码

class Solution {
	public:
		vector<int> setIntersection(vector<int> &A, vector<int> &B) {
			vector<int> C;
			sort(A.begin(), A.end());
			sort(B.begin(), B.end());
			int ia = 0, ib = 0;
			for(int ia = 0, ib = 0; ia < na && ib < nb;) {
				if(A[ia] < B[ib]) ++ia;
				else if(A[ia] > B[ib]) ++ib;
				else {
					C.push_back(A[ia]);
					++ia;
					++ib;
				}
			}
			return C;
		}
};

pots-of-gold 一组整数，A、B两个玩家，每次只能在数组端点处拿走数字，最后拿走数字的人多的剩。谁有必胜策略？
用 f(i, j) 表示面对数组的 i … j，先手玩家所能得到的最高分值。则 f(i, j) = max{arr[i] + min{f(i + 2, j), f(i + 1, j - 1)}, arr[j] + min{f(i, j - 2), f(i + 1, j - 1)}}

代码

function max_coin( int *coin, int start, int end ):
	if start > end:
		return 0
	int a = coin[start] + min( max_coin( coin, start+2,end ), max_coin( coin, start+1,end-1 ) )
	int b = coin[end] + min( max_coin( coin, start+1,end-1 ), max_coin( coin, start,end-2 ) )

k-Palindrome 给定一个字符串，判断是否能通过删除不超过k个字符将其变为回文串
- 定义编辑操作只能是删除，然后计算字符串与其反串之间的编辑距离。复杂度 O(n^2)
- 参考最短编辑距离的方法，在计算f[i][j]时，最多只需用到 f[i - 1][j - k] … f[i - 1][j + k]，因此复杂度可以降到 O(nk)

maxium-sub-array-diff 找到数组中两个不相交的连续子数组，使得它们之间的差值最大
- 两次遍历，第一次从0到n-1，计算 forwardMax[i]，forwardMin[i]；第二次从 n - 1到 0，计算 backwardMax[i]，backwardMin[i]
- 最后一次遍历，计算 max(abs(forwardMax[i] - backwardMin[i + 1]), abs(forwardMin[i] - backwardMax[i + 1]))，并更新答案。

move-negative 把一个数组中的负数放在前面，正数放在后面，且保持相对位置
- 与move-zeros、sort-colors类似，但是应该要求更多一些。貌似没有线性解法？
- Partition操作是稳定的吗？先找出最小的正数，然后根据它来做Partition如何？
- 有个 O(n logn) 的解法，分治，两部分 A，B，负数部分是 A1，B1，正数部分是 A2，B2 ，要将它们合并成 A1 B1 A2 B2 ，即交换 B1 与 A2 的位置，可以用数组循环位移的方法，在线性时间，常数空间内解决。

n-steps-alive NxN的矩阵上，等概率地向四个方向前进一格，如果跳出矩阵就会死掉，给出初始坐标(x, y)，求n步后仍未死掉的概率

perfect-shuffle a1, a2, …, an, b1, b2, …, bn 排列成 a1, b1, a2, b2, …, an, bn
线性时间，常数空间