KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 007 Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2<sup>31</sup>, 2<sup>31</sup> - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

<pre>Input: x = 123 Output: 321 </pre>

Example 2:

<pre>Input: x = -123 Output: -321 </pre>

Example 3:

<pre>Input: x = 120 Output: 21 </pre>

Example 4:

<pre>Input: x = 0 Output: 0 </pre>

Constraints:

  • -2<sup>31</sup> <= x <= 2<sup>31</sup> - 1

题目大意：

反转整数中的数字。

数学法解题思路：

用数学方法每位取余，余数左移。另一种方法是转成字符串然后用字符串反转的方法。

与Java的区别：

  1. 不需要定义long，因为Python3所有int默认都是long
  2. 反转str一行完成，非常简洁

注意事项：

  1. 负值
  2. 溢出

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def reverse(self, x: int) -> int:
	res, is_negative = 0, False
	if x < 0:
		is_negative = True
		x = -x
	while x > 0:
		digit = x % 10
		res = res * 10 + digit
		x //= 10
	if res > pow(2, 31) - 1:
		return 0
	if is_negative:
		res = -res
	return res

字符串法解题思路：

转为字符串，然后反转。

1
2
3
4
5
6
7
8
9
def reverse(self, x: int) -> int:
	res, is_negative = 0, False
	if x < 0:
		is_negative = True
		x = -x
	res = int(str(x)[::-1])
	if res > pow(2, 31) - 1:
		return 0
	return -res if is_negative else res

算法分析：

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

Posted on Edited on Disqus:

LintCode 683 Word Break III

<div>

Give a dictionary of words and a sentence with all whitespace removed, return the number of sentences you can form by inserting whitespaces to the sentence so that each word can be found in the dictionary.

Example 1:

<pre> Input: "CatMat" ["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"] Output: 3 Explanation: we can form 3 sentences, as follows: "CatMat" = "Cat" + "Mat" "CatMat" = "Ca" + "tM" + "at" "CatMat" = "C" + "at" + "Mat" </pre>

Example 2:

<pre> Input: "a" [] Output: 0 </pre>

</div>

题目大意：

一个字符串s，被“字典集合”（wordDict）中的单词拼接而成的可能性种数。

解题思路：

这是经典题。如果知道s[0:n-1)很容易知道s[0:n)是否有解，既然和子问题有关，就用DP。

  1. 定义dp[i]为字符串s[0,i)是合法分解种数。
  2. 判断一个字符串是否可以合法分解，方案是尝试在每一位进行分解，若其中一个可分解，即有解，加入到dp[i]中。
    递归式为dp[i] += dp[k] * isWord(s[k:i)), 0 <= k < i.
  3. 方向为从左到右i=0..n, 初始值为dp[0] = 1.

注意事项：

  1. 将两个输入都转换成小写。
  2. dp[n+1]而不是dp[n]，而for循环从1开始。
  3. 递归中dp[i]用+操作符。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int wordBreak3(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	Set<String> lowerDict = new HashSet<>();
	for(String c : dict)
		lowerDict.add(c.toLowerCase());
	dict = lowerDict;
	s = s.toLowerCase();
	
	int[] dp = new int[s.length() + 1];
	dp[0] = 1;
	
	// dp[i][j] = sum(dp[i][k] * isWord(s[k,j])), i=0..n-1, j=i..n-1
	// dp[0][n-1] = sum(dp[0][k] * isWord(s[k,n-1]))
	// dp[n] = sum(dp[k] * isWord(s[k,n]))
	for(int i = 1; i <= s.length(); i++) {
		for(int k = 0; k < i; k++) {
			dp[i] += dp[k] * (dict.contains(s.substring(k, i)) ? 1 : 0); 
		}
	}
	return dp[s.length()];
}

算法分析：

时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度为O(n)。

这道题一开始走过一些弯路，首先我觉得类似于Catalan算法，左右半部都是子问题，但其实这属于单边问题。所以写了以下算法：

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int wordBreak3_wrong(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	// dp[i][j] = sum(dp[i][k] * dp[k][j])
	int[][] dp = new int[s.length() + 1][s.length() + 1];
	
	// use "ab" as an example
	for(int len = 1; len <= s.length(); len++) {
		for(int i = 0; i < s.length() - len + 1; i++) {
			for(int j = i + 1; j < i + len; j++) {
				//"a","b"
				dp[i][i+len] += dp[i][j] * dp[j][i+len];    		
			}
			//"ab"
			if(dict.contains(s.substring(i, i+len)))
				dp[i][i+len]++;
			
		}
	}
	return dp[0][s.length()];
}

但这个方法会有重复解，比如
"abc", "a","b","c"
-> dp["ab"] * dp["c"] = 1
-> dp["a"] * dp["bc"] = 1
所以解重复，因为这问题是单边子问题而不是Catalan问题。
更改版本为单边子问题，一开始用dp[n]导致初始化稍复杂，其实初始化可以并入到递归式，只要用dp[n+1]即可。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int wordBreak32(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	int[] dp = new int[s.length()];
	for(int i = 0; i < s.length(); i++)
		dp[i] = dict.contains(s.substring(0, i + 1)) ? 1 : 0;

	for(int i = 0; i < s.length(); i++) {
		for(int k = 0; k < i; k++) {
			dp[i] += dp[k] * (dict.contains(s.substring(k + 1, i + 1)) ? 1 : 0); 
		}
	}
	return dp[s.length() - 1];
}

Posted on Edited on Disqus:

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:

<pre>Input: [1, 5, 11, 5]

Output: true

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

Example 2:

<pre>Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets. </pre>

题目大意：

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

解题思路：

这题转化为求是否有子序列的和等于数组和的一半，这就是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为数组个数。

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:

<pre> 3 /
4 5 /
1 2 </pre>

Given tree t:

<pre> 4 /
1 2 </pre>

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

Example 2:
Given tree s:

<pre> 3 /
4 5 /
1 2 / 0 </pre>

Given tree t:

<pre> 4 /
1 2 </pre>

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:

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

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

Free mock interview