Monthly Archives: March 2017

LeetCode Reconstruct Itinerary

LeetCode Reconstruct Itinerary
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.
Note:

  1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
  2. All airports are represented by three capital letters (IATA code).
  3. You may assume all tickets form at least one valid itinerary.

Example 1:
tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Return ["JFK", "MUC", "LHR", "SFO", "SJC"].
Example 2:
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Return ["JFK","ATL","JFK","SFO","ATL","SFO"].
Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"]. But it is larger in lexical order.


给定一系列机票,每张机票标明了A→B的一段旅程,现在要求把所有的机票旅程连成一条完整的长距离航线,要求起点是JFK。如果有多条合法的航线,则输出字典序最小的那条。
显然要转换为图的问题,每个机场转换为一个点,每张机票转换为一条边,然后从JFK开始DFS,保留每条合法的航线,然后sort取字典序最小的航线。
把问题转换为图不难,使用hash给每个机场编号,然后新建一个图。在图中以JFK开始DFS也不难,每深入DFS一层,机票数目减1,当机票数目为0时,DFS结束,找到一条合法航线。
我一开始是这么做的,但是TLE了,因为这样可能会进行很多次DFS, 找到多条航线,还需要sort取字典序最小的航线。
有没有办法一次找到字典序最小的航线呢,只需要在DFS的时候,每次都从字典序最小的机场开始下一层DFS,这样第一次DFS成功的航线肯定是字典序最小的航线。
所以我们给机场编号的时候,先使用map记录,map会自动按key的字典序从小到大排好。然后遍历map重新编号,并且用hash2记录编号和机场的对应关系。这样,在DFS的时候,从0→n的遍历,就自动是按字典序从小到大遍历。
代码如下:

class Solution {
private:
	bool dfs(string& ans, vector<string>& hash2, vector<vector<int>>& graph, int start, int lines) {
		if (lines == 0) return true;
		int n = hash2.size();
		for (int i = 0; i < n; ++i) { // 字典序从小到大深搜
			if (graph[start][i] > 0) {
				--graph[start][i];
				ans += hash2[i];
				if (dfs(ans, hash2, graph, i, lines - 1))return true;
				++graph[start][i];
				ans = ans.substr(0, ans.size() - 3);
			}
		}
		return false;
	}
public:
	vector<string> findItinerary(vector<pair<string, string>> tickets) {
		map<string, int> hash1;
		vector<string> hash2;
		int cnt = 0, n = tickets.size();
		for (int i = 0; i < tickets.size(); ++i) { // 记录
			hash1[tickets[i].first] = 0;
			hash1[tickets[i].second] = 0;
		}
		for (auto it = hash1.begin(); it != hash1.end(); ++it) {
			it->second = cnt++; // 字典序从小到大编号
			hash2.push_back(it->first);
		}
		vector<vector<int>> graph(cnt, vector<int>(cnt, 0)); // 构图
		for (int i = 0; i < tickets.size(); ++i)++graph[hash1[tickets[i].first]][hash1[tickets[i].second]];
		int start = hash1["JFK"];
		string ans = "JFK";
		dfs(ans, hash2, graph, start, n); // 深搜
		vector<string> Itinerary;
		for (int i = 0; i <= ans.size() - 3; i += 3)Itinerary.push_back(ans.substr(i, 3));
		return Itinerary;
	}
};

本代码提交AC,用时22MS。

LeetCode 132 Pattern

LeetCode 132 Pattern
Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Example 1:

Input: [1, 2, 3, 4]
Output: False
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: [3, 1, 4, 2]
Output: True
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: [-1, 3, 2, 0]
Output: True
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

