題目描述

求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數。 思路： 1)暴力解法，遍歷每一個數字的每一位，O(nlgn); 2)這題參照編程之美P140上面的算法寫的。可以參考資料。

設N = abcde ,其中abcde分別為十進制中各位上的數字。

如果要計算百位上1出現的次數，它要受到3方面的影響：百位上的數字，百位一下（低位）上的數字，百位一上（高位）上的數字。

如果百位上數字為0，百位上可能出現1的次數由更高位決定。比如：12013，則可以知道百位出現1的情況可能是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200個?？梢钥闯鍪怯筛呶粩底?#xff08;12）決定，并且等于更高位數字（12）乘以 當前位數（100）。

如果百位上數字為1，百位上可能出現1的次數不僅受更高位影響還受低位影響。比如：12113，則可以知道百位受高位影響出現的情況是：100~199，1100~1199,2100~2199，，.........，11100~11199，一共1200個。和上面情況一樣，并且等于更高位數字（12）乘以 當前位數（100）。但同時它還受低位影響，百位出現1的情況是：12100~12113,一共114個，等于低位數字（113）+1。

如果百位上數字大于1（2~9），則百位上出現1的情況僅由更高位決定，比如12213，則百位出現1的情況是：100~199,1100~1199，2100~2199，...........，11100~11199,12100~12199,一共有1300個，并且等于更高位數字+1（12+1）乘以當前位數（100）。

/*N = abcde 百位上數字是c 僅以求百位上出現1的情況為例。 */ int count = 0; //百位上數字為0,百位上可能出現1的次數由更高位決定 if(c == 0){ //等于更高位數字（ab）* 當前位數（100） count += ab*100; } //百位上數字為1,百位上可能出現1的次數不僅受更高位影響還受低位影響 else if(c == 1){ //更高位數字（ab） * 當前位數（100） + 低位數字（de）+1 count += ab*100 + de + 1; } //百位上數字大于1（2~9）,百位上出現1的情況僅由更高位決定 else{ //（更高位數字+1（ab+1））* 當前位數（100） count += (ab + 1) * 100; }

?

這里得到high,cur,low的方法一定要掌握，得到高位需要當前base * 10,得到低位就是利用除法去掉地位的方法，得到當前位的方法就是除法去掉低位后再除以10.舉例方法進行解決。

記住n /factor得到的是以factor對應的位結束的高位整數。

long long int Count(long long int n){ //1的個數 long long int count = 0; //當前位 long long int Factor = 1; //低位數字 long long int LowerNum = 0; //當前位數字 long long int CurrNum = 0; //高位數字 long long int HigherNum = 0; if(n <= 0){ return 0; } while(n / Factor != 0){ //低位數字 LowerNum = n - (n / Factor) * Factor; //當前位數字 CurrNum = (n / Factor) % 10; //高位數字 HigherNum = n / (Factor * 10); //如果為0,出現1的次數由高位決定 if(CurrNum == 0){ //等于高位數字 * 當前位數 count += HigherNum * Factor; } //如果為1,出現1的次數由高位和低位決定 else if(CurrNum == 1){ //高位數字 * 當前位數 + 低位數字 + 1 count += HigherNum * Factor + LowerNum + 1; } //如果大于1,出現1的次數由高位決定 else{ //（高位數字+1）* 當前位數 count += (HigherNum + 1) * Factor; } //前移一位 Factor *= 10; } return count; }

leetcode上面這道題必須寫成long類型才能通過，寫成int不能通過。

public:int NumberOf1Between1AndN_Solution(int n){if(n <= 0){return 0;}unsigned long long base = 1;unsigned long long low = 0;unsigned long long cur = 0;unsigned long long high = 0;unsigned long long cnt = 0;while((n / base) != 0){low = n - (n / base) * base;cur = (n / base) % 10;high = n / (base * 10);if(cur == 0){cnt += high * base;}else if(cur == 1){cnt += high * base + low + 1;}else if(cur > 1){cnt += (high + 1) * base;}base *= 10;}return cnt;} };

?

轉載于:https://www.cnblogs.com/dingxiaoqiang/p/8068153.html

總結

以上是生活随笔為你收集整理的30 整数中1出现的次数（从1到n整数中1出现的次数）这题很难要多看*的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。