跳转至

数据结构与算法

之前都是找对应的题然后去做，一直没有形成系统；现在还是选择代码随想录。

排序算法

1. 算法介绍

排序算法是计算机科学中常见的一类算法，用于将一组数据按照特定的顺序进行排列。下面介绍几种常见的排序算法：

  1. 冒泡排序（Bubble Sort）：

  2. 从待排序序列的第一个元素开始，两两比较相邻元素的大小，如果顺序不对则交换位置。

  3. 每一轮结束后，最大（或最小）的元素会移动到末尾。
  4. 时间复杂度：平均情况和最坏情况下为 O(n^2)，最好情况下为 O(n)。
  5. 空间复杂度：O(1)。

  6. 插入排序（Insertion Sort）：

  7. 将未排序序列的第一个元素插入已排序序列的正确位置。

  8. 从第二个元素开始，依次与前面的元素比较并插入到正确位置。
  9. 时间复杂度：平均情况和最坏情况下为 O(n^2)，最好情况下为 O(n)。
  10. 空间复杂度：O(1)。

  11. 选择排序（Selection Sort）：

  12. 每一轮从待排序序列中选择最小（或最大）的元素，与当前位置交换。

  13. 每一轮结束后，当前位置之前的元素都是有序的。
  14. 时间复杂度：平均情况和最坏情况下为 O(n^2)。
  15. 空间复杂度：O(1)。

  16. 快速排序（Quick Sort）：

  17. 选择一个基准元素，将序列分为比基准小的元素和比基准大的元素。

  18. 递归地对划分后的子序列进行快速排序。
  19. 时间复杂度：平均情况下为 O(nlogn)，最坏情况下为 O(n^2)。
  20. 空间复杂度：平均情况下为 O(logn)，最坏情况下为 O(n)。

  21. 归并排序（Merge Sort）：

  22. 将序列递归地拆分成两个子序列，对子序列进行排序，然后合并两个有序子序列。

  23. 使用分治法思想，将排序问题分解为较小的子问题。
  24. 时间复杂度：平均情况下为 O(nlogn)。
  25. 空间复杂度：O(n)。

2. C++实现

#include <iostream>
#include <cstdlib>
#include <ctime>

// 冒泡排序 bubbleSort 两两比较
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                std::swap(arr[j], arr[j+1]);
            }
        }
    }
}

// 选择排序 selectionSort 选最小值
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;

        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        std::swap(arr[i], arr[minIndex]);
    }
}

// 插入排序 insertionSort 依次成序
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

// 归并排序 mergeSort
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int* L = new int[n1];
    int* R = new int[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

// 快速排序 quickSort
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }

    std::swap(arr[i+1], arr[high]);

    return i+1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    const int SIZE = 10;

    // 生成随机整数数组
    int arr[SIZE];
    srand(time(0));
    for (int i = 0; i < SIZE; i++) {
        arr[i] = rand() % 100; // 生成 0 到 99 的随机数
    }

    std::cout << "Original array: ";
    printArray(arr, SIZE);

    // 使用冒泡排序进行排序
    bubbleSort(arr, SIZE);
    std::cout << "Array after bubble sort: ";
    printArray(arr, SIZE);

    // 使用选择排序进行排序
    selectionSort(arr, SIZE);
    std::cout << "Array after selection sort: ";
    printArray(arr, SIZE);

    // 使用插入排序进行排序
    insertionSort(arr, SIZE);
    std::cout << "Array after insertion sort: ";
    printArray(arr, SIZE);

    // 使用归并排序进行排序
    mergeSort(arr, 0, SIZE-1);
    std::cout << "Array after merge sort: ";
    printArray(arr, SIZE);

    // 使用快速排序进行排序
    quickSort(arr, 0, SIZE-1);
    std::cout << "Array after quick sort: ";
    printArray(arr, SIZE);

    return 0;
}

编译运行：

g++ -o main main.cpp && ./main

以上。

查找算法

😏1. 算法介绍

查找算法的作用是在给定的数据集合中搜索目标元素或确定目标元素是否存在。它可以帮助我们快速地找到所需的数据，提供有效的数据访问和处理方式。

