Strobogrammatic 数生成
为什么一个这么简单的 DFS 能超过 89% ..
注意:index == 0 并且 i == 0 的时候要跳过,免得在起始位置填上 0 .
public class Solution {
public List<String> findStrobogrammatic(int n) {
List<String> list = new ArrayList<>();
char[] num1 = {'0','1','8','6','9'};
char[] num2 = {'0','1','8','9','6'};
char[] number = new char[n];
dfs(list, number, num1, num2, 0);
return list;
}
private void dfs(List<String> list, char[] number, char[] num1, char[] num2, int index){
int left = index;
int right = number.length - index - 1;
if(left > right){
list.add(new String(number));
return;
}
// We can fill in 0,1,8 only
if(left == right){
for(int i = 0; i < 3; i++){
number[left] = num1[i];
dfs(list, number, num1, num2, index + 1);
}
} else {
for(int i = 0; i < num1.length; i++){
if(index == 0 && i == 0) continue;
number[left] = num1[i];
number[right] = num2[i];
dfs(list, number, num1, num2, index + 1);
}
}
}
}
Google 面经里的 follow-up 是,给定一个上限 n ,输出所有上限范围内的数。
办法土了点,遍历所有 lowLen ~ highLen 区间的长度,生成所有可能的结果,考虑到区间可能是大数,我们就改一下,自己写一个 String compare 函数好了。
后来发现有点多余,可以直接用内置的 str1.compareTo(str2).
超过 81.92% ~
public class Solution {
int count = 0;
public int strobogrammaticInRange(String low, String high) {
int lowLen = low.length();
int highLen = high.length();
char[] num1 = {'0','1','8','6','9'};
char[] num2 = {'0','1','8','9','6'};
for(int i = lowLen; i <= highLen; i++){
char[] number = new char[i];
dfs(number, num1, num2, 0, low, high);
}
return count;
}
private void dfs(char[] number, char[] num1, char[] num2, int index, String low, String high){
int left = index;
int right = number.length - index - 1;
if(left > right){
String num = new String(number);
if(compare(low, num) <= 0 && compare(num, high) <= 0) count++;
return;
} else if(left == right){
for(int i = 0; i < 3; i++){
number[left] = num1[i];
dfs(number, num1, num2, index + 1, low, high);
}
} else {
for(int i = 0; i < 5; i++){
if(index == 0 && i == 0) continue;
number[left] = num1[i];
number[right] = num2[i];
dfs(number, num1, num2, index + 1, low, high);
}
}
}
// -1 : str1 is bigger
// 1 : str 2 is bigger
// 0 : equal
private int compare(String str1, String str2){
if(str1.length() > str2.length()) return 1;
else if(str1.length() < str2.length()) return -1;
else {
for(int i = 0; i < str1.length(); i++){
int digit1 = str1.charAt(i) - '0';
int digit2 = str2.charAt(i) - '0';
if(digit1 != digit2) return (digit1 > digit2) ? 1: -1;
}
}
// Equal
return 0;
}
}
Last updated