编程之美1:那些关于1的个数的经典面试题 - XIAXIA__的专栏 - 博客频道 - CSDN.NET


编程之美1:那些关于1的个数的经典面试题 - XIAXIA__的专栏 - 博客频道 - CSDN.NET

题目1 给定一个十进制正整数N,写下从1开始,到N的所有整数,然后数一下其中出现的所有"1"的个数

<1>1位数情况
这个简单,如果N = 3,那么从1到3的所有数字:1,2,3,只有个位数出现1,而且只出现一次。可以发现,N是个位数时,N >=1,那么f(N)= 1;N = 0,f(N)= 0;
<2>2位数情况
<3>3位数情况

同理分析4位数,5位数。。。。。
设N = abcde ,其中abcde分别为十进制中各位上的数字。
如果要计算百位上1出现的次数,它要受到3方面的影响:百位上的数字,百位一下(低位)上的数字,百位一上(高位)上的数字
如果百位上数字为0,百位上可能出现1的次数由更高位决定。比如:12013,则可以知道百位出现1的情况可能是:100~199,1100~1199,2100~2199,,.........,11100~11199,一共1200个。可以看出是由更高位数字(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)。

int Sumls(int n)
{
    int iCount=0,iFactor=1,iLowerNum=0,iCurrNum=0,iHigherNum=0;
    while(n/iFactor!=0)
    {
        iLowerNum=n-(n/iFactor)*iFactor;
        iCurrNum=(n/iFactor)%10;
        iHigherNum=n/(iFactor*10);
       
        switch(iCurrNum)
        {
            case 0:
                iCount+=iHigherNum*iFactor;
                break;
            case 1:
                iCount+=iHigherNum*iFactor+iLowerNum+1;
                break;
            default:
                iCount+=(iHigherNum+1)*iFactor;
                break;
                       
        }
        iFactor*=10;
       
    }
    return iCount; 
}

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;
}
http://blog.csdn.net/xiaxia__/article/details/44957999
public static int getOneShowTimes(int N) { int numPerBit; //存储每一位的数目 int sumTimes = 0; //存储最后的结果 int quan = 1; //每一位的权值,各位为1,十位为10,依次类推 int tempN = N; if (0 == N) { return 0; } while(0 != tempN) { numPerBit = tempN % 10; sumTimes += getOneShowTimesPerBit(N, numPerBit, quan); tempN /= 10; quan *= 10; } return sumTimes; } public static int getOneShowTimesPerBit(int N, int numPerBit, int quan) { if (0 == numPerBit) { return N / (quan * 10) * quan; } else if (1 == numPerBit) { return (N / (quan * 10)) * quan + N % quan + 1; } else { return (N / (quan * 10) + 1 ) * quan; } }

解法1 暴力穷举
层循环要循环N次,内存循环要循环log10N+1次,所以总的复杂度为O(N(log10N+1))
int getOneShowSumTimes(unsigned int N) { unsigned int count = 0; for (unsigned int i = 0; i <= N; i++) { count += getOneShowTimes(i); } return count; } int getOneShowTimes(unsigned int n) { unsigned count = 0; while(0 != n) { count += (n % 10) == 1 ? 1 : 0; n /= 10; } return count; }
Read full article from 编程之美1:那些关于1的个数的经典面试题 - XIAXIA__的专栏 - 博客频道 - CSDN.NET

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts