Java题目训练——反转部分单向链表和猴子分桃
一、反转部分单向链表
题目描述：
给定一个单链表，在链表中把第 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 + nlong a = (long)Math.pow(5, n);long b = (long)Math.pow(4, n);System.out.println((a - 4) + " " + (b - 4 + n));}}
}如有建议或想法，欢迎一起学习讨论~