share my java solution, got an idea from @stupidbird911, beating 94%!


  • 0
    T

    I referenced some ideas from https://discuss.leetcode.com/topic/39448/java-0ms-solution-99-5

    public class Solution {
        private char[][] dirs=new char[][]{{'0','0'},{'1','1'},{'8','8'},{'6','9'},{'9','6'}};
        public int strobogrammaticInRange(String low, String high) {
             if(low.length()>high.length()||(low.length()==high.length()&&low.compareTo(high)>0)){
                 return 0;
             }
             int sum=0;
             for(int i=low.length();i<=high.length();i++){
                 sum+=CalSameLen(i,true);
             }
             //System.out.println(sum);
             char[] low_array=low.toCharArray();
             char[] high_array=high.toCharArray();
             
             sum-=CalLowerThan(low_array,new char[low_array.length],0,low_array.length-1);
             //System.out.println(sum);
             sum-=CalHigherThan(high_array,new char[high_array.length],0,high_array.length-1);
             //System.out.println(sum);
             return sum;
        }
        
        public int CalLowerThan(char[] num,char[] array,int left,int right){
            if(left>right){
                if(compare(array,num,array.length-1)==-1){
                      return 1;
                }
                return 0;
            }else{
                int res=0;
                for(char[] ele:dirs){
                    if(left==right&&(ele[0]=='6'||ele[0]=='9')){
                        continue;
                    }
                    if(left==0&&left<right&&(ele[0]=='0')){
                        continue;
                    }
                    
                    array[left]=ele[0];
                    array[right]=ele[1];
                    if(compare(array,num,left)>0){
                        continue;
                    }
                    res+=CalLowerThan(num,array,left+1,right-1);
                }
                
                return res;
            }
        }
        
        public int CalHigherThan(char[] num,char[] array,int left,int right){
            if(left>right){
                if(compare(array,num,array.length-1)==1){
                    return 1;
                }
                return 0;
            }else{
                int sum=0;
                for(char[] ele:dirs){
                    if(left==right&&(ele[0]=='6'||ele[0]=='9')){
                        continue;
                    }
                    
                    if(left==0&&left<right&&ele[0]=='0'){
                        continue;
                    }
                    
                    array[left]=ele[0];
                    array[right]=ele[1];
                    if(compare(array,num,left)<0){
                        continue;
                    }
                    sum+=CalHigherThan(num,array,left+1,right-1);
                }
                
                return sum;
            }
        }
        
        public int compare(char[] array1,char[] array2,int index){
            for(int i=0;i<=index;i++){
                if(array1[i]==array2[i]){
                    continue;
                }else if(array1[i]>array2[i]){
                    return 1;
                }else{
                    return -1;
                }
            }
            return 0;
        }
        
        public int CalSameLen(int len,boolean outside){
            if(len<=0) return 1;
            if(len==1) return 3;
            
            if(outside==true){
                return 4*CalSameLen(len-2,false);
            }else{
                return 5*CalSameLen(len-2,false);
            }
        }
        
    
    }
    

  • 0
    T

    Modifying solution!

    public class Solution {
        private char[][] dirs=new char[][]{{'0','0'},{'1','1'},{'8','8'},{'6','9'},{'9','6'}};
        public int strobogrammaticInRange(String low, String high) {
             if(low.length()>high.length()||(low.length()==high.length()&&low.compareTo(high)>0)){
                 return 0;
             }
             int sum=0;
             for(int i=low.length();i<=high.length();i++){
                 sum+=CalSameLen(i,true);
             }
             //System.out.println(sum);
             char[] low_array=low.toCharArray();
             char[] high_array=high.toCharArray();
             
             sum-=CalLowerHigherThan(low_array,new char[low_array.length],0,low_array.length-1,true);
             sum-=CalLowerHigherThan(high_array,new char[high_array.length],0,high_array.length-1,false);
             return sum;
        }
        
        public int CalLowerHigherThan(char[] num,char[] array,int left,int right,boolean findlower){
            if(left>right){
                if((findlower&&compare(array,num,array.length-1)==-1)||(!findlower&&compare(array,num,array.length-1)==1)){
                      return 1;
                }
                return 0;
            }else{
                int res=0;
                for(char[] ele:dirs){
                    if(left==right&&(ele[0]=='6'||ele[0]=='9')){
                        continue;
                    }
                    if(left==0&&left<right&&(ele[0]=='0')){
                        continue;
                    }
                    
                    array[left]=ele[0];
                    array[right]=ele[1];
                    if((findlower&&compare(array,num,left)>0)||(!findlower&&compare(array,num,left)<0)){
                        continue;
                    }
                    res+=CalLowerHigherThan(num,array,left+1,right-1,findlower);
                }
                
                return res;
            }
        }
        
        public int compare(char[] array1,char[] array2,int index){
            for(int i=0;i<=index;i++){
                if(array1[i]==array2[i]){
                    continue;
                }else if(array1[i]>array2[i]){
                    return 1;
                }else{
                    return -1;
                }
            }
            return 0;
        }
        
        public int CalSameLen(int len,boolean outside){
            if(len<=0) return 1;
            if(len==1) return 3;
            
            if(outside==true){
                return 4*CalSameLen(len-2,false);
            }else{
                return 5*CalSameLen(len-2,false);
            }
        }
        
    
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.