Skip to main content

leetcode 233, number of digit one

This question is marked as hard in leetcode. Initially, I think it is easy to solve and give an answer quickly, however, it can not pass by a very big number with the prompt: "Time Limit Exceeded", that means my algorithm do no work in a high efficiency.
Then I tried to find the regular pattern of this question. The regular pattern is as follows:
First, I divide the number by the sum of different numbers, such as 532, I divided it as 500+30+2, and calculate the number of one in (0,500], (0,30], (0,2]. However, this is a wrong solution, since I calculate duplicate numbers, (0,500], (0,30] all include (0,2]. Then I have to find another solution.
Second, I found the mistake in my last solution, that missed the number from (500, 532], then I divide the number 532 into three sets, 500, (500, 530], (530, 532]. It is pretty close to correct solution, however, I still missed another situation, that is if the number is 1111.
Finally, I get the correct solution, that is first I divide the number into different intervals which is the same with last solution, 500, (500, 530], (530, 532]. we still need to consider the situation if there is one in the number, such as 1101. I add another variable to store how many ones in the number. so the solution is as follows:

Labels:

Comments

Post a Comment

Popular posts from this blog

leetcode 141 && 142 Linked List Cycle I && II

141. Linked List Cycle Given a linked list, determine if it has a cycle in it. Follow-up : Can you solve it without using extra space? 142. Linked List Cycle 2 Given a linked list, return the node where the cycle begins. If there is no cycle, return NULL Note:  Do not modify the linked list. Follow-up : Can you solve it without using extra space? These two questions are all related to linked list, question 2 goes further than 1. First, we set two pointers: one is "fast", means it forwards two step each loop, another is "slow", means it forwards one step each loop. Initially, both of them point to the head. Second, if there exists a cycle in linked list, finally "fast" will catch up "slow" from the backward; otherwise, fast will reach to NULL first, then we return. That is the end of question 1. The accepted code is as following:            bool hasCycle(ListNode *head) {         ListNode *f...
Post a Comment
Read more