search

lunix555 / Cpp-interview-tips

主要是一些C++常用知识总结
1 stars 0 forks source link

数据结构篇 #6

Open lunix555 opened 2 years ago

lunix555 commented 2 years ago

1、快排和归并的联系与区别

联系：原理都基于分治法，首先将待排序数组分为两组，对两组的数据进行排序，最后将两组结果合并起来。 区别：分解和合并的策略不同。快速排序是根据元素的值来分的，大于某个值的元素一组，小于某个值的元素一组。合并时只要前后相连即可。归并排序是直接将待排序数组的前一半分为一组，后一半分为一组，然后进行排序。合并时还要再将两个有序数组进行排序。

2、链表和数组的区别

数组的元素在内存地址中是连续存放的。链表的元素在内存中不一定是连续存放的，但是逻辑上是连续的 数组的访问速度很快，因为数组可以根据下标进行快速定位。链表的访问速度较慢，因为链表访问元素需要移动指针 数组增加或者删除元素时间复杂度通常是O(n),都需要大量移动元素。而链表在任意位置插入元素和删除元素的速度快，只要修改指针指向就可以，时间复杂度为O(1)

3、说出你所知道的排序算法及其复杂度

1、直接插入排序：一开始假设第一个元素为有序，然后从第二个元素开始向前找到合适的位置并插入。稳定，平均时间复杂度为O(n^2) 2、希尔排序：是对直接插入排序的优化和扩展，把数据按下标的一定增量分组，对每组使用直接插入排序算法排序；当增量减至 1 时，整个元素恰被分成一组，进行整体排序后终止排序。不稳定，时间复杂度为O(n^1.3) 到O(n^2) 3、选择排序：第一次从数组中找到最小的元素放到起始位置，然后从之后未排序元素中再找到最小的元素，放到以排序元素的末尾。不稳定，时间复杂度为O(n^2) 4、堆排序：构建一个大堆，将堆顶元素和末尾元素进行交换，然后再对n-1个元素重新构建一个大堆，如此重复循环，就可以得到一个有序的数组了。不稳定，时间复杂度为O(nlogn) 5、冒泡排序：循环n次，每次循环都通过相邻比较交换，每轮循环找出未排序数组中的最大元素，将其放未排序部分的末尾。稳定，时间复杂度为O(n^2) 6、快速排序：通过一趟排序将待排数据分隔成独立的两部分，其中一部分数据是比关键字小的，另一部分是比关键字大的，则可分别对这两部分数据继续进行排序，以达到整个序列有序。不稳定，O(nlogn)到O(n^2)，当数据全部反向排序时时间复杂度最高 7、归并排序：首先把一个数组中的元素，按照某一方法，先拆分了之后，按照一定的顺序各自排列，然后再归并到一起，使得归并后依然是有一定顺序的。稳定，时间复杂度为O(nlogn) image

lunix555 commented 2 years ago

4、topK问题-如何从海量数据取最大的k个数 最小堆法：先读取k个数，建成小堆，然后将剩余元素依次和堆顶元素比较，如果小于或者等于堆顶元素，则继续比较下一个，如果大于堆顶元素，则删除堆顶元素，并将新元素插入堆中，重新建立一个小堆。当遍历完全部元素后，最小堆中的数据即为最大的k个数

void adjustSmall(vector& arr, int sz, int idx) { int child = 2 idx + 1; while (child < sz) { if ((child + 1 < sz) && (arr[child] > arr[child + 1])) ++child; if (arr[idx] > arr[child]) { swap(arr[idx], arr[child]); idx = child; child = 2 idx + 1; } else break; } }

void topK(vector& arr, int k) { vector res(arr.begin(), arr.begin() + k); make_heap(res.begin(), res.end(), greater()); for (size_t i = k; i < arr.size(); ++i) { if (arr[i] > res[0]) { swap(arr[i], res[0]); adjustSmall(res, k, 0); } } for (const auto& e : res) cout << e << " "; }

lunix555 commented 2 years ago

5、快排非递归

通过一趟排序将待排数据分隔成独立的两部分，其中一部分数据是比关键字小的，另一部分是比关键字大的，则可分别对这两部分数据继续进行排序，以达到整个序列有序

