⭐️猴子分桃⭐️

🔐题目详情

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

输入描述:

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

输出描述:

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

示例1

输入

5
1
0

输出

3121 1025
1 1

题目链接：猴子分桃

💡解题思路

基本思路： 数学
解题思路：
我们不妨设最开始最少所需的桃子数为x，老猴子最后拿到的桃子数为y，为了计算简单， 我们在最开始借4个桃子给猴子，则最开始第一只猴子拿到的桃子数目为x+4，此时x+4一定为5的整数。
当n=1时， 第一只猴子拿到的桃子数为(x+4) * (1 / 5) - 1，拿到桃子后剩余桃子数为(x+4) * (4 / 5)。

剩余的桃子数相较于之前多了 (X+4)*(4/5) - (X-1)*(4/5) = 4 个，但这样就恰巧保证了下一只小猴子分桃时，也能刚好均分为 5 堆。由此可见，所有的小猴子都不会多得桃子，老猴子也不会少得桃子，并且每次小猴子都能刚好将桃子均分为 5 堆，而借给的那 4 个桃子每次都在剩余的那部分里，最后去除即可。

当n=2时，第二只猴子拿到的桃子后剩余桃子数为(x+4) * (4/5) ^ 2。
当n=3时，第三只猴子拿到桃子后，剩余桃子数为(x+4) * (4 / 5) ^3。
…
当n=n时，第n只猴子拿完桃子之后，剩余的桃子数为(x+4) * (4 / 5) ^ n。

最终需要满足(x+4) * (4 / 5) ^ n为整数，即x=5^n-4。
同时老猴子的桃子数为y=(x+4) * (4 / 5) ^ n + n - 4 = 4 ^ n + n - 4，其中n表示每轮猴子分桃所贡献的桃子数，减去4为了除去借来桃子数所做的贡献。

🔑源代码

C++实现：

// write your code here cp
#include <iostream>
#include <cmath>

int main()
{
    int n = 0;
    while (std::cin >> n) 
    {
        if (n == 0) continue;
        long x = pow(5, n) - 4;
        long y = pow(4, n) + n - 4;
        std::cout << x << " " << y << std::endl;
    }
    return 0;
}

java实现：

// write your code here
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) break;
            long x = (long) Math.pow(5, n) - 4;
            long y = (long) Math.pow(4, n) + n - 4;
            System.out.println(x + " " + y);
        }
    }
}

🌱总结

本题为数学推理题，主要考察数学推理能力。

⭐️判断是否为回文字符串⭐️

🔐题目详情

给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。

字符串回文指该字符串正序与其逆序逐字符一致。

数据范围：0<n≤1000000

要求：空间复杂度 O(1)，时间复杂度O*(*n)

示例1

输入：

"absba"

返回值：

true

示例2

输入：

"ranko"

返回值：

false

示例3

输入：

"yamatomaya"

返回值：

false

示例4

输入：

"a"

返回值：

true

备注：

字符串长度不大于1000000，且仅由小写字母组成

题目链接：判断是否为回文字符串

💡解题思路

基本思路： 双指针
解题思路：
我们不妨设字符串长度为n，左指针为l，初始指向字符串第一个字符，右指针为r，初始指向字符串的最后一个字符，然后我们对比l所指向的字符与r所指向的字符是否相同，如果相同则l++ r--继续进行比较，直到l==r为止，如果比较的结果全部是相同的，则返回true，遍历过程中只要出现不相同的情况直接返回false。

🔑源代码

C++版本实现：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    bool judge(string str) {
        // write code here
        int n = str.length();
        int l = 0;
        int r = n - 1;
        while (l < r) {
            if (str[l] != str[r]) return false;
            l++;
            r--;
        }
        return true;
    }
};

Java版本实现：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    public boolean judge (String str) {
        // write code here
        //双指针模拟
        char[] cs = str.toCharArray();
        int n = cs.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            if (cs[l] != cs[r]) return false;
            l++;
            r--; 
        }
        return true;
    }
}

🌱总结

本题为双指针模拟题，主要考察字符串的比较与对回文串的理解。