题解 | #在字符串中找出连续最长的数字串#

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

http://www.nowcoder.com/practice/2c81f88ecd5a4cc395b5308a99afbbec

解题思路

  • 滑动窗口
  • 动态规划

(1)滑动窗口

import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    while (scan.hasNextLine()) {
      String line = scan.nextLine();
      // 滑动窗口
      int left = 0;
      int right = 0;
      int max = 0;
      String ans = "";
      int len = line.length() - 1;
      while (right <= len) {
        // 什么是时候需要移动left左窗口
        if (!Character.isDigit(line.charAt(right)) || right == len) {
          String sub = "";
          if (right < len) {
            sub = line.substring(left, right);
            if ("".equals(ans) || max == (right - left)) {
              ans += sub;
            } else if (max < (right - left)) {
              ans = "";
              ans = sub;
            }
            max = Math.max(max, right - left);
          } else {
            sub = line.substring(left, right + 1);
            if ("".equals(ans) || max == (right - left + 1)) {
              ans += sub;
            } else if (max < (right - left + 1)) {
              ans = "";
              ans = sub;
            }
            max = Math.max(max, right - left + 1);
          }
          left = right + 1;
        }
        right++; // 移动右窗口
      }
      ans += ","+max;
      System.out.println(ans);
    }
  }
}

(2)动态规划

import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    while (scan.hasNextLine()) {
      String line = scan.nextLine();
      // 滑动窗口
      int len = line.length();
      // 动态方程,dp[i]表示当前i位置最长的数字串长度
      int[] dp = new int[len];
      // 动态规划边界条件判断
      if (Character.isDigit(line.charAt(0))) {
        dp[0] = 1;
      }
      // 开始计算
      for (int i = 1; i < len; i++) {
        if (Character.isDigit(line.charAt(i))) {
          dp[i] = dp[i-1] + 1;
        } else {
          dp[i] = 0;
        }
      }
      // 找出最大长度
      int max = 0;
      for (int num : dp) {
        max = Math.max(max, num);
      }
      // 找出最大长度字符串
      String ans = "";
      for (int i = 0; i < len; i++) {
        if (max == dp[i]) {
          ans += line.substring(i - max + 1, i + 1);
        }
      }
      // 输出结果
      System.out.println(ans + "," + max);
    }
  }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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