首页 > 试题广场 >

在字符串中找出连续最长的数字串

[编程题]在字符串中找出连续最长的数字串
  • 热度指数：151230 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的由数字和小写字母混合构成的字符串 s，找到其中最长的数字子串。如果由多个相同长度的数字子串，则需要全部输出，具体输出的格式请参考输出描述。

\hspace{15pt}子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入描述:
\hspace{15pt}输入一个长度为 1 \leqq {\rm len}(s) \leqq 200、由数字和小写字母混合构成的字符串 s。保证至少存在一个数字子串。


输出描述:
\hspace{15pt}记最长的数字子串长度为 l，有 m 个长度为 l 的数字子串。在一行上先首尾相连的输出 m 个长度为 l 的数字子串（不使用空格分割），随后输出一个逗号，再输出 l。
示例1

输入

abcd12345ed125ss123058789

输出

123058789,9
示例2

输入

11a22b33c

输出

112233,2

说明

\hspace{15pt}在这个样例中，数字子串 \texttt{ 长度均为 2，都是最长的数字子串。

备注:
\hspace{15pt}本题数据已规范为单组询问（2025/01/15）。
算法知识视频讲解
添加回答
Java
牛客916838684号头像 牛客916838684号
做出来了 
import java.util.HashSet;
import java.util.Scanner;
import java.util.TreeSet;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();

        str = str.replaceAll("[a-z]", "*");
        str = str.replaceAll("\\*{1,}", "*");

        String[] str0 = str.split("\\*");


        int maxlen = 0;

        for (int i = 0; i < str0.length; i++) {
            maxlen = Math.max(maxlen, str0[i].length());
        }

        for (int i = 0; i < str0.length; i++) {
            if(str0[i].length() == maxlen){
                System.out.print(str0[i]);
            }
        }
        System.out.println(","+maxlen);

    }
}

发表于 2025-09-30 10:56:39 回复(0)
Java
牛客281381469号头像 牛客281381469号 
java实现：先用str来接收控制台过来的字符串，并转为char[] chars（这样运行速率比用String快），用max保存过程中最大的连续数字串长度。
当遇到数字时，count计数加一，用dp[i]记录该索引值的count值，期间总是更新count的最大值max；当遇到字符时，count归零，等再次遇到数字字符时，count重新从0开始计数。
依次遍历结束后，遍历dp数组，当dp[i] == max时，说明找到目标子串，输出即可。
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int[] dp = new int[str.length()];
            int max = 0, nowcount = 0;
            char[] chars = str.toCharArray();
            for (int i = 0; i < chars.length; i++){
                char c = chars[i];
                if (c >= '0' && c <= '9'){
                    nowcount++;
                    dp[i] = nowcount;
                    max = Math.max(nowcount, max);
                }else{
                    nowcount = 0;
                    dp[i] = nowcount;
                }
            }
            for (int i = 0; i < dp.length; i++){
                if (dp[i] == max){
                    String res = str.substring(i - max + 1, i + 1);
                    System.out.print(res);
                }
            }
            System.out.println("," + max);
        }
    }
}

发表于 2025-07-18 09:56:31 回复(0)
Java
牛客430757235号头像 牛客430757235号
/*
List<String> q = new ArrayList<>();
        StringBuilder w = new StringBuilder();
联合取出数字  
*/
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String s = in.nextLine();
        List<String> q = new ArrayList<>();
        StringBuilder w = new StringBuilder();

        for (int i = 0; i < s.length() + 1; i++) {
            char a = 'a';
            if (i >= s.length()) {
                a = 'a';
            } else {
                a = s.charAt(i);
            }
            if (Character.isDigit(a)) {
                w.append(a);
            } else {
                if (w.length() > 0) {
                    q.add(w.toString());
                    w.setLength(0);
                }
            }
        }
        /*for (int i = 0; i < q.size(); i++) {
            System.out.print(q.get(i) + " ");
        }
        //打印q list
        */
        int max = 0;
        for(String i:q){
            max = Math.max(max,i.length());
        }
        w.setLength(0);
        for(String i:q){
            if(i.length()==max){
                w.append(i);
            }
        }
        System.out.print(w+","+max);
    }
}

