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

一.反转部分单向链表

题目链接：

反转部分单向链表

题目描述：

给定一个单链表，在链表中把第 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();}}
}