2023年7月20日发(作者：)

整理C++⾯试经典编程题1.数组乘机输⼊：⼀个长度为n的整数数组input；输出：⼀个长度为n的整数数组result，满⾜result[i]=input数组中除了input[i]之外所有数的乘积（假设不会溢出）。⽐如输⼊：input={2,3,4,5}，输出result={60,40,30,24}。程序要求：具有线性复杂度，且不能使⽤除法运算符。思路：left[i]存储input[i]之前所有元素的乘积，right[i]存储input[i]之后所有元素的乘积，那么result[i]=left[i]*right[i]。则时间复杂度为O(n)，空间复杂度为O(n)。int* calresult(int* input, int n){ int* left = new int[n]; int* right = new int[n]; int* result = new int[n]; left[0] = 1; for (int i = 1; i < n; i++) { left[i] = left[i - 1] * input[i - 1]; } right[n - 1] = 1; for (int i = n - 2; i >= 0; i--) { right[i] = right[i + 1] * input[i + 1]; } for (int i = 0; i < n; i++) { result[i] = left[i] * right[i]; } delete[] left; delete[] right; return result;}提⾼：可以把空间复杂度降低，result[i]先存储input[i]之前所有元素的乘积，然后从右到左依次算出真正的result[i]。int* calresult1(int* input, int n){ int* result = new int[n]; result[0] = 1; for (int i = 1; i < n; i++) { result[i] = result[i - 1] * input[i - 1]; } result[0] = input[n - 1]; for (int i = n - 2; i > 0; i--) { result[i] *= result[0]; result[0] *= input[i]; } return result;}2.⼀个int数组，求出所有这样的数a[i]，其左边的数都⼩于等于它，右边的数都⼤于等于它。思路：使⽤rightMin[]来记录原始数组array[i]右边（包括⾃⼰）的最⼩值。然后从头遍历原始数组时，保存⼀个当前最⼤值leftMax，如果leftMax刚好等于rightMin[i]，则当前值满⾜条件。void smallLarge(int* arr, int n){ int i, leftMax; int* rightMin = new int[n]; rightMin[n - 1] = arr[n - 1]; for (i = n - 2; i >= 0; i--) { if (arr[i] < rightMin[i + 1]) rightMin[i] = arr[i]; else rightMin[i] = rightMin[i + 1]; } leftMax = arr[0]; for (i = 0; i < n; i++) { if (arr[i]>leftMax) leftMax = arr[i]; if (leftMax == rightMin[i]) cout << arr[i] << endl; } delete[] rightMin;}3.数组中有⼀个数字出现的次数超过了数组长度的⼀半，请找出这个数字。思路：也是“⽔王帖⼦”问题，使⽤排除法。可以理解为这个数字出现的个数⼀定⼤于其他全部数字出现的个数之和。int function(int* a, int n){ int cur_val; int cur_num=0; for (int i = 1; i < n; i++) { if (cur_num == 0) { cur_val = a[i]; cur_num++; } else { if (a[i] == cur_val) cur_num++; else cur_num--; } } return cur_val;}4.在长度为M的字符串中，查找长度为N的字符串。思路：KMP算法，是⾼效率的字符串匹配算法，时间复杂度为O(m+n)。KMP算法每当⼀趟匹配过程中出现字符⽐较不等时，不需回溯主串，⽽是利⽤已经得到的“部分匹配”结果将模式串向右滑动尽可能远的⼀段距离后，继续进⾏⽐较，且此时并不⼀定是拿模式串的第⼀位继续⽐较。//计算nextval数组。nextval[]存放的是⼦串每⼀个位置之前的字符串的前缀和后缀公共部分的最⼤长度void getNextVal(const char* partn, int plen, int* nextval){ int i = 0, j = -1; nextval[0] = -1; while (i < plen-1) { if (j == -1 || partn[i] == partn[j]) { i++; j++; nextval[i] = j; } else j = nextval[j]; }}int kmpSearch(const char* src, int slen, const char* partn, int plen){ int* nextval = new int[plen]; getNextVal(partn, plen, nextval); int i = 0, j = 0; while (i < slen && j < plen) { if (j == -1 || src[i] == partn[j]) { i++; j++; } else j = nextval[j]; //当匹配失败时 } delete[] nextval; if (j >= plen) return i - plen; else return -1;}5. 字符串转换为数字。输⼊⼀个表⽰整数的字符串，把该字符串转换成整数并输出。思路：需要考虑，正负号；⾮法输⼊——（1）需要判断指针是不是为空（2）输⼊的字符串可能含有不是数字的字符。每当碰到⾮法字符，转换停⽌（3）溢出问题。若溢出，返回0//字符串转换为数字int strToInt(const char* str){ assert(str != NULL); long long num; bool type = true; if (*str == '+') //是否带正负号 str++; else if (*str == '-') { type = false; str++; } num = 0; while (*str != '0') { if (*str >= '0'&& *str <= '9') { num = num * 10 + (*str - '0'); if (num > std::numeric_limits::max()) //溢出时返回0 { num = 0; break; } str++; } else //含有⾮法字符时返回0 { num = 0; break; } } if (!type) //负数的情况 num = 0 - num; return num;}6.输⼊两个很⼤的正数（⽤C字符串表⽰），输出它们的乘积。假设不考虑⾮法输⼊。注意：相乘的结果位数最多为la+lb。char* multiply(const char* a, const char* b){ assert(a != NULL && b != NULL); int i, j; int la = strlen(a); int lb = strlen(b); int* s = new int[la + lb]; memset(s, 0, (la+lb)*sizeof(int)); //每个元素赋初值0 for (i = 0; i < la; i++) for (j = 0; j < lb; j++) s[i + j + 1] += (a[i] - '0')*(b[j] - '0'); for (i = la + lb - 1; i > 0; i--) //这⾥实现进位操作 { if (s[i] >= 10) { s[i - 1] += s[i] / 10; s[i] %= 10; } } char* c = new char[la + lb+1]; i = 0; while (s[i] == 0) //跳过头部0元素 i++; for (j = 0; i < la + lb; i++, j++) { c[j] = s[i] + '0'; } c[j] = '0'; delete[] s; return c;}7.