【数据结构与算法】【约瑟夫问题】还在用递归?教你用链表秒杀约瑟夫

简介: 【数据结构与算法】【约瑟夫问题】还在用递归?教你用链表秒杀约瑟夫

引言:为什么学习链表是数据结构与算法的必备知识


链表是数据结构与算法中最基本、最常用的数据结构之一。它在实际应用中具有重要性和优势,不仅在面试中扮演着重要角色,而且在竞赛中也占据相当比重。


根据广泛的面试经验和回馈,链表问题是面试中常见的考点之一,并且经常出现在技术公司的编程面试中。链表问题可以考察面试者对数据结构的理解、编码能力以及解决复杂问题的能力。掌握链表的基本操作和常见问题解法,可以帮助面试者在面试过程中更好地展现自己的能力。


其次,我们来分析链表在面试题中的比重。虽然具体比例会因面试的难度和类型而有所变化,但链表问题通常占据了相当大的比重。根据统计数据,链表问题在技术公司的编程面试中占据了约20%至30%的问题比例。这意味着,如果一个面试者没有对链表问题进行足够的准备,可能会错失相当多的机会。


此外,在竞赛中,链表问题同样具有一定的比重。在算法竞赛中,链表常常被用作构建和实现其他复杂数据结构的基础,如栈、队列和图等。因此,掌握链表的知识和技巧,对于在竞赛中迅速解决问题、提高算法效率至关重要。


单链表:定义、特点与基本操作


解释单链表的概念、结构和节点关系


单链表是一种由节点组成的数据结构,每个节点包含一个值和指向下一个节点的指针。这种结构使得单链表具有高效的插入和删除操作,但查找操作相对耗时。


单链表的抽象形态表现


在定义单链表的抽象形态时,我们可以通过表格框来展现其节点形态:

struct Node {
    int data;
    Node* next;
};

这里的data表示节点的数据,next表示指向下一个节点的指针。


示例链表抽象形态表现


以下是一个示例链表的抽象形态表现,我们用表格框展示链表的结构:

+---------+    +---------+    +---------+
|  data   |    |  data   |    |  data   |
+---------+    +---------+    +---------+
|  next   | -> |  next   | -> |  nullptr|
+---------+    +---------+    +---------+
   Node 1       Node 2       Node 3


单链表的基本操作


插入操作


在头部插入节点

void insertAtHead(Node*& head, int value) {
    Node* newNode = new Node(value);
    newNode->next = head;
    head = newNode;
}

插入节点后的抽象形态表现:

+---------+    +---------+    +---------+    +---------+
|  value  |    |  data   |    |  data   |    |  data   |
+---------+    +---------+    +---------+    +---------+
|  next   | -> |  next   | -> |  next   | -> |  nullptr|
+---------+    +---------+    +---------+    +---------+
  New Node     Node 1       Node 2       Node 3


在尾部插入节点

void insertAtTail(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}


删除操作


删除头节点

void deleteAtHead(Node*& head) {
    if (head == nullptr) {
        return;
    }
    Node* temp = head;
    head = head->next;
    delete temp;
}


删除尾节点

void deleteAtTail(Node*& head) {
    if (head == nullptr) {
        return;
    }
    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }
    Node* temp = head;
    while (temp->next->next != nullptr) {
        temp = temp->next;
    }
    delete temp->next;
    temp->next = nullptr;
}


查找操作


遍历查找

Node* search(Node* head, int value) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == value) {
            return temp;
        }
        temp = temp->next;
    }
    return nullptr;
}


递归查找

Node* searchRecursive(Node* head, int value) {
    if (head == nullptr) {
        return nullptr;
    }
    if (head->data == value) {
        return head;
    }
    return searchRecursive(head->next, value);
}


单链表的案例分析


LCR 078. 合并 K 个升序链表


给定一个链表数组,每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中,返回合并后的链表。


示例 1:


输入:lists = [[1,4,5],[1,3,4],[2,6]]

输出:[1,1,2,3,4,4,5,6]

解释:链表数组如下:

