从功能测试，边界测试和负面测试三个方面设计测试用例，保证代码的完整性。
关于异常处理的三种方式
| 优点 | 缺点 | |
|---|---|---|
| 返回值 | 和系统api一致 | 不能方便使用计算结果 |
| 全局变量 | 能够方便使用计算结果 | 用户可能会忘记检查全局变量 |
| 异常 | 可以为不同的出错原因定义不同异常类，逻辑清晰明了 | 有些语言不支持抛出异常，抛出异常时对性能有负面影响 |
面试题11：数值的整数次方
题目：实现函数double Power(double base, int exponent)， 求base的exponent次方。不得使用库函数，同时，不考虑大数问题。
牛客网链接 https://www.nowcoder.com/practice/1a834e5e3e1a4b7ba251417554e07c00?tpId=13&&tqId=11165&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-rankingclass Solution { public: bool Invalid_flag = false; // 全局变量，标志输入是否合法 double Power(double base, unsigned int exponent) { double result = 1; for(int i = 1; i <= exponent; i++) { result *= base; } return result; } bool equal(double a, double b) { if ((a-b) < 0.0000001 && (a-b) > 0.0000001) { return true; } return false; } double Power(double base, int exponent) { Invalid_flag = false; if(equal(base, 0.0) && exponent < 0) // 注意小数相等判断不能直接用== { Invalid_flag = true; // 输入数据无效 return 0; } unsigned int tmp = (unsigned int)exponent; if (exponent < 0) { tmp = (unsigned int)(-exponent); } double result = Power(base, tmp); if (exponent < 0) { result = 1 / result; } return result; } };
考察点：
1.考虑到指数为负数的情况。尤其是指数为负数，底数为0的情况。注意在c++中判断小数相等不能直接用==，因为计算机在表示小数的时候是有误差的，要判断两个数绝对值的差在一个很小的范围内。
2.考察对于异常处理的方式。
3.乘方可以进行拆分
4.用右移代替除法，与代替余数运算，可以调高运算效率
面试题12：打印1到最大的n位数
题目：输入数字n，按顺序打印出从1到最大的n位10进制数。比如输入3，则打印1，2，3一直到999。 两种方法 1.字符串模拟加法 2.全排列，递归实现
leetcode链接
https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/ leetcode上这个链接其实有问题，他的返回定义成了vector<int>既然是int，其实没有考虑大数问题// // Created by Xue,Lin on 2020/6/25. // #ifndef UNTITLED_PRINT_N_NUMBER_H #define UNTITLED_PRINT_N_NUMBER_H #include "string" #include "iostream" using namespace std; // 方法1：字符串模拟加法操作 // 因为数字可能存在越界情况，因此用长度为n+1的字符串模拟数字，+1的原因是字符串末尾需要'/0'结束符 // increase函数进行+1操作，当达到上限返回true。printNumber函数进行打印操作 void printNumber(char* number) { // 打印非0开始数字 // 因为有字符串结束标志符，可以在函数中进行长度判断 bool start = true; for(int i = 0; i < strlen(number); i++) { if (number[i] == '0' && start) { continue; } start = false; cout << number[i]; } cout << " "; } // 注意需要变量保留进位标志 // 注意结束标志是当前已是n位数，且产生了进位 bool increase(char* number) { // 达到n位且产生进位时置true，外部循环可以结束 bool overFlow = false; // 进位标志符 int takeOver = 0; int len = strlen(number); for(int i = len - 1; i >= 0; i--) { // cout << "number: " << number << endl; // cout << "i: " << i << " takeover: " << takeOver << endl; int tmp; if (i == len - 1) { // 最后一位+1 tmp = number[i] - '0' + 1; } else{ // 其余位+进位 tmp = number[i] - '0' + takeOver; } number[i] = tmp % 10 + '0'; takeOver = tmp / 10; if (i == 0 && takeOver != 0) { overFlow = true; } // cout << "takeOver: " << takeOver << endl; } return overFlow; } void printMaxN(int n) { if(n <= 0) { return; } char* number = new char[n+1]; memset(number, '0', n); number[n] = '\0'; while(!increase(number)) { printNumber(number); } delete [] number; } // 方法2：全排列，递归 // 每一位都有0-9 10种选择 // 递归结束条件是已经设置到数字的最后一位 void printMaxRec(char* number, int index) { int len = strlen(number); // cout << "len: " << len << endl; if (index == len - 1) { printNumber(number); return; } for(int i = 0; i <= 9; i++) { number[index + 1] = '0' + i; printMaxRec(number, index + 1); } } void printMaxNRec(int n) { if (n <= 0) { return; } // cout << "n:" << n << endl; char* number = new char[n+1]; memset(number, '0', n); // 注意一定要有这个赋值操作，不然strlen长度是0 ！！！ number[n] = '\0'; // cout << "len1: " << strlen(number) << endl; for(int i = 0; i <= 9; i++) { number[0] = '0' + i; printMaxRec(number, 0); } } #endif //UNTITLED_PRINT_N_NUMBER_H
考察点：大数问题
当存在大数越界风险，需要用字符串模拟数字
注意用字符串模拟数字相加时进位和判断长度是否超限方法。
注意打印函数需要去前面无效0
本题扩展：在前面代码中，我们都是用一个char型字符表示十进制数字中的一位，但是char占8个bit，可以表示256个字符，用来表示10进制有些浪费，有没有其余更高效的方法来表示大数。
答：想到的方法是用bit来表示，用4个bit来表示一个数。但是感觉写起来比较麻烦，不研究了。
相关题目：定义一个函数，在该函数中可以实现任意两个整数的加法。
// // Created by Xue,Lin on 2020/6/25. // #ifndef UNTITLED_SUM_H #define UNTITLED_SUM_H #include <iostream> #include "math.h" using namespace std; // 任意两个整数的和，是个大数问题，两个整数的和可能会超出int // 相比+1这个大数问题，这个函数需要增加考虑负数情况 // 一个加法函数，一个打印函数 void printNumber(char* number) { // 符号在函数外处理，打印的时候不考虑 bool start = true; for(int i = 0; i < strlen(number); i++) { if (number[i] == '0' && start) { continue; } start = false; cout << number[i]; } cout << " "; } void sum(const int a, const int b) { // 如果是一个正数，一个负数，肯定不会超限 if ((a >= 0 && b <= 0) || (a <= 0 && b >= 0)) { cout << a + b << endl; return; } // 这里需要判断下a和b的符号，若是负数，可以先输出-号 // 这里有个坑，负数最小 -2^31，正数最大2^31-1 转换会有问题 // 这里转换下的原因是我更习惯操作正数，没有其余原因 int tmpA = a; int tmpB = b; if(a < 0) { cout << '-'; tmpA = -1 - a; tmpB = -1 - b; } // 我有个不一样的想法 // 不用转换字符串 // c++带符号int最多2147483647,为10位数 // 把进位和最高位记录下来，再加一下就可以了 int max = int(pow(10, 9)); // 注意pow返回是double int a1 = tmpA / max; int b1 = tmpB / max; int a2 = tmpA % max; int b2 = tmpB % max; int low; if (a < 0) { low = a2 + b2 + 2; } else{ low = a2 + b2; } /* cout << "a1: " << a1 << " b1: " << b1; cout << " a2: " << a2 << " b2: " << b2; cout << " low: " << low << endl; */ int high = low / max + a1 + b1; if (high != 0) { cout << high << low << endl; } else{ cout << low << endl; } // printNumber(number); return; } #endif //UNTITLED_SUM_H
考察点：由于没有限定两个数大小范围，需要当做大数来处理。同时，需要考虑，如果输入数字中有负数，应该如何处理。
面试题13：在o(1)时间内删除链表节点
给定单向链表的头指针和一个节点指针，定义一个函数，在o(1)时间内删除该节点链表节点和函数的定义如下：保证要删除节点一定在链表中
leetcode链接 https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/ 不太一样，还是自己写吧，正好再练下建立链表struct ListNode { int m_pValue; ListNode* m_pNext; }; void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)// // Created by Xue,Lin on 2020/6/25. // #ifndef UNTITLED_DELETE_VECTOR_NODE_H #define UNTITLED_DELETE_VECTOR_NODE_H #include<iostream> #include<vector> using namespace std; struct ListNode{ int val; ListNode* next; }; ListNode* createList(vector<int> arr) { if (arr.size() == 0) { return NULL; } ListNode* head = new ListNode; head->val = arr[0]; ListNode* pre = head; for(int i = 1; i < arr.size(); i++) { ListNode* tmp = new ListNode; tmp->val = arr[i]; pre->next = tmp; pre = pre->next; } pre->next = NULL; return head; } void printList(ListNode* head) { if (head == NULL) { return; } ListNode* tmp = head; while(tmp != NULL) { cout << tmp->val << " "; tmp = tmp->next; } cout << endl; } void deleteNode(ListNode** pListHead, ListNode* pToBeDelete) { // 因为要求时间复杂度是1，不能直接遍历 if (pListHead == NULL || *pListHead == NULL) { return; } // 要删除节点不是尾节点 if(pToBeDelete->next != NULL) { ListNode* next = pToBeDelete->next; pToBeDelete->val = next->val; pToBeDelete->next = next->next; delete next; next = NULL; } else if(*pListHead == pToBeDelete) { // 链表只有一个节点 delete pToBeDelete; pToBeDelete = NULL; *pListHead = NULL; } else { // 多个节点，但是是尾节点 /* 本来以为这么直接写会成功的，但是并没有，为什么这样不行呢。。 delete pToBeDelete; pToBeDelete = NULL; */ ListNode* tmp = *pListHead; while(tmp->next != pToBeDelete) { tmp = tmp->next; } tmp->next = NULL; delete pToBeDelete; pToBeDelete = NULL; } } #endif //UNTITLED_DELETE_VECTOR_NODE_H // main中 vector<int> arr = {2,3,1}; ListNode* head = createList(arr); deleteNode(&head, head->next->next); printList(head);
解题思路：
要删除节点，首先想到是找到该节点前一个节点，然后将其next指向要删除节点next，但是找到前一个节点需要从头指针开始遍历，不符合时间复杂度o(1)要求。
变换思路，要删除当前节点，其实可以用当前节点next覆盖掉当前节点，然后删除当前节点的next节点，不需要从前往后遍历，时间复杂度o(1)。
注意要删除节点是尾节点和链表只有一个节点的情况。
leetcode 上那个题因为给的是value，只能找前一个节点，注意判断删除节点是不是头节点：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if (head->val == val)
{
head = head->next;
return head;
}
ListNode* index = head;
while(index->next != NULL)
{
if (index->next->val == val)
{
index->next = index->next->next;
break;
}
index = index->next;
}
return head;
}
};
面试题14：调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数，调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
leetcode链接 https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/class Solution { public: vector<int> exchange(vector<int>& nums) { // 双指针 vector<int> result = nums; int begin = 0, end = result.size() - 1; while(begin <= end) { if (result[begin] % 2 != 0) { begin++; continue; } if (result[end] % 2 == 0) { end--; continue; } int tmp = result[end]; result[end] = result[begin]; result[begin] = tmp; } return result; } };
解题思路：首尾双指针。尾指针指向遇到的第一个奇数，首指针指向遇到的第一个偶数，交换。
升级：把判断条件拎出来设计成独立函数，可以提高代码兼容性。
