Java题目训练——反转部分单向链表和猴子分桃

亦凉 2023-09-30 23:00 18阅读 0赞

### 一、反转部分单向链表 ###

题目描述：

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

输入描述：

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

输出描述：

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

补充说明：

> 1<=n<=1000000
> 
> 1<=L<=R<=n
> 
> \-1000000<=val<=1000000

示例

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

**题目解析：**

> 本题考察关于链表的基本操作，首先需要我们手动写一个结点类，包含此时的值和连接下一个结点的指向。
> 
> 在主函数中，将输入的数据先存入数组，然后设置一个头结点，通过遍历数组，将值赋给当前结点，依次如此建立链表，然后就是对该链表进行部分反转的操作。
> 
> 这里使用一个方法实现反转部分链表的功能，将链表的头结点，反转的起始位置和结束位置传入，存下起始位置的前一个位置pre，设立一个临时结点temp，指向当前结点cur的下一个结点，然后让当前结点指向temp的下一个结点，temp结点指向当前结点，pre结点指向temp结点，实现将结点插入至反转的起始位置，遍历至结束位置，实现链表部分反转。
> 
> 最后按照要求输出即可。

import java.util.Scanner;
    
    class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val){
            this.val = val;
            this.next = null;
        }
    }
    
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
            }
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            ListNode head = new ListNode(arr[0]);
            ListNode cur = head;
            for (int i = 1; i < n; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
    
            ListNode ans = res(head, start, end);
            while(ans.next != null){
                System.out.print(ans.val + " ");
                ans = ans.next;
            }
            System.out.println(ans.val);
        }
    
       public static ListNode res(ListNode head, int start, int end){
            ListNode ans = new ListNode(-1);
            ans.next = head;
            ListNode pre = ans;
           for (int i = 1; i < start; i++) {
               pre = pre.next;
           }
           ListNode cur = pre.next;
           for (int i = start; i < end; i++) {
               ListNode temp = cur.next;
               cur.next = temp.next;
               temp.next = pre.next;
               pre.next = temp;
           }
           return ans.next;
       }
    }

### 二、猴子分桃 ###

题目描述：

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

输入描述：

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

输出描述：

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

示例

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

**题目解析：**

> 这道题目主要需要找到规律，寻找其中的隐含的关系。我们设本来有x个桃子，一开始就可以借给其4个桃子，实现被5均分，然后观察分桃的规律：
> 
> 第一个猴子拿走： (x + 4) / 5 , 剩余： (x + 4) \* (4 / 5)
> 
> 第二个猴子拿走：(x + 4) \* (4 / 5) / 5 , 剩余： (x + 4) \* (4 / 5) \* (4 / 5)
> 
> 第三个猴子拿走：(x + 4) \* (4 / 5) / 5 / 5 , 剩余： (x + 4) \* (4 / 5) \* (4 / 5) \* (4 / 5)
> 
> 第n个猴子拿走后剩余：(x + 4) \* ((4 / 5)) ^ n
> 
> 由于剩余的桃子是整数，所以可以得到关系：x + 4 = 5 ^ n
> 
> 即x = 5 ^ n - 4 ，x为一开始的桃子数。
> 
> 将 x = 5 ^ n - 4 代入 (x + 4) \* ((4 / 5)) ^ n 得到：
> 
> 老猴子最后得到的桃子数：4 ^ n 然后再加上n个猴子每次给他的一个桃子，减去一开始借给其的4个桃子，最后得到4 ^ n - 4 + n。

import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext()){
            int n = scanner.nextInt();
            if(n == 0){
                break;
            }
            //a个桃子，借给其4个
            //第一个猴子：(x + 4) / 5 , 剩余 (x + 4) * (4 / 5)
            //第二个猴子：(x + 4) * (4 / 5) / 5 , 剩余 (x + 4) * (4 / 5) * (4 / 5)
            //第三个猴子：(x + 4) * (4 / 5) / 5 / 5 , 剩余 (x + 4) * (4 / 5) * (4 / 5) * (4 / 5)
            //n...(x + 4) * ((4 / 5)) ^ n
            //剩余的桃子是整数：x + 4 = 5 ^ n
            //x = 5 ^ n - 4代入：
            //老猴子：(x + 4) * ((4 / 5)) ^ n + n - 4
            //老猴子：4 ^ n - 4 + n
            long a = (long)Math.pow(5, n);
            long b = (long)Math.pow(4, n);
            System.out.println((a - 4) + " " + (b - 4 + n));
            }
        }
    }

如有建议或想法，欢迎一起学习讨论~