发表于 2025-03-20 11:46:15 回复(0)
Java
聪明的牛油果在刷题头像 聪明的牛油果在刷题 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine();

            int[][] res = new int[str.length()][str.length()];
            int maxLen = process(str.toCharArray(), 0, str.length() - 1, res);
            String s = "";

            for (int i = 0, j = maxLen-1 ; j < str.length() ; i++,j++) {
                if(res[i][j] == maxLen){
                    s += str.substring(i , i+maxLen);
                }
            }
            System.out.println(s + ',' + maxLen);
        }
    }


    public static int process(char[] str, int left, int right, int[][] res) {
        if (res[left][right] != 0) {
            return res[left][right];
        }
        if (left == right) {
            res[left][right] = isNumber(str[left]) ? 1 : 0;
        } else {
            int p1 = process(str, left + 1, right, res);
            int p2 = process(str, left, right - 1, res);
            if (p1 == right - left) {
                p1 += isNumber(str[left]) ? 1 : 0;
            }
            if (p2 == right - left) {
                p2 += isNumber(str[right]) ? 1 : 0;
            }
            res[left][right] = Math.max(p1, p2);
        }

        return res[left][right];
    }

    public static boolean isNumber(char c) {
        return c >= '0' && c <= '9';
    }
}

发表于 2025-02-20 12:07:45 回复(0)
Java
Sen🍓🍀头像 Sen🍓🍀 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();

        List<String> list = new ArrayList<>(); // list存当前最长的数字子串
        int max = 0, i = 0, j;

        // 双指针i,j 找数字子串，遍历一遍即可
        while (i < s.length()) {
            while (i < s.length() && !Character.isDigit(s.charAt(i))) i++;  // 数字子串 头
            j = i;
            while (j < s.length() && Character.isDigit(s.charAt(j))) j++;   // 数字子串 尾
            if (j - i >= max) {
                if (j - i > max)
                    list.clear(); // 更大数字子串，需先清空list，再加入list
                max = j - i;
                list.add(s.substring(i, j));
            }
            i = j;
        }

        list.forEach(System.out::print);
        System.out.print("," + max);
    }
}

发表于 2025-01-29 09:20:22 回复(0)
Java
牛客400624899号头像 牛客400624899号 
import java.util.*;
import java.util.regex.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String temp = in.nextLine();
            Pattern pattern = Pattern.compile("([0-9]{1,})");
            Matcher matcher = pattern.matcher(temp);
            int length = 0;
            StringBuffer sb = new StringBuffer();
            while (matcher.find()) {
                if (matcher.group(1) == null) return;
                String current = matcher.group(1);
                if (current.length() > length) {
                    length = current.length();
                    sb.delete(0, sb.length());
                    sb.append(current);
                } else if (current.length() == length) {
                    length = current.length();
                    sb.append(current);
                }
            }
            System.out.println(sb.toString() + "," + length);
        }
    }
}

发表于 2025-01-12 18:35:00 回复(0)
Java
牛笔头像 牛笔 
//一维动态规划解法
import java.util.*;
public class Main{
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            String line = sc.nextLine();
            char [] chars = line.toCharArray();
            //dp[i]表示以i结尾时最长数字子串的长度
            int[] dp = new int[chars.length];

            //第一个字符是否为数字
            if(Character.isDigit(chars[0])) {
                dp[0] = 1;
            }else {
                dp[0]=0;
            }

            int max =0;
            //填表
            for(int i = 1; i < chars.length; i++){
                if(Character.isDigit(chars[i])){
                        dp[i]=1;
                        if(dp[i-1]>0)
                        dp[i] += dp[i-1];
                }else{
                dp[i]=0;
                }
                if(max<dp[i])max=dp[i];
            }

            //输出
            for (int i = 0; i < chars.length; i++) {
                if(dp[i]==max) {
                    System.out.print(line.substring(i-max+1,i+1));

                }
            }
            System.out.print(",");
            System.out.print(max);
            System.out.println();
        }
    }
}

发表于 2024-09-14 19:45:04 回复(0)
Java
想去广东逛gai的里根说等下个版本吧头像 想去广东逛gai的里根说等下个版本吧 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            Map<Integer, String> map = new HashMap<>();
            int left = 0, right = left + 1;
            while (right <= str.length()) {
                String substr = str.substring(left, right);
                boolean isAllDigit = false;
                for (char c : substr.toCharArray()) {
                    if (!Character.isDigit(c)) {
                        left += 1;
                        right = left + 1;
                        break;
                    }
                    isAllDigit = true;
                }
                if (isAllDigit) {
                    int len = right - left;
                    map.put(len, map.getOrDefault(len, "") + substr);
                    right++;
                }
            }
            int maxKey = 0;
            for (Map.Entry<Integer, String> entry : map.entrySet()) {
                Integer key = entry.getKey();
                maxKey = Math.max(maxKey, key);
            }
            System.out.println(map.get(maxKey) + "," + maxKey);
        }
    }
}

