【算法刷题日记之本手篇】猴子分桃与判断是否为回文字符串

举报
未见花闻 发表于 2022/11/30 21:07:17 2022/11/30
【摘要】 ⭐️猴子分桃⭐️ 🔐题目详情老猴子辛苦了一辈子,给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。第一个猴子来了,它把桃子分成五堆,五堆一样多,但还多出一个。它把剩下的一个留给老猴子,自己拿走其中的一堆。第二个猴子来了,它把桃子分成五堆,五堆一样多,但又多出一个。它把多出的一个留给老猴子,自己拿走其中的一堆。后来的小猴子都如此照办。最后剩下的桃子全部留给老...

⭐️猴子分桃⭐️

🔐题目详情

老猴子辛苦了一辈子,给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。
第一个猴子来了,它把桃子分成五堆,五堆一样多,但还多出一个。它把剩下的一个留给老猴子,自己拿走其中的一堆。
第二个猴子来了,它把桃子分成五堆,五堆一样多,但又多出一个。它把多出的一个留给老猴子,自己拿走其中的一堆。
后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。
这里有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;
    }
}

🌱总结

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200