《剑指Offer 第二版》阅读笔记

面试题1：赋值运算符函数

个人总结：
这道题目除了掌握必要的知识点外，比较注重实现的细节。

考察知识点：

重载的概念
运算符重载

解答思路：
1、如何写运算符重载函数
2、传入参数和返回值类型：传入参数是否需要const，返回值是否需要引用
3、包含指针成员变量的拷贝：深拷贝or浅拷贝？
4、如何尽可能保证异常安全？比如申请、释放当前对象的指针成员变量所指示地内存区域

class CMyString {
public:
    CMyString(char *pData = nullptr);
    CMyString(const CMyString& rhs);
    ~CMyString();
    CMyString& operator=(const CMyString& rhs);
private:
    char *m_pData;
};

CMyString& CMyString::operator=(const CMyString& rhs) {
    if (&rhs == this) return *this;
    // 避免内存申请异常处理，直接调用拷贝构造函数创建临时对象
    CMyString tmp(rhs);
    // 保存临时对象所分配的内存空间指针
    char *p_tempData = tmp.m_pData;
    // 将临时对象的指针成员变量置为当前对象所对应变量的值
    // 借助临时对象的析构，安全地释放当前对象地指针变量所申请的内存
    tmp.m_pData = m_pData;
    // 现在可以将当前对象地指针指向刚刚申请地内存了
    m_pData = p_tempData;
    // 为了连续赋值不出错，必须返回引用
    return *this;
}

衍生问题：

C++中，哪些函数能重载？哪些不能重载？
重载的原理
介绍下虚函数机制

面试题2：实现Singleton模式

个人总结：
对C++11及以后来说，这道题实现非常简单。对之前的C++版本，其实现相对复杂，但也只不过是需要考虑的情景变多了。

考察知识点：

static关键字的用法
设计模式

解答思路：
1、提供统一接口获取类对象。因为对象没创建，所以是需要static函数
2、私有化构造函数，防止被外部访问
3、一般不允许单例类拷贝构造和赋值构造，所以把它们删掉

// 这里给出C++11及以后的做法
// TODO: 需要补充C++11之前的解法
class Singleton {
public:
    // 视实际需求选择返回指针或者引用
    static Singleton *GetInstance();
private:
    Singleton() = default;    // 按需实现
    ~Singleton() = default;   // 按需实现
    Singleton(const Singleton& rhs) = delete; // 删除拷贝构造函数
    Singleton& operator=(const Singleton& rhs) = delete; // 删除赋值构造函数

};

Singleton* Singleton::GetInstance() {
    // C++11及以后的版本，保证了局部静态变量的创建是线程安全的
    // 局部静态变量有两个特点：
    //   1. 第一次调用时初始化
    //   2. 仅第一次被调用时初始化，后续再调用不会再初始化
    static Singleton instance;
    return &instance;
}

衍生问题：

说下对static关键字的理解
成员函数后面加= default、= 0、= delete有什么含义

面试题3：数组中的重复数字

解答思路：
注意题目条件：
1、数组长度为n
2、每个元素的范围0 ~ n-1
3、有一个至多个数字重复
4、只需要返回任意一个重复数字
应当问清楚的事：
1、能不能修改原数组
2、一定能找到吗？找不到应该如何返回

class Solution {
public:
    int findRepeatNumber(std::vector<int>& nums) {
        if (nums.empty()) return -1; // 这里定义找不到时返回-1，实际需要与面试官确认
        // 解法1：时间O(n)，空间O(n)
        std::unordered_set<int> st;
        for (const int& n : nums) {
            if (st.count(n)) return n;
            st.insert(n);
        }
        // 解法2：时间O(n)，空间O(1)
        for (int i = 0; i < nums.size(); ++i) {
            // 比较当前i与nums[i]
            // 如果相等，进行下一轮for循环；否则，找到“i”
            while(nums[i] != i) {
                // 如果第nums[i]和它所对应的数nums[nums[i]]相等
                // 则说明这个数重复，故而返回
                if (nums[i] == nums[nums[i]]) return nums[i];
                // 否则，将nums[i]放到它应该在的位置
                std::swap(nums[i], nums[nums[i]]);
            }
        }
        return -1;
    }
};

衍生问题：

在长度为n+1的数组中寻找重复数字，数组中元素的范围1~n