[

 1->4->5,

 1->3->4,

 2->6

]

将它们合并到一个有序链表中得到。

1->1->2->3->4->4->5->6


示例 2:


输入:lists = []

输出:[]


示例 3:


输入:lists = [[]]

输出:[]


提示:


  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4


题目分析: 题目要求合并K个升序链表,其中每个链表可能包含0个或多个节点。我们需要以升序顺序返回合并后的链表。


解题思路: 为了解决这个问题,我们可以使用优先队列来维护所有的头节点,并依次弹出最小的头节点,并将其对应的链表的下一个节点插入到队列中。这个过程可以看作是归并排序的一部分,因为它类似于归并排序中合并两个有序数组的操作。这种方法的时间复杂度为O(Nlogk),其中k是链表数,N是所有链表中的节点数。


代码解读:


  1. 定义一个优先队列,将所有的头节点添加到队列中。
  2. 定义一个哨兵节点,方便处理边界情况。
  3. 不断弹出最小的头节点,并将其对应的链表的下一个节点添加到队列中。
  4. 返回哨兵节点的下一个节点作为合并后的链表头。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
// 定义一个链表节点比较函数,用于优先队列的排序
int cmp(const void* a, const void* b) {
    return (*((struct ListNode**)a))->val - (*((struct ListNode**)b))->val;
}
 
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    // 创建一个优先队列
    struct ListNode** pq = (struct ListNode**)malloc(sizeof(struct ListNode*) * listsSize);
    int size = 0;
 
    // 将所有的头节点添加到队列中
    for (int i = 0; i < listsSize; i++) {
        if (lists[i]) {
            pq[size++] = lists[i];
        }
    }
 
    // 使用自定义比较函数对队列中的元素进行排序
    qsort(pq, size, sizeof(struct ListNode*), cmp);
 
    // 定义一个哨兵节点,方便处理边界情况
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = -1;
    dummy->next = NULL;
    struct ListNode* cur = dummy;
 
    // 不断弹出最小的头节点,并将其对应的链表的下一个节点插入到队列中
    while (size > 0) {
        struct ListNode* node = pq[0];
        cur->next = node;
        cur = cur->next;
        if (node->next) {
            pq[0] = node->next;
        } else {
            pq[0] = pq[--size];
        }
        if (size > 0) {
            // 对队列中的元素重新排序
            int i = 0, j = 2 * i + 1;
            while (j < size) {
                if (j + 1 < size && pq[j + 1]->val < pq[j]->val) {
                    j++;
                }
                if (pq[j]->val < pq[i]->val) {
                    struct ListNode* tmp = pq[i];
                    pq[i] = pq[j];
                    pq[j] = tmp;
                    i = j;
                    j = 2 * i + 1;
                } else {
                    break;
                }
            }
        }
    }
 
    return dummy->next;
}


. 双链表:定义、特点与基本操作


1.1 介绍双链表的定义和结构


在计算机科学中,双链表(Doubly Linked List)是一种常见的数据结构,它由一系列节点组成,每个节点包含两个指针,分别指向前一个节点和后一个节点,形成一个双向链表。与单链表相比,双链表可以更高效地进行向前和向后遍历,但也因为需要额外的指针而占用更多的内存空间。


下面是一个双链表节点的抽象形态表现:

节点结构
数据
前驱指针
后继指针

在这个表格框中,我们可以看到双链表节点的三个属性:数据、前驱指针和后继指针。数据存储了节点所需的信息,而前驱指针和后继指针则分别指向了前一个节点和后一个节点,使得节点之间能够互相连接。


1.2 学习双链表的基本操作:插入、删除、查找等


接下来,让我们一起学习双链表的基本操作,包括插入、删除和查找。


插入操作


在双链表中,插入操作可用于在任意位置插入一个新节点。下面是一个用 C 语言实现的双链表插入操作的示例代码:

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};
 
void insert(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->prev = NULL;
    new_node->next = NULL;
 
    if (*head == NULL) {
        *head = new_node;
    } else {
        struct Node* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
        new_node->prev = current;
    }
}

