专栏首页LeetCode圆圈中最后剩余的数字
原创

圆圈中最后剩余的数字

题目:

0,1,2,3 ,. . . ,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字,求这个圆圈里剩余的最后一个数字。

例如,0,1,2,3,4这5个数字组成的环中,从数字0开始每次删除第三个数字,那么依次删除的前四个数字就是:2,0,4,1

因此最后剩余的数字是3。

解法一:

直观的解法,将这环构造成一个环形链表。

首先,定义一个节点类作为数据类型。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

将所有的数据放入一个环形的链表中,while循环用于找到要删除的节点为cur.next,cur用于记录待删除的节点的前导。注意这里的循环的退出的条件。

public int lastRemaining(int n,int m){
    if (n<1 || m<1) return -1;
    ListNode cur = new ListNode(0) ;
    ListNode head = cur;
    for (int i=1;i<n;i++){
        cur.next = new ListNode(i);
        cur = cur.next;
    }
    cur.next = head;

    while (cur.next!=cur){
        for (int i = 1 ; i< m;i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
    }
    return cur.val;
}

这个解法的算法复杂度为O(n*m);

解法二:

通过归纳得到规律,简化算法。推导过程参照《剑指offer》的45题。

public int lastRemaining(int n,int m){
    if (n<1 || m<1) return -1;
    int last = 0;
    for (int i = 2;i<=n;i++){
        last = (last+m)%i;
    }
    return last;
}

这个算法的算法复杂度为O(n)。

总结:

在一些数学比较敏感的题目中,往往可以归纳出以一种简单的解法,避免使用大量的循环,当然解法一也是一种比较经典的思路,设计的环的问题,借用数据结构可以方便处理。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode <dfs>105&106 Construct Binary Tree

    Given preorder and inorder traversal of a tree, construct the binary tree.

    大学里的混子
  • 二叉树的Morris遍历

    大学里的混子
  • 复制含有随机指针节点的链表

    Node类中的value是节点值, next指针和正常单链表中next指针的意义一 样, 都指向下一个节点, rand指针是Node类中新增的指针, 这个指针可...

    大学里的混子
  • 暴力搜索------回溯法

    回溯法(backtracking)是深度优先搜索(DFS)的一种,按照深度优先的顺序便利解答树。应用范围很广,只要能把待求解的问题分成不太多的步骤,每个步骤又...

    刘开心_1266679
  • 文本相似度——编辑距离

    莫斯
  • LeetCode 1214. 查找两棵二叉搜索树之和(二叉树迭代器+双指针)

    给出两棵二叉搜索树,请你从两棵树中各找出一个节点,使得这两个节点的值之和等于目标值 Target。

    Michael阿明
  • 【剑指Offer】复杂链表的复制

    请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链...

    小新哟
  • LeetCode 430. 扁平化多级双向链表(DFS)

    您将获得一个双向链表,除了下一个和前一个指针之外,它还有一个子指针,可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项,依此类推,生成多级数据结构,如...

    Michael阿明
  • SystemVerilog的一个简单验证demo

    是一个简单的memory。就六个信号,时钟信号clk,复位信号reset(高有效),读使能信号rd_en,写使能信号wr_en,写数据信号wdata,读数据信号...

    数字IC小站
  • 数据结构-静态链表及其插入删除操作

    什么是静态链表 我们平常提及的链表一般指的是动态链表,是使用指针将一个一个的结点连起来,除了动态链表之外,还有静态链表,这种链表用数组来描述,主要为了解决没有指...

    chaibubble

扫码关注云+社区

领取腾讯云代金券