剑指offer—数字1的个数 解答

剑指offer—数字1的个数

题目描述

给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例:

输入: 13
输出: 6 
解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。

思路

如果使用循环n个数的方法,每个数还要对每一位进行判断,时间复杂度太高,我们想一想能不能使用数位的方式,只需要循环数字的位数次,获得每一位上出现1的次数,总的加起来就是总的1的个数

我们只需要计算出每一位为1时,其他位数有多少种组合即可

代码

class Solution {
    public int countDigitOne(int n) {
        if(n<=9) return n>0?1:0;
        int count = 0;
        String s = String.valueOf(n);
        for(int i=0;i<s.length();i++){
            if(i==0){//第一位
                int v = s.charAt(i)-'0';
                if(v>1) count += Math.pow(10,s.length()-i-1);
                else count += Integer.parseInt(s.substring(i+1)) + 1;
            } else if (i == s.length()-1) {//最后一位
                int left = Integer.parseInt(s.substring(0, i));
                int v = s.charAt(i)-'0';
                if(v>=1){
                    count += 1;
                }
                count += left;
            } else {//中间位
                int left = Integer.parseInt(s.substring(0, i));
                int right = Integer.parseInt(s.substring(i+1));
                count += Math.pow(10,s.substring(i).length()-1)*left;
                if(s.charAt(i)-'0'==1){
                    count += right+1;
                }else if(s.charAt(i)-'0'>1){
                    count += Math.pow(10,s.substring(i).length()-1);
                }
            }
        }
        return count;
    }
}

注意我们不能使用String.charAt()作为int值,因为它的char是ascii码,我们需要减去字符'0',才能获取int的值

  • 优化后
class Solution {
    public int countDigitOne(int n) {
        if(n<=9) return n>0?1:0;
        int count = 0;
        String s = String.valueOf(n);
        int l = s.length();
        for(int i=0;i<l;i++){
            int v = s.charAt(i)-'0';
            String s1 = s.substring(i+1).equals("")?"0":s.substring(i+1);
            String s2 = s.substring(0, i).equals("")?"0":s.substring(0,i);
            int subl = s.substring(i).length()-1;
            if(i==0){
                if(v>1) count += Math.pow(10,l-i-1);
                else count += Integer.parseInt(s1) + 1;
            } else {
                int left = Integer.parseInt(s2);
                int right = Integer.parseInt(s1);
                if (i == s.length()-1) {
                    count += v>=1?left+1:left;
                } else {
                    count += Math.pow(10,subl)*left;
                    if(v==1){
                        count += right+1;
                    }else if(v>1){
                        count += Math.pow(10,subl);
                    }
                }
            }
        }
        return count;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/num-1-counts.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!