基于Java解决华为机试实现密码截取 

目录
  • 1.简述
    • 示例1
    • 示例2
    • 示例3
  • 2.代码实现

1.简述

描述:

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

数据范围：字符串长度满足1 \le n \le 2500 \1≤n≤2500 

输入描述：

输入一个字符串（字符串的长度不超过2500）

输出描述：

返回有效密码串的最大长度

示例1

输入：

ABBA

输出：

4

示例2

输入：

ABBBA

输出：

5

示例3

输入：

12HHHHA

复制输出：

4

2.代码实现

​解题思路：

最长回文子串的中心扩散法，遍历每个字符作为中间位，进行左右比较

算法流程：

从右到左，对每个字符进行遍历处理，并且每个字符要处理两次，因为回文子串有两种情况：

ABA型：只需要从当前字符向两边扩散，比较左右字符是否相等，找出以当前字符为中心的最长回文子串长度

ABBA型：只需要从当前字符和下一个字符向两边扩散，比较左右字符是否相等，找出以当前字符和下一个字符为中心的最长回文子串长度

最后比对两种类型的长度，取自较长的长度

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(solution(s));
    }
    
    private static int solution(String s) {
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            // ABA型
            int len1 = longest(s, i, i);
            // ABBA型
            int len2 = longest(s, i, i + 1);
            res = Math.max(res, len1 > len2 ? len1 : len2);
        }
        return res;
    }
    
    private static int longest(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

方法二：动态规划

解题思路：

对于最值问题，往往可以采用动态规划思想降低时间复杂度和状态压缩，采用空间换时间的思想

算法流程：

确定状态：对比的两个字符索引起始和终止索引位置

定义 dp 数组：字符串s的 i 到 j 索引位置的字符组成的子串是否为回文子串

状态转移: 如果左右两字符相等, 同时[l+1...r-1]范围内的字符是回文子串, 则[l...r] 也是回文子串

状态转移的同时，不断更新对比的子串长度，最终确定最长回文子串的长度

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = "";
        while ((s = br.readLine()) != null) {
            System.out.println(validLen(s));
        }
        br.close();
    }

    public static int validLen(String s) {
        int len = s.length();
        // 状态：对比的两个字符索引起始和终止索引位置
        // 定义: 字符串s的i到j字符组成的子串是否为回文子串
        boolean[][] dp = new boolean[len][len];
        int res = 0;
        // base case
        for(int i = 0; i < len - 1; i++) {
            dp[i][i] = true;
        }

        for(int r = 1; r < len; r++) {
            for(int l = 0; l < r; l++) {
                // 状态转移：如果左右两字符相等,同时[l+1...r-1]范围内的字符是回文子串
                // 则 [l...r] 也是回文子串
                if(s.charAt(l) == s.charAt(r) && (r-l <= 2 || dp[l+1][r-1])) {
                    dp[l][r] = true;
                    // 不断更新最大长度
                    res = Math.max(res, r - l + 1);
                } 
            }
        }
        return res;
    }
}

