剑指offer——第一章（C++实现）

写在前面的话

面试官会关注边界条件、特殊输入（如nullptr指针、空字符串等）以及错误处理。

题目1：把一个字符串转换成整数

边界条件：

1）考虑到输入的字符串中有非数字字符和正负号

2）要考虑到最大的正整数和最小的负整数以及溢出

3）考虑到当输入的字符串不能转换成整数时，应该如何做错误处理。

实现代码：

#include <iostream>
#include<string>


int StrToInt(std::string input) {
	int len = input.length(), str_index=0;
	int positive_num = 0, negative_num = 0;
	if (len == 0) return 0;
	long long answer = 0;

	//去除字符串前置空格
	while (input[str_index] == ' ') str_index++;

	//正负号判断
	if (input[str_index] == '+') {
		positive_num++;
		str_index++;
	}
	else if (input[str_index] == '-') {
		negative_num++;
		str_index++;
	}
	
	for (; str_index < len; str_index++) {
		if (input[str_index] >= '0' && input[str_index] <= '9') {
			answer = answer * 10 + input[str_index] - '0';
			//溢出判断
			if (positive_num && (answer>= 2147483647)) {
				return 2147483647;
			}
			if (negative_num && (answer >= 2147483648)) {
				return -2147483648;
			}
		}
		else{
			return 0;
		}
	}
	return negative_num ? -answer: answer;
}

int main()
{
	printf("请输入字符串：\n");
	std::string  input;
	//读取一行字符串
	getline(std::cin, input);
	int answer = StrToInt(input);
	printf("%d\n", answer);
	system("pause");
 	return 0;

}

小技巧：

c++语言，cin和cout的比scanf和printf更耗时。所以，在线笔试的时候，多用后者。或者添加下图中的函数

题目2：求链表中的导数第k个节点

边界条件：

1、判断输入的指针是否为空

2、链表节点数是否小于k

3、k的值是否为0

实现代码：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if ((pListHead == nullptr) || (k == 0)) return  nullptr;
        ListNode *fast = pListHead, *slow = pListHead;
        
        //快指针移动k-1步，使其移动到链表第k个节点的位置
        while ((fast->next != nullptr) && (k-1 > 0)) {
            fast = fast->next;
            k--;
        }
        
        //此时快指针移动到了链表第k个节点的位置
        if ((k == 1) && (fast->next != nullptr)) {
            while (fast->next != nullptr) {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
        //此时快指针没有移动到链表第k个节点的位置（链表长度小于k）
        else if ((fast->next == nullptr) && (k > 1)){
            return nullptr;
        }
        //k节点为链表头节点
        else{
            return pListHead;
        }
    
    }
};