// 可参考上一个解法，用hash map。这里放上另一种解法
class Solution {
public:
  // 以时间换空间：时间：O(nlogn)，空间：O(1)
  int findRepeatNumber(const std::vector<int>& nums) {
      if (nums.empty()) return -1;
      int start = 1;
      int end = nums.size() - 1;
      while(start <= end) {
          int mid = start + (end - start) / 2;
          int cnt = count(nums, start, mid);
          if (start == end) {
              if (cnt > 1) return start;
              else break;
          }
          if (cnt > (mid - start + 1))
              end = mid;
          else
              start = mid + 1;
      }
      return -1;
  }
};

找出所有重复数字

面试题4：二维数组中的查找

考察知识点：

矩阵操作

解答思路：
根据增长特点，选择一个能缩小查找范围的位置进行查找。本题适合从左下角或者右上角入手。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (!matrix.empty()) {
            const int m = matrix.size();
            const int n = matrix[0].size();
            int i = 0;
            int j = n - 1;
            // 这里从右上角开始查询
            while(i < m && j >= 0) {
                if (matrix[i][j] == target) return true;
                else if (matrix[i][j] < target) ++i;
                else --j;
            }
        }
        return false;
    }
};

衍生问题：

三维空间中的查找？？？

面试题5：替换空格

考察知识点：
从后往前遍历

解答思路：

class Solution {
public:
    // Leetcode上将这道题目简化了，实际是在原数组上操作，从后往前遍历才对
    string replaceSpace(string s) {
        string res;
        for (char& c : s) {
            if (c == ' ') {
                res += "%20";
            } else {
                res += c;
            }
        }
        return res;
    }
    //
    void replaceSpace(char str[], int length, int n) {
        if (str == nullptr) return ;
        int idx = n - 1;
        for (int i = length - 1; i >= 0; --i) {
            if (str[i] == ' ') {
                str[idx--] = '0';
                str[idx--] = '2';
                str[idx--] = '%';
            } else {
                str[idx--] = str[i];
            }
        }
    }
};

面试题6：从尾到头打印链表

考察知识点：

解答思路：

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if (head == nullptr) return {};
        vector<int> res;
        stack<ListNode*> st;
        ListNode* node = head;
        while(node != nullptr) {
            st.push(node);
            node = node->next;
        }
        res.resize(st.size());
        int idx = 0;
        while(!st.empty()) {
            res[idx++] = st.top()->val;
            st.pop();
        }
        return res;
    }
};

面试题7：重建二叉树

解答思路：
1、已知前序遍历和中序遍历
2、二叉树中不含重复元素

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder, 0, preorder.size() - 1,
                      inorder, 0, inorder.size() - 1);
    }

    TreeNode* helper(const vector<int>& preorder, int preStart, int preStop,
                     const vector<int>& inorder, int inStart, int inStop) {
        if (preStart > preStop || inStart > inStop) return nullptr;
        // 前序遍历第一个数是根节点的值
        TreeNode* root = new TreeNode(preorder[preStart]);
        int idx = inStart;
        for (idx = inStart; idx <= inStop; ++idx) {
            // 在中序遍历中找到根节点的index
            if (inorder[idx] == root->val) break;
        }

        // 计算出左子树的长度
        int lenOfLeft = idx - inStart + 1;

        if (lenOfLeft) {
            // 递归构建左子树
            root->left = helper(preorder, preStart + 1, preStart + lenOfLeft - 1,
                                inorder, inStart, idx - 1);
        }

        if (lenOfLeft < preStop - preStart) {
            // 递归构建右子树
            root->right = helper(preorder, preStart + lenOfLeft, preStop,
                                 inorder, idx + 1, inStop);
        }
        return root;
    }
};

面试题8：二叉树的下一个节点

解答思路：
观察题目，注意到条件：
1、子节点包含指向父节点的指针
既然提到了这个，说明它是十分右帮助的

struct BTNode {
    int val;
    BTNode* parent;
    BTNode* left;
    BTNode* right;

    BTNode(int _val) : val(_val),
        parent(nullptr), left(nullptr), right(nullptr) {}
    BTNode(int _val, BTNode* _p, BTNode* _l, BTNode* _r) : val(_val),
        parent(_p), left(_l), right(_r) {}
};

