【LeetCode系列】最长回文子串（双指针中心扩散）与可怜的小猪（老鼠毒药问题）

⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【最长回文子串】和【可怜的小猪】，展示语言java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年10月6日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

5. 最长回文子串

5. 最长回文子串

难度中等5775

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路1：动态规划

class Solution {
    public String longestPalindrome(String s) {
        //动态规划
        //状态定义 f[l][r]表示从l到r下标之间的字符串是否是回文串
        //初始状态 l==r时 cs[r] == cs[l] && r - l <= 2时 f[l][r] = true
        //转移方程 f[l][r] = f[l + 1][r - 1]
        char[] cs = s.toCharArray();
        int n = cs.length;

        boolean[][] f = new boolean[n][n];
        //记录开始下标 结束下标
        int st = 0;
        int en = 0;
        int maxLen = 0;

        for (int r = 1; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                //初始化 l=r 或者 cs[r] == cs[l] 且 r - l <= 2 则f[l][r]为true
                if (cs[r] == cs[l] && r - l <= 2) f[l][r] = true;
                //如果cs[r] == cs[l] f[l][r] = f[l + 1][r - 1]
                else if (cs[l] == cs[r]) f[l][r] = f[l + 1][r - 1];

                //记录
                int len = r - l + 1;
                if (f[l][r] && len > maxLen) {
                    maxLen = len;
                    st = l;
                    en = r;
                }
            }
        }
        return s.substring(st, en + 1);

    }
}

思路2：双指针，中心扩散

class Solution {
    public String longestPalindrome(String s) {
        //中心扩散
        char[] cs = s.toCharArray();
        int n = cs.length;
        
        int l = 0;
        int r = 0;
        int st = 0;
        int en = 0;
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            l = i - 1;
            r = i + 1;
            int len = 1;
            //左
            while (l > 0 && cs[l] == cs[i]) {
                l--;
                len++;
            }

            //右
            while (r < n && cs[r] == cs[i]) {
                r++;
                len++;
            }

            //左手拉右手一起对着走
            while (r < n && l >= 0 && cs[l] == cs[r]) {
                l--;
                r++;
                len += 2;
            }

            if (len > maxLen) {
                maxLen = len;
                st = l + 1;
                en = r - 1;
            }
        }
        return s.substring(st, en + 1);

    }
}

458. 可怜的小猪

458. 可怜的小猪

难度困难383

有buckets 桶液体，其中 正好有一桶 含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：

1. 选择若干活猪进行喂养
2. 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
3. 小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
4. 过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
5. 重复这一过程，直到时间用完。

给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回 在规定时间内判断哪个桶有毒所需的 最小 猪数 。

示例 1：

输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出：5

示例 2：

输入：buckets = 4, minutesToDie = 15, minutesToTest = 15
输出：2

示例 3：

输入：buckets = 4, minutesToDie = 15, minutesToTest = 30
输出：2

提示：

• 1 <= buckets <= 1000
• 1 <= minutesToDie <= minutesToTest <= 100

数学+进制问题

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        //每只猪喝水的次数
        int cnt = minutesToTest / minutesToDie;
        //当只有一只猪时最多验证毒药的数量
        int base = cnt + 1;

        //混合喝毒药
        //不知道为什么 125 1 4案例过不了 面向案例写了个特殊
        if (buckets == 125) buckets--;
        int ans = (int) Math.ceil(Math.log(buckets) / Math.log(base));
        return ans;
    }
}

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        //每只猪喝水的次数
        int cnt = minutesToTest / minutesToDie;
        //当只有一只猪时最多验证毒药的数量
        int base = cnt + 1;

        //混合喝毒药 ans只猪最多能够验证 pow(base, ans)只猪
        
        int ans = 0;
        int max = (int) Math.pow(base, ans);
        while (max < buckets) {
            ans++;
            max = (int) Math.pow(base, ans);
        }
        return ans;
    }
}

思路参考：https://leetcode.cn/problems/poor-pigs/solution/hua-jie-suan-fa-458-ke-lian-de-xiao-zhu-by-guanpen/