编程笔试题解析：计算正整数序列与字符串排序算法

"这篇资源包含了来自百度、腾讯等知名IT公司的校园招聘软件工程师笔试题，主要涉及编程题目，包括序列生成和字符串处理两个问题。" 在这篇资源中，我们有两个编程题目，它们都是针对软件工程师的基本能力进行考察的。首先，第一道题目要求设计一个函数`void generate(int a, int b, int N, int* Q)`，该函数用于生成一个序列，序列中的每个元素都能被正整数a和b中的至少一个整除。给定a、b和序列长度N，函数需要将序列的前N项存储到数组Q中。 该问题可以通过合并两个序列的方法解决，类似于归并排序中的合并操作。我们可以创建两个虚拟序列A和B，A包含所有a的倍数，B包含所有b的倍数。然后使用两个指针i和j分别跟踪A和B的当前元素，每次选取较小的值放入结果序列，并将对应的指针向后移动一位，直到达到N项。在实际实现时，无需额外创建两个数组，仅用两个变量就能完成。 下面是一个简单的C++实现： ```cpp #include<iostream> using namespace std; void Generate(int a, int b, int N, int* Q) { int tmpA, tmpB; int i = 1; int j = 1; for (int k = 0; k < N; k++) { tmpA = a * i; tmpB = b * j; if (tmpA <= tmpB) { Q[k] = tmpA; i++; } else { Q[k] = tmpB; j++; } } } int main() { int Q[6]; Generate(3, 5, 6, Q); return 0; } ``` 第二道题目是一个字符串处理问题，要求编写一个函数`void proc(char* str)`，将输入字符串中的所有小写字母移到所有大写字母之前，同时保持大写和小写字母各自的相对顺序。这个问题可以借鉴快速排序中的分区思想来解决。 我们可以使用两个指针i和j，i初始指向字符串的开头，j从i+1开始向后遍历。当j遇到一个小写字母时，与i指向的字符交换位置，然后将i和j都向后移动一位。重复这个过程，直到j遍历完整个字符串。这样，最终i之前的字符就是所有的小写字母，i之后的就是大写字母，它们之间的相对顺序保持不变。 以下是一个C++的示例实现： ```cpp #include<iostream> using namespace std; void proc(char* str) { int i = 0, j = 0; while (str[j] != '\0') { if (islower(str[j])) { char temp = str[i]; str[i] = str[j]; str[j] = temp; i++; } j++; } } int main() { char str[] = "BaCdaEfGhI"; proc(str); cout << str << endl; return 0; } ``` 这两个题目考察了程序员的基础算法知识和解决问题的能力，包括序列生成、数组操作、字符串处理以及对排序算法的理解。在准备这类笔试题时，应重点掌握基础数据结构、算法以及逻辑思维能力，这对于软件工程师来说是非常重要的。