https://leetcode.com/problems/strobogrammatic-number/description/
image.png
第一问 一个数是不是STROBO数，我们通过观察可以发现。在一个STROBO数的2边加上11,88 ，69,96 还是STROBO数。如果这2个数不是最外层的那么还可以加一个00.（第一题最外层00也没RETURN FALSE）根据这个性质，我们可以写出判断函数。就是用2根指针，从外到内。来依次判断。
public boolean isStrobogrammatic(String num) {
int i = 0, j = num.length()-1;
while(i<=j){
char a = num.charAt(i);
char b = num.charAt(j);
if(a == b && (a == '1' || a=='0' || a == '8')){
i++;j--;
}else if( (a== '6' && b=='9') || (a== '9' && b=='6') ){
i++;j--;
}else{
return false;
}
}
return true;
}
follow up:
image.png
长度为N的这个STRING怎么构造呢。我们可以想到从内构造。两边不断加上00,11,88,69,96. 这道题最外层不能为00.
那么下面再想，递归终止条件是啥。如果N是偶数，那么就是空STRING，如果N是奇数，那么核心必须是1,0,8； 下面就可以出代码了。
int N;
public List<String> findStrobogrammatic(int n) {
N = n;
return help(n);
}
private List<String> help(int n){
if(n == 0) return new ArrayList<String>(Arrays.asList(new String[]{""}));
if(n == 1) return new ArrayList<String>(Arrays.asList(new String[]{"0","1","8"}));
List<String> inner = help(n-2);
List<String> cur = new ArrayList<>();
for(String w : inner){
cur.add("1"+w+"1");
cur.add("8"+w+"8");
cur.add("6"+w+"9");
cur.add("9"+w+"6");
if(n!=N)
cur.add("0"+w+"0");
}
return cur;
}
follow up:
image.png
要求去一个范围了，我们可以算出每个N长的个数。全部加起来。这样可能会有多。下面就是要减去那些比LOW小，比UP大的字符。我们这边可以用前一个方法的，构建的字符串用从小到大的排序构造。这样出来就可以根据LOW和HIGH的字符串在结果集里做2分搜索。
public int strobogrammaticInRange(String low, String high) {
int up = high.length(),lw = low.length();
if(lw > up || (lw == up && low.compareTo(high)>0)) return 0;
int[][] res = new int[up+1][2];
res[0] = new int[]{1,1};
res[1] = new int[]{3,3};
int cnt = 0;
if(lw==1) cnt+=3;
for(int i=2;i<=up;i++){
res[i][0] = res[i-2][1]*4;
if(i >= lw) cnt += res[i][0];
res[i][1] = res[i-2][1]*5;
}
List<String> highs = helper(up,up);
int p1 = Collections.binarySearch(highs,high);
cnt -= highs.size()-(p1>=0?p1+1:-p1-1);
List<String> lows = helper(lw,lw);
int p2 = Collections.binarySearch(lows,low);
return cnt - ((p2>=0? p2 : (-p2-1)) - (lw>1?res[lw-2][1]:0));
}
private List<String> helper(int cur, int max){
if(cur == 0) return new ArrayList<String>(Arrays.asList(""));
if(cur == 1) return new ArrayList<String>(Arrays.asList("0", "1", "8"));
List<String> rst = new ArrayList<String>();
List<String> center = helper(cur - 2, max);
char[][] cs = {{'0','0'},{'1','1'},{'6','9'},{'8','8'},{'9','6'}};
for(char[] c : cs)
for(String w : center) rst.add(c[0]+w+c[1]);
return rst;
}