class Solution {
public:
    BTNode *next(BTNode* root) {
        if (root == nullptr) return nullptr;
        BTNode* next = nullptr;
        // 1. 如果root节点的右孩子存在，则下一个节点是右子树的最左叶节点
        if (root->right != nullptr) {
            BTNode *pRight = root->right;
            while(pRight->left != nullptr)
                pRight = pRight->left;
            next = pRight;
        // 2. 如果root节点没有右孩子，沿着它的父节点查找
        } else if (root->parent != nullptr) {
            BTNode *cur = root;
            BTNode *parent = cur->parent;
            // 3. 如果父节点存在，且当前节点是父节点的右孩子
            //   一直向上找到不是父节点右节点的节点
            while(parent != nullptr && parent->right == cur) {
                cur = parent;
                parent = parent->parent;
            }
            next = parent;
        }

        return next;
    }

};

面试题9：用两个栈实现队列

解答思路：
1、队列的特点：先进先出
2、栈的特点：先进后出
故而可以这么做：
1、push()操作时，往一个栈里填数据
2、pop()操作时，
2.1 首先检查另一个栈是否为空，如果不为空，则直接对这个栈进行pop()
2.2 如果为空，则将第一个栈的数据压入这个栈，再对这个栈执行pop()

class CQueue {
public:
    CQueue() {

    }

    void appendTail(int value) {
        mStackIn.push(value);
    }

    int deleteHead() {
        int ans = -1;
        // 输出栈不为空，则直接从输出栈弹出数据
        if (!mStackOut.empty()) {
            ans = mStackOut.top();
            mStackOut.pop();
        } else {
            // 输出栈为空，把输入栈中的数据“灌”入输出栈
            while(!mStackIn.empty()) {
                mStackOut.push(mStack1.top());
                mStackIn.pop();
            }
            // 注意，输入栈同样可能也为空，因此取值前需要对该异常情况检测
            // 这一步操作也可挪到函数开头完成
            if (!mStackOut.empty()) {
                ans = mStackOut.top();
                mStackOut.pop();
            }
        }
        return ans;
    }
private:
    stack<int> mStackIn;    // 用于外部数据输入，appendTail()操作只会影响这一个栈
    stack<int> mStackOut;   // 用于外部数据输出
};

面试题10：斐波那契数列

解答思路：
有几种做法：
1、递归法。此种方法太过简单，此处不赘述
2、动态规划。写出状态转移方程。
注意：
1、这道题目需要仔细确认起始值
2、整型溢出问题

class Solution {
public:
    // Leetcode这里对返回结果有限制，注意整型溢出问题
    static constexpr int MOD = 1000000007;
    int fib(int n) {
        if (n < 0) return -1;
        if (n < 2) return n;
        int fst = 0;
        int sec = 1;
        for (int i = 2; i <= n; ++i) {
            int tmp = sec;
            sec = (int)((long)(fst + sec) % MOD);
            fst = tmp;
        }
        return sec;
    }
};

衍生问题：

题目二：青蛙跳台阶问题

解答思路：
动态规划问题，最后分析发现本质上仍是一道斐波那契数列问题

class Solution {
public:
    static constexpr int MOD = 1000000007;
    int numWays(int n) {
        if (n < 0) return -1;
        if (n < 2) return 1;

        int fst = 1;
        int sec = 1;
        for (int i = 2; i <= n; ++i) {
            int tmp = sec;
            sec = static_cast<int>(static_cast<long>(fst + sec) % MOD);
            fst = tmp;
        }
        return sec;
    }
};

面试题11：旋转数组的最小数字

解答思路：

面试题12：

解答思路：

面试题13：

解答思路：

面试题14：

解答思路：

面试题15：

解答思路：

面试题16：

解答思路：

面试题17：

解答思路：

面试题18：

解答思路：

面试题19：

解答思路：

面试题20：

解答思路：

《剑指Offer 第二版》 阅读笔记

面试题1：赋值运算符函数

面试题2：实现Singleton模式

面试题3：数组中的重复数字

面试题4：二维数组中的查找

面试题5：替换空格

面试题6：从尾到头打印链表

面试题7：重建二叉树

面试题8：二叉树的下一个节点

面试题9：用两个栈实现队列

面试题10：斐波那契数列

题目二：青蛙跳台阶问题

面试题11：旋转数组的最小数字

面试题12：

面试题13：

面试题14：

面试题15：

面试题16：

面试题17：

面试题18：

面试题19：

面试题20：

《剑指Offer 第二版》阅读笔记