算法题¶

1 算法思想¶

1.1 动态规划¶

算法思想：动态规范把原问题分解成许多子问题，自底向上求解子问题，合并子问题的解。子问题解保存在数组中，供后续子问题使用，避免重复计算，增加算法效率。
动态规范要素：
最优子结构
重叠子问题

title: tip 重叠子问题
在求解子问题过程中，有大量子问题是重复的，只需将求得的子问题解保存在数组中，以后使用时直接调用，增加了算法效率。重叠子问题不是动态规划的必要条件，但更能体现动态规划优点。

2 排序算法¶

2.1 冒泡排序¶

从后往前排
相邻 2 数比较、交换
2 层 for 循环
时间复杂度 $O(n^{2})$
空间复杂度 $O(1)$
示例

/**
 * @brief 冒泡排序
 * 相邻元素比较，交换，每一次循环最值都在数组顶部
 * @tparam T 
 * @param data 
 * @param num 
 */
template <typename T>
void sort(T data[], int num)
{
    for (size_t i = 0; i < num; ++i)
    {
        for (size_t j = num; j > i; --j)
        {
            if (data[j] < data[j - 1])
            {
                T tmp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = tmp;
            }
        }
    }
}

2.2 选择排序¶

每第 i 次循环从 n-i 元素中选择最小元素 k 与第 i 元素交换
2 层 for 循环
时间复杂度 $O(n^{2})$
空间复杂度 $O(1)$
示例

/**
 * @brief 选择排序
 * 从第i～n范围元素中找出最小值元素索引min,交换data[i]与data[min]数据 
 * @tparam T 
 * @param data 
 * @param num 
 */
template <typename T>
void sort(T data[], int num)
{
    for (size_t i = 0; i < num - 1; ++i)
    {
        //最小元素索引
        int min = i;
        for (size_t j = i + 1; j < num; ++j)
        {
            if (data[j] < data[min])
                min = j;
        }
        if (i != min)
        {
            T tmp = data[min];
            data[min] = data[i];
            data[i] = tmp;
        }
    }
}

2.3 插入排序¶

将第 i（i>=2）与前 i-1 个元素依次比较，插入到前 i-1 个元素中
2 层 for 循环
时间复杂度 $O(n^{2})$
空间复杂度 $O(1)$
示例

/**
 * @brief 插入排序
 * 将第i个元素与前i-1个元素比较，找到合适位置j，j～i-1间元素向后移动以为，将data[i]插入data[j]处
 * @tparam T 
 * @param data 
 * @param num 
 */
template <typename T>
void sort(T data[], int num)
{
    for (int i = 1; i < num; ++i)
    {
        int j;
        T tmp = data[i];
        for (j = i; j > 0; --j)
        {
            if (tmp < data[j - 1]) //将大值往后一位
                data[j] = data[j - 1];
            else //找到合适位置
                break;
        }
        //j位置就是合适位置
        data[j] = tmp;
    }
}

2.4 快速排序¶

首尾指针，选择首元素作为基本值（一般选择首尾或中间值）
先比较尾部元素与基本值大小，小于基本值与头指针指向元素交换，再移动头指针元素比较直到元素值大于基本值，再与尾部指针元素交换，再移动尾部指针，循环此操作，直到头尾指针相等。
再与头尾指针汇聚处作上述处理，直到分组中只含一个元素，此时元素以排序。
平均时间复杂度 $O(n\log_{}{n})$
最差时间复杂度 $O(n^2)$

2.5 归并排序¶

递归将数组分成 2 部分
将两两子数组合并并排序组成一个已排序子数组
最终合并成一个已排序数组
平均时间复杂度 $O(n\log_{}{n})$
最差时间复杂度 $O(n^2)$
示例

template <typename T>
void mergeSort(T data[], int L, int R);
template <typename T>
void merge(T data[], int L, int R, int M);
/**
 * @brief 归并排序
 * 将数组分成多个子数组，再将子数组合并时排序，最终合并成一个排序数组
 * @tparam T 
 * @param data 
 * @param num 
 */
template <typename T>
void sort(T data[], int num)
{
    mergeSort(data, 0, num - 1);
}

template <typename T>
void mergeSort(T data[], int L, int R)
{
    //递归终止条件
    if (L == R)
        return;
    int mid = (L + R) / 2;
    //分割
    mergeSort(data, L, mid);
    mergeSort(data, mid + 1, R);
    //合并
    merge(data, L, R, mid);
}

