当前位置：首页 > article >正文

刷题_28：反转部分单向链表 and 猴子分桃

article 2024/11/17 16:01:28

一.反转部分单向链表

题目链接：

反转部分单向链表

题目描述：

给定一个单链表，在链表中把第 L 个节点到第 R 个节点这一部分进行反转。

输入描述：

n 表示单链表的长度。
val 表示单链表各个节点的值。
L 表示翻转区间的左端点。
R 表示翻转区间的右端点。

输出描述：

在给定的函数中返回指定链表的头指针。

示例1：

输入：
5
1 2 3 4 5
1 3
输出：
3 2 1 4 5

示例2：

输入：
0,0
输出：
0

个人总结：

定义一个单链表节点，然后构造单链表，再根据输入的l找到左端点和其前驱节点，根据r找到右端点和其后继节点，接着断开链表，翻转链表，最后在重新连接链表，按照顺序输出即可。

代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //构造单链表
        int n = sc.nextInt();
        Node dummyHead = new Node(-1);
        Node tail = dummyHead;
        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            tail.next = new Node(val);
            tail = tail.next;
        }
        int l = sc.nextInt();
        int r = sc.nextInt();
        //找到第l个节点和他的前驱节点
        Node pre = null;
        Node ln = dummyHead;
        while (l-- != 0) {
            pre = ln;
            ln = ln.next;
        }
        //找到第r个节点和他的后继节点
        Node rn = dummyHead;
        Node next = rn.next;
        while (r-- != 0) {
            rn = rn.next;
            next = rn.next;
        }
        //断开
        pre.next = null;
        rn.next = null;
        //逆置部分
        reverse(ln);
        //在链接上
        //逆置之后 rn为头 ln为尾
        pre.next = rn;
        ln.next = next;
        //打印
        Node tmp = dummyHead.next;
        while (tmp != null) {
            System.out.print(tmp.val + " ");
            tmp = tmp.next;
        }
    }

    public static Node reverse(Node head) {
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    static class Node {
        int val;
        Node next;

        public Node() {

        }

        public Node(int val) {
            this.val = val;
        }
    }
}

二.猴子分桃

题目链接：

猴子分桃

题目描述：

老猴子辛苦了一辈子，给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。
第一个猴子来了，它把桃子分成五堆，五堆一样多，但还多出一个。它把剩下的一个留给老猴子，自己拿走其中的一堆。
第二个猴子来了，它把桃子分成五堆，五堆一样多，但又多出一个。它把多出的一个留给老猴子，自己拿走其中的一堆。
后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。
这里有n只小猴子，请你写个程序计算一下在开始时至少有多少个桃子，以及最后老猴子最少能得到几个桃子。

输入描述：

输入包括多组测试数据。
每组测试数据包括一个整数n(1≤n≤20)。
输入以0结束，该行不做处理。

输出描述：

每组测试数据对应一行输出。
包括两个整数a，b。
分别代表开始时最小需要的桃子数，和结束后老猴子最少能得到的桃子数。

示例1：

输入：
5
1
0
输出：
3121 1025
1 1

他人思路：

纯数学题，思路与前面人的思路不太一样，不用借桃子，直接根据题意来进行求解，设最少需要桃子X个：
第一次经过题目的处理剩余桃子数目为：4/5(X-1)=(4/5)X-(4/5)；
第二次剩余桃子个数为：4/5(4/5(X-1)-1)=((4/5)^2)*X-(4/5)2-(4/5)；
第三次剩余桃子个数为：4/5(4/5(4/5(X-1)-1)-1)=((4/5)^3)*X-(4/5)3-(4/5)^2-(4/5)；
…
依次类推，经过n只猴子的类似处理，剩余桃子数为：
4/5(4/5(4/5(…(4/5(X-1)…)-1)-1)-1)=((4/5)^n)*X)-(4/5)n-(4/5)^(n-1)-…-(4/5)
=((4/5)^{n)*X)-4[1-(4/5)}n]
=(X+4)(4/5)^n-4
因此，同前人的推导一致，最终，只需要满足x+4的值为5^n次方则可以保证最后能得到一个整数，满足题目的要求。

代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n != 0) {
                System.out.print((long) Math.pow(5, n) - 4 + " ");
                System.out.print((long) Math.pow(4, n) - 4 + n);
            }
            System.out.println();
        }
    }
}