資訊專欄INFORMATION COLUMN
摘要：題目給一個數(shù)求從到所有數(shù)中數(shù)字在各個位上出現(xiàn)的總次數(shù)。解法可以做循環(huán)從到挨個找。更好的是用歸納法總結(jié)出出現(xiàn)的次數(shù)的規(guī)律。
題目：
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
給一個數(shù)n,求從1到n所有數(shù)中數(shù)字1在各個位上出現(xiàn)的總次數(shù)。
解法：
可以做循環(huán)從1到n挨個找。慢。
更好的是用歸納法總結(jié)出1出現(xiàn)的次數(shù)的規(guī)律。
假設(shè)n=abcde五位數(shù)字的時候，我們分析百位c，有三種情況：
1）c == 0的時候，比如12013，此時百位出現(xiàn)1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，共1200個，顯然這個有高位數(shù)字決定，并且受當(dāng)前位數(shù)影響； 個數(shù)就是 ab*100
2）c == 1的時候，比如12113，此時百位出現(xiàn)1的肯定包括c=0的情況，另外還需要考慮低位的情況即：00100 ~ 00113共14個; 個數(shù)等于ab*100+ de + 1
3）c >= 2的時候，比如12213，此時百位出現(xiàn)1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，12 100 ~ 12 199，共1300個，這個有高位數(shù)字決定，其實是加一，并且乘以當(dāng)前位數(shù); 個數(shù)就是 (ab+1)*100
總結(jié)起來，對于一個 n = abcde 來說，百位出現(xiàn)1的個數(shù)計算方法為 ：
if(c==0) ans = ab*100;
if(c==1) ans = ab*100+cd+1
if(c>1) ans = (ab+1)*100
代碼：
public class Solution {
public int countDigitOne(int n) {
if(n <= 0) return 0;
int q = n; int x = 1; int ans = 0; int temp = 0;
do{
temp = q%10;
q/=10;
if(temp == 0) ans+=q*x;
else if(temp == 1) ans+=q*x + n%x + 1;
else
ans+=(q+1)*x;
x*=10;
} while (q > 0);
return ans;
}
}
Ref：
java one pass easy understand
leetcode 233
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66097.html
摘要：遞歸復(fù)雜度思路每次將一個數(shù)拆分成兩部分考慮，并考慮當(dāng)前最高是不是比如，將數(shù)拆分成，和，這兩部分分別計算。每次抹去高位，觀察重復(fù)情況。代碼代表位數(shù)，代表最高的值除了高位的剩余部分 LeetCode[23] Number of Digit One Given an integer n, count the total number of digit 1 appearing in alln...
摘要：題目要求計算所有小于等于的正整數(shù)中數(shù)字的個數(shù)。比如比小的正整數(shù)中包含的有，一共有個。因此，我們需要用更好的方法，減少這種方法的浪費。其實等價于中的的個數(shù)。 題目要求 Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal...
摘要：只有大于左邊界才部分包含，且只有大于右邊界的數(shù)才完整包含，這些中多余的。對于而言，部分包含用余數(shù)做，完整包含用進位后的商做。逐位向上累加，可得結(jié)果。千位萬位，大致如此。例如個位十位百位千位 Problem Given an integer n, count the total number of digit 1 appearing in all non-negative integer...
摘要：加一給定一個由整數(shù)組成的非空數(shù)組所表示的非負整數(shù)，在該數(shù)的基礎(chǔ)上加一。示例輸入輸出解釋輸入數(shù)組表示數(shù)字。思路指針從最后往前移動，若值為逐個加一，并賦值。不等于則退出循環(huán)。首位如果為是則證明需要進一。只需首位賦值即可。 加一 給定一個由整數(shù)組成的非空數(shù)組所表示的非負整數(shù)，在該數(shù)的基礎(chǔ)上加一。 最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個元素只存儲一個數(shù)字。 你可以假設(shè)除了整數(shù) 0 之外，這個...
摘要：加一給定一個由整數(shù)組成的非空數(shù)組所表示的非負整數(shù)，在該數(shù)的基礎(chǔ)上加一。示例輸入輸出解釋輸入數(shù)組表示數(shù)字。思路指針從最后往前移動，若值為逐個加一，并賦值。不等于則退出循環(huán)。首位如果為是則證明需要進一。只需首位賦值即可。 加一 給定一個由整數(shù)組成的非空數(shù)組所表示的非負整數(shù)，在該數(shù)的基礎(chǔ)上加一。 最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個元素只存儲一個數(shù)字。 你可以假設(shè)除了整數(shù) 0 之外，這個...
閱讀 4592·2021-09-10 11:22
閱讀 543·2019-08-30 11:17
閱讀 2576·2019-08-30 11:03
閱讀 439·2019-08-29 11:18
閱讀 3466·2019-08-28 17:59
閱讀 3225·2019-08-26 13:40
閱讀 3174·2019-08-26 10:29
閱讀 1145·2019-08-26 10:14