常用的查找算法有以下几种：

  1. 线性查找：也称为顺序查找，是最简单直接的查找算法。它从数据结构的起始位置开始，逐个比较元素，直到找到目标元素或遍历完整个数据结构。时间复杂度为O(n)，其中n是数据结构中元素的个数。
  2. 二分查找：适用于已排序的数据结构（如有序数组）。它将目标元素与中间元素进行比较，根据比较结果确定目标元素在左半部分还是右半部分，并继续在该部分进行查找。通过每次排除一半的元素，二分查找能够快速定位目标元素。时间复杂度为O(log n)。
  3. 哈希表查找：利用哈希表数据结构实现的查找算法。哈希表根据关键字的哈希值存储元素，并提供快速的查找操作。通过将关键字映射到哈希表的索引位置，可以在常数时间内（平均情况下）找到目标元素。哈希表查找的平均时间复杂度是O(1)，但在最坏情况下可能达到O(n)。
  4. 二叉搜索树查找：利用二叉搜索树数据结构实现的查找算法。二叉搜索树是一颗有序二叉树，对于树中的每个节点，左子树中的所有节点的值小于当前节点的值，右子树中的所有节点的值大于当前节点的值。通过比较目标值与当前节点的值，可以决定继续在左子树还是右子树中进行查找。二叉搜索树查找的平均时间复杂度为O(log n)，但在最坏情况下可能达到O(n)。
  5. 平衡二叉搜索树查找：为了解决二叉搜索树在某些情况下退化成链表的问题，引入了平衡二叉搜索树（如AVL树、红黑树）。这些树通过自平衡机制保持树的平衡性，从而保证查找操作的平均时间复杂度为O(log n)。
  6. 插值查找：是二分查找的变体，用于在有序数组中进行查找。它不像二分查找每次都将查找范围一分为二，而是根据目标值与数组元素的分布情况，在靠近目标值的位置更有可能找到目标元素。最好情况下的时间复杂度为O(1)，最坏情况下为O(n)，平均情况下为O(log log n)。

😊2. C++实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered\_map>

// 线性查找
int linearSearch(const std::vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;  // 没有找到目标元素
}

// 二分查找（针对已排序数组）
int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;  // 没有找到目标元素
}

// 哈希表查找
int hashTableSearch(const std::unordered_map<int, int>& table, int target) {
    auto it = table.find(target);
    if (it != table.end()) {
        return it->second;
    }
    return -1;  // 没有找到目标元素
}

int main() {
    std::vector<int> arr = {10, 25, 4, 15, 8, 36};

    // 线性查找
    int target1 = 15;
    int index1 = linearSearch(arr, target1);
    if (index1 != -1) {
        std::cout << "线性查找：" << target1 << " 的索引为 " << index1 << std::endl;
    } else {
        std::cout << "线性查找：没有找到 " << target1 << std::endl;
    }

    // 二分查找前需要将数组排序
    std::sort(arr.begin(), arr.end());

    // 二分查找
    int target2 = 25;
    int index2 = binarySearch(arr, target2);
    if (index2 != -1) {
        std::cout << "二分查找：" << target2 << " 的索引为 " << index2 << std::endl;
    } else {
        std::cout << "二分查找：没有找到 " << target2 << std::endl;
    }

    // 哈希表查找
    std::unordered_map<int, int> table;
    for (int i = 0; i < arr.size(); i++) {
        table[arr[i]] = i;
    }

    int target3 = 8;
    int index3 = hashTableSearch(table, target3);
    if (index3 != -1) {
        std::cout << "哈希表查找：" << target3 << " 的索引为 " << index3 << std::endl;
    } else {
        std::cout << "哈希表查找：没有找到 " << target3 << std::endl;
    }

    return 0;
}

编译运行：

g++ -o main main.cpp && ./main
线性查找：15 的索引为 3
二分查找：25 的索引为 4
哈希表查找：8 的索引为 1

以上。

搜索算法介绍

深度优先

回溯

广度优先

动态规划算法

一维

二维

分割类型

子序列

背包

字符串编辑

股票交易

字符串

字符串可以看成是字符组成的数组。由于字符串是程序里经常需要处理的数据类型，因此有 很多针对字符串处理的题目。

字符串比较

字符串理解

字符串匹配

链表

链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点 的指针，因此很多链表问题可以用递归来处理。

反转链表

链表反转是C++面试经常会考的一道题目，也是链表的基本操作。下面是2种解法，分别是非递归法和递归法。

1.非递归法（迭代反转）
创建3个指针pre cur nex，每个循环指针各向后移动一个节点。

2.递归法
通过不断压栈，然后退栈，先进后出。

//test 反转链表

#include <iostream>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
};

//打印链表
void printList(ListNode* head)
{
    while (head)
    {
        cout << head->val;
        head = head->next;
        if (head)
            cout << "->";
    }
    cout << "\n";
}

//反转链表
//1.非递归法
ListNode* reverseList1(ListNode* head)
{
    //初始化ListNode
    ListNode *pre = NULL;
    ListNode *cur = head;
    ListNode *nex = NULL;

    while (cur)
    {
        //当前链表非空，进行以下处理
        nex = cur->next;    //当前值的下一位
        cur->next = pre;
        pre = cur;  //当前值赋给pre
        cur = nex;  //下一位赋给当前值
    }
    return pre;
}

//2.递归法
ListNode* reverseList2(ListNode* head)
{
    if (!head || !head->next)
        return head;
    ListNode *pNode = reverseList2(head->next);
    head->next->next = head;
    head->next = NULL;
    return pNode;
}