在上述代码中,我们定义了一个结构体 Node,表示双链表的节点。insert 函数用于向双链表中插入一个新节点。如果双链表为空,则将新节点作为头节点;否则,遍历双链表至末尾,将新节点插入到最后一个节点之后。


删除操作


删除操作允许我们从双链表中移除指定节点。下面是一个用 C 语言实现的双链表删除操作的示例代码:

void delete(struct Node** head, int data) {
    struct Node* current = *head;
    while (current != NULL) {
        if (current->data == data) {
            if (current->prev != NULL) {
                current->prev->next = current->next;
            }
            if (current->next != NULL) {
                current->next->prev = current->prev;
            }
            if (current == *head) {
                *head = current->next;
            }
            free(current);
            return;
        }
        current = current->next;
    }
}

在上述代码中,我们定义了一个 delete 函数,用于从双链表中删除包含指定数据的节点。通过遍历双链表,我们找到目标节点后,更新前驱和后继节点的指针,并正确处理头节点的情况。最后,释放目标节点的内存。


查找操作


查找操作用于确定双链表中是否存在包含特定数据的节点。下面是一个用 C 语言实现的双链表查找操作的示例代码:

int search(struct Node* head, int data) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == data) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

在上述代码中,我们定义了一个 search 函数,用于在双链表中搜索包含特定数据的节点。通过遍历双链表,我们可以确定是否存在满足条件的节点。


【链表应用】约瑟夫问题


上面铺垫了那么多 其实也只是为了解决问题而做的嘛  那么现在我们来面对一个实际的问题 约瑟夫问题 (典中典了属于是)


约瑟夫问题(Josephus Problem)是一个经典的数学问题,它的形式是:n个人围成一圈,从第k个人开始报数,数到m的那个人出列,然后从下一个人开始重新报数,直到最后剩下一个人。这个问题可以用链表来解决。


我们可以使用循环链表来模拟这个过程。具体地,我们先创建一个有n个节点的循环链表,每个节点代表一个人。然后,我们从第k个人开始,遍历链表并数m个人,将第m个人删除并输出,然后从下一个人开始重新报数,直到只剩下一个人为止。


下面是一个使用单向循环链表解决约瑟夫问题的示例代码:

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
void create_circle(struct Node** head, int n) {
    struct Node* current = *head;
    for (int i = 1; i <= n; i++) {
        struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
        new_node->data = i;
        new_node->next = NULL;
        if (*head == NULL) {
            *head = new_node;
            current = new_node;
        } else {
            current->next = new_node;
            current = new_node;
        }
    }
    current->next = *head;
}
 
void josephus(struct Node** head, int k, int m) {
    struct Node* current = *head;
    for (int i = 1; i < k; i++) {
        current = current->next;
    }
    while (current->next != current) {
        for (int i = 1; i < m; i++) {
            current = current->next;
        }
        struct Node* temp = current->next;
        printf("%d ", temp->data);
        current->next = temp->next;
        free(temp);
    }
    printf("%d\n", current->data);
    *head = NULL;
}
 
int main() {
    struct Node* head = NULL;
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);
    create_circle(&head, n);
    josephus(&head, k, m);
    return 0;
}

在上述代码中,我们首先使用 create_circle 函数创建了一个有n个节点的循环链表,每个节点的数据为从1到n的整数。接着,我们使用 josephus 函数解决约瑟夫问题。该函数从第k个人开始遍历链表并数m个人,删除第m个人并输出,直到只剩下一个人为止。


运行程序时,输入n、k和m的值,即可得到最后留下的人的编号。


当然了!除了使用链表来解决约瑟夫问题,还有一种更巧妙的思路可以用数学方法直接求解。


假设n个人围成一圈,从第k个人开始报数,数到m的那个人出列。我们可以用一个递推公式来求解最后留下的人的编号。

首先,我们定义一个函数f(n, m)表示在n个人中,每次数m个人后剩下的人的编号。根据题意,我们知道当只有一个人时,即n=1时,这个人的编号为1,所以我们有基本情况:f(1, m) = 1。


