1.计算阶乘中尾部零的个数
描述：
计算出n阶乘中尾部零的个数
样例：
11！ = 39916800，故返回2
分析
- 对数字做质数分解，例如20=225，可以知道能够在尾部产生零的只有质数2和质数5的乘积
- 由于是阶乘，质数2的个数明显大于质数5的个数
- 特别需要注意的是，类似25=5*5，数字里面是有5的指数的
因而，总的个数应当是n/5 + n/(55) + n/(55*5) + ...
解答
fun trailingZeors(n: Long): Long { var num : Long = n / 5 var zeroNums : Long = num while (num > 0){ num /= 5 zeroNums += num } return zeroNums} public long trailingZeros(long n) { long num = n / 5; long zeroNums = num; while (num > 0) { num /= 5; zeroNums += num; } return zeroNums;} 2. 打印数字
描述
给一个整数n. 从 1 到 n 按照下面的规则打印每个数：
- 如果这个数被3整除，打印fizz
- 如果这个数被5整除，打印buzz
- 如果这个数能同时被3和5整除，打印fizz buzz
样例
比如 n = 15, 返回一个字符串数组：
[ "1", "2", "fizz", "4", "buzz", "fizz", "7", "8", "fizz", "buzz", "11", "fizz", "13", "14", "fizz buzz"]分析
逻辑清晰简单，并无值得分析之处
解答
fun fizzBuzz(n : Int) : Array{ var output : Array = Array(n, {""}) for (i in 1..n) { if (i % 3 == 0 && i % 5 == 0) { output[i-1] = "fizz buzz" } else if (i % 3 == 0) { output[i-1] = "fizz" } else if (i % 5 == 0) { output[i-1] = "buzz" } else { output[i-1] = i.toString() } } return output}
public ListfizzBuzz(int n) { // write your code here List output = new ArrayList<>(); for (int i=1; i<=n; i++) { if (i % 3 == 0 && i % 5 == 0) { output.add("fizz buzz"); } else if (i % 3 == 0) { output.add("fizz"); } else if (i % 5 == 0) { output.add("buzz"); } else { output.add(String.valueOf(i)); } } return output;}
3.二分查找
描述
给定一个排序的整数数组和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1
样例
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2
分析
简单的二分查找问题，无须分析
解答
fun binarySearch(nums : IntArray, target : Int) : Int{ var start = 0 var end = nums.size while (end - start > 1) { var mid = (end + start) / 2 when { nums[mid] > target -> end = mid nums[mid] < target -> start = mid else -> return mid } } return when(target) { nums[start] -> start nums[end] -> end else -> -1 }} 4.出现次数统计
描述：
计算数字k在0到n中的出现的次数，k可能是0~9的一个值
样例
例如n=12，k=1，在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]，我们发现1出现了5次 (1, 10, 11, 12)
分析
假设一个数n=4324，先考虑低位上的规律（先不计入千位）
- 只考虑个位数上的出现次数(n>10)，则可以按照0~9，10~19来划分，每10个数字出现1次，记为$$1*10^0$$
- 只考虑十位数和个位数的出现次数(n>100)，则除了个位数上的出现次数，在十位数上，还会出现10次重复，即10+10*1=20，记为$$2*10^1$$
- 只考虑百位数和十位、各位数的出现次数(n>1000)，则在百位数上会出现100次重复，同时，前面讨论的重复次数会再增加十倍，即100+20*10,记为$$3*10^2$$
再考虑千位本身，此时千位数字为4
- 若k<4，那么在千位上会出现1000次重复
- 若k=4，那么在千位上会出现324+1次重复
- 若k>4，那么在前为上不会出现重复
其它数字规律以此类推
解答
fun digitCounts(k : Int, n : Int) : Int{ var num = n var sum = 0 while (num > 0) { val len = num.toString().length - 1 val base = Math.pow(10.0, len.toDouble()).toInt() sum += len * (base / 10) * (num / base) if (k > 0 && num / base > k) { sum += base } else if (k > 0 && num / base == k) { sum += num % base + 1 } num %= base } //计算式对0不通用，需要再+1 if (k == 0) { sum += 1 } return sum} public int digitCounts(int k, int n) { int sum = 0; while (n > 0) { int len = String.valueOf(n).length() - 1; int base = (int)Math.pow(10, len); sum += len * (base / 10) * (n / base); if (k > 0 && n / base > k) { sum += base; } else if (k > 0 && n / base == k) { sum += n % base + 1; } n %= base; } //计算式对0不通用，需要再+1 if (k == 0) { sum += 1; } return sum;}