<commit_before>---
layout: post
title:  "《剑指Offer》第二章——面试需要的基础知识"
date:   2019-7-10 00:00:00
categories: 剑指Offer
tags: 笔试题
excerpt: 《剑指Offer》第二章面试题
mathjax: true
---
* content
{:toc}
---


## 编程语言

### 面试题1：赋值运算符函数(C++)


> 题目：如下为类型CMyString的声明，请为改类型添加赋值运算符函数。<br/>
>
```
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#)

> 题目：设计一个类，我们只能生成该类的一个实例。<br/>


- C#的语法中有一个函数能够确保只调用一次，那就是静态构造函数，我们可以利用C#的这个特性实现单例模式。<br/>


## 数据结构

### 面试题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：二维数组中的查找（数组）


>在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。<br/>



```
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/
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;
    }
};
```


### 1.二叉树的镜像


![Zcn0Ds.png](https://s2.ax1x.com/2019/07/10/Zcn0Ds.png)


```<commit_msg>Update 2019-7-10-剑指Offer-第二章.markdown<commit_after>---
layout: post
title:  "《剑指Offer》第二章——面试需要的基础知识"
date:   2019-7-10 00:00:00
categories: 剑指Offer
tags: 笔试题
excerpt: 《剑指Offer》第二章面试题
mathjax: true
---
* content
{:toc}
---


## 编程语言

### 面试题1：赋值运算符函数(C++)


> 题目：如下为类型CMyString的声明，请为改类型添加赋值运算符函数。<br/>
>
```
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#)

> 题目：设计一个类，我们只能生成该类的一个实例。<br/>


- C#的语法中有一个函数能够确保只调用一次，那就是静态构造函数，我们可以利用C#的这个特性实现单例模式。<br/>


## 数据结构

### 面试题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：二维数组中的查找（数组）


>在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。<br/>



```
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/
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;
    }
};
```


### 1.二叉树的镜像


![Zcn0Ds.png](https://s2.ax1x.com/2019/07/10/Zcn0Ds.png)


```
{'fraction_non_alphanumeric': 0.14332214423761572, 'fraction_numerical': 0.01535957684874377, 'mean_word_length': 1.7502097902097902, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 55, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3862663', 'n_tokens_mistral': 4162, 'n_tokens_neox': 4310, 'n_words': 613}