给定一个数组,问数组中是否存在132这样的子序列。132是指i<j<k,但a[i]<a[k]<a[j]的形式,132就是这样一个例子,中间最大,右边次之,左边最小。
解法1。朴素解法,直接查找是否存在这样的i,j,k。首先找i,即满足a[i]<a[i+1]这样的i。然后找j,我们希望a[j]越大越好,这样的话,才可能找到a[k]<a[j]的k,所以a[j]<a[j+1]时,j++,因为前面有更大的a[j],照样满足a[i]<a[j],还可能更容易找到小于a[j]的a[k]。当确定i,j之后,a[k]就在j后面不断找在a[i]和a[j]之间的数。
代码如下:

class Solution {
public:
	bool find132pattern(vector<int>& nums) {
		int i = 0, j = 0, k = 0, n = nums.size();
		while (i < n) {
			while (i < n - 1 && nums[i] >= nums[i + 1])++i;
			j = i + 1;
			while (j < n - 1 && nums[j] <= nums[j + 1])++j;
			k = j + 1;
			while (k < n) {
				if (nums[k] > nums[i] && nums[k] < nums[j])return true;
				++k;
			}
			++i;
		}
		return false;
	}
};

本代码提交AC,用时299MS。
解法2。使用栈。从数组末尾往前找,我们希望a[j]越大越好,而a[k]最好是次大的,这样a[i]就更容易小于a[k]了。定义一个变量third表示132模式中的第三个数,就是132中的2。初始时令third=INT_MIN。定义一个堆栈stk保存比third大的所有数,如果nums[i]小于third,表示找到了第一个数1,返回true。如果nums[i]大于stk栈顶,表示找到了更大的数,则把stk中的数给third,表示third保存的是次大的数,然后把nums[i]压入stk。
代码如下:

class Solution {
public:
	bool find132pattern(vector<int>& nums) {
		stack<int> stk;
		int third = INT_MIN;
		for (int i = nums.size() - 1; i >= 0; --i) {
			if (nums[i] < third)return true;
			else {
				while (!stk.empty() && nums[i] > stk.top()) {
					third = stk.top();
					stk.pop();
				}
				stk.push(nums[i]);
			}
		}
		return false;
	}
};

本代码提交AC,用时23MS,快了不少。

LeetCode H-Index

LeetCode H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
Hint:

  1. An easy approach is to sort the array first.
  2. What are the possible values of h-index?
  3. A faster approach is to use extra space.

给定一个研究人员的n篇文章及其引用数,求该研究人员的H-index。
一个人的H-index为h说明他有h篇引用数至少为h的论文,比如例子中[3,0,6,1,5]的H-index为3,指他有3篇引用数至少为3的文章,即引用数为3,6,5的3篇文章。
求解方法也不难,先对所有引用数按从大到小排序,然后从大到小累加文章数目,直到引用数小于文章数时停止。代码如下:

class Solution {
public:
	int hIndex(vector<int>& citations) {
		sort(citations.begin(), citations.end(), std::greater<int>());
		int h = 1;
		while (h <= citations.size()) {
			if (citations[h - 1] < h)return h - 1;
			++h;
		}
		return h - 1;
	}
};

本代码提交AC,用时3MS。
还有一种方法是,不排序,使用Hash。先求出最大引用数,然后把相同引用数的文章Hash到同一个位置。最后从引用数大的开始遍历,累加文章数,直到文章数大于引用数时停止。
此时的返回值需要注意,是较大的h-index,即max(h - hash, c)。比如[2,3,3,3],则hash[3]=3,hash[2]=1,当遍历到2时,发现不满足,此时的最大h-index是h-hash=4-1=3。但是如果[2,3,2],则hash[3]=1,hash[2]=2,当遍历到2时,也发现不满足,但此时并不需要完全回退到3,还可以拿一篇2引用的文章,即最大的h-index是c=2。
代码如下:

class Solution {
public:
	int hIndex(vector<int>& citations) {
		int maxC = -1, n = citations.size();
		if (n == 0)return 0;
		for (int i = 0; i < n; ++i)maxC = max(maxC, citations[i]);
		vector<int> hash(maxC + 1, 0);
		for (int i = 0; i < n; ++i)++hash[citations[i]];
		int c = maxC, h = hash[maxC];
		while (c >= h) {
			--c;
			h += hash;
		}
		return max(h - hash, c);
	}
};

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