发表于 2024-08-22 23:46:31 回复(0)
Java
明明就是你头像 明明就是你
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            // 接收输入的字符串
            String str = in.nextLine();
            // 加上一个字母防止不统计最后的数字串
            char[] chs = (str+"a").toCharArray();
            // 最大长度
            int maxLength = 0;
            // 临时字符串中数字串的大小
            int tempSize = 0;
            // 创建map存放结果，key为数字串的长度， value是具体字符串
            Map<Integer, String> map = new HashMap<>();
            for(int i = 0; i< chs.length; i++) {
                if(Character.isDigit(chs[i])) {
                    // 如果是数字，直接tempSize+1即可
                    tempSize ++;
                } else {
                    // 不是数字，需要判断tempSize是否大于等于最大数字串长度
                    if(maxLength == tempSize) {
                        // 相等的话，需要将i-tempSize 到i的数字串添加进结果中
                        map.put(tempSize, map.getOrDefault(tempSize, "") + str.substring(i-tempSize, i));
                    } else if(maxLength < tempSize) {
                        // tempSize大于maxLength,清空map，同时把该数字串加入结果map中
                        map.clear();
                        map.put(tempSize, str.substring(i-tempSize, i));
                        maxLength = tempSize;
                    }
                    // 不是字符串，需要将临时变量置为0
                    tempSize = 0;
                }
            }
            // 最后直接输出结果
            System.out.println(map.getOrDefault(maxLength, "") + "," + maxLength);
        }
    }
}
发表于 2024-05-22 10:52:58 回复(0)
Java
王小二_头像 王小二_

import java.util.*;

