题目：
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.
For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the low and high numbers are represented as string.
链接： http://leetcode.com/problems/strobogrammatic-number-iii/
题解：
由于有了上一题目的臭长解法，这里继续沿用...优化留给二刷吧，看官图个乐子好了。 思路是使用Strobogrammatic Number II的代码，我们对于从 low.length()到high.length()的每一个n，求解Strobogrammatic Number，然后把这个数字与low和high进行比较，假如这个数字在[low，high]的闭区间里，则可以算作一个结果。下面的方法大量使用了Strobogrammatic Number II的代码，其实有很多地方可以优化，比如不需要传递一个List<>，只用传递一个数组，用首元素进行计数就可以了，比如int[] arr = new int[1]，然后用a[0]来记录数字的增减。 还有methods可以由四个变为三个，合并第一和第二个method，这样也可以不用每次都create一个map，等等。复杂度也要好好计算一下。
Time Complexity - O(L * 2n)， Space Complexity - O(2n)。
public class Solution {
public int strobogrammaticInRange(String low, String high) {
if(low == null || high == null)
return 0;
int lo = low.length(), hi = high.length();
int res = 0;
for(int i = lo; i <= hi; i++)
res += findStrobogrammatic(i, low, high).size();
return res;
}
private List<String> findStrobogrammatic(int n, String low, String high) {
if(n < 1)
return new ArrayList<String>();
List<String> res = new ArrayList<>();
Map<Character, Character> map = new HashMap<>();
map.put('0', '0');
map.put('1', '1');
map.put('6', '9');
map.put('8', '8');
map.put('9', '6');
StringBuilder sb = new StringBuilder();
int position = (n % 2 == 0) ? 0 : 1;
findStrobogrammatic(res, sb, map, n, position, low, high);
return res;
}
private void findStrobogrammatic(List<String> res, StringBuilder sb, Map<Character, Character> map, int n, int position, String low, String high) {
if(sb.length() > n)
return;
if(sb.length() == n) {
String s = sb.toString();
if(firstStringEqualToOrSmaller(low, s) && firstStringEqualToOrSmaller(s, high))
res.add(sb.toString());
return;
}
if(position == 1) {
for(char c : map.keySet()) {
if(c == '6' || c == '9')
continue;
sb.append(c);
findStrobogrammatic(res, sb, map, n, position + 1, low, high);
sb.setLength(0);
}
} else {
for(char c : map.keySet()) {
if(n - sb.length() == 2 && c == '0')
continue;
sb.insert(0, c);
sb.append(map.get(c));
findStrobogrammatic(res, sb, map, n, position + 2, low, high);
sb.deleteCharAt(0);
sb.deleteCharAt(sb.length() - 1);
}
}
}
private boolean firstStringEqualToOrSmaller(String s, String t) {
if(s.length() < t.length())
return true;
else if(s.length() > t.length())
return false;
else {
for(int i = 0; i < s.length(); i++)
if(s.charAt(i) > t.charAt(i))
return false;
else if(s.charAt(i) < t.charAt(i))
return true;
return true;
}
}
}
Reference:
https://leetcode.com/discuss/55468/clear-java-ac-solution-using-strobogrammatic-number-method
https://leetcode.com/discuss/54562/clean-and-easy-java-recursive-solution
https://leetcode.com/discuss/50628/ac-java-solution-with-explanation
https://leetcode.com/discuss/50624/clean-and-easy-understanding-java-solution
https://leetcode.com/discuss/50604/solution-based-on-strobogrammatic-number-ii