S*******C
发帖数: 822 | 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;
}
这答案该怎么改？ | S*******C
发帖数: 822 | 2 想出来了
最优解是
public int digitCounts(int k, int n) {
int res = k == 0 ? 1 : 0;
for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
long left = n / powerOf10, right = n % powerOf10;
if (k != 0)
res += (left + 9 - k) / 10 * powerOf10;
else
res += left / 10 * powerOf10;
if (left % 10 == k && k > 0)
res += right + 1;
}
return res;
}
你可以用Brute force的解法来测试
public int digitCounts(int k, int n) {
int[] record = new int[10];
for (int i = 0; i <= n; i++) {
String s = Integer.toString(i);
for (int j = 0; j < s.length(); j++)
record[s.charAt(j) - '0']++;
}
return record[k];
} | S*******C
发帖数: 822 | 3 有些test case还是不对，谁帮忙优化一下
比如
Between 0 and 806471: 401888
Between 0 and 806471: 398360
Between 0 and 1396407: 787881
Between 0 and 1396407: 787879
【在 S*******C 的大作中提到】
: 想出来了
: 最优解是
: public int digitCounts(int k, int n) {
: int res = k == 0 ? 1 : 0;
: for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
: long left = n / powerOf10, right = n % powerOf10;
: if (k != 0)
: res += (left + 9 - k) / 10 * powerOf10;
: else
: res += left / 10 * powerOf10;
| x*******1
发帖数: 28835 | |
|