LeetCode Additive Number

LeetCode Additive Number
Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Follow up:
How would you handle overflow for very large input integers?


给定一个数字字符串,问这个字符串是否是可加的数。一个可加的数是指它可以分割成若干个字符串,每个字符串代表一个数,且这个数列满足斐波那契数列的规律,即后一个数等于前两个数之和。
明显的DFS题。从起点枚举所有可能的长度,转换成数字,然后判断是否等于前两个数字之和。
需要注意的是数组至少要有3个数,且每个数不能有前导0。另外字符串可能很长,导致转换成的数超过int范围,所以用long long和atoll函数。
代码如下:

typedef long long LL;
class Solution {
private:
	bool dfs(const string& num, int start, LL last1, LL last2, int cnt) {
		int n = num.size();
		if (start == n&&cnt >= 3)return true;
		//if (start < n&&num[start] == '0')return false; // "101" is true
		int m = num.size() - start; // left length
		bool ans = false;
		for (int i = 1; i <= m; ++i) {
			if (i != 1 && num[start] == '0')continue; // leading zero
			LL sum = atoll(num.substr(start, i).c_str());
			if (cnt >= 2) {
				if (last1 + last2 > sum)continue;
				else if (last1 + last2 < sum)return false;
				else ans = dfs(num, start + i, last2, sum, cnt + 1);
			}
			else if (cnt == 0)ans = dfs(num, start + i, sum, last2, cnt + 1);
			else if(cnt==1)ans= dfs(num, start + i, last1, sum, cnt + 1);
			if (ans)return true;
		}
		return false;
	}
public:
	bool isAdditiveNumber(string num) {
		return dfs(num, 0, 0, 0, 0);
	}
};

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

LeetCode Count Complete Tree Nodes

LeetCode Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.


计算完全二叉树的节点个数。如果忽略完全二叉树的性质,像普通二叉树那样进行遍历(先序、中序、后序都可以)统计节点个数,会TLE,所以还是需要用到完全二叉树的性质的。
这里的完全二叉树是指除了最后一层,其他层都是满的,并且最后一层所有节点都是靠左的。具体定义可以看维基百科,下图就是一个完全二叉树的例子:

如果二叉树是满的,比如下面这种,且树的高度是h,则树的节点个数等于2^h-1

那么怎样判断一棵完全二叉树是否是满的呢,只需求一下其极左高度lh和极右高度rh是否相等,如果相等,则是满的,可以用上述公式求解节点数。如果不是满的,则在其左右子树中递归求解节点数,再加上根节点这个节点个数1。
代码如下:

class Solution {
public:
	int countNodes(TreeNode* root) {
		if (!root)return 0;
		int lh = 0, rh = 0;
		TreeNode *l = root, *r = root;
		while (l) {
			++lh;
			l = l->left;
		}
		while (r) {
			++rh;
			r = r->right;
		}
		if (lh == rh)return (1 << lh) - 1;
		return countNodes(root->left) + countNodes(root->right) + 1;
	}
};

本代码提交AC,用时82MS。
以上代码还可优化,因为如果知道父亲节点的高度时,其实也就知道了孩子节点的高度了,就是父亲的高度减1,所以在递归时,可以保留高度信息,减少冗余计算。代码如下:

class Solution {
private:
	int height(TreeNode* root, int lh, int rh) {
		if (lh == -1) {
			lh = 0;
			TreeNode *l = root;
			while (l) {
				++lh;
				l = l->left;
			}
		}
		if (rh == -1) {
			rh = 0;
			TreeNode *r = root;
			while (r) {
				++rh;
				r = r->right;
			}
		}
		if (lh == rh)return (1 << lh) - 1;
		return height(root->left, lh - 1, -1) + height(root->right, -1, rh - 1) + 1;
	}
public:
	int countNodes(TreeNode* root) {
		return height(root, -1, -1);
	}
};

本代码提交AC,用时55MS,快了一些。

LeetCode Water and Jug Problem

LeetCode Water and Jug Problem
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:

  • Fill any of the jugs completely with water.
  • Empty any of the jugs.
  • Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True

Example 2:

Input: x = 2, y = 6, z = 5
Output: False

很有意思的水罐问题。给定一个3L的水罐和一个5L的水罐和无限的水,问怎样才能得到4L的水。
这个例子很常见了,可以这样做:

  1. 盛满5L水罐;
  2. 将5L水罐中的水导入3L水罐,此时5L水罐中还剩2L水;
  3. 将3L水罐中的水清空;
  4. 将5L水罐中的2L水倒入3L水罐中;
  5. 盛满5L水罐;
  6. 将5L水罐中的水倒入3L水罐中,此时5L水罐中剩余4L水,3L水罐中是满的;
  7. 将3L水罐中的水清空,此时只剩5L水罐中的4L水。

但是遇到一般的x、y、z时,怎样解呢,这里面肯定暗含某种数学规律,看了题解才恍然大悟
将问题转换为这样一个问题:给定xL和yL水罐和无限的水,以及一起无穷大的水罐,怎样利用x和y才能在无穷大的水罐中盛满zL的水。假设我们要往无穷大的水罐中倒m次xL的水和n次yL的水,则有mx+ny=z,如果m为正,则是倒入,为负则是舀出。比如x=3, y=5, z=4时,有(-2)*3+2*5=4,表示往无穷大的水罐中倒入2次5L的水,并且舀出2次3L的水,剩余正好4L。而上面的7步正好也包含2次盛满5L水,2次清空3L水。
所以问题就转换为方程mx+ny=z对于m,n是否有整数解。这需要用到裴蜀定理,又是头一回听说。
假设x和y的最大公约数是d=gcd(x,y),如果z是d的整数倍,则上式有整数解。所以问题就好办了,求一下x,y的最大公约数,然后判断z是否是最大公约数的整数倍就好了。
另外要保证x+y>=z,因为如果x和y加起来的容量都没有z大,怎么可能使得两个罐中水量之和正好等于z呢。
代码如下:

class Solution {
private:
	int gcd(int x, int y) {
		return y == 0 ? x : gcd(y, x%y);
	}
public:
	bool canMeasureWater(int x, int y, int z) {
		return z == 0 || (x + y >= z&&z%gcd(x, y) == 0);
	}
};

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

LeetCode Wiggle Subsequence

LeetCode Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?


一个抖动序列是指第一个数比第二个数小,第二个数比第三个数大,第三个数比第四个数小...或者第一个数比第二个数大,后续类似的交替的大小关系。
现给定一个数组,要求数组中最长的抖动序列的长度。
首先可以用贪心的方法,每次我们选择数据的拐点(局部最大或最小值点)。比如下图中,第一选了A,后续一直是上升的趋势,则选择最大的D能获得更长的抖动序列长度。如果此时选较小的C的话,则下一个只能选H了,这样就漏了E和G。

贪心的代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		int ans = 1, i = 0, j = 1;
		bool up = false;
		while (j < n && nums[j] == nums[i])++j;
		if (nums[j] > nums[i])up = true;
		else up = false;
		while (j < n) {
			if (nums[j] > nums[i] && up) {
				++ans;
				up = false;
				while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
			}
			else if (nums[j] < nums[i] && !up) {
				++ans;
				up = true;
				while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
			}
			i = j++;
		}
		return ans;
	}
};

