函数的机器级表示

概念

函数提高了一种封装代码的方式,它可以被多次调用,调用完成后会返回调用点,可选的它可以接收多个参数,返回一个值。

运行时栈

栈是后进先出的数据结构,系统在程序运行时会分配一块内存区域以栈的方式管理,这块内存区域就叫运行时栈或栈内存空间。

字节序之大小端

内存以字节为单位保存信息,每个字节都有一个编号,这个编号就是内存地址。

一个 int a = 0x12345678 变量占用 4 个字节,而变量的地址为变量 a 在内存中的最低地址,比如 &a0x100 时,说明 a 在内存中的位置为 0x100 0x101 0x102 0x103

枚举算法技巧

枚举算法即遍历已有的集合,判断哪些元素符合要求,最终求解问题。

例如 LeetCode 第一题,两数之和:

1
2
3
4
5
6
7
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

示例 1:

  输入:nums = [2,7,11,15], target = 9
  输出:[0,1]
  解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1]

暴力枚举

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return { 0, 0 };
    }
};

时间复杂度:\(O(N^2)\) ,空间复杂度:\(O(1)\)

C++ 奇异的递归模板 CRTP

CRTP (The Curiously Recurring Template Pattern) 是 C++ 模板中的一种习惯用法:子类继承时将自己作为基类的模板参数。

一般形式:

1
2
3
4
5
6
7
8
template <typename T>
class Base {

};

class Derived: public Base<Derived> {

};

这样就能在基类访问子类的成员变量及函数。

并查集的概念及实现

动态连通性问题

“连通” 是一种等价关系,两个对象 p 和 q 是相连通的,意味着它具有:

  • 自反性:p 和 p 是相连的
  • 对称性:如果 p 和 q 是相连的,那么 q 和 p 也是相连的
  • 传递性:如果 p 和 q 相连且 q 和 r 相连,那么 p 和 r 也是相连的

等价关系将对象分为多个等价类,在这个,当且仅当两个对象相连通时才属于同一个等价类。