#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { char* str = "abcde"; int array[15] = {1, 2, 4, 8, 16, 3, 6, 12, 24, 7, 14, 28, 15, 30, 31}; int len = strlen(str); int i = 0; for (i = 0; i < 15; ++i) { int k = 0; int m = 0; for (k = 1; k <= 32; k <<= 1) { if (array[i] & k) { printf("%c\t", str[m]); } ++m; } printf("\n"); } system("pause"); return 0; }
可以看到如果把对数值的计算提取到之前的循环外边的话 时间复杂度会降低很多
对于这个题要输出的子串存在一个规律:比如输出我们对所有的字符都以一位编码 则对于abcde 这样一个串 输出a记作00001(1) 输出b记作00010(2) 输出c记作00100(4) 输出d记作01000(8) 输出e则记作10000(16) 输出ab 则记作00011(3) 输出bc 则记作00110(6) 输出cd记作01100(12) 输出de则记作11000(24) 输出abc记作00111(7) 输出bcd记作01110(14) 输出cde记作11100(28) 输出abcd记作01111(15) 输出11110(30) 输出abcde 记作11111(31) 则可以发现规律 前5个记作(2^1-1)*2^i 从第六个开始的四个数记作 (2^2-1)*2^i 之后的3个数记作 (2^3-1)*2^i 之后的两个数 (2^4-1)*2^i 之后的一个数记作(2^5-1)*2^i i从零开始. 整体发现规律则是记字符串长度为n, 则对于长度为1的个数为n 长度为2的长度为n-1 对于长度为3的个数为n-2 依次类推 这样我们就可以总结出一个规律 for (i = n; i > 0; --i) { int len = n; int pos = len - i; int j = 0; for (; j < n; ++j){ nums[j] = array[pos] * array[j];}} 在array[]数组中存储的2^0-2^30 这样再做位运算 从而决定输出那个位置的字符就可以 但是貌似这样对时间复杂度没有什么改善 也是O(n*n*n)的。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47 |
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 15int
main(void){ char* str = "abcde"; int
array[MAX] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384}; int
len = strlen(str); int
i = len; for
(; i > 0; --i) { int
numbers[14]; int
j = 0; int
pos = len - i + 1; for
(j = 0; j < i; ++j) { numbers[j] = (array[pos] - 1) * array[j]; } for
(j = 0; j < i; ++j) { int
k = 0; int
m = 0; for
(k = 1; k <= array[MAX-1]; k <<= 1) { if
(numbers[j] & k) { printf("%c\t", str[m]); } ++m; } printf("\n"); } } system("pause"); return
0;} |
阿里实习生电面题目：输出给定字符串的全部连续子串,布布扣,bubuko.com
原文：http://www.cnblogs.com/coder-zhang/p/3618092.html