到此这篇关于基于Java解决华为机试实现密码截取 的文章就介绍到这了,更多相关Java密码截取 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  •  基于Java解决华为机试之字符串合并处理实操

    目录 1.简述 示例1 示例2 示例3 1.简述 描述: 按照指定规则对输入的字符串进行处理. 详细描述: 第一步:将输入的两个字符串str1和str2进行前后合并.如给定字符串 "dec" 和字符串 "fab" , 合并后生成的字符串为 "decfab" 第二步:对合并后的字符串进行排序,要求为:下标为奇数的字符和下标为偶数的字符分别从小到大排序.这里的下标的意思是字符在字符串中的位置.注意排序后在新串中仍需要保持原来的奇偶性.例如刚刚得到的字

  • Java实现IP地址到二进制的转换

    Java编程实现十进制IP地址到二进制IP地址的转换. 如:192.168.1.100,转换后:11000000.10101000.00000001.01100100 要求: 1.定义自定义异常类InvalidIP(检查型的),代表IP地址非法---如:点分十进制IP段数不是4:各段数值不是0~255范围 2.定义公有静态方法convertIP实现转换,点分十进制IP地址为参数,转换后的二进制IP为返回值,在方法内检查参数IP地址的合法性,如非法,请抛出自定义异常InvalidIP public

  • Java编程IP地址和数字相互转换代码示例

    最近才知道,将ip地址转换成十进制.八进制.十六进制同样可以访问网站. IP转为数字(第二种算法.用左移.按位或实现.效率更高.): public long ipToLong(String ipAddress) { long result = 0; String[] ipAddressInArray = ipAddress.split("\\."); for (int i = 3; i >= 0; i--) { long ip = Long.parseLong(ipAddress

  • java实现IP地址转换

    一个IP地址是用四个字节(每个字节8位)的二进制码组成.请将32位二进制码表示的IP地址转换为十进制格式表示的IP地址输出. 输入数据要求: 必须为二进制数,即只能输入0或者1 长度必须是32位 违背以上规则程序直接输出Wrong Format 输入格式: 在一行中给出32位二进制字符串. 输出格式: 在一行中输出十进制格式的IP地址,其由4个十进制数组成(分别对应4个8位的二进制数),中间用"."分隔开. 输入样例: 在这里给出一组输入.例如: 1100011010100100001

  • 使用Java代码将IP地址转换为int类型的方法

    基本知识点    IP --> 整数: 把IP地址转化为字节数组 通过左移位(<<).与(&).或(|)这些操作转为int 整数 --> IP: 将整数值进行右移位操作(>>>),右移24位,再进行与操作符(&)0xFF,得到的数字即为第一段IP. 将整数值进行右移位操作(>>>),右移16位,再进行与操作符(&)0xFF,得到的数字即为第二段IP. 将整数值进行右移位操作(>>>),右移8位,再进行与操

  • java实现ip地址与十进制数相互转换

    先看实例 代码如下 复制代码 代码如下: classip { privatestaticlongiptolong(stringstrip) //将127.0.0.1形式的ip地址转换成10进制整数,这里没有进行任何错误处理 { intj=0; inti=0; long[]ip=newlong[4]; intposition1=strip.indexof("."); intposition2=strip.indexof(".",position1+1); intpos

  • 基于Java解决华为机试之字符串加解密 

    目录 1.简述 2.示例1 2.代码实现 1.简述 描述: 1.对输入的字符串进行加解密,并输出. 2.加密方法为: 当内容是英文字母时则用该英文字母的后一个字母替换,同时字母变换大小写,如字母a时则替换为B:字母Z时则替换为a: 当内容是数字时则把该数字加1,如0替换1,1替换2,9替换0: 其他字符不做变化. 3.解密方法为加密的逆过程. 本题含有多组样例输入. 数据范围:输入的两个字符串长度满足1 \le n \le 1000 \1≤n≤1000  ,保证输入的字符串都是大小写字母或者数字

  • Java实现ip地址和int数字的相互转换

    Java版本的 ip地址和int数字的相互转换 对于ipv4的地址来说,如果用字符串的形式存储的话,其占用字节就比较大,比如对于IPv4地址0.0.0.0的字符串,就需要7个字节,IPv4为255.255.255.255 的字符串,需要15个字节,也就是说存储一个ip需要占用7~15个字节. 那么有没有更节省空间的存储方式呢?答案是有. 方案1: 直接把字符串中的'.'去掉,不就变成一个数字了嘛,比如 "255.255.255.255" 变成 255255255255,然而我们知道in

  • 基于Java解决华为机试实现整数与IP地址间的转换 

    目录 1.简述 示例1 2.代码实现 1.简述 描述: 原理:ip地址的每段可以看成是一个0-255的整数,把每段拆分成一个二进制形式组合起来,然后把这个二进制数转变成 一个长整数. 举例:一个ip地址为10.0.3.193 每段数字                相对应的二进制数 10                          00001010 0                            00000000 3                            0000

  • 基于Java解决华为机试实现密码截取 

    目录 1.简述 示例1 示例2 示例3 2.代码实现 1.简述 描述: Catcher是MCA国的情报员,他工作时发现敌国会用一些对称的密码进行通信,比如像这些ABBA,ABA,A,123321,但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解.比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214 .因为截获的串太长了,而且存在多种可能的情况(abaaab可看作是aba,或baaab的加密形式),Cathcer的工作量实在是太大了

  • Java基于递归解决全排列问题算法示例

    本文实例讲述了Java基于递归解决全排列问题算法.分享给大家供大家参考,具体如下: 排列问题 设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}.集合x中元素的全排列记为Perm(X).(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳如下: 当n=1时,Perm(R)=(r),其中r是集合中唯一的元素: 当n>1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),(r3)Perm(R3)....(

  • 基于界面适配华为手机的虚拟按键的解决方法

    基于界面适配华为手机的虚拟按键的解决方法

    一.概述 在项目中,测试发现在一些华为手机的屏幕适配上出现了问题,主要是因为华为Mate等一些系列的手机有一个虚拟按键的设计.当这些虚拟按键由用户手势滑出,或默认显示的话,就会遮挡我们本身的应用布局.比如欢迎界面过后是四个Fragment,那么底部的四个tab就会被虚拟的导航栏遮住,非常难看. 当然,欢迎页的图片适配也同样会出现问题. Google后得出第一个问题的解决方案.第二个图片的问题则用自己摸索的方式解决,当然也非常简单. 二.布局由于虚拟按键导致导航栏顶上去的解决方法 在我们的项目中加

  • 基于java时区转换夏令时的问题及解决方法

    一.准备知识 1.America/New_York的夏令时时间如下: 包左不包右 2016-3-13, 02:00:00到2016-11-6, 02:00:00 2017-3-12, 02:00:00到2017-11-5, 02:00:00 2.三字母时区 ID 为了与 JDK 1.1.x 兼容,一些三字母时区 ID(比如 "PST"."CTT"."AST")也受支持. 但是,它们的使用被废弃,这是因为相同的缩写经常用于多个时区 例如 CST:有

  • 基于Java编写串口通信工具

    基于Java编写串口通信工具

    最近一门课要求编写一个上位机串口通信工具,我基于Java编写了一个带有图形界面的简单串口通信工具,下面详述一下过程,供大家参考 ^_^ 一: 首先,你需要下载一个额外的支持Java串口通信操作的jar包,由于java.comm比较老了,而且不支持64位系统,这里推荐Rxtx这个jar包(32位/64位均支持). 官方下载地址:http://fizzed.com/oss/rxtx-for-java (注:可能需要FQ才能下载) 不能FQ的童鞋,可以在这里下载: http://xiazai.jb51

  • Java解压和压缩带密码的zip文件过程详解

    前言 JDK自带的ZIP操作接口(java.util.zip包,请参看文章末尾的博客链接)并不支持密码,甚至也不支持中文文件名. 为了解决ZIP压缩文件的密码问题,在网上搜索良久,终于找到了winzipaes开源项目. 该项目在google code下托管 ,仅支持AES压缩和解压zip文件( This library only supports Win-Zip's 256-Bit AES mode.).网站上下载的文件是源代码,最新版本为winzipaes_src_20120416.zip,本

  • 基于Java实现互联网实时聊天系统(附源码)

    目录 0. 前言 1.技术准备 2. 整体说明 2.1 设计思想 2.2 系统结构 2.3 项目结构 2.4 系统功能模块 2.5 系统界面 3. 核心编码 3.1 Netty服务器启动与关闭 4. 效果及操作演示 4.1 登录操作 4.2 聊天演示 5. 源码下载 0. 前言 决定以Netty为核心,以WebSocket为应用层通信协议做一个互联网聊天系统,整体而言就像微信网页版一样,但考虑到这个聊天系统的功能非常多,因此只打算实现核心的聊天功能,包括单发.群发.文件发送,然后把项目与Spri

随机推荐