接下来,我们考虑n个人的情况。当第一个人被数到并出列后,剩下的人变成了n-1个人,同时原来的第m+1个人变成了新的第一个人。因此,我们可以得到递推关系式:


f(n, m) = (f(n-1, m) + m) % n


其中,%表示取模运算。通过这个递推关系式,我们可以从n=1开始递推,直到n等于给定的人数。


下面是使用递推公式解决约瑟夫问题的示例代码:

#include <stdio.h>
 
int josephus(int n, int k, int m) {
    if (n == 1) {
        return 1;
    } else {
        return (josephus(n-1, k, m) + m) % n;
    }
}
 
int main() {
    int n, k, m;
    printf("请输入人数n:");
    scanf("%d", &n);
    printf("请输入起始位置k:");
    scanf("%d", &k);
    printf("请输入报数m:");
    scanf("%d", &m);
 
    int last_person = josephus(n, k, m);
    printf("最后留下的人的编号为:%d\n", last_person);
 
    return 0;
}

运行程序时,输入n、k和m的值,即可得到最后留下的人的编号。


通过使用递推公式,我们可以直接求解约瑟夫问题,避免了构建链表和模拟报数的过程。这种方法更加简洁、高效,并且易于理解和实现。


面试官一看,眉毛邹了起来,递推可以是可以  但是这资源利用....嘶小伙子不懂得勤俭持家呀,万一栈溢出了怎么办?他正想微笑告诉你,小伙子回去等通知吧

你说 别急 因为我还有又简单又能节约资源的办法  --环形链表来解决这个问题


于是就有了下文


使用环形链表可以很方便地解决约瑟夫问题。我们可以按照如下步骤进行:


  1. 创建一个含有n个结点的环形链表,表示围成一圈的n个人。
  2. 从第k个人开始报数,每次数到m的那个人出列,直到只剩下一个人为止。
  3. 得到最后留下的人的编号。


下面是使用C语言编写的基于环形链表的解决约瑟夫问题的示例代码:

#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int data;
    struct node *next;
} Node;
 
Node *createList(int n) {
    Node *head = NULL, *prev = NULL;
    for (int i = 1; i <= n; i++) {
        Node *new_node = (Node *)malloc(sizeof(Node));
        new_node->data = i;
        if (prev == NULL) {
            head = new_node;
        } else {
            prev->next = new_node;
        }
        prev = new_node;
    }
    prev->next = head;  // 链接首尾结点,形成环形链表
    return head;
}
 
int josephus(Node *head, int k, int m) {
    Node *prev = NULL, *curr = head;
    for (int i = 1; i < k; i++) {
        prev = curr;
        curr = curr->next;
    }
    while (curr->next != curr) {  // 只剩下一个人时退出循环
        for (int i = 1; i < m; i++) {
            prev = curr;
            curr = curr->next;
        }
        prev->next = curr->next;  // 删除当前结点
        Node *temp = curr;
        curr = curr->next;
        free(temp);
    }
    return curr->data;  // 返回最后留下的结点的编号
}
 
int main() {
    int n, k, m;
    printf("请输入人数n:");
    scanf("%d", &n);
    printf("请输入起始位置k:");
    scanf("%d", &k);
    printf("请输入报数m:");
    scanf("%d", &m);
 
    Node *head = createList(n);
    int last_person = josephus(head, k, m);
    printf("最后留下的人的编号为:%d\n", last_person);
 
    return 0;
}

在上述代码中,我们定义了一个名为 createList 的函数,用于创建含有n个结点的环形链表;定义了一个名为 josephus 的函数,用于解决约瑟夫问题。在 main 函数中,我们首先输入人数n、起始位置k和报数m的值,然后调用 createList 函数创建环形链表,并调用 josephus 函数求解并输出最后留下的人的编号。


通过使用环形链表来解决约瑟夫问题,我们避免了构建数组和模拟报数的过程,使得代码更加简洁、高效,并且易于理解和实现。


相关文章
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
55 4
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
45 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
87 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
48 0
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
61 0
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
26 0
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
92 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
41 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