编程语言
面试题1：赋值运算符函数(C++)
题目：如下为类型CMyString的声明，请为改类型添加赋值运算符函数。
class CMyString { public: CMyString(char* pData = nullptr); CMyString(const CMyString& str); ~CMyString(void); private: char* m_pData; };
CMyString& CMyString::operator = (const CMyString& str)
{
if(this == &str)
return *this;
delete []m_pData;
m_pData = nullptr;
m_pData = new char[strlen(str.m_pData) + 1];
strcpy(m_pData, str.m_pData);
return *this;
}
面试题2：实现Singleton模式 (C#)
题目：设计一个类，我们只能生成该类的一个实例。
- C#的语法中有一个函数能够确保只调用一次，那就是静态构造函数，我们可以利用C#的这个特性实现单例模式。
数据结构
面试题3：数组中重复的数字（数组）
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
if(numbers == nullptr || length <= 0) {
return false;
}
for(int i=0; i < length;i++) {
if(numbers[i] <0 || numbers[i] > (length -1 )) {
return false;
}
}
for(int i = 0; i < length;i++){
while(numbers[i] != i) {
if(numbers[i] == numbers[numbers[i]]) {
*duplication = numbers[i];
return true;
}
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
}
};
面试题4：二维数组中的查找（数组）
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int columns = array.size();
int rows = array[0].size();
bool found = false;
if(rows > 0 && columns > 0) {
int row = 0;
int column = columns - 1;
while(row < rows && column >= 0) {
if(array[row][column] == target) {
found = true;
break;
}
else if(array[row][column] > target) {
--column;
}
else {
++row;
}
}
}
return found;
}
};
面试题5：替换空格（字符串）
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution {
public:
void replaceSpace(char *str,int length) {
if (str == nullptr || length <= 0) {
return;
}
int originalLength = 0;//源字符串的长度
int numberOfBlank = 0;//源字符串空格的个数
int i = 0;
while (str[i] != '\0') {
++originalLength;
if (str[i] == ' ') {
++numberOfBlank;
}
++i;
}
int newLength = originalLength + numberOfBlank*2;//插入%20，除了空格外，还需要额外的两个地址
if (newLength > length) {
return;
}
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) {
if (str[indexOfOriginal] == ' ') {
str[indexOfNew--] = '0';
str[indexOfNew--] = '2';
str[indexOfNew--] = '%';
} else {
str[indexOfNew--] = str[indexOfOriginal];
}
--indexOfOriginal;
}
}
};
面试题6：从头到尾打印链表（链表）
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
//利用栈先进后出特性
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
std::stack<int> nodes;
vector <int> res;
ListNode* pNode = head;
while(pNode != nullptr) {
nodes.push(pNode->val);//取栈顶元素
pNode = pNode->next;//弹出栈顶元素
}
while(!nodes.empty()) {
res.push_back(nodes.top());
nodes.pop();
}
return res;
}
};
面试题9：用两个栈实现队列（栈和队列）
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
int data = 0;
if(stack2.empty()) {
while(stack1.size()>0) {
data = stack1.top();
stack1.pop();
stack2.push(data);
}
}
data = stack2.top();
stack2.pop();
return data;
}
private:
stack<int> stack1;
stack<int> stack2;
};
面试题10：斐波那契数列（算法和数据操作）
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
/*
* 首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)······以此类推就可以算出第n项了。这种算法的时间复杂度是O(n).
*/
class Solution {
public:
int Fibonacci(int n) {
int result[2] = {0,1};
if(n < 2) {
return result[n];
}
long long fibNMinusOne = 1;
long long fibNMinusTwo = 0;
long long fibN = 0;
for(unsigned int i = 2;i <= n;i++) {
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}
};
面试题11：旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int index1 = 0;
int index2 = rotateArray.size()-1;
int indexMid = index1;
while(rotateArray[index1]>=rotateArray[index2]) {
if(index2 - index1 == 1) {
indexMid = index2;
break;
}
indexMid = (index1 + index2)/2;
if(rotateArray[index1] == rotateArray[index2] && rotateArray[index1] == rotateArray[indexMid]){
return MinOrder(rotateArray,index1,index2);
}
if(rotateArray[indexMid]>=rotateArray[index1]) {
index1 = indexMid;
} else if(rotateArray[indexMid]<=rotateArray[index2]) {
index2 = indexMid;
}
}
return rotateArray[indexMid];
}
private:
int MinOrder(vector<int> &num,int left,int right){
int result = num[left];
for(int i = left + 1;i < right;++i){
if(num[i] < result){
result = num[i];
}
}
return result;
}
};
1.二叉树的镜像
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
/* 先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子节点，
当交换完所有的非叶子结点的左右子结点之后，就得到了树的镜像 */
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot == NULL) {
return;
}
if(pRoot->left == NULL && pRoot->right == NULL) {
return;
}
TreeNode *pTemp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = pTemp;
if(pRoot->left != NULL) {
Mirror(pRoot->left);
}
if(pRoot->right != NULL) {
Mirror(pRoot->right);
}
}
};