原题目
描述
信息社会，有海量的数据需要分析处理，比如公安局分析身份证号码、 QQ 用户、手机号码、银行帐号等信息及活动记录。
采集输入大数据和分类规则，通过大数据分类处理程序，将大数据分类输出。
请注意本题有多组输入用例。
输入描述：
- 一组输入整数序列I和一组规则整数序列R，I和R序列的第一个整数为序列的个数（个数不包含第一个整数）；整数范围为0~0xFFFFFFFF，序列个数不限
输出描述：
- 从R依次中取出R，对I进行处理，找到满足条件的I： I整数对应的数字需要连续包含R对应的数字。比如R为23，I为231，那么I包含了R，条件满足 。
按R从小到大的顺序:
附加条件：
序列I：15,123,456,786,453,46,7,5,3,665,453456,745,456,786,453,123（第一个15表明后续有15个整数）
序列R：5,6,3,6,3,0（第一个5表明后续有5个整数）
输出：30, 3,6,0,123,3,453,7,3,9,453456,13,453,14,123,6,7,1,456,2,786,4,46,8,665,9,453456,11,456,12,786
说明：
示例1
输入：
15 123 456 786 453 46 7 5 3 665 453456 745 456 786 453 123
5 6 3 6 3 0
输出：
30 3 6 0 123 3 453 7 3 9 453456 13 453 14 123 6 7 1 456 2 786 4 46 8 665 9 453456 11 456 12 786
错误思路
一开始把重点放到这句话上了：
整数范围为0~0xFFFFFFFF，序列个数不限
这个取值范围已经超过了Integer的最大值，所以不能用Integer了。
又看到序列个数不限。脑海里第一个想到是海量数据。
一想到海量数据，就潜意识的给自己指了个方向：
如果想查询快，就得建立查询索引，加上查询条件是包含关系。所以得设计一个数据结构，支持基于输入的数据解析成索引结构，然后支持查询。
一路想下去：
- 要设计一个多叉树，支持将"123123221"这类数字解析成由数字0到9组成的树型结构。叶子节点记录对应的索引位置。
- 需要在节点类有一个索引数组，记录实际该值在数组中的位置。
- 需要在根节点上又一个指针数组，引用所有以它开头的非根节点，设这个List为random，然后有一个HashMap，里面记录了0到9共10个根节点，假设有数组1234. 现在查询key=34. 我只要找到3的根节点。然后再找到random 列表，在里面找到节点4. 就会从根节点直接跳到另外一个节点，这个节点可能不是这棵树的节点，它可能是其他树的节点。
- 在查询的时候，我要一直往下遍历，图中经过的所有节点，只要该节点有索引值，我就要拿出索引值。同时往上串，再用stack做逆序，就能拿到该字符串的值。
一路想了就开始写代码了，搞了一上午写完了，调试各种报错。我开始怀疑了，是不是过度设计了，我这么做到底是为了什么？
错误总结
- 这道题题目字太多，迷惑性强。不能太抠字眼，把这个测试题目当需求做了。
- 一般考题会考算法，算法的三个指标是：时间复杂度，额外空间复杂度，常数项复杂度。我犯错就犯在额外空间复杂度上，且不说题目规模说输入量很大，这部分即使占用空间，也不算作算法的额外空间。而我想的思路，为了所谓的块， 引入了太复杂的设计。
- 太追求所谓的高效，而走入了怪圈。
正确思路
洗洗脸，第二天接着做，觉得需要做以下几点：
- 解析输入的数据，搞成两个数组。
- 对查询参数数组做排序，排序后去重。至于排序，参数少的时候可以选择O(N^2)级别的冒泡排序，插入排序，选择排序，参数多的时候，可以选择O(logN)的归并排序，堆排序，快速排序。
- 遍历去重后的查询数组参数，根据每个查询参数，遍历数据数组。
- 遍历的过程中，处理好 一共发现了多少个，统计有多少个数字，注意边界问题。
写代码的时候注意处理一下细节就好了。
不完美的代码如下：
import java.util.ArrayList;
import java.util.Scanner;
public class Main3 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLine()) {
String[] rArray = scanner.nextLine().split(" ");
String[] iArray = scanner.nextLine().split(" ");
Integer size = Integer.valueOf(iArray[0]);
int[] searchKeys = new int[size];
for (int i = 0; i < size; i++) {
searchKeys[i] = Integer.valueOf(iArray[i+1]);
}
selectSort(searchKeys);
ArrayList<String> params = new ArrayList(searchKeys.length);
int previous = Integer.MIN_VALUE;
for (int i = 0; i<searchKeys.length; i++) {
if (previous == searchKeys[i]) {
continue;
}
params.add(String.valueOf(searchKeys[i]));
previous = searchKeys[i];
}
params.trimToSize();
int total = 0;
StringBuilder sb = new StringBuilder();
for(String k : params) {
total = search(rArray, total, sb, k);
}
System.out.print(total);
System.out.println(sb.toString());
}
}
public static void selectSort(int[] arr) {
if (arr == null || arr.length<2) {
return;
}
for(int i=0; i<arr.length-1; i++) {
int minIndex = i;
for(int j=i+1; j<arr.length; j++) {
if (arr[j]<arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int a, int b) {
if (a==b) {
return;
}
arr[a] = arr[a] ^ arr[b];
arr[b] = arr[a] ^ arr[b];
arr[a] = arr[a] ^ arr[b];
}
private static int search(String[] rArray, int total, StringBuilder sb, String k) {
boolean notFind = true;
int findCount = 0;
StringBuilder single = new StringBuilder();
for(int j = 1; j<rArray.length; j++) {
if (rArray[j].contains(k)) {
if (notFind) {
notFind = false;
}
single.append(" ").append(j-1).append(" ").append(rArray[j]);
findCount++;
total += 2;
}
}
if (!notFind) {
total += 2;
sb.append(" ").append(k).append(" ").append(findCount);
sb.append(single.toString());
}
return total;
}
}
|