统计1－N的1的个数------递归尝试

 准备用递归做， 前109通过， 后面的不行了， 代码的复杂度太大，违背代码应该简单明了的原则。

 

 

<script>
 //alert('0'.substr(1) === '');

 function count_1_from_1_to_N(N, index) {
  
  var first_char = N.substr(index,1); 
  var last_N = N.substr(index+1); 

  if (N == 0) {
   return 0;
  } else if (N < 0) {
   N = N * -1
  } else if (N < 10) {
   return 1;
  }
    

  if (last_N === '') {
   return 1;
  }

  if (first_char == 0) {
   return 0;
  }

  //alert("first_char : " + first_char);
  //alert("last : " + last_N);

  var value = 1 +  (first_char==1?(last_N-(-1)):0) + 1;
  // alert(value);
  //alert(first_char * sign((""+last_N).charAt(0)));
  var count = 0;

  var middle_count = 0;
  var last_left_str = last_N.substr(0, last_N.length-1);
  
  for (var i=0; i<last_left_str.length; i++) {
   if (last_left_str.charAt(i) == '1') {
    middle_count ++;
    alert(last_left_str);
   }
  }
  count = (N.length-index-1) * Math.pow(10, N.length-index-2) * first_char + sign(first_char-1)*Math.pow(10, N.length-index-1) + (first_char==1?(last_N-(-1))*(1+middle_count):0);// +  first_char * sign(last_N.charAt(0));
  //alert(count);
  return count + count_1_from_1_to_N(last_N, index+1);

        }

 function sign(n) {
  return n < 0 ? -1 : (n > 0 ? 1 : 0);
 }

 /*var N_arr = [1,3,9,10,11,12,13,14,15,16,17,18,19,20,21,22,30,31,32,40,41,42,50,51,60,61,70,71,80,81,90,91,100, 101,102,110,111,112, 1000, 10001, 10010, 10011,100112];

 for (var i =0; i<N_arr.length; i++) {
  //alert(N_arr[i]);
  var count = count_1_from_1_to_N(""+N_arr[i], 0);
  alert(N_arr[i] + " : " + count);
 }
*/
 var all_str = "";
 for (var i =0; i<122; i++) {
  //alert(N_arr[i]);
  all_str = all_str + i;
  var count_right = 0;
  for (var j=0; j<all_str.length; j++) {
   if (all_str.charAt(j) == '1') {
    count_right ++;
   }
  }
   
  var count = count_1_from_1_to_N(""+i, 0);

  if (count != count_right) {

   alert(i + " : " + count + " == " + count_right);
  }
  //alert(i + " : " + count + " == " + count_right);
 }
 

</script>