//main
int main()
{
    //创建链表
    ListNode* head = NULL;
    ListNode* cur = NULL;   //current
    for (int i = 1; i <= 6; ++i)
    {
        ListNode* node = new ListNode;
        node->val = i;
        node->next = NULL;
        if (head == NULL)
        {
            head = node;
            cur = node;
        }
        else
        {
            cur->next = node;
            cur = node;
        }
    }
    printList(head);    //打印当前链表
    printList(reverseList1(head));  //第一种方法
    //printList(reverseList2(head)); //第二种方法
    return 0;
}

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

使用哈希表和快慢指针两种方法来检测环形链表：

#include <iostream>
#include <unordered_set>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// 使用哈希表检测环形链表
bool hasCycleHash(Node* head) {
    std::unordered_set<Node*> visited;
    while (head) {
        if (visited.count(head)) {
            return true;
        }
        visited.insert(head);
        head = head->next;
    }
    return false;
}

// 使用快慢指针检测环形链表
bool hasCycleTwoPointers(Node* head) {
    if (!head || !head->next) {
        return false;
    }
    Node* slow = head;
    Node* fast = head->next;
    while (slow != fast) {
        if (!fast || !fast->next) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

int main() {
    // 创建一个环形链表
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = second; // 形成环

    // 使用哈希表检测环形链表
    bool hasCycleHashResult = hasCycleHash(head);
    std::cout << "Using hash table: " << (hasCycleHashResult ? "True" : "False") << std::endl;

    // 使用快慢指针检测环形链表
    bool hasCycleTwoPointersResult = hasCycleTwoPointers(head);
    std::cout << "Using two pointers: " << (hasCycleTwoPointersResult ? "True" : "False") << std::endl;

    return 0;
}

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

使用哈希表和快慢指针两种方法来找到相交链表的交点：

#include <iostream>
#include <unordered_set>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 使用哈希表找到相交链表的交点
ListNode* getIntersectionNodeHash(ListNode* headA, ListNode* headB) {
    std::unordered_set<ListNode*> visited;
    while (headA) {
        visited.insert(headA);
        headA = headA->next;
    }
    while (headB) {
        if (visited.count(headB)) {
            return headB;
        }
        headB = headB->next;
    }
    return nullptr;
}

// 使用快慢指针找到相交链表的交点
ListNode* getIntersectionNodeTwoPointers(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) {
        return nullptr;
    }
    ListNode* pA = headA;
    ListNode* pB = headB;
    while (pA != pB) {
        pA = pA ? pA->next : headB;
        pB = pB ? pB->next : headA;
    }
    return pA;
}

int main() {
    // 创建链表 A
    ListNode* a1 = new ListNode(4);
    ListNode* a2 = new ListNode(1);

    // 创建链表 B
    ListNode* b1 = new ListNode(5);
    ListNode* b2 = new ListNode(6);
    ListNode* b3 = new ListNode(1);

    // 创建相交节点
    ListNode* intersection = new ListNode(8);
    ListNode* intersection2 = new ListNode(4);
    ListNode* intersection3 = new ListNode(5);

    // 构建链表 A
    a1->next = a2;
    a2->next = intersection;
    intersection->next = intersection2;
    intersection2->next = intersection3;

    // 构建链表 B
    b1->next = b2;
    b2->next = b3;
    b3->next = intersection;

    // 使用哈希表找到相交链表的交点
    ListNode* intersectionNodeHash = getIntersectionNodeHash(a1, b1);
    std::cout << "Using hash table: " << intersectionNodeHash->val << std::endl;

    // 使用快慢指针找到相交链表的交点
    ListNode* intersectionNodeTwoPointers = getIntersectionNodeTwoPointers(a1, b1);
    std::cout << "Using two pointers: " << intersectionNodeTwoPointers->val << std::endl;

    return 0;
}

树

作为（单）链表的升级版，我们通常接触的树都是二叉树（binary tree），即每个节点最多有 两个子节点。

树的默认表示方法为：

struct TreeNode { 
    int val; 
    TreeNode *left; 
    TreeNode *right; 
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
};

树的递归

层次遍历

前中后序遍历

二叉查找树

图

作为指针三剑客之三，图是树的升级版。图通常分为有向（directed）或无向（undirected），有 循环（cyclic）或无循环（acyclic），所有节点相连（connected）或不相连（disconnected）。

二分图

拓扑排序

位运算

位运算是算法题里比较特殊的一种类型，它们利用二进制位运算的特性进行一些奇妙的优化 和计算。常用的位运算符号包括：“^”按位异或、“&”按位与、“|”按位或、“~”取反、“<<” 算术左移和“>>”算术右移。

数学

公倍数和公因数

质数

数字处理

随机与取样