十一、旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

测试用例：

• 功能测试，如输入的数组是升序排序数组的一个旋转。
• 边界值测试，如输入的数组是一个升序排序的数组，或只包含一个数字的数组。
• 特殊输入测试，如输入nullptr指针。

分析：旋转之后的数组实际上可以划分为两个排序的子数组，而且前面子数组的元素值更大，元素值最小的元素恰好是两个子数组的分界点。

拙劣二分查找法：

int find_min(int *pArr, int length){	if(pArr == nullptr || length <= 0)		return -1;	if(length == 1)		return pArr[0];	int left = 0;	int right = length - 1;	int mid = (right - left) / 2;	if(pArr[mid] < pArr[mid+1]) {		if(pArr[mid] > pArr[mid-1]) {			return find_min(pArr, mid + 1);			return find_min(pArr + mid, right - mid + 1);		}		else			return pArr[mid]; 	}	if(pArr[mid] > pArr[mid+1]) {		return pArr[mid+1];	}}

分析：没有考虑数组中有重复数字的情况，且该二叉查找法的实现代码存在纰漏。

完整解法：

int Min(int* numbers, int length){    if(numbers == nullptr || length <= 0)        throw new std::exception("Invalid parameters");     int index1 = 0;    int index2 = length - 1;    int indexMid = index1;    while(numbers[index1] >= numbers[index2])    {        // 如果index1和index2指向相邻的两个数，        // 则index1指向第一个递增子数组的最后一个数字，        // index2指向第二个子数组的第一个数字，也就是数组中的最小数字        if(index2 - index1 == 1)        {            indexMid = index2;            break;        }         // 如果下标为index1、index2和indexMid指向的三个数字相等，        // 则只能顺序查找        indexMid = (index1 + index2) / 2;        if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])            return MinInOrder(numbers, index1, index2);        // 缩小查找范围        if(numbers[indexMid] >= numbers[index1])            index1 = indexMid;        else if(numbers[indexMid] <= numbers[index2])            index2 = indexMid;    }     return numbers[indexMid];}int MinInOrder(int* numbers, int index1, int index2){    int result = numbers[index1];    for(int i = index1 + 1; i <= index2; ++i)    {        if(result > numbers[i])            result = numbers[i];    }    return result;}

考点：

• 对二分查找的理解。
• 应聘者思维的全面性，如排序数组本身是数组旋转的一个特例。

 

十二、矩阵中的路径

 

十三、机器人的运动范围

 

十四、剪绳子

 

十五、二进制中1的个数

题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如，把9表示成二进制是1001，有2位是1。

测试用例：

• 正数，包括边界值1、0x7FFFFFFF。
• 负数，包括边界值0x80000000、0xFFFFFFFF。
• 0。

循环的次数等于整数二进制的位数：

int number_of_1(int n){	int count = 0;	unsigned int flag = 1;	while(flag) {		if(n & flag)			count++;		flag = flag << 1;		// 左移32次后，flag变为0 	}	return count;}

分析：首先把n和1做与运算，判断n的最低位是不是为1。接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1……这样反复左移，每次都能判断n的其中一位是不是1。

循环的次数等于整数二进制中1的位数：

int number_of_1(int n){	int count = 0;	while(n) {		++count;		n = (n - 1) & n;	}	return count;}

　　

十六、数值的整数次方

题目：实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

分析：此题要求实现一个具有pow函数的功能的函数。要求实现特定库函数的功能是一类常见的面试题，特别是处理数值和字符串的函数。

考虑全面但不够高效的解法：

bool invalidInput = false;bool equal_double(double x1, double x2){	if ((x1 - x2 < 0.0000001) && (x1 - x2 > -0.0000001))		return true;	return false;}double Power(double base, int exponent){	if(equal_double(base, 0.0) && exponent <= 0) {		invalidInput = true;		return 0.0;	}	double ans = 1.0;	bool expIsNegative = false;	if(exponent < 0) {		expIsNegative = true;		exponent *= -1;	}	for(int i = 1; i <= exponent; ++i) {		ans *= base;	}	if(expIsNegative) {		ans = 1.0 / ans;	}	return ans;}

分析：在上段代码中，我们既考虑到底/指数为0的情况，又考虑到正确处理错误输入的情况。但该函数要做exponent-1次乘法，效率较低。

 

十七、打印从1到最大的n位数

题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数999。

简单思考后的解法：

void print_1_to_max(int n){	int maxNum = 1;	for(int i = 1; i <= n; ++i)		maxNum *= 10;	maxNum = maxNum - 1;	for (int i = 1; i <= maxNum; ++i)		printf("%d\t", i);}

分析：本题没有规定n的范围，故当输入的n很大时，整型（int）或者长整型（long long）都将溢出，即我们要考虑大数问题。

在字符串上模拟数字加法的解法：

/* 用字符串来解决大数问题 */void print_1_to_max(int n){	if(n <= 0)	return;	char *pNum = new char[n + 1];	memset(pNum, '0', n);	pNum[n] = '\0';	/* 开始依次处理每一个数 */ 	while(!increment(pNum))			// 当没有增加到999...9时 	{		print_pNum(pNum);	} 	delete []pNum;}/* 在表示数字的字符串pNum上增加1 *//* 在字符串表达的数字上模拟加法 */ bool increment(char *pNum){	bool isOverflow = false;　　　　　　// 用于判断最高位是否超出9	int takeOver = 0;　　　　　　　　　　// 用于进位	int len = strlen(pNum);	for(int i = len - 1; i >= 0; --i) {		int sum = pNum[i] - '0' + takeOver;		if(i == len -1)	sum++;		if(sum >= 10) {			if(i == 0) {				isOverflow = true;			}			else {				takeOver = 1;				sum -= 10;				pNum[i] = sum + '0';			}		}		else {			pNum[i] = sum + '0';			break;		}	}	return isOverflow;}/* 把字符串表达的数字打印出来 */void print_pNum(char *pNum){	int len = strlen(pNum);	bool isFirstNonZero = false;		// 更整齐地输出不足n位的数 	for(int i = 0; i < len; ++i) {		if(pNum[i] > '0' && isFirstNonZero == false)			isFirstNonZero = true;		if(isFirstNonZero == true)			printf("%c", pNum[i]);	}	printf("\t");}

考点：

• 解决大数问题的能力。

 

十八、删除链表的节点

题目一：在O(1)时间内删除链表节点。给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。

分析：在单向链表中删除一个节点，常规的解法是根据所给的头节点，顺序遍历查找要删除的节点，并在链表中删除该节点。然而，这种思路的时间复杂度为O(n)。

正确解法：

void DeleteNode(ListNode **pListHead, ListNode *pToBeDeleted){	if(*pListHead == nullptr || pToBeDeleted == nullptr)		return;	// 链表中有多个节点，要删除的节点不是尾节点	if(pToBeDeleted->next != nullptr) {		ListNode *pNode = pToBeDeleted->next;		/* 巧妙地避免了查找前一个节点所需的开销 */ 		pToBeDeleted->value = pNode->value;		pToBeDeleted->next = pNode->next;		delete pNode;		pNode = nullptr;	}	// 链表只有一个节点，要删除的节点是尾节点（也是头节点） 	else if(pToBeDeleted == *pListHead) {		delete pToBeDeleted;		pToBeDeleted = nullptr;		*pListHead = nullptr; 	}	// 链表中有多个节点，要删除的节点是尾节点 	else {		ListNode *pTemp = *pListHead;		while(pTemp->next != pToBeDeleted) {			pTemp = pTemp->next;	// 只有这一种情况需要遍历整个链表 		}		pTemp->next = nullptr;		delete pToBeDeleted;		pToBeDeleted = nullptr;	}}

小结：在知晓指向要删除的节点的指针时，就不一定需要得到被删除的节点的前一个节点。正如上段代码所示，我们把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除，这就相当于把当前需要删除的节点删除了。

 

题目二：删除链表中重复的节点。在一个排序的链表中，如何删除重复的节点？

解法：

void DeleteDuplication(ListNode **pListHead){	if(pListHead == nullptr || *pListHead == nullptr)	return;	ListNode *pPreNode = nullptr;	ListNode *pCurrent = *pListHead;	while(pCurrent != nullptr) {		ListNode *pNext = pCurrent->next;		bool isNeedDeleted = false;		if(pNext != nullptr && pNext->value == pCurrent->value)			isNeedDeleted = true;		if(!isNeedDeleted) {			pPreNode = pCurrent;			pCurrent = pCurrent->next;		}		else {			int value = pCurrent->value;			ListNode *pToBeDeleted = pCurrent;			while(pToBeDeleted != nullptr && pToBeDeleted->value == value) {				pNext = pToBeDeleted->next;				delete pToBeDeleted;				pToBeDeleted = nullptr;				pToBeDeleted = pNext;			}			if (pPreNode == nullptr) {				*pListHead = pNext;			}			else {				pPreNode->next = pNext;			}			pCurrent = pNext;		}	}}

分析：此题关键在于分析问题的全面性，例如头节点可能被删除，故传入的参数为指向指向头节点的指针的指针。　　

 

十九、正则表达式匹配

 

二十、表示数值的字符串

题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"及"-1E-16"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

分析：表示数值的字符串遵循一定的模式，如A[.[B]][e|EC]或者.B[e|EC]，其中A为数值的整数部分，B紧跟着小数点为数值的小数部分，C紧跟着'e'或者'E'为数值的指数部分。要注意的是，在小数里可能没有数值的整数部分，因此A部分不是必需的。

解法：

bool isNumeric(const char *str){	if(str == nullptr)	return false;	bool numeric = scanInteger(&str);	if(*str == '.') {		++str;		numeric = numeric || scanUnsignedInteger(&str);		// 小数点可以没有整数部分，如.123,123.等 	}	if(*str == 'e' || *str == 'E') {		++str;		numeric = numeric && scanInteger(&str);	} 	return numeric && *str == '\0';} bool scanInteger(const char **str){	if(**str == '+' || **str == '-')	(*str)++;	return scanUnsignedInteger(str);}bool scanUnsignedInteger(const char **str){	const char *before = *str;	while(**str != '\0' && **str >= '0' && **str <= '9')		(*str)++;	return *str > before;}

分析：判断一个字符串是否符合上述模式时，首先尽可能多地扫描0~9的数位，如模式中的A、B、C部分。