KK's blog

LeetCode 416 Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

题目大意：

给定一个只包含正整数的非空数组，判断数组是否可以分成两个和相等的子数组。

解题思路：

这题转化为求是否有子序列的和等于数组和的一半，这就是0-1背包问题。价值和重量是一样数组的背包问题。背包问题递归式：
f[j] = Math.max(f[j], f[j-w[i]]+v[i]);
背包问题最后的解为容量为C的背包能装的最大价值，也就是在这题中，容量为数组一半和的背包能装的最大价值是否为数组一半。如果能，即有解。
表示存在前i个数它的和（最大价值）等于和的一半。
举例说明，容量一半表示刚好可以凑到几个数和为一半，如[1,5,11,5]，容量为11，就可以凑到[1,5,5]重量和价值均为一半。
如[1,2,3,10]和为16，容量为8，只能找到[1,2,3]价值为6达不到一半。所以这里C是限制条件并不是一定要达到。但刚好达到即为解。

注意事项：

1. 数组和为奇数，无解
2. 背包问题的解若为数组一半的和即有解
3. 背包问题解法C向前滚

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public boolean canPartition(int[] nums) {
	int sum = 0;
	for(int i=0;i<nums.length;i++)
		sum+=nums[i];
	if(sum%2==1)
		return false;
	int[] result = knapsack(nums,nums,sum/2);
	if(sum/2==result[result.length-1])
		return true;
	return false;
}

public int[] knapsack(int v[], int w[], int C){
	int n = v.length;
	//int[][] re = new int[n][C+1];
	int[] f = new int[C+1];
	
	for(int i=0;i<n;i++){
		for(int j=C;j>=w[i];j--){
			f[j] = Math.max(f[j], f[j-w[i]]+v[i]);
			//if(f[j]==f[j-w[i]]+v[i])
			   // re[i][j] = 1;
		}
	}
	return f;
}

算法分析：

时间复杂度为O(nC)，空间复杂度O(C)。C为数组和的一半，n为数组个数。

LeetCode 572 Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

题目大意：

给定两个非空二叉树s和t，判断t是否是s的子树。s的子树是指由s中某节点及该节点的所有子节点构成的二叉树。
特别的，s是其本身的子树。

解题思路：

这是A公司的题目。DFS解题：

1. s树的每一个节点与t树的根节点比较，若值相等进行下一步。
2. s树的某节点为根的子树和t树进行结构+值比较。

注意事项：

1. s=null和t=null，是子树
2. s和t任一为空，另一个不为空，不是子树。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public boolean isSubtree(TreeNode s, TreeNode t) {
	if(isSame(s, t))
		return true;
	if(t==null)
		return false;
	return s!=null && (isSubtree(s.left, t) || isSubtree(s.right, t));
}

public boolean isSame(TreeNode root, TreeNode root2){
	if(root==null && root2 == null)
		return true;
	if(root==null || root2 == null)
		return false;
	return root.val==root2.val && isSame(root.left,root2.left) && isSame(root.right, root2.right);
}

算法分析：

时间复杂度为O(nm)，空间复杂度O(1)，n和m分别为s数和t数大小。

Follow-up:

如果s是BST，怎么改进算法？
二分法先找到s的节点值等于t根节点值的节点再比较。时间复杂度为O(logn+m)。

1
2
3
4
5
6
7
8
9
10
11

public boolean contains(TreeNode t, TreeNode node) {
	if (node == null)
		return false;
	int result = t.compareTo(node.val);
	if (result > 0)
		return contains(t, node.right);
	else if (result < 0)
		return contains(t, node.left);
	else
		return true;
}

LeetCode 698 Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

• 1 <= k <= len(nums) <= 16.
• 0 < nums[i] < 10000.

题目大意：

判断数组nums是否可以划分为k个和相等的子数组

解题思路：

这题与416类似，所以一开始考虑用0-1背包问题思路，但是0-1背包问题得出的解为2,2,1，与答案不同。因为背包问题只能求出第一个解，并不能求出k个解。所以类似于排列组合，
需要DFS来一个个数来试。参数为visited数组为记录该数是否用了，curSum，k，若curSum等于target(sum/k)，找到第一个解，k–，curSum=0，找下一个解。这个方法是用k次排列组合法组成最终解。

注意事项：

1. 数组和为不能被k整除，无解
2. 引入st，排列组合必须，用于for循环的起始点。
3. k=1立刻剪枝，因为前三个解都是等于sum/k,最后一个也一定是sum/k
4. 当curSum==target时，进行k-1，curSum=0的下一轮dfs。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public boolean canPartitionKSubsets0(int[] nums, int k) {
	int sum = 0;
	for(int i : nums)
		sum+=i;
	if(sum%k!=0)
		return false;
	boolean[] visited = new boolean[nums.length];
	return dfs0(nums, k, sum/k, 0, visited, 0);
}

public boolean dfs0(int[] nums, int k, int target, int curSum, boolean[] visited, int start){
	if(k==1)
		return true;
	if(curSum==target)
		return dfs0(nums, k-1, target, 0, visited, 0);
	
	for(int i=start;i<nums.length;i++){
		if(visited[i])
			continue;
		if(curSum+nums[i]<=target){
			visited[i] = true;
			if(dfs0(nums, k, target, curSum+nums[i], visited, i+1))
				return true;
			visited[i] = false;
		}
	}
	return false;
}

算法分析：

这是NP问题。

