JAVA朴素解法 简单dp 注意顺序

字符串运用-密码截取

http://www.nowcoder.com/questionTerminal/12e081cd10ee4794a2bd70c7d68f5507

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        String a=in.next();
        System.out.println(getString(a));
    }
    public static  int getString(String a){
        char[] chararr = a.toCharArray();
        int len=chararr.length;
        if(len<2) return len;
        int start=0;
        int end=0;
        int maxLen=0;
        boolean[][] dp=new boolean[len][len];
        /*这部分可不要
        for(int i=0;i<len;i++){
            dp[i][i]=true;
        }*/
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(chararr[i]==chararr[j]){
                    if(j-i<3) dp[i][j]=true;
                    else{
                        dp[i][j]=dp[i+1][j-1];
                    }
                    if(dp[i][j]){
                        if(j-i+1>maxLen){
                            maxLen=j-i+1;
                            start=i;
                            end=j;
                        }
                    }
                }
            }//for j end
        }//for i end

        return maxLen;
    }
}
全部评论
这个解法比其他解法更奇妙,dp[i][j]表示第i到第j位置的子串是否是回文子串,i递减,j递增,利用dp[i][j]=dp[i+1][j-1]动态规划来确定当前子串的dp[i][j]。
1 回复 分享
发布于 2023-02-01 10:13 广东

相关推荐

不愿透露姓名的神秘牛友
07-15 17:46
暑期就挂了,秋招还有机会吗
大聪明777:研发提前批,14号刚开的,官网上面的配图上有写。提前批没过的话,秋招还可以投,不过前面的笔试/面试记录会被保留,供秋招参考
26届校招投递进展
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
6
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务