算法3

A non-negative integer is called heavy if the average value of its digits in decimal representation exceeds 7. Assume that 0 has an average value of its digits equal to 0.

For example, the number 8,698 is heavy because the average value of its digits is (8+6+9+8)/4 = 7.75. The number 53,141 has an average value of its digits of (5+3+1+4+1)/5 = 2.8, so it is not heavy.

Write a function:

class Solution { public int heavy_decimal_count(int A,int B); }

that, given two non-negative integers A and B, returns the number of heavy integers within the interval [A..B] (both ends included).

Assume that:

• A is an integer within the range [0..200,000,000];
• B is an integer within the range [0..200,000,000];
• A ≤ B.

For example, given A=8,675 and B=8,689 the function should return 5, because there are five heavy integers within the range [8,675..8,689]:

?

8675    avg=6.508676    avg=6.758677    avg=7.008678    avg=7.25    HEAVY8679    avg=7.50    HEAVY8680    avg=5.508681    avg=5.758682    avg=6.008683    avg=6.258684    avg=6.508685    avg=6.758686    avg=7.008687    avg=7.25    HEAVY8688    avg=7.50    HEAVY8689    avg=7.75    HEAVY

?

Complexity:

• expected worst-case time complexity is O((log(A)+log(B))3);
• expected worst-case space complexity is O(log(A)+log(B)).

  ?

  ?

  这个不确定，高手可以指教。

  方案一：

  public int heavy_decimal_count(int A,int B) {
  ??int result = 0;
  ??int n = B - A;
  ??for(int i = 0; i <= n; i++) {
  ???int t = A + i;
  ???if(t == 0) {
  ????continue;
  ???}
  ???int w = 0;
  ???double sum = 0;
  ???while(t > 0) {
  ????sum += (t % 10);
  ????t = t / 10;
  ????w++;
  ???};
  ???
  ???if((sum / w) > 7) {
  ????result++;
  ???}
  ??}
  ??return result;
  ?}

  ?

  方案二：

  public int heavy_decimal_count(int A,int B) {
  ??int result = 0;
  ??
  ??int x = A;
  ??double sum = 0;
  ??
  ??Vector<Integer> v = new Vector<Integer>(9);
  ??
  ??if(x == 0) {
  ???v.add(0);
  ??} else {
  ???while(x > 0) {
  ????int ys = (x % 10);
  ????v.add(ys);
  ????sum += ys;
  ????x = x / 10;
  ???};
  ???if(sum / v.size() > 7) {
  ????result++;
  ???}
  ??}
  ??
  ??
  ??int n = B - A;
  ??for(int i = 1; i <= n; i++) {
  ???int jw = 0;
  ???for(int j = 0; j < v.size(); j++) {
  ????if(v.get(j) + 1 == 10) {
  ?????v.set(j, 0);
  ?????jw++;
  ?????if(jw < v.size()) {
  ??????continue;
  ?????} else {
  ??????v.add(1);
  ?????}
  ????} else {
  ?????v.set(j, v.get(j) + 1);
  ????}
  ????break;
  ???}
  ???sum = sum - (9 * jw) + 1;//这个是关键，不需要每次循环求和，而是根据上一个数的结果得到下一个数的结果，其中jw表示相当上一个数，当前数做了几次进位操作
  ???if(sum / v.size() > 7) {
  ????result++;
  ???}
  ??}
  ??return result;
  ?}