另一个方法是，将k次排列组合法整合成一次，途径是开一个k大小数组，每一个数肯定属于其中一个。visited数组替换成ksum数组和idx控制遍历数组顺序。某一个数肯定是属于ksum数组的任一个，
所以所有可能性都考虑到，可以求得解。先对原数组排序方便从后往前遍历，贪心算法可以帮助剪枝，因为先填大的数，容易获得结果或排除结果。如[1….1, 4], target=4, k=2，从前往后的话，
多个1可以有非常多的可能。提高算法效率但若不排序的话会得到LTE。
这个方法比第一个方法的优势在于它用ksum数组取代visited和curSum参数，第一种方法要从头开始扫k遍数组，而此法只需扫一遍数组+每个元素试k次。

1. 数组和为不能被k整除，无解
2. 对数组排序
3. DFS四部曲，从后往前遍历数组加入ksum

注意事项：

1. 数组和为不能被k整除，无解
2. 从后往前遍历数组

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public boolean canPartitionKSubsets(int[] nums, int k) {
	int sum = 0;
	for(int i : nums)
		sum+=i;
	if(sum%k!=0)
		return false;
	Arrays.sort(nums);
	int[] ksum = new int[k];
	return dfs(nums, k, sum/k, ksum, nums.length-1);
}

public boolean dfs(int[] nums, int k, int target, int[] ksum, int idx){
	if(idx==-1){
		for(int a : ksum)
			if(a!=target)
				return false;
		return true;
	}
	for(int i=0; i<k; i++){
		if(ksum[i]+nums[idx]<=target){
			ksum[i] += nums[idx];
			if(dfs(nums, k, target, ksum, idx-1))
				return true;
			ksum[i] -= nums[idx];
		}
		
	}
	return false;
}

算法分析：

这是NP问题。

LeetCode 006 ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

题目大意：

给定字符串按如上的“Z”字锯齿形进行按行重排。

解题思路：

这是一个周期性的字符串。周期是竖+折（不含首节点）。

首节点和竖的最后一点在每周期只会出现一次，其他点会出现两次。
T=2×numRows-2(因为不含竖节点最后一点+折线上的最后一点属于另一个周期)。nT是有几个周期，即使不完成的周期也算一个。
按行遍历（实质是周期上的每个点），再按周期遍历，非顶点有两个需加入到结果中：j×T+i,(j+1)×T-i。由于周期可能不完成，只要写一个API检查边界且加入字符即可。

注意事项：

一个字符的字符串。此时T=0.直接返回原字符串。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public String convert2(String s, int numRows) {
	StringBuffer sb = new StringBuffer();
	int T = numRows*2-2;
	if(T==0)
		return s;
	int nT = (int)Math.ceil((s.length()+0.0)/T);
	for(int i=0;i<numRows;i++){
		for(int j=0;j<nT;j++){
			if(i==0 || i==numRows-1)
				sb.append(addChar(s, j*T+i));
			else{
				sb.append(addChar(s, j*T+i));
				sb.append(addChar(s, (j+1)*T-i));
			}
		}
	}
	return sb.toString();
}

public String addChar(String s, int index){
	String a = "";
	if(index<s.length())
		return s.substring(index, index+1);
	return a;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

LeetCode 123 Best Time to Buy and Sell Stock III

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目大意：

假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

解题思路：

回顾一下前两题：只能进行一次交易和可以无数次交易。分别是用(min, p),sum(prices[i]-prices[i-1])的方法。这题很明显比较接近只能进行一次交易的题。
如果考虑将此问题分为两个子问题(Divide & Conquer,二分法)，prices[0,k]和prices[k,n-1]，只要将k取遍所有值就得到解。

Java代码：

1
2
3
4
5
6
7
8
9
10

public int maxProfit(int[] prices) {
	int max = 0;
	for(int i=0;i<prices.length;i++){
		int p = maxProfitSingle(Arrays.copyOfRange(prices,0, i+1))
				+ maxProfitSingle(Arrays.copyOfRange(prices,i, prices.length));
		if(max<p)
			max = p;
	}
	return max;
}

算法分析：

时间复杂度为O(n2)，空间复杂度O(1)。

上述解法并非最优，因为计算prices[0,k-1]到prices[0,k]时候再次重复计算用了O(n)，但由只能进行一次交易题解中知道，其实O(1)可得，只要在计算过程中把结果存入left数组中即可。
下面的难点在于计算prices[k,n-1]。右端点固定，从右到左计算，所以其实是只能进行一次交易题解的逆运算并把结果存入到right数组。区别是(max, p)。最后只要遍历left[k]+right[k],即可得到最大利润。

注意事项：

1. 数组长度为0。
2. 二分法
3. 用数组存储重复计算结果(DP)

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	//前i天最大利润，并非需要第i天卖出
	int[] left = new int[prices.length];
	int[] right = new int[prices.length];
	
	int min = prices[0], maxPL = 0;
	for(int i=0;i<prices.length;i++){
		int p = prices[i] - min;
		if(maxPL<p)
			maxPL = p;
		left[i] = maxPL;
		if(min>prices[i])
			min=prices[i];
	}
	int max=prices[prices.length-1],maxPR=0;
	for(int j=prices.length-1;j>=0;j--){
		int p=max-prices[j];
		if(maxPR<p)
			maxPR = p;
		right[j] = maxPR;
		if(max<prices[j])
			max=prices[j];
	}
	int maxP = 0;
	for(int k=0;k<prices.length;k++){
		if(maxP<left[k]+right[k])
			maxP = left[k]+right[k];
	}
	return maxP;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

相关题目：

LeetCode 121 Best Time to Buy and Sell Stock
LeetCode 122 Best Time to Buy and Sell Stock II
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown
LeetCode 123 Best Time to Buy and Sell Stock III