/**
 * @Classname Main
 * @Description TODO
 * @Date 2024/4/17 16:17
 * @Created by admin
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String next = sc.next();
            int length = next.length();
            int[][] dp = new int[length][length];
            char[] arr = next.toCharArray();
            for (int i = 0; i < length; i++) {
                if (arr[i] >= '0' && arr[i] <= '9') {
                    dp[i][i] = 1;
                }
            }
            // 先进行end循环
            int max = 0;
            int start = 0;
            int end = 0;
            for (int i = 1; i < length; i++) {
                if (arr[i] >= '0' && arr[i] <= '9') {
                    for (int j = i - 1; j >= 0; j--) {
                        if (arr[j] >= '0' && arr[j] <= '9') {
                            dp[j][i] = dp[j + 1][i] + 1;
                            if (max < dp[j][i]) {
                                max = dp[j][i];
                                start = j;
                                end = i;
                            }
                        } else {
                            break;
                        }
                    }
                }
            }
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < length; i++) {
                if (arr[i] >= '0' && arr[i] <= '9') {
                    for (int j = i; j < length; j++) {
                        if (arr[j] >= '0' && arr[j] <= '9') {
                            if (dp[i][j] == max){
                                map.put(i, j);
                            }
                        }
                    }
                }
            }
            StringBuilder sb = new StringBuilder();
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                sb.append(next, entry.getKey(), entry.getValue() + 1);
            }
            System.out.println(sb + "," + max);
        }
    }
}

发表于 2024-04-20 13:01:14 回复(0)
Java
欢哥你是大神头像 欢哥你是大神 
import java.util.Scanner;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Iterator;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            System.out.println(getMaxString(str).getKey() + "," + getMaxString(
                                   str).getValue());
        }
    }
    public static Map.Entry<String, Integer> getMaxString(String str1) {
        StringBuilder sb = new StringBuilder("");
        LinkedHashMap <String, Integer> hm = new LinkedHashMap();
        for (int i = 0; i < str1.length();) {
            char c = str1.charAt(i);
            if (c >= '0' && c <= '9') {
                sb.append(c);
                i++;
                if (i < str1.length()) {
                    char c2 = str1.charAt(i);
                    if (c2 >= '0' && c2 <= '9') {
                        continue;
                    } else {
                        hm.put(sb.toString(), sb.length());
                        sb.replace(0, sb.length(), "");

                    }
                } else if (i == str1.length()) {
                    char c2 = str1.charAt(i - 1);
                    if (c2 >= '0' && c2 <= '9') {
                        hm.put(sb.toString(), sb.length());
                    } else {
                        hm.put(String.valueOf(str1.charAt(i)), 1);
                    }
                }
            } else {
                i++;
            }
        }
        int max = 0;
        //求得长度最大值
        for (Map.Entry<String, Integer> entry : hm.entrySet()) {
            if (entry.getValue() > max) {
                max = entry.getValue();
            }
        }
        sb.replace(0, sb.length(), "");
        //迭代器遍历删除小于最大值的元素
        Iterator<Map.Entry<String, Integer>> it = hm.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, Integer> entry = it.next();
            if (entry.getValue() < max) {
                it.remove();
            } else {
                //相同长度的字符串拼接在一起
                sb.append(entry.getKey());
            }
        }
        hm.clear();
        hm.put(sb.toString(), max);
        for (Map.Entry<String, Integer> entry : hm.entrySet()) {
            return entry;
        }
        return null;
    }
}

发表于 2024-03-28 17:30:48 回复(0)
Java
香辣素毛肚头像 香辣素毛肚 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.nextLine();
            String[] sp = s.split("[^\\d]+");
            int maxLength = 0;
            String result = "";
            for (int i = 0; i < sp.length; i++) {
                if (maxLength < sp[i].length()) {
                    result = sp[i];
                    maxLength = sp[i].length();

                } else if (maxLength == sp[i].length()) {
                    result = result + sp[i];
                }
            }

            System.out.println(result + "," + maxLength);
        }
    }
}
核心就是正则表达式，识别分割符是非数字
发表于 2024-03-28 14:40:28 回复(0)
Java
Kili_66头像 Kili_66 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextLine()){
            String s = in.nextLine();
            List<String> list = new ArrayList();
            int max = 0;
            int[] dp = new int[s.length()+1];
            for(int i = 1; i <= s.length(); i++){
                if(Character.isDigit(s.charAt(i-1))){
                    dp[i] = dp[i-1] +1;
                    if(dp[i] == max){
                        list.add(s.substring(i-max, i));
                    }else if(dp[i] > max){
                        max = dp[i];
                        list.clear();
                        list.add(s.substring(i-max, i));
                    }
                }
            }
            list.forEach(k->System.out.print(k));
            System.out.println(","+ max);
        }
    }
}

发表于 2023-11-28 16:14:24 回复(0)
Java
呜哈哈_头像 呜哈哈_ 
import java.lang.Math;
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String inputStr = in.nextLine();
            String[] strSplit = inputStr.replaceAll("[^0-9]", ",").split(",");

            // 计算最长长度
            int maxLeng = 0;
            for (String a : strSplit) {
                maxLeng = Math.max(maxLeng, a.length());
            }
            for (String a : strSplit) {
                if (a.length() == maxLeng) {
                    System.out.print(a);
                }
            }
            System.out.print("," + maxLeng + "\n");

        }
    }
}

发表于 2023-10-19 21:57:35 回复(0)
Java
GCID头像 GCID 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNext()) { // 注意 while 处理多个 case
            char[] str=in.nextLine().toCharArray();
            int[] DP=new int[str.length+1];
            List<Integer> list=new ArrayList<>();
            int max=0;
            for(int i=1;i<=str.length;i++){
                if(str[i-1]>='0'&&str[i-1]<='9'){
                    DP[i]=DP[i-1]+1;
                    if(DP[i]>max){
                        if(!list.isEmpty()){
                            list.clear();
                            list.add(i-1);
                            max=DP[i];
                        }else{
                            list.add(i-1);
                            max=DP[i];
                        }
                    }else if(DP[i]==max){
                        list.add(i-1);
                    }
                }
            }
            for(int i=0;i<list.size();i++){
                int index=list.get(i)-max+1;
                for(int j=0;j<max;j++){
                    System.out.print(str[index+j]);
                }
            }
            System.out.println(","+max);
        }
    }
}

发表于 2023-09-09 21:05:05 回复(0)
Java
才华横溢的小学生很坚定头像 才华横溢的小学生很坚定 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while ((str = br.readLine()) != null) {
            int k = 0, count = 0, startIndex = 0, currentIndex = 0;
            StringBuilder sb = new StringBuilder();
            int length = str.length();
            for (int i = 0; i < length; i++) {
                char ch = str.charAt(i);
                if ('0' <= ch && ch <= '9') {
                    count++;
                    if (k < count) {
                        k = count;
                        currentIndex = startIndex;
                        // 清空 StringBuilder
                        sb.setLength(0);
                    } else if (k == count) {
                        sb.append(str.substring(currentIndex, k + currentIndex));
                        currentIndex = startIndex;
                    }
                } else {
                    count = 0;
                    //当前分支是非数字，需要+1
                    startIndex = i + 1;
                }
            }
            System.out.println(sb.append(str.substring(currentIndex,
                                         k + currentIndex) + "," + k));
        }
    }
}


发表于 2023-07-18 14:56:36 回复(0)
Java
牛客114488943号头像 牛客114488943号 
import java.util.*;
import java.util.regex.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextLine()) {
            String input = in.nextLine();

            Pattern p = Pattern.compile("[0-9]+");
            Matcher m = p.matcher(input);

            int length = 0;
            String numStr = "";
            while (m.find()) {
                String nums = m.group();
                if (nums.length() > length) {
                    length = nums.length();
                    numStr = nums;
                } else if (nums.length() == length) {
                    numStr += nums;
                }
            }
            System.out.println(numStr + "," + length);
        }
    }
}

发表于 2023-07-01 02:00:34 回复(0)
提交观点

问题信息

字符串 模拟
难度：
107条回答 76201浏览

热门推荐

通过挑战的用户

查看代码

相关试题

在字符串中找出连续最长的数字串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号