剑指offer - 整数中1出现的次数（从1到n整数中1出现的次数）(Java实现)

题目链接：https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6?tpId=13&&tqId=11184&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：直接遍历，然后判断每一位数中含有一的个数。

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int cnt = 0;
        for(int i  = 1; i <= n; ++ i) {
            cnt += solve(i);
        }
        return cnt;
    }
    public static int solve(int x) {
        int ans = 0;
        while(x > 0) {
            if(x % 10 == 1) ++ ans;
            x /= 10;
        }
        return ans;
    }
}

  思路二：题解区某位大佬的思路，非常巧妙，按照每一位能够出现多少个 1 来进行思考。比如 2123405

• 当前位 cur = 0 时，前面的数字 high = 21234, 后面的数字 low = 5, 下面我们来看当前为可以为 1 的情况：[0000010, 0000019], ......, [2123310, 2123319], 此时当前位可以为 1 的个数就是 cnt = high * 10;
• 当前位 cur = 1 时，high = 2, low = 23405, 当前位为 1 的情况：[0100000, 0199999], ......, [2100000, 2123405]，此时当前位可以为 1 的个数就是 cnt = high * 100000 + (low + 1);
• 当前为 cur > 1 时，high = 2123, cur = 4, low = 5, 当前位为 1 的情况：[0000100 - 0000199], ......, [2123100 - 2123199], 此时当前位可以为 1 的个数就是 cnt = (high + 1) * 100。

  public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int cnt = 0;
        for(int i  = 1; i <= n; i *= 10) {
            int low = n % i, high = n / (i * 10), cur = n / i % 10;
            if(cur == 0) {
                cnt += high * i;
            } else if(cur == 1) {
                cnt += high * i + (low + 1);
            } else {
                cnt += (high + 1) * i;
            }
        }
        return cnt;
    }
  }