有换房顶的contractor 推荐么？# Living
S*C
1 楼
一道career cup、leetcode的原题变种，也是lintcode原题，但目前没有发现无bug的
最优解，所有中国人都做错了，或者明显是非最优解
leetcode上是
Number of Digit One My Submissions Question
Total Accepted: 12345 Total Submissions: 55909 Difficulty: Medium
Given an integer n, count the total number of digit 1 appearing in all non-
negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12,
13.
https://leetcode.com/problems/number-of-digit-one/
最精简最优解是
public int countDigitOne(int n) {
int res = 0;
for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
long left = n / powerOf10, right = n % powerOf10;
res += (left + 8) / 10 * powerOf10;
if (left % 10 == 1)
res += right + 1;
}
return res;
}
career cup上是8.4 Write a method to count the number of 2s between 0 and n
最优解是
public int countDigitTwo(int n) {
int res = 0;
for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
long left = n / powerOf10, right = n % powerOf10;
res += (left + 7) / 10 * powerOf10;
if(left % 10 == 2)
res += right + 1;
}
return res;
}
lintcode上的变种是
Digit Counts
Count the number of k's between 0 and n. k can be 0 - 9.
Example: if n=12, in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we have
FIVE 1's (1, 10, 11, 12)
http://lintcode.com/en/problem/digit-counts/
用同样的方法能通过绝大部分test case，但当k=0时答案错误
public int digitCounts(int k, int n) {
int res = 0;
for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
long left = n / powerOf10, right = n % powerOf10;
res += (left + 9 - k) / 10 * powerOf10;
if(left % 10 == k && k > 0)
res += right + 1;
}
return res;
}
这答案该怎么改？
最优解，所有中国人都做错了，或者明显是非最优解
leetcode上是
Number of Digit One My Submissions Question
Total Accepted: 12345 Total Submissions: 55909 Difficulty: Medium
Given an integer n, count the total number of digit 1 appearing in all non-
negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12,
13.
https://leetcode.com/problems/number-of-digit-one/
最精简最优解是
public int countDigitOne(int n) {
int res = 0;
for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
long left = n / powerOf10, right = n % powerOf10;
res += (left + 8) / 10 * powerOf10;
if (left % 10 == 1)
res += right + 1;
}
return res;
}
career cup上是8.4 Write a method to count the number of 2s between 0 and n
最优解是
public int countDigitTwo(int n) {
int res = 0;
for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
long left = n / powerOf10, right = n % powerOf10;
res += (left + 7) / 10 * powerOf10;
if(left % 10 == 2)
res += right + 1;
}
return res;
}
lintcode上的变种是
Digit Counts
Count the number of k's between 0 and n. k can be 0 - 9.
Example: if n=12, in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we have
FIVE 1's (1, 10, 11, 12)
http://lintcode.com/en/problem/digit-counts/
用同样的方法能通过绝大部分test case，但当k=0时答案错误
public int digitCounts(int k, int n) {
int res = 0;
for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
long left = n / powerOf10, right = n % powerOf10;
res += (left + 9 - k) / 10 * powerOf10;
if(left % 10 == k && k > 0)
res += right + 1;
}
return res;
}
这答案该怎么改？