int getMid(vector& arr, int low, int high) { int mid = low + ((high - low) >> 1);

if (arr[mid] > arr[high])
{
    swap(arr[mid], arr[high]);
}
if (arr[low] > arr[high])
{
    swap(arr[low], arr[high]);
}
if (arr[mid] > arr[low])
{
    swap(arr[mid], arr[low]);
}

return arr[low];

}

int helper(vector& arr, int left, int right) { int key =getMid(arr, left, right); int start = left; while (left < right) { while (left < right && arr[right] >= key) --right; while (left < right && arr[left] <= key) ++left; swap(arr[left], arr[right]); } swap(arr[left], arr[start]); return left; }

void quickSort(vector& arr) { stack st; st.push(arr.size() - 1); st.push(0);

while (!st.empty())
{
    int left = st.top();
    st.pop();
    int right = st.top();
    st.pop();
    int div = helper(arr, left, right);
    if (left < div - 1)
    {
        st.push(div - 1);
        st.push(left);
    }
    if (div + 1 < right)
    {
        st.push(right);
        st.push(div + 1);
    }
}

}

lunix555 commented 2 years ago

6、堆排序

构建一个大堆，将堆顶元素和末尾元素进行交换，然后再对n-1个元素重新构建一个大堆，如此重复循环，就可以得到一个有序的数组了

void adjust(vector& arr, int sz, int idx) { int child = 2 idx + 1; while (child < sz) { if ((child + 1 < sz) && (arr[child] < arr[child + 1])) ++child; if (arr[idx] < arr[child]) { swap(arr[idx], arr[child]); idx = child; child = 2 idx + 1; } else break;

}

}

void makeHeap(vector& arr) { for (int i = (arr.size()-2)/2; i >= 0; --i) { adjust(arr, arr.size() ,i); } }

void heapSort(vector& arr) { makeHeap(arr); int end = arr.size()-1; for (int i = 0; i < arr.size(); ++i) { swap(arr[0], arr[end]); adjust(arr, end, 0); --end; } }

lunix555 commented 2 years ago

7、直接插入排序

一开始假设第一个元素为有序，然后从第二个元素开始向前找到合适的位置并插入

void insertSort(vector& arr) { for (int i = 1; i < arr.size(); ++i) { int data = arr[i]; int end = i - 1; while (end >= 0 && arr[end] > data) { arr[end + 1] = arr[end]; --end; } arr[end + 1] = data; } }

lunix555 commented 2 years ago

8、希尔排序

是对直接插入排序的优化和扩展，把数据按下标的一定增量分组，对每组使用直接插入排序算法排序；当增量减至 1 时，整个元素恰被分成一组，进行整体排序后终止排序

void shellSort(vector& arr) { int gap = arr.size() / 2; while (gap > 0) { for (int i = gap; i < arr.size(); ++i) { int data = arr[i]; int end = i - gap; while (end >= 0 && arr[end] > data) { arr[end + gap] = arr[end]; end -= gap; } arr[end + gap] = data; } gap /= 2; } }

lunix555 commented 2 years ago

9、选择排序

第一次从数组中找到最小的元素放到起始位置，然后从之后未排序元素中再找到最小的元素，放到已排序元素的末尾

void selectSort(vector& arr) { for (int i = 0; i < arr.size(); ++i) { int minIdx = i; for (int j = i + 1; j < arr.size(); ++j) { if (arr[j] < arr[minIdx]) minIdx = j; } swap(arr[i], arr[minIdx]); } }

lunix555 commented 2 years ago

10、冒泡排序

循环n次，每次循环都通过相邻比较交换，每轮循环找出未排序数组中的最大元素，将其放未排序部分的末尾

void bubbleSort(vector& arr) { int n = arr.size() - 1; int pos = 0; for (int i = 0; i < arr.size(); ++i) { bool flag = false; for (int j = 0; j < n; ++j) { if (arr[j + 1] < arr[j]) { swap(arr[j + 1], arr[j]); flag = true; pos = j; } } if (!flag) break; n = pos; } }

lunix555 commented 2 years ago

11.红黑树

红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。 红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。 除了具备该特性之外，红黑树还包括许多额外的信息。

红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。 红黑树的特性: (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！] (4) 如果一个节点是红色的，则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

关于它的特性，需要注意的是： 第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。 第二，特性(5)，确保没有一条路径会比其他路径长出两倍。因而，红黑树是相对是接近平衡的二叉树。 image

