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

解题思路

• 滑动窗口
• 动态规划

(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);
    }
  }
}