本代码提交AC,用时3MS。
还可以用动态规划的方法,假设up[i]表示第i个元素处于抖动序列的最后一个位置,且是上升的趋势时,前[0,i]的抖动子序列的最大长度。类似的,down[i]表示第i个元素处于抖动序列的最后一个位置,且是下降趋势时,前[0,i]的抖动子序列的最大长度。
则对于第i个元素,可以枚举所有i前面的元素j跳到i,如果nums[i]>nums[j],则i处于抖动序列的上升末尾,则从j到i构成的抖动序列中,j是处于下降趋势的,所以有up[i]=max(up[i],down[j]+1)。类似的,如果nums[i]<nums[j],则有down[i]=max(down[i],up[j]+1)。最后返回1+max(up[n-1],down[n-1])。
代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		vector<int> up(n, 0), down(n, 0);
		for (int i = 1; i < n; ++i) {
			for (int j = 0; j < i; ++j) {
				if (nums[i] > nums[j])up[i] = max(up[i], down[j] + 1);
				else if (nums[i] < nums[j])down[i] = max(down[i], up[j] + 1);
			}
		}
		return 1 + max(up[n - 1], down[n - 1]);
	}
};

本代码提交AC,用时6MS。
可以对上述代码优化。j无需枚举所有i前面的元素,而是i直接根据和前一个元素i-1的大小关系进行更新。如果nums[i]>nums[i-1],则i处于上升末端,所以i-1必须处于下降末端,有up[i]=down[i-1]+1,down[i]不变,即down[i]=down[i-1]。如果nums[i]<nums[i-1],则i处于下降末端,所以i-1必须处于上升末端,有down[i]=up[i-1]+1,up[i]不变,即up[i]=up[i-1]。如果nums[i]==nums[i-1],则up[i]和down[i]都不变,分别等于up[i-1]和down[i-1]。
为什么这里可以不用枚举所有i前面的元素了呢,因为上述三种情况中,只更新了该更新的,不能更新的情况都等于前一个元素的结果了,比如第一种情况更新了up[i],则down[i]保持了down[i-1]的值,所以后续如果要用到down[i-1]的值,也可以直接用down[i]的值了。
代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		vector<int> up(n, 0), down(n, 0);
		up[0] = down[0] = 1;
		for (int i = 1; i < n; ++i) {
			if (nums[i] > nums[i - 1]) {
				up[i] = down[i - 1] + 1;
				down[i] = down[i - 1];
			}
			else if (nums[i] < nums[i - 1]) {
				down[i] = up[i - 1] + 1;
				up[i] = up[i - 1];
			}
			else {
				up[i] = up[i - 1];
				down[i] = down[i - 1];
			}
		}
		return max(up[n - 1], down[n - 1]);
	}
};

本代码提交AC,用时3MS。
还可以对上述代码进行空间的优化,因为up[i]和down[i]都只用到了前一个结果up[i-1]和down[i-1],所以只需保留前一个结果就行,不需要两个数组。代码如下:

class Solution {
public:
	int wiggleMaxLength(vector<int>& nums) {
		int n = nums.size();
		if (n < 2)return n;
		int up = 1, down = 1;
		for (int i = 1; i < n; ++i) {
			if (nums[i] > nums[i - 1]) {
				up = down + 1;
			}
			else if (nums[i] < nums[i - 1]) {
				down = up + 1;
			}
		}
		return max(up, down);
	}
};

本代码提交AC,用时0MS,是效率最好的一种解法了。
参考:https://leetcode.com/articles/wiggle-subsequence/,完整介绍了所有方法。

LeetCode Perfect Number

LeetCode Perfect Number
We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.
Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.
Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)


判断一个数是否是完美数。完美数的定义是:一个正数,它等于它的所有不包括自己正因子数之和。比如28的所有不包括自己的正因子数有1,2,4,7,14,加起来正好等于28,所以28是一个完美数。
判断的方法也简单,因子i从1~sqrt(num),判断i是否是num的因子,如果是,则把i和num/i都加到结果里。最后判断结果是否等于num。
需要说明两点。一是循环只需进行到sqrt(num),因为大于sqrt(num)的因子可以由小于sqrt(num)的因子被num除得到,比如num=a*b,且a<b,则遍历到a时,如果num%a==0,则num/a就是b。二是注意要排除num自己这个因子,所以当a=1时,就不加num/a了。
代码如下:

class Solution {
public:
	bool checkPerfectNumber(int num) {
		if (num <= 1)return false;
		int ans = 0, n = sqrt(num);
		for (int i = 1; i <= n; ++i) {
			if (num%i == 0) {
				ans += i;
				if (i != 1 && num / i != i)ans += num / i;
			}
		}
		return ans == num;
	}
};

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

LeetCode Target Sum

LeetCode Target Sum
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.

给定一个数组nums,和目标结果S,要求给数组中的每个数加上符号+或-,使得和为S。问共有多少种加符号的方案。
第一反应是DFS,遍历每个数,对其加上+或者-,更新S,然后递归。当遍历完所有数,且和等于0时,找到一种方案。
代码如下:

class Solution {
private:
	void dfs(vector<int>& nums, int step, int S, int& ans) {
		if (step == nums.size() && S == 0) {
			++ans;
			return;
		}
		if (step == nums.size())return;
		dfs(nums, step + 1, S - nums[step], ans);
		dfs(nums, step + 1, S + nums[step], ans);
	}
public:
	int findTargetSumWays(vector<int>& nums, int S) {
		int ans = 0;
		dfs(nums, 0, S, ans);
		return ans;
	}
};

本代码提交AC,用时1072MS。居然需要这么长时间,果断优化。
思来想去,这本质是一个背包问题,常规0/1背包是对每个商品要还是不要,这题的背包是,对每个数字,是加正号还是负号。
假设dp[i][j]表示前i个数字之和为j的不同加符号方案数,则有如下递归公式
dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]
右边第一项是指对第i个数字,要赋加号,那么就要保证前i-1个数字之和是j-nums[i],这样(j-nums[i])+nums[i]才会等于j。类似的,如果要对第i个数字赋减号,就要保证前i-1个数字之和是j+nums[i]。所以总的就是这两种情况加和。
需要注意的是,因为可以赋负号,所以加和的结果可能是负数(范围是[-sum,sum]),为了dp[i][j]中的j能用下标访问,统一把所有和加上总和sum,做一个偏移(范围是[0,2*sum]),最终结果就是dp[n][S+sum]。
DP的代码如下:

class Solution {
public:
	int findTargetSumWays(vector<int>& nums, int S) {
		int n = nums.size(), sum = 0;
		for (int i = 0; i < n; ++i)sum += nums[i];
		if (S<-sum || S>sum)return 0;
		//if (S == -sum || S == sum)return 1; // nums={1,0},S=1; 1=1+0=1-0
		vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0));
		dp[0][sum] = 1;
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j < 2 * sum + 1; ++j) {
				//考虑第i个数字是+还是-
				//i从1开始,所以第i个数字的下标是i-1
				if (j >= nums[i - 1])dp[i][j] += dp[i - 1][j - nums[i - 1]];
				if (j + nums[i - 1] < 2 * sum + 1)dp[i][j] += dp[i - 1][j + nums[i - 1]];
			}
		}
		return dp[n][S + sum];
	}
};

本代码提交AC,用时19MS,加速将近100倍!
DP的问题一般都可以优化空间,比如上述代码可以用两个数组互相滚动赋值来代替n+1个数组。
上面的DP公式理解起来还是有点费劲,下面介绍另一种DP思路,非常简单。
假设我们已经求到前i-1个数字赋不同的符号可以得到的不同和的方案数了,也就是dp[pre]数组,现在要求对第i个数字赋不同符号可能得到的不同和的方案数。那么我们可以遍历dp[pre]数组,只要某个和j对应的方案数不为0(dp[pre][j]!=0),则说明前i-1个数能够组合出和j,且和为j的方案数正好是dp[pre][j],那么我们只需要在和j的基础上考虑加nums[i]或者减nums[i],如果对应的j+nums[i]或j-nums[i]没有超出范围,则这一轮和为j+nums[i]的方案数要加上上一轮和为j的方案数,这一轮和为j-nums[i]的方案数要加上上一轮和为j的方案数。
最后返回dp[cur][S+sum]。非常好理解的一个思路。用这种思路还可以求出从给定数组中取任意多个数相加,可以得到的不同和的方案数,其实和这个题类似,只不过把每个数字的状态改为了取和不取。
代码如下:

class Solution {
public:
	int findTargetSumWays(vector<int>& nums, int S) {
		int n = nums.size(), sum = 0;
		for (int i = 0; i < n; ++i)sum += nums[i];
		if (S<-sum || S>sum)return 0;
		vector<vector<int>> dp(2, vector<int>(2 * sum + 1, 0));
		int i = 0, pre = (i & 1) ? 1 : 0, cur = (i & 1) ? 0 : 1;
		dp[pre][sum] = 1; // 取0个数字,加和为0的方案有1种。把和0偏移到sum位置
		while (i < n) {
			pre = (i & 1) ? 1 : 0;
			cur = (i & 1) ? 0 : 1;
			for (int j = 0; j < 2 * sum + 1; ++j) {
				if (dp[pre][j] != 0) {
					if (j + nums[i] < 2 * sum + 1)dp[cur][j + nums[i]] += dp[pre][j]; // 在j的基础上加nums[i]
					if (j - nums[i] >= 0)dp[cur][j - nums[i]] += dp[pre][j]; // 在j的基础上减nums[i]
				}
			}
			fill(dp[pre].begin(), dp[pre].end(), 0); // 清空pre数组,因为下一轮pre要用作cur数组
			++i;
		}
		return dp[cur][S + sum];
	}
};

本代码提交AC,用时13MS。用了两个滚动数组,空间效率高一点。

LeetCode Maximum XOR of Two Numbers in an Array

LeetCode Maximum XOR of Two Numbers in an Array
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:

Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.

给定一个非空数组,从中任意选两个数进行异或操作,问最大的异或结果是多少。
暴力两层循环肯定是不行的,本题需要一些位运算的技巧,解法参考讨论区
题目限制数值范围在[0,231),所以异或操作最多需要考虑32位。我们从最高位开始考察,判断每一位在数组中异或之后能否得到1的结果。
假设我们已经知道前i-1位的异或最大值为ans,现在要求前i位的异或最大值。我们先把数组中所有数的前i位结果取出来,放到unordered_set<int> hash中。理想情况下,我们希望第i位的异或结果是1,即假设前i位的异或最大值为tmpmax=ans|(1<<i)。我们需要判断hash中是否有两个数异或能得到tmpmax的结果,如果能,说明前i位的异或最大值确实可以达到tmpmax。
也就是说我们需要从hash中选两个数a和b,判断a^b==tmpmax是否成立。常规方法是对hash两层循环判断,但是这样太慢了。利用异或的性质,我们有:如果a^b==tmpmax,则a=b^tmpmax和b=a^tmpmax。比如下面的例子,只是把^和=换了个位置,结果照样成立。

  • 0^0=0 | 0=0^0
  • 0^1=1 | 0=1^1
  • 1^0=1 | 1=0^1
  • 1^1=0 | 1=1^0

所以,我们只需要遍历hash中的数a,和tmpmax异或,如果异或结果b还在hash中,则说明b==a^tmpmax也在hash中,即a^b==tmpmax也成立。说明前i位的异或最大值确实可以达到tmpmax。
代码如下:

class Solution {
public:
	int findMaximumXOR(vector<int>& nums) {
		int ans = 0, mask = 0;
		for (int i = 31; i >= 0; --i) {
			mask |= (1 << i);
			unordered_set<int> hash;
			for (const auto& num : nums) {
				hash.insert(num & mask);
			}
			int tmpmax = ans | (1 << i);
			for (const auto& prefix : hash) {
				if (hash.find(prefix ^ tmpmax) != hash.end()) {
					ans = tmpmax;
					break;
				}
			}
		}
		return ans;
	}
};

本代码提交AC,用时242MS。