##題目描述 求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了，ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數），
思路
數字轉字串統計，
時間復雜度O(nlgn)，空間復雜度O(nlgn)，
數學方法分析，
回圈數字的每一位，固定該位，計算其余位的組合情況，
時間復雜度O(len)，空間復雜度O(1)，
轉字串代碼
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if(n < 1) return 0;
int count = 0;
char[] cs = null;
for(int i = 1; i <= n; i++) {
cs = (i+"").toCharArray();
for(char c : cs) {
if(c == '1') {
count++;
}
}
}
return count;
}
}
數學方法代碼
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if(n < 1) return 0;
int count = 0;
int a = 0, b = 0;
for(int k = 1; k <= n; k*=10) {
a = n/k;
b = n%k;
count += (a+8)/10*k + (a%10 == 1 ? b+1 : 0);
}
return count;
}
}
筆記
(a+8)/10*k ≠ k*(a+8)/10
-
String轉int兩種方式
1.Integer.parseInt(str)
2.Integer.valueOf(str).intValue() -
int轉String三種方式
1.num + ""
2.String.valueOf(num)
2.Integer.toString(num)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83466.html
標籤：其他
上一篇：連續子陣列的最大和
下一篇：把陣列排成最小的數