首页 > 代码库 > Chap5:32– 35
Chap5:32– 35
32. 从 1 到 n 整数中 k (0,1, 2, 3, 4, 5, 6, 7, 8, 9)出现的次数。 时间 O(log10N)
A. 当 K != 0 时:
以 n = 2014,K = 1 为例来找规律。从 1 至 2014 中,数字 1 总计出现了 1607 次,其中有 202 次出现在个位,205 次出现在十位,200 次出现在百位,1000 次出现在千位。
分析:
首先是个位。从 1 至 2014 中,包含了 201 个 10,个位是 1 时,高位分别为 0 — 200。当高位为 201 时,因为 4 > K,出现 1 次 2011。故共出现 201 * 1 + 1 = 202 次。
然后是十位。从 1 至 2014 中,包含了 20 个 100,高位为 0 — 19 ,十位为 1 时,低位(个位)分别有10种情况。剩下的数字是从 2000 至 2014,它们的十位数字 1 = K,因此包含了 2010, 2011,2012,2013, 2014 共 5 个数。所以有 20 * 10 + 5 = 205 次。
接下来是百位。从 1 至 2000 中,包含了 2 个 1000,因此 K 出现了 2×100=200 次。剩下的数字是从 2000 至 2014,它们最大的百位数字 0 < K,所以高位为 20 时,百位不会出现 1 。因此共有 2 * 100 = 200 次。
最后是千位。此时高位是 0 一种情况,千位数字 2 > K,所以千位是 K 的情况有 1 * 1000 = 1000 。到此为止,已经计算出全部数字 1 的出现次数。
B. 当 K = 0 时:
高位是 0 的情况取消(想想为什么),如 2014,共有 516 次。其中个位 201 次,十位 200 次, 百位 115次, 千位 0 次。
#include <iostream> using namespace std; int numberOfK(int n, int k) // 10 > k >= 0 { int count = 0; int cur_pos = 1; int high, low; do { high = n / (cur_pos * 10); low = n % cur_pos; int cur_digit = n % (cur_pos * 10) / cur_pos; if(cur_digit < k) count += high * cur_pos; else{ if(k == 0) --high; if(cur_digit == k) count += high * cur_pos + low + 1; // when high == 0, cur_digit must be the last number that is not 0. else count += high * cur_pos + cur_pos; if(k == 0) ++high; } cur_pos *= 10; }while(high > 0); return count; } int main() { cout << numberOfK(101, 1) << endl; cout << numberOfK(101, 0) << endl; return 0; }
33. 把正整数数组排成最小的数
#include <iostream> #include <cstdlib> #include <cstring> using namespace std; #pragma warning(disable : 4996) int cmp(const void *str1, const void *str2); char combine1[21]; // length of int number is no more than 10 char combine2[21]; void getMinNumber(int data[], int length) { if(data =http://www.mamicode.com/= NULL || length < 0) return; char **strData = http://www.mamicode.com/new char*[length]; for(int i = 0; i < length; ++i) { strData[i] = new char[11]; sprintf(strData[i], "%d", data[i]); } qsort(strData, length, sizeof(char*), cmp); for(int i = 0; i < length; ++i) printf("%s", strData[i]); printf("\n"); for(int i = 0; i < length; ++i) delete[] strData[i]; delete[] strData; } int cmp(const void *str1, const void *str2) { strcpy(combine1, *(const char**)str1); strcpy(combine2, *(const char**)str2); strcat(combine1, *(const char**)str2); strcat(combine2, *(const char**)str1); return strcmp(combine1, combine2); } int main() { int data[] = {3, 2, 1, 6, 5, 4, 9, 8, 7, 10}; getMinNumber(data, 10); return 0; }
34. 丑数
丑数:只包含因子 2、3 和 5 的数。习惯把 1 作为第一个丑数。
找出第 n 个丑数。 如 n = 1500.
#include <iostream> #include <cstdlib> #include <cstring> using namespace std; const int N = 1000000; int uglyNumber[N] = {1}; int min(int a, int b, int c) { a = a > b ? b : a; a = a > c ? c : a; return a; } void getUglyNumber(int N) { int t2, t3, t5, cnt = 1; t2 = t3 = t5 = 1; while(cnt < N) { uglyNumber[cnt] = min(t2*2, t3*3, t5*5); while(t2*2 <= uglyNumber[cnt]) ++t2; while(t3*3 <= uglyNumber[cnt]) ++t3; while(t5*5 <= uglyNumber[cnt]) ++t5; ++cnt; } } int main() { int k; getUglyNumber(N); while(true) { cin >> k; if(k < N) cout << uglyNumber[k] << endl; } return 0; }