目录
本系列面试题来自《剑指offer》第二版，以c/c++实现，代码在
g++ 11.4.0均运行通过
面试题1：赋值运算符函数
- 本题考察实现自己的string类
#include <iostream>
#include <string.h>
using namespace std;
class CMyString {
public:
CMyString(char* pData = NULL);
CMyString(const CMyString& str);
CMyString& operator = (const CMyString& str);
~CMyString();
const char* c_str() { return this->m_pData; }
private:
char* m_pData;
};
CMyString::CMyString(char* pData) {
if (pData) {
// 分配空间
int len = strlen(pData);
m_pData = new char[len + 1];
// 拷贝
for (int i = 0; i < len; ++i) {
this->m_pData[i] = pData[i];
}
m_pData[len] = '\0';
}
}
CMyString::CMyString(const CMyString& str) {
if (str.m_pData) {
int len = strlen(str.m_pData);
m_pData = new char[len+1];
for (int i = 0; i < len; ++i) {
this->m_pData[i] = str.m_pData[i];
}
m_pData[len] = '\0';
}
}
CMyString& CMyString::operator = (const CMyString& str) {
// 非自赋值
if (this != &str) {
CMyString tempStr(str);
char* pTemp = tempStr.m_pData;
tempStr.m_pData = m_pData;
m_pData = pTemp;
}
return *this;
}
CMyString::~CMyString() {
if (m_pData) {
delete[] m_pData;
m_pData = nullptr;
}
}
int main() {
CMyString str1;
str1 = "Hello World";
cout << str1.c_str() << endl;
CMyString str2(str1);
cout << str2.c_str() << endl;
CMyString str3 = str1;
cout << str3.c_str() << endl;
return 0;
}
面试题2：实现单例模式
- 饿汉式实现示例如下：
#include <iostream>
#include <thread>
using namespace std;
class Singleton {
private:
Singleton() {}
static Singleton* instance;
public:
static Singleton* getInstance() {
return instance;
}
static void destroyInstance() {
if (instance) {
delete instance;
instance = nullptr;
}
}
};
Singleton* Singleton::instance = new Singleton();
int main() {
for (int i = 0; i < 1000; ++i) {
thread t([](){
Singleton* instance = Singleton::getInstance();
cout << instance << endl;
});
if (t.joinable()) {t.join();}
}
Singleton::destroyInstance();
return 0;
}
面试题3：二维数组中的查找
- 实现如下：
#include <iostream>
using namespace std;
/**
* @desc 在二维数组中查找number，这个二维数组满足每一行递增，每一列递增
*/
bool find(int* matrix, int rows, int columns, int number) {
bool find = false;
if (matrix && rows > 0 && columns > 0) {
int column = columns - 1;
int row = 0;
while (row < rows && column >= 0) {
if (matrix[row*columns + column] == number) {
find = true;
return find;
} else if (matrix[row*columns + column] < number) {
row++;
} else {
column--;
}
}
}
return find;
}
int main() {
int arr[][3] = {1, 2, 4, 5, 6, 7};
cout << find(arr[0], 2, 3, 6) << endl;
cout << find(arr[0], 2, 3, 7) << endl;
cout << find(arr[0], 2, 3, 3) << endl;
cout << find(arr[0], 2, 3, 1) << endl;
return 0;
}
面试题4：替换空格
- 实现如下：
#include <iostream>
#include <string.h>
using namespace std;
/**
* @desc 替换字符串str中的空格，将每一个空格替换成"%20"。假设输入的字符串后面有足够多的空域内存
* @param len 字符串的有效长度
*/
void replaceSpace(char str[], int len) {
if (str && len > 0) {
// 统计空格的个数
int count = 0;
for (int i = 0; i < len; ++i) {
if (str[i] == ' ') {
count++;
}
}
int newLength = len + count * 2;
if (count == 0) return;
str[newLength] = '\0';
for (int i = len - 1, j = newLength - 1; i >= 0; i--) {
if (str[i] == ' ') {
str[j--] = '0';
str[j--] = '2';
str[j--] = '%';
} else {
str[j] = str[i];
j--;
}
}
}
}
int main() {
char str[64] = "test haha dd d hhh";
replaceSpace(str, strlen(str));
cout << str << endl;
return 0;
}
面试题5：从尾到头打印链表
- 不可以更改链表结构，实现如下：
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define VALUE_TYPE int
typedef struct SingleLinkList {
VALUE_TYPE value;
SingleLinkList* next;
}Node;
/**
* @desc 头插法创建单链表
*/
Node* createLinkList(const vector<VALUE_TYPE>& vec) {
Node* head = nullptr;
for (auto value : vec) {
Node* newnode = (Node*)malloc(sizeof(Node));
newnode->value = value;
newnode->next = head;
head = newnode;
}
return head;
}
/**
* @desc 逆序遍历单链表
* @param head 单链表的第一个数据节点
*/
void reversePrintLinkList(Node* head) {
if (head) {
Node* cur = head;
stack<VALUE_TYPE> s;
while (cur) {
s.push(cur->value);
cur = cur->next;
}
while (!s.empty()) {
VALUE_TYPE value = s.top();
s.pop();
cout << value << "\t";
}
cout << endl;
}
}
/**
* @desc 正序遍历单链表
*/
void printLinkList(Node* head) {
Node* cur = head;
while (cur) {
cout << cur->value << "\t";
cur = cur->next;
}
cout << endl;
}
int main() {
Node* node = createLinkList({1, 3, 5, 7});
printLinkList(node);
reversePrintLinkList(node);
return 0;
}
- 可以更改链表结构，则反转链表再打印