【Java版oj】day28反转部分单向链表、猴子分桃

小咪咪 2024-03-24 17:06 60阅读 0赞

**目录**

一、反转部分单向链表

（1）原题再现

（2）问题分析

（3）完整代码

二、猴子分桃

（1）原题再现

（2）问题分析

（3）完整代码

--------------------

> ## 一、反转部分单向链表 ##
> 
> ### （1）原题再现 ###
> 
> [反转部分单向链表\_\_牛客网][Link 1]
> 
> 给定一个单链表，在链表中把第 L 个节点到第 R 个节点这一部分进行反转。
> 
> **输入描述:**
> 
> n 表示单链表的长度。
> 
> val 表示单链表各个节点的值。
> 
> L 表示翻转区间的左端点。
> 
> R 表示翻转区间的右端点。
> 
> **输出描述:**
> 
> 在给定的函数中返回指定链表的头指针。
> 
> 示例1
> 
> 输入
> 
> 5
> 
> 1 2 3 4 5
> 
> 1 3
> 
> 输出
> 
> 3 2 1 4 5
> 
> ### （2）问题分析 ###
> 
> 这道题需要先定义一个结点类，里面包括结点存储的值和下一个指向，定义一个构造方法。因为这里输入输出全是自己写的，所以我先定义了一个数组，将输入的所有值放入数组中，先进行部分反转，然后再把每个值装入结点中，并连接起来。最后输出。
> 
> ps：其实好像直接用数组输入输出也可以，不知道这道题到底考什么。
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     
>     /*
>      * 反转部分单向链表
>      */
>     class Node {
>         int val;
>         Node next;
>         public Node(int val) {//构造方法
>             super();
>             this.val = val;
>             this.next = null;
>         }
>     }
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             int len = sc.nextInt();
>             int []value = new int[len];
>     
>             for (int i = 0; i < len; i++) {
>                 value[i] = sc.nextInt();
>             }
>     
>             int left = sc.nextInt();
>             int right = sc.nextInt();
>     
>             reverse( value, left-1, right-1);
>             Node head = arrayToList(value);
>             Node node;
>             for (node = head; node.next != null; node = node.next) {
>                 System.out.print(node.val + " ");
>             }
>             System.out.print(node.val);
>         }
>         public static void reverse(int []value, int left, int right) {
>             while (left < right) {
>                 int tmp = value[left];
>                 value[left] = value[right];
>                 value[right] = tmp;
>                 left++;
>                 right--;
>             }
>         }
>         public static Node arrayToList(int []value) {
>             Node head = new Node(-1);
>             Node node = head;
>             for (int i = 0; i < value.length; i++) {
>                 Node newNode = new Node(value[i]);
>                 node.next = newNode;
>                 node = newNode;
>             }
>             return head.next;
>         }
>     }
> 
> ![0cdbdc5b58fb4892b0ba2d26ca3b2789.png][]

