1. 題目

輸入一個整數 n ，求1～n這n個整數的十進制表示中1出現的次數。

例如，輸入12，1～12這些整數中包含1 的數字有1、10、11和12，1一共出現了5次。

示例 1： 輸入：n = 12 輸出：5示例 2： 輸入：n = 13 輸出：6限制： 1 <= n < 2^31

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

leetcode 同題：233. 數字 1 的個數

2. 解題

同題：程序員面試金典 - 面試題 17.06. 2出現的次數（找遞推規律）
LeetCode 1067. 范圍內的數字計數

• 循環，按位遍歷

class Solution { public:int countDigitOne(int n) {int i = 1, count = 0, high, cur, low;while(n/i)//遍歷每個位{high = n/(10*i);//高位cur = (n/i)%10;//當前位low = n-(n/i)*i;//低位if(cur == 0)count += high*i;else if(cur == 1)count += high*i+low+1;elsecount += (high+1)*i;i *= 10;}return count;} };

遞歸參考：leetcode題解

class Solution { public:int countDigitOne(int n) {if(n <= 0)return 0;string s = to_string(n);int high = s[0]-'0';int Pow = pow(10, s.size()-1);int last = n - high*Pow;if(high == 1)return countDigitOne(Pow-1)+countDigitOne(last)+last+1;// 最高位是1，如1234, 此時pow = 1000,那么結果由以下三部分構成：// (1) dfs(pow - 1)代表[0,999]中1的個數;// (2) dfs(last)代表234中1出現的個數;// (3) last+1代表固定高位1有多少種情況。elsereturn high*countDigitOne(Pow-1)+countDigitOne(last)+Pow;} };

總結

以上是生活随笔為你收集整理的剑指Offer - 面试题43. 1～n整数中1出现的次数（找规律+公式）的全部內容，希望文章能夠幫你解決所遇到的問題。

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