快过年了,闲暇练脑。
用了三种方式实现,做对比。
第一种方法,循环出每一个数据值,然后对每个数据的每一个数字进行计算。时间复杂度O(n)
第二种方法,循环出每个数据,然后对包含1的数据组合成字符串,然后进行字符串替换。替换前后长度对比,得出长度。时间复杂度O(n)
第三种方法,分别计算1在每个位(个、十、百....)上出现的次数,叠加。时间复杂度O(1)
package com.iot.demo.viso.algorithm; public class AlgoTest1 { private final static String str = "1"; public static void main(String[] args) { for(int n = 1 ; n < 2999; n+=12) { int count1 = getCount1(n); int count2 = getCount2(n); int count3 = getCount3(n); System.out.println(String.format("1 - %s 中 1 的个数 count1:%s, count2:%s, count3:%s", n, count1, count2, count3)); } } // 第一种方法,循环出每一个数据值,然后对每个数据的每一个数字进行计算。时间复杂度O(n) public static int getCount1(int n) { int count = 0; for(int i = 1; i<= n; i++) { String s = String.valueOf(i); if(s.contains(str)) { String [] lists = s.split(""); for(int w = 0; w< lists.length; w ++) { if(str.equals(lists[w])) { count++; } } } } return count; } // 第二种方法,循环出每个数据,然后对包含1的数据组合成字符串,然后进行字符串替换。替换前后长度对比,得出长度。时间复杂度O(n) public static int getCount2(int n){ StringBuffer bf = new StringBuffer(); for(int i = 1; i<=n; i++){ if(String.valueOf(i).contains("1")) { bf.append(i); } } int allen = bf.length(); String reStr = bf.toString().replaceAll("1", ""); return allen - reStr.length(); } // 第三种方法,分别计算1在每个位(个、十、百....)上出现的次数,叠加。时间复杂度O(1) public static int getCount3(int n) { int count = 0, lowerNum, currentNum, highNum; int factor = 1; // 从个位开始循环计算 while ( n / factor != 0){ // 计算比当前位低的数值 lowerNum = n - n / factor * factor; // 计算当前位数值 currentNum = (n / factor) % 10; // 计算比当前位高的数值 highNum = n / (factor * 10); // 判断当前位 switch (currentNum){ case 0: count += factor * highNum; break; case 1: count += factor * highNum + lowerNum + 1; break; default: count += factor * (highNum + 1); break; } factor *= 10; } return count; } }