> ## 二、猴子分桃 ##
> 
> ### （1）原题再现 ###
> 
> [猴子分桃\_\_牛客网][Link 2]
> 
> 老猴子辛苦了一辈子，给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。  
> 第一个猴子来了，它把桃子分成五堆，五堆一样多，但还多出一个。它把剩下的一个留给老猴子，自己拿走其中的一堆。  
> 第二个猴子来了，它把桃子分成五堆，五堆一样多，但又多出一个。它把多出的一个留给老猴子，自己拿走其中的一堆。  
> 后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。  
> 这里有n只小猴子，请你写个程序计算一下在开始时至少有多少个桃子，以及最后老猴子最少能得到几个桃子。
> 
> **输入描述:**
> 
> 输入包括多组测试数据。
> 
> 每组测试数据包括一个整数n(1≤n≤20)。
> 
> 输入以0结束，该行不做处理。
> 
> **输出描述:**
> 
> 每组测试数据对应一行输出。
> 
> 包括两个整数a，b。 分别代表开始时最小需要的桃子数，和结束后老猴子最少能得到的桃子数。
> 
> 示例1
> 
> 输入
> 
> 5
> 
> 1
> 
> 0
> 
> 输出
> 
> 3121 1025
> 
> 1 1
> 
> ### （2）问题分析 ###
> 
> 这道题是一道找规律。因为每次分5堆都会多出来1个，所以我们借4个桃子，这样每次都可以刚好分成5堆并且，每次给老猴子的桃子都不在我们借出的那4个中，这样最后减掉4就可以得到结果。假设最初由x个桃子，我们借给猴子4个，则此时有x+4个，第一个猴子得到![\\frac\{\\left ( x+4 \\right )\}\{5\}][frac_left _ x_4 _right _5]，剩余![\\frac\{4\\left ( x+4 \\right )\}\{5\}][frac_4_left _ x_4 _right _5]个。第二个猴子分完后剩余![\\frac\{4^\{2\}\\left ( x+4 \\right )\}\{5^\{2\}\}][frac_4_2_left _ x_4 _right _5_2]个。第三个猴子分完后剩余![\\frac\{4^\{3\}\\left ( x+4 \\right )\}\{5^\{3\}][frac_4_3_left _ x_4 _right _5_3]个。依次类推，最后一个猴子分完后剩余![\\frac\{4^\{n\}\\left ( x+4 \\right )\}\{5^\{n\}][frac_4_n_left _ x_4 _right _5_n]。老猴子得到就是每次分到的1个+最后剩余的减去一开始借给他的四个得到![n-4+\\frac\{4^\{n\}\\left ( x+4 \\right )\}\{5^\{n\}][n-4_frac_4_n_left _ x_4 _right _5_n]。要满足最后剩余的为整数，并且x最小，则当 ![x+4=5^\{n\}][x_4_5_n]时，满足要求，老猴子最终得到![n-4+4^\{n\}][n-4_4_n]。
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     
>     /*
>      * 猴子分桃
>      */
>     
>     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) {
>                     return;
>                 }
>                 long a = (long)Math.pow(5, n);
>                 long b = (long)Math.pow(4, n);
>                 System.out.println((a - 4) + " " + (b - 4 + n));
>             }
>         }
>     }
> 
> ![b6e9e731543c4cc8804cfebe907e76e4.png][]

--------------------

![78f4a2edc6834fcc8b5ab75ba81e3083.png][]

[Link 1]: https://www.nowcoder.com/questionTerminal/f11155006f154419b0bef6de8918aea2?answerType=1&f=discussion
[0cdbdc5b58fb4892b0ba2d26ca3b2789.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/5ed725cc00f442d28fec5539dee502bf.png
[Link 2]: https://www.nowcoder.com/questionTerminal/480d2b484e1f43af8ea8434770811b4a
[frac_left _ x_4 _right _5]: https://latex.csdn.net/eq?%5Cfrac%7B%5Cleft%20%28%20x&plus;4%20%5Cright%20%29%7D%7B5%7D
[frac_4_left _ x_4 _right _5]: https://latex.csdn.net/eq?%5Cfrac%7B4%5Cleft%20%28%20x&plus;4%20%5Cright%20%29%7D%7B5%7D
[frac_4_2_left _ x_4 _right _5_2]: https://latex.csdn.net/eq?%5Cfrac%7B4%5E%7B2%7D%5Cleft%20%28%20x&plus;4%20%5Cright%20%29%7D%7B5%5E%7B2%7D%7D
[frac_4_3_left _ x_4 _right _5_3]: https://latex.csdn.net/eq?%5Cfrac%7B4%5E%7B3%7D%5Cleft%20%28%20x&plus;4%20%5Cright%20%29%7D%7B5%5E%7B3%7D
[frac_4_n_left _ x_4 _right _5_n]: https://latex.csdn.net/eq?%5Cfrac%7B4%5E%7Bn%7D%5Cleft%20%28%20x&plus;4%20%5Cright%20%29%7D%7B5%5E%7Bn%7D
[n-4_frac_4_n_left _ x_4 _right _5_n]: https://latex.csdn.net/eq?n-4&plus;%5Cfrac%7B4%5E%7Bn%7D%5Cleft%20%28%20x&plus;4%20%5Cright%20%29%7D%7B5%5E%7Bn%7D
[x_4_5_n]: https://latex.csdn.net/eq?x&plus;4%3D5%5E%7Bn%7D
[n-4_4_n]: https://latex.csdn.net/eq?n-4&plus;4%5E%7Bn%7D
[b6e9e731543c4cc8804cfebe907e76e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9d433d8fe8ef4d1098d3eee66b3a5941.png
[78f4a2edc6834fcc8b5ab75ba81e3083.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/26459f0a2b7846b3af1e503276804710.png