KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

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;
}

若BST不是严格递增 (allow duplicates)，多比较几个相等节点即可。

Posted on Edited on Disqus:

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问题。

Posted on Edited on Disqus:

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)。

Posted on Edited on Disqus:

LeetCode 123 Best Time to Buy and Sell Stock III

Say you have an array for which the ith 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

Posted on Edited on Disqus:

常用知识点

类型 函数名 作用 输入参数 返回值 例子
String split 根据输入参数分拆成字符串数组 String String[] String[] tokens = s.split(“ “);
String trim 将前后空格去掉 N/A String s = s.trim()
String toCharArray 将字符串变成字符数组 N/A char char[] a = s.toCharArray()
String charAt 取某字符 int char num1.charAt(i)
String length 取某字符长度 int int num1.length()
String equals 判断相等 String boolean “”.equals(str)
String substring 取某字符[beginIdx, endIdx)子串 int, int String “smiles”.substring(1,5)->”mile”
Integer parseInt 字符串变整型 String int Integer.parseInt(“2”); Integer.parseInt(“100”, 2) -> 4，任意进制数转为10进制。
Integer Integer.MIN_VALUE 整型最小值 N/A int Integer.MIN_VALUE
Integer Integer.toString 整型->String int String Integer.toString(root.val)
StringBuilder append 将新字符（串）加入到末尾 String或char N/A sb.append(“abc”)
StringBuilder new StringBuilder() 新建这个类当然也将目前字符串清空 N/A N/A sb=new StringBuilder()
StringBuilder reverse 反转 N/A StringBuilder sb.reverse()
StringBuilder toString StringBuilder变成字符串 N/A String sb.reverse().toString()
StringBuilder deleteCharAt StringBuilder删除某字符 N/A int sb.deleteCharAt(sb.length() - 1);
Arrays length 数组长度 N/A int ary.length
Arrays sort 对数组正(逆)排序 T[] N/A Arrays.sort(nums1); Arrays.sort(nums1,Collections.reverseOrder()); Arrays.sort(nums1,new Comparator(){});
Arrays asList 包装类型数组转化成List T[] List Arrays.asList(ary), ary为Integer数组或者常量 List: Arrays.asList(“a”, “b”);
Arrays stream 基本类型数组转化成List N/A N/A List re = Arrays.stream(ints).boxed() .collect(Collectors.toList())
Arrays N/A 去重 int[] int[] Set set = new HashSet<>(list);set->int[]
Collections sort 对List排序 List N/A Collections.sort(list); Collections.sort(l, Collections.reverseOrder());
ArrayList new ArrayList<>() 新建List N/A List List l = new ArrayList<>()
ArrayList stream List转为基本类型数组 List int[] int[] re = l.stream().mapToInt(i->i).toArray()
ArrayList stream List转为Object类型数组 List Integer[] Integer[] re = l.toArray(new Integer[0]);
ArrayList add 把一个元素加入到List l中 List N/A l.add(“pen”);
ArrayList addAll 把一个List的所有元素加入到另一个中 List N/A l2.addAll(l);
ArrayList get 返回给定的下标对应的元素 List T l.get(2);
ArrayList remove 把给定下标的元素从List l中删除 List N/A l.remove(2);
ArrayList remove 把第一个出现的元素从List l中删除 List N/A l.remove(“pen”);
ArrayList size 大小 List int l.size();
ArrayList reverse 反转 List N/A Collections.reverse(l);
LinkedList add 加到末尾 T N/a ll.add(2);
LinkedList remove 头部删除 N/A T ll.remove();
LinkedList addFirst 加到头部 T N/A ll.addFirst(2);
LinkedList removeLast 末尾删除 N/A T ll.removeLast();
Queue new LinkedList() 新建/复制队列 N/A Queue Queue q = new LinkedList<>(q2)
Queue offer 不抛异常的加入尾元素 T N/A q.offer(5)
Queue poll 不抛异常的取出头元素 N/A T Integer i = q.poll()
Queue peek 不抛异常的看看头元素 N/A T Integer i = q.peek()
Stack new Stack 新建栈 N/A Stack Stack s = new Stack<>()
Stack peek 获取栈顶元素但不出栈 N/A T Integer i = s.peek()
Stack pop 获取栈顶元素且出栈 N/A T Integer i = s.pop()
Stack push 加入 T N/A s.push(5)
Stack isEmpty 是否为空 N/A boolean s.isEmpty()
HashMap new HashMap 新建哈希表 N/A Map Map m = new HashMap<>()
HashMap get 获取 T T m.get(‘a’)
HashMap put 加入 T,T N/A m.put(‘a’,5)
HashMap containsKey 是否含有某个key T boolean m.containsKey(‘a’)
HashMap get,put 更新key对应的value N/A N/A m.put(‘a’,m.get(‘a’)+1)
Map Map.of Map常量 N/A Map Map.of(2, “abc”, 3, “def”);
Iterator Iterator entrySet N/A N/A Iterator it = map.entrySet().iterator();
Iterator Iterator keySet N/A N/A Iterator it = map.keySet().iterator();
Iterator hasNext 有无下一个元素 N/A N/A while(it.hasNext())
Iterator next 下一个元素 N/A N/A Map.Entry pair = (Map.Entry)it.next()
Map.Entry getValue, getKey 得到key, Value N/A N/A pair.getValue(), pair.getKey()
HashSet new HashSet 新建哈希集 N/A Set Set m = new HashSet<>()
HashSet add 加入 T N/A m.add(‘a’)
HashSet remove 删除 T N/A m.remove(‘a’)
HashSet contains 是否含有某个元素 T boolean m.contains(‘a’)
PriorityQueue offer,poll,peek 与Queue相同 N/A N/A N/A
PriorityQueue Comparator k大小的heap N/A N/A 见下 
1
2
3
4
5
6
7
8
PriorityQueue<Node> minHeap = new PriorityQueue<Node>(k,
				new Comparator<Node>() {
					@Override
					public int compare(Node o1, Node o2) {
						return o1.value - o2.value;
					}
				}
		);

Arrays的二分法： 若找不到，返回比tgt大的数的下标数组长度的负值-1。

1
2
3
4
5
6
7
8
int[] lis = new int[len];
int index = Arrays.binarySearch(lis, 0, len, tgt);
if(index < 0) {
	index = -index - 1;
	lis[index] = tgt;
}
else
	lis[index] = tgt;

Free mock interview