题解 | #牛群的回文队列#

牛群的回文队列

https://www.nowcoder.com/practice/fdd01d1c1ea047f0b2206a477ccf8a90?tpId=363&tqId=10609105&ru=/exam/oj&qru=/ta/super-company23Year/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D363

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
     public String longest_palindrome_cow_queue(String s) {
        int n = s.length();
        // 用于记录从dp [i...j]是否为回文子串
        boolean [][] dp = new boolean[n][n];
        // 最大子串长度
        int maxLen = 0;
        // 最大子串的起始位置
        int begin = 0;
        // 单个字符一定是回文,直接返回
        if(s.length()<2){
            return s;
        }
        // dp初始化,长度为1的一定是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        for (int  left= 2; left <= n; left++) {
            for (int i = 0; i < n; i++) {
                // 右边界在哪个位置
                int j = left+i-1;
                // 如果右边界大于n长度
                if(j>=n){
                    break;
                }
                // 判断字符是否相同 不相等设置false
                if(s.charAt(i)!=s.charAt(j)){
                    dp[i][j] = false;
                }else {
                    // 如果字符相同并且长度小于3,那么必定是true
                    if(j-i<3){
                        dp[i][j] = true;
                    }else {
                        // 如果大于等于3,需要判断其他值
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j]&&j-i+1>maxLen){
                    maxLen= j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxLen);
    }
}

本题知识点分析:

1.动态规划

2.数学模拟

3.API函数

4.数组遍历

本题解题思路分析:

1.先进行一些特殊判断,比如长度为1的情况,直接返回s

2.dp数组代表从i 到 j 是否是回文子串

3.dp 初始化 每一个长度为1的字符都是true

4.长度可以从2开始到n

5.左边界从0开始,右边界可以通过计算 left+i-1得到

6.如果右边界大于n长度 直接break;

7.判断字符是否相同 不相等设置false

8.如果字符相同并且长度小于3,那么必定是true

9.如果大于等于3,需要判断其他值

10.dp为真并且长度大于maxLen,更新最大长度,记录此时左边界索引

本题使用编程语言: Java

时间复杂度:O(n2) 暴力是O(n3) 有O(n)的解法,需要Manacher 算法 ,这是数学,一般面试不会要求那么细

如果你觉得本篇文章对你有帮助的话,可以点个赞支持一下,感谢~

全部评论

相关推荐

(黑话警告⚠️:hc=岗位数量,&nbsp;mt=导师,&nbsp;ld=直属领导,&nbsp;cr=代码审查)25年1月,我加入了字节某前端团队,并期望能在这里待到秋招并尝试转正。然而,就在上周,ld&nbsp;找我1v1,告诉我,我的能力和团队预期不太匹配,并和我劝退。晴天霹雳吗?肯定是有的。那一刻,脑子里嗡嗡作响,各种情绪翻涌。但冷静下来想想,这几个月,自己在能掌控的范围内,确实有不少地方做得不尽如人意。所以,我想把这段不算成功的经历复盘一下,希望能给同样在努力转正的你提个醒,避开我踩过的坑。一、ld&nbsp;的要求要注意刚进组时,ld就和我聊过转正的事。我当时发问:“咱们这儿有hc&nbsp;吗?”&nbsp;ld没直接回答,只是说:“看能力,能力到了...
牛客上的彭于晏:过来人告诉你,入职后要做的第一件事儿不是说主动找活儿做,你要先学会融入团队,摸清ld的性格,投其所好。然后才是展示你的能力,能力上可以说技术或者业务,以业务能力为主,技术能力为辅。优先保证自己对业务需求的开发保证质量效率,然后再谈技术的问题,不要你觉得啥啥啥不行就想着整体优化了(发现校招生最喜欢干这事儿),我工作快5年了发现搞这种的最后都没啥好的结果,产出没有还引入新的bug,校招或者实习的水平看到的问题别人看不到嘛?为什么别人不去搞?浪费时间还没收益的事儿不要去做,技术上的能力体现在对于一个新需求,在不符合现在业务发展的架构设计上,你能拿出好的技术方案同时能考虑到后续业务发展逐渐将技术架构引入合理的架构,这是一个漫长的过程而不是一次性的
点赞 评论 收藏
分享
Wy_m:只要不是能叫的上名的公司 去实习没有任何意义 不如好好沉淀自己
点赞 评论 收藏
分享
AI牛可乐:哇塞,恭喜恭喜!48万的年薪,真是让人羡慕呀!看来你找到了一个超棒的工作,可以享受不卷的生活啦!🎉有没有什么求职秘诀想要分享给小牛牛呢?或者,想不想知道我是谁呢?😉(点击我的头像,我们可以私信聊聊哦~)
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务