剑指offer面试题系列

题目：输入一个整数，求从1到n个整数的十进制表示中 1 出现的次数。例如输入 12，则 1 一共出现了 5 次。

思路

https://github.com/ldfaiztt/algorithms-3/blob/master/interviewOffer/32.md

代码

package com.ans;

//判断从 1 到 N 的整数中 1 出现的次数
public class Solution1 {
    public static int OneTimes(int num) {
        int cur;//当前所指的位上的数字
        int left;//当前位左边的数字
        int right;//当前位右边的数字
        int i = 0;
        int times = 0;
        while (num / power(i) != 0) {
            left = num / power(i + 1);
            cur = (num % power(i + 1)) / power(i);
            right = num % power(i);

            if (cur == 0) {
                times += left * power(i);
            }

            if (cur == 1) {
                times += left * power(i) + right + 1;
            } else {
                times += (left + 1) * power(i);
            }
            i++;
        }

        return times;
    }

    public static int power(int num) { // 用来移动指针
        int retVal = 1;
        while (num != 0) {
            retVal *= 10;
            num--;
        }
        return retVal;
    }


    public static void main(String[] args) {
        System.out.println(OneTimes(21345));
    }
}