Lovely Number

count the lovely number from a to a given b.(a,b are numbers) eg. 135,8462

lovely number

 is a number with unique characters. eg. 123 is a lovely number while 122 isn't

2算法：
Permutation
从高位往下走，注意0开头不算
a, b are non-negative

      public static HashSet<Integer> visited = new HashSet<>();  
      public static HashMap<Integer,Integer> numberToCount = new HashMap<>();  
      public static int countLovelyNumbers(int a, int b){  
           int len1 = String.valueOf(a).length();   
           int len2 = String.valueOf(b).length();  
           return bracktracking(0,len2-1,a,b);  
      }  
      public static int bracktracking(int num,int digit,int a,int b){  
           int ans = 0;  
           if(digit==-1)             
               return num >= a? 1:0;  
           if(numberToCount.containsKey(num)) return numberToCount.get(num);  
           for(int i = 0; i <= 9; i++){  
                if(!visited.contains(i) && num <= b - i*Math.pow(10,digit)){  
                     if(!(i==0 && num==0 && digit!=0))  
                          visited.add(i);  
                     int tmp = (int) (num+i*Math.pow(10,digit));  
                     ans += bracktracking(tmp,digit-1,a,b);  
                     visited.remove(i);  
                }
           }  
           numberToCount.put(num,ans);  
           return ans;  
      }  

a, b can be any integer

      public static HashSet<Integer> visited = new HashSet<>();  
      public static HashMap<Long,Long> numberToCount = new HashMap<>();  
      public static long countLovelyNumbers(int a, int b){  
           if(a<0&&b>0)  
                return bracktracking(0,Math.max(String.valueOf(-(long)a).length(),  
                                                             String.valueOf(b).length())-1,  
                                              Math.min(-(long)a, b),Math.max(-(long)a, b));  
           if(a<0&&b<0)  
                return bracktracking(0,  
                          Math.max(String.valueOf(-(long)a).length(),  
                                    String.valueOf(-(long)b).length())-1,  
                          Math.min(-(long)a, -b),Math.max(-(long)a, -b));  
           return bracktracking(0,String.valueOf(b).length()-1,a,b);  
      }  
      public static long bracktracking(long num,int digit,long a,long b){  
           long ans = 0;  
           if(digit==-1){       
                return num >= a? 1:0;  
           }  
           if(numberToCount.containsKey(num)) return numberToCount.get(num);  
           for(int i = 0; i <= 9; i++){  
                if(!visited.contains(i) && num <= b - i*Math.pow(10,digit)){  
                     if(!(i==0 && num==0 && digit!=0))  
                          visited.add(i);  
                     long tmp = (long) (num+i*Math.pow(10,digit));  
                     ans += bracktracking(tmp,digit-1,a,b);  
                     visited.remove(i);  
                }  
           }  
           numberToCount.put(num,ans);  
           return ans;  
      }