KK's blog

每天积累多一些

0%

LeetCode 248 Strobogrammatic Number III

Posted on Edited on Disqus:

LeetCode 248 Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example: 

**Input: low = "50", high = "100"

**Output:** 3 

Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note: Because the range might be a large number, the lowand high numbers are represented as string.

题目大意：

求某范围的旋转数的个数。旋转数是这个数旋转180度还是一样，如0, 1, 8， 还含两位的如69， 96.

解题思路：

低频题。这是M公司的题目。这题不能用乘法原理，因为情况多变，要实实在在地找出每一个可能性。
类似于L351安卓解码种数，数字间有关系，求[m, n]范围间种数。用DFS将每一位填上合法位，此题区别是
需要它有对称性，所以DFS从中间向两边。API为f(res, low, high, map), res为当前结果字符串，map为旋转数的映射关系，
终止条件为res超过high，若在范围内，结果+1，也就是先将自己加入到结果中，然后两边加入旋转字符，进入下一轮递归，
累加到结果中。

注意: 与上题一样，和最左位不能为0除了0自己本身。

注意事项：

  1. 带限制条件的填位法DFS。
  2. 奇偶位。对称中心既可以是奇数位也可以是偶数位。所以DFS有空字符，单个字符0, 1, 8等4种。
  3. 此题难点在验证： 三种情况，需要比较字符串，所以要比较长度
    1) 当前结果长度大于high, 长度等于high但大于high，返回0. 只有这种情况是终止条件
    2) 当前结果长度大于low, 长度等于low但大于等于low，res = 1
    3) 最左位为0，不合法如0880，但0本身除外， res = 0

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def strobogrammaticInRange(self, low: str, high: str) -> int:
	stro_dict = {'0': '0', '1': '1', '8': '8', '6': '9', '9': '6'}
	res = 0
	res += self.dfs('', low, high, stro_dict)
	res += self.dfs('0', low, high, stro_dict)
	res += self.dfs('1', low, high, stro_dict)
	res += self.dfs('8', low, high, stro_dict)
	return res

def dfs(self, s, low, high, stro_dict):
	if len(s) > len(high) or (len(s) == len(high) and s > high):
		return 0
	res = 0
	if len(s) > len(low) or (len(s) == len(low) and s >= low):
		res = 1
	if len(s) > 1 and s[0] == '0': # i.e. 08
		res = 0
	for key, val in stro_dict.items():
		res += self.dfs(key + s + val, low, high, stro_dict)
	return res

注意事项：

  1. 奇偶位。对称中心既可以是奇数位也可以是偶数位。
  2. 最左位为0，不合法如0880，但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
26
27
28
29
30
public int strobogrammaticInRange(String low, String high) {
	Map<String, String> map = new HashMap<>();
	map.put("6", "9");
	map.put("9", "6");
	map.put("1", "1");
	map.put("8", "8");
	map.put("0", "0");
	
	int result = 0;
	result += dfs("", low, high, map);
	result += dfs("1", low, high, map);
	result += dfs("0", low, high, map);
	result += dfs("8", low, high, map);
	return result;
}
	
public int dfs(String res, String low, String high, Map<String, String> map) {
	if(res.length() > high.length() || (res.length() == high.length() && res.compareTo(high) > 0)) 
		return 0;
	int result = 0;
	if((res.length() == low.length() && res.compareTo(low) >= 0)  || res.length() > low.length()) 
		result = 1;
	if(res.length() > 1 && res.charAt(0) == '0')
		result = 0;
	
	for (Map.Entry<String, String> entry : map.entrySet()) {
		result += dfs(entry.getKey() + res + entry.getValue(), low, high, map);
	}
	return result;
}

算法分析：

时间复杂度为O(# of results)，空间复杂度O(lengh(high))。

Free mock interview