您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“Java怎么計算1到n整數(shù)中1出現(xiàn)的次數(shù)”的有關(guān)知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
求出1 ~ 13的整數(shù)中1出現(xiàn)的次數(shù),并算出100 ~ 1300的整數(shù)中1出現(xiàn)的次數(shù)?為此他特別數(shù)了一下1 ~ 13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)(從1 到 n 中1出現(xiàn)的次數(shù))。
思路很簡單,寫個for循環(huán),從1到n,在循環(huán)體中判斷這個數(shù)包含了多少個1
復(fù)雜度O(nlogn),面試官不怎么開心呢。。
設(shè)N = abcde,其中abcde分別為十進制中各位上的數(shù)字。
如果要計算百位上1出現(xiàn)的次數(shù),它要受到3方面的影響:百位上的數(shù)字,百位以下(低位)的數(shù)字,百位以上(高位)的數(shù)字。
①如果百位上數(shù)字為0,百位上可能出現(xiàn)1的次數(shù)由更高位決定。比如:12013,則可以知道百位出現(xiàn)1的情況可能是:100 ~ 199,1100 ~ 1199,2100 ~ 2199,,…,11100 ~ 11199,一共1200個??梢钥闯鍪怯筛呶粩?shù)字(12)決定,并且等于更高位數(shù)字(12)乘以 當(dāng)前位數(shù)(100)。
② 如果百位上數(shù)字為1,百位上可能出現(xiàn)1的次數(shù)不僅受更高位影響還受低位影響。比如:12113,則可以知道百位受高位影響出現(xiàn)的情況是:100 ~ 199,1100 ~ 1199,2100 ~ 2199,,….,11100 ~ 11199,一共1200個。和上面情況一樣,并且等于更高位數(shù)字(12)乘以當(dāng)前位數(shù)(100)。但同時它還受低位影響,百位出現(xiàn)1的情況是:12100~12113,一共114個,等于低位數(shù)字(113)+1。
③ 如果百位上數(shù)字大于1(2 ~ 9),則百位上出現(xiàn)1的情況僅由更高位決定,比如12213,則百位出現(xiàn)1的情況是:100 ~ 199,1100 ~ 1199,2100 ~ 2199,…,11100 ~ 11199,12100 ~ 12199,一共有1300個,并且等于更高位數(shù)字+1(12+1)乘以當(dāng)前位數(shù)(100)。
public int NumberOf1Between1AndN_Solution(int n) {
//1的個數(shù)
int count = 0;
//當(dāng)前位
int i = 1;
int current, after, before;
while((n/i)!= 0){
//高位數(shù)字
current = (n/i)%10;
//當(dāng)前位數(shù)字
before = n/(i*10);
//低位數(shù)字
after = n-(n/i)*i;
//如果為0,出現(xiàn)1的次數(shù)由高位決定,數(shù)量等于高位數(shù)字 * 當(dāng)前位數(shù)
if (current == 0) {
count += before * i;
} else if(current == 1) {
//如果為1,出現(xiàn)1的次數(shù)由高位和低位決定,高位*當(dāng)前位+低位+1
count += before * i + after + 1;
} else{
//如果大于1,出現(xiàn)1的次數(shù)由高位決定,(高位數(shù)字+1)* 當(dāng)前位數(shù)
count += (before + 1) * i;
}
//前移一位
i = i*10;
}
return count;
}
“Java怎么計算1到n整數(shù)中1出現(xiàn)的次數(shù)”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。