红黑树的基本操作是添加、删除和旋转。在对红黑树进行添加或删除后，会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。 旋转包括两种：左旋 和 右旋。下面分别对红黑树的基本操作进行介绍

1基本定义:

`enum RBTColor{RED, BLACK};

template class RBTNode{ public: RBTColor color; // 颜色 T key; // 关键字(键值) RBTNode left; // 左孩子 RBTNode right; // 右孩子 RBTNode *parent; // 父结点

    RBTNode(T value, RBTColor c, RBTNode *p, RBTNode *l, RBTNode *r):
        key(value),color(c),parent(),left(l),right(r) {}

};

template class RBTree { private: RBTNode *mRoot; // 根结点

public:
    RBTree();
    ~RBTree();

    // 前序遍历"红黑树"
    void preOrder();
    // 中序遍历"红黑树"
    void inOrder();
    // 后序遍历"红黑树"
    void postOrder();

    // (递归实现)查找"红黑树"中键值为key的节点
    RBTNode<T>* search(T key);
    // (非递归实现)查找"红黑树"中键值为key的节点
    RBTNode<T>* iterativeSearch(T key);

    // 查找最小结点：返回最小结点的键值。
    T minimum();
    // 查找最大结点：返回最大结点的键值。
    T maximum();

    // 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
    RBTNode<T>* successor(RBTNode<T> *x);
    // 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
    RBTNode<T>* predecessor(RBTNode<T> *x);

    // 将结点(key为节点键值)插入到红黑树中
    void insert(T key);

    // 删除结点(key为节点键值)
    void remove(T key);

    // 销毁红黑树
    void destroy();

    // 打印红黑树
    void print();
private:
    // 前序遍历"红黑树"
    void preOrder(RBTNode<T>* tree) const;
    // 中序遍历"红黑树"
    void inOrder(RBTNode<T>* tree) const;
    // 后序遍历"红黑树"
    void postOrder(RBTNode<T>* tree) const;

    // (递归实现)查找"红黑树x"中键值为key的节点
    RBTNode<T>* search(RBTNode<T>* x, T key) const;
    // (非递归实现)查找"红黑树x"中键值为key的节点
    RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;

    // 查找最小结点：返回tree为根结点的红黑树的最小结点。
    RBTNode<T>* minimum(RBTNode<T>* tree);
    // 查找最大结点：返回tree为根结点的红黑树的最大结点。
    RBTNode<T>* maximum(RBTNode<T>* tree);

    // 左旋
    void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);
    // 右旋
    void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);
    // 插入函数
    void insert(RBTNode<T>* &root, RBTNode<T>* node);
    // 插入修正函数
    void insertFixUp(RBTNode<T>* &root, RBTNode<T>* node);
    // 删除函数
    void remove(RBTNode<T>* &root, RBTNode<T> *node);
    // 删除修正函数
    void removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent);

    // 销毁红黑树
    void destroy(RBTNode<T>* &tree);

    // 打印红黑树
    void print(RBTNode<T>* tree, T key, int direction);

define rb_parent(r) ((r)->parent)

define rb_color(r) ((r)->color)

define rb_is_red(r) ((r)->color==RED)

define rb_is_black(r) ((r)->color==BLACK)

define rb_set_black(r) do { (r)->color = BLACK; } while (0)

define rb_set_red(r) do { (r)->color = RED; } while (0)

define rb_set_parent(r,p) do { (r)->parent = (p); } while (0)

define rb_set_color(r,c) do { (r)->color = (c); } while (0)`

左旋转

image 对x进行左旋，意味着"将x变成一个左节点"。

右旋转

image 对y进行左旋，意味着"将y变成一个右节点"。

添加

将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过"旋转和重新着色"等一系列操作来修正该树，使之重新成为一颗红黑树。详细描述如下： 第一步: 将红黑树当作一颗二叉查找树，将节点插入。 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。 好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！

第二步：将插入的节点着色为"红色"。 为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性： (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！] (4) 如果一个节点是红色的，则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。o(∩∩)o...哈哈

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。 第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？ 对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。 对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。 对于"特性(4)"，是有可能违背的！ 那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。

删除操作

将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：

第一步：将红黑树当作一颗二叉查找树，将节点删除。 这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况： ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。 ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。 ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。

第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。 因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。