template <typename T>
void merge(T data[], int L, int R, int M)
{
    T *arr = new T[R - L + 1];
    int l = L, r = M + 1, index = 0;
    //排序完成条件
    while (l <= M && r <= R)
    {
        if (data[l] <= data[r])
        {
            arr[index++] = data[l++];
        }
        else
        {
            arr[index++] = data[r++];
        }
    }
    //将剩下的元素放入临时数组中
    while(l <= M)
    { //左数组剩余
        arr[index++]=data[l++];
    }
    while (r<=R)
    {//右数组剩余
        arr[index++]=data[r++];
    }
    //复制临时数组中元素到原数组中
    for(index=0;L<=R;++L)
    {
        data[L]=arr[index++];
    }
    //释放临时数组
    delete []arr;
}

2.6 堆排序¶

以二叉树形式查找 n 个元素中最值，将其放入数组末尾
在 n-1 次循环处理下，数组已排好序
平均时间复杂度 $O(n\log_{}{n})$
最差时间复杂度 $O(n\log_{}{n})$

3 算法常识¶

3.1 推导大 O 阶方法¶

用常数 1 替代所有加法性质的常数
只保留最高阶项，去除其它次要项
如果最高项含常量系数（如 3n 则去除 3，只保留 n），则去除常量系数

常用时间复杂度排序表

4 英文字符大小写转换¶

前置知识:A~Z 范围是 0x41~0x0x5a(65~90),a~z 范围是 0x61~0x7a(97~122) 1. 传统方法：遍历字符串大写字母 +32，小写字母 -32 2. 高级方法：因为大小写字母只在第 6bit 位置上不同，如 A(0100 0001) 和 a(0110 0001)，因此采用对 0x40(0010 0000) 异或运算就能达到大小写字母转换。如 01000001^0x0010000 结果是 01100001,即 A。

5 树¶

度：指节点含多少个子节点
树的深度：指树有多少层
完全二叉树：从左往右按顺序排列节点二叉树
满二叉树：叶子节点都在同一层的完全二叉树

5.1 二叉树¶

深度为 k 的二叉树最多有 $2^{k}-1(k\ge 1)$ 个节点
第 i 层上，最多有 $2^{i-1}(i\ge1)$ 个节点
假设叶子节点树是 $n_{0}$,度为 2 的节点数为 $n_{2}$,则有 $n_{0}=n_{2}+1$
具有 n 个节点的完全二叉树的深度为 ${\left \lfloor \log_{2}{n} \right \rfloor +1}(\left \lfloor x \right \rfloor表示不大于x的最大整数)$
具有 n 个节点的满二叉树的深度为 $log_{2}{(n+1)}$

5.2 二叉树遍历方法¶

区分前序、中序、后序关键是访问根节点。
前序：根->左->右
中序：左->根->右
后序：左->右->根
其中**中序遍历可以得到排序数据**。

5.2.1 前序遍历¶

顺序：A->B->D->G->H->C->E->I->F

5.2.2 中序遍历¶

顺序：G->D->H->B->A->E->I->C->F

5.2.3 后序遍历¶

顺序：G->H->D->B->I->E->F->C->A

5.2.4 层序遍历¶

顺序：A->B->C->D->E->F->G->H->I

5.2.5 遍历算法实现¶

typedef char ElemType;
typedef struct BiNode {
    ElemType data;
    BiNode* lChild, * rChild;
}BiNode,*BiTree;
//前序遍历
void preOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    printf("%c", T->data);// 先打印节点信息
    preOrderTraverse(T->lChild);//再遍历左子树
    preOrderTraverse(T->rChild);//最后遍历右子树
}
//中序遍历
void inOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    inOrderTraverse(T->lChild);
    printf("%c", T->data);
    inOrderTraverse(T->rChild);
}
//后序遍历
void postOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    postOrderTraverse(T->lChild);
    postOrderTraverse(T->rChild);
    printf("%c", T->data);
}

5.3 红黑树¶

资料红黑树-维基百科

5.3.1 性质¶

节点非黑即红
根节点必为黑
每个叶节点（NIL 节点）都是黑色
新插入节点必为红
不能有 2 个连续的红色节点（即父节点和子节点都为红），黑色节点不限制，或者说每一个红色节点必含黑色左右子节点
从任意一节点到叶子节点，所经过路径上黑色节点数目相同

title: NIL节点
1. NIL节点也就是NULL节点
2. 在红黑树中用NIL节点填补原节点中缺失的左右子节点
3. 在红黑树中叶子节点指的是NIL节点

5.3.2 操作¶

红黑树插入删除操作会导致不满足红黑树性质，这时可以通过旋转（左旋、右旋），重新着色操作来维持红黑树。下图展现了红黑树插入的几种情况