(C卷,100分)- 在字符串中找出连续最长的数字串(含“+-”号)（Java & JS & Python）

题目描述

请在一个字符串中找出连续最长的数字串，并返回这个数字串。

如果存在长度相同的连续数字串，返回最后一个。

如果没有符合条件的字符串，返回空字符串””。

注意：

• 数字串可以由数字”0-9″、小数点”.”、正负号”±”组成，长度包括组成数字串的所有符号。
• “.”、“±”仅能出现一次，”.”的两边必须是数字，”±”仅能出现在开头且其后必须要有数字。
• 长度不定，可能含有空格。

输入描述

无

输出描述

无

用例

题目解析

本题我的思路是利用双指针。

定义两个指针变量L，R，其中L指向数字串的开头，R用于扫描。

首先，我们需要确定第一个数字串的开头位置，逻辑很简单，遍历输入字符串S的每一个字符c：

• 如果c是数字，则c字符所在位置可以作为第一个数字串的开头位置，否则继续查找下一个c
• 如果c是加减号，则还需要进一步检查这个加减号的后面是不是跟着数字，如果跟着数字，则可以作为第一个数字串的开头，否则继续查找下一个c

找到第一个数字串的开头后，即知道L位置后，我们可以初始化R = L+1，即R从L+1位置开始扫描，假设扫描到的字符是c，则存在以下情况：

• c是数字，则不会中断数字串，可以继续R++扫描
• c是点，则需要先判断，这个点是否是合法的数字串点（即点位置R前后都是数字）：

1. 如果点位置前后不都是数字，则说明，点位置 R 前面的内容无法复用到下一个数字串中，此时我们需要先将[L, R-1]范围的合法数字串记录下来，然后按照前面遍历S来找数字串开头位置的逻辑，来找下一个数字串开头位置
2. 如果点位置前后都是数字，则此时我们进一步判断，当前数字串，即[L, R-1]部分是否还有其他点，如果有，则一个数字串中不能包含两个点，此时我们需要先记录[L, R-1]范围内的合法数字串，假设第一个点位置是dotIdx，则下一个数字开头位置L = dotIdx + 1，这样才能保证下一个数字串最长，然后更新dotIdx = R，最后继续R++扫描

• c是加减号，此时会中断数字串，因此我们需要先记录[L, R-1]范围内的合法数字串，然后判断当前R位置的后面是否跟着数字，这将决定我们下一个数字的开头位置：

1. 如果R+1位置是数字，则下一个数字串的开头L=R，因为数字串可以以加减号开头，只要加减号后面跟着数字，之后R++继续扫描
2. 如果R+1位置不是数字，则我们应该按照前面遍历S来找数字串开头位置的逻辑，来找下一个数字串的开头位置。

• c是其他字符，则会中断数字串，此时我们应该记录[L, R-1]部分合法数字串，然后按照前面遍历S来找数字串开头位置的逻辑，来找下一个数字串的开头位置。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  console.log(getResult(line));
});

function getResult(s) {
  // 记录题解
  let ans = "";

  // 记录数字串中“.”的位置，-1表示数字串中没有点
  let dotIdx = -1;

  // l 指向数字串的开头
  l = findStartIdx(s, 0);

  // r 用于扫描数字串
  r = l + 1;
  while (r < s.length) {
    // 当前扫描的到的字符
    const c = s[r];

    if (isDigit(c)) {
      // c是数字，则继续扫描下一个
      r++;
    } else if (isSign(c)) {
      // c是加减号，则数字串扫描中断，我们需要先记录[l, r-1]范围的数字串
      ans = getAns(s, l, r, ans);

      if (isValidSign(r, s)) {
        // 由于加减号可以作为数字串开头，如果r位置的加减号是一个合法数字串开头加减号，则可以当成下一个数字串的开头
        l = r;
      } else {
        // 否则，从r+1开始继续找下一个数字的开头
        l = findStartIdx(s, r + 1);
      }

      // 新数字串的开头找到后，从l+1开始扫描
      r = l + 1;
      // 同时注意重置dotIdx记录
      dotIdx = -1;
    } else if (isDot(c)) {
      // 由于dot处理比较复杂，这里无论dot是否会中断数字串扫描，都先将[l, r-1]部分的数字串记录下来
      ans = getAns(s, l, r, ans);

      if (isValidDot(r, s)) {
        // 如果是合法数字串dot, 则判断当前数字串是否已存在”.“
        if (dotIdx != -1) {
          // 如果已存在".", 则当前数字串包含了两个"."，肯定不合法，此时需要舍弃第一个".", 即新数字串开头位置设置在第一个"."后面
          l = dotIdx + 1;
        }

        // 更新dotIdx为第二个"."的位置
        dotIdx = r;
        // r继续扫描下一个
        r++;
      } else {
        // 如果不是合法数字串dot，即该dot前后不都是数字，则新数字串不能包含进当前dot位置，新数字串开头需要从r+1开始找
        l = findStartIdx(s, r + 1);
        r = l + 1;
        dotIdx = -1;
      }
    } else {
      // c是其他字符, 则数字串被打断，此时需要先记录[l, r-1]范围的当前数字串， 然后重新寻找下一个数字串的开头
      ans = getAns(s, l, r, ans);
      l = findStartIdx(s, r + 1);
      r = l + 1;
      dotIdx = -1;
    }
  }

  return getAns(s, l, r, ans);
}

function isSign(c) {
  return c == "+" || c == "-";
}

function isDot(c) {
  return c == ".";
}

function isDigit(c) {
  return c >= "0" && c <= "9";
}

// ”.”的两边必须是数字
function isValidDot(dotIdx, s) {
  const preIdx = dotIdx - 1;
  const nxtIdx = dotIdx + 1;

  return (
    preIdx >= 0 && isDigit(s[preIdx]) && nxtIdx < s.length && isDigit(s[nxtIdx])
  );
}

// ”±”仅能出现在开头且其后必须要有数字
function isValidSign(signIdx, s) {
  const nxtIdx = signIdx + 1;
  return nxtIdx < s.length && isDigit(s[nxtIdx]);
}

// 记录数字串时，只保留最长的数字串
function getAns(s, l, r, ans) {
  // 如果存在长度相同的连续数字串，返回最后一个。 因此下面判断是>=
  return l < s.length && r - l >= ans.length ? s.slice(l, r) : ans;
}

// 从s字符串的start位置开始找数字串的开头字符，数字串的开头字符可以是数字，也可以是符号
function findStartIdx(s, i) {
  while (i < s.length) {
    const c = s[i];
    if (isDigit(c) || (isSign(c) && isValidSign(i, s))) break;
    i++;
  }

  return i;
}

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println(getResult(sc.nextLine()));
  }

  public static String getResult(String s) {
    // 记录题解
    String ans = "";

    // 记录数字串中“.”的位置，-1表示数字串中没有点
    int dotIdx = -1;

    // l 指向数字串的开头
    int l = findStartIdx(s, 0);

    // r 用于扫描数字串
    int r = l + 1;
    while (r < s.length()) {
      // 当前扫描的到的字符
      char c = s.charAt(r);

      if (isDigit(c)) {
        // c是数字，则继续扫描下一个
        r++;
      } else if (isSign(c)) {
        // c是加减号，则数字串扫描中断，我们需要先记录[l, r-1]范围的数字串
        ans = getAns(s, l, r, ans);

        if (isValidSign(r, s)) {
          // 由于加减号可以作为数字串开头，如果r位置的加减号是一个合法数字串开头加减号，则可以当成下一个数字串的开头
          l = r;
        } else {
          // 否则，从r+1开始继续找下一个数字的开头
          l = findStartIdx(s, r + 1);
        }

        // 新数字串的开头找到后，从l+1开始扫描
        r = l + 1;
        // 同时注意重置dotIdx记录
        dotIdx = -1;

      } else if (isDot(c)) {
        // 由于dot处理比较复杂，这里无论dot是否会中断数字串扫描，都先将[l, r-1]部分的数字串记录下来
        ans = getAns(s, l, r, ans);

        if (isValidDot(r, s)) {
          // 如果是合法数字串dot, 则判断当前数字串是否已存在”.“
          if (dotIdx != -1) {
            // 如果已存在".", 则当前数字串包含了两个"."，肯定不合法，此时需要舍弃第一个".", 即新数字串开头位置设置在第一个"."后面
            l = dotIdx + 1;
          }

          // 更新dotIdx为第二个"."的位置
          dotIdx = r;
          // r继续扫描下一个
          r++;
        } else {
          // 如果不是合法数字串dot，即该dot前后不都是数字，则新数字串不能包含进当前dot位置，新数字串开头需要从r+1开始找
          l = findStartIdx(s, r + 1);
          r = l + 1;
          dotIdx = -1;
        }
      } else {
        // c是其他字符, 则数字串被打断，此时需要先记录[l, r-1]范围的当前数字串， 然后重新寻找下一个数字串的开头
        ans = getAns(s, l, r, ans);
        l = findStartIdx(s, r + 1);
        r = l + 1;
        dotIdx = -1;
      }
    }

    return getAns(s, l, r, ans);
  }

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

  public static boolean isSign(char c) {
    return c == '+' || c == '-';
  }

  public static boolean isDot(char c) {
    return c == '.';
  }

  // ”.”的两边必须是数字
  public static boolean isValidDot(int dotIdx, String s) {
    int preIdx = dotIdx - 1;
    int nxtIdx = dotIdx + 1;
    return preIdx >= 0
        && isDigit(s.charAt(preIdx))
        && nxtIdx < s.length()
        && isDigit(s.charAt(nxtIdx));
  }

  // ”±”仅能出现在开头且其后必须要有数字
  public static boolean isValidSign(int signIdx, String s) {
    int nxtIdx = signIdx + 1;
    return nxtIdx < s.length() && isDigit(s.charAt(nxtIdx));
  }

  // 从s字符串的i位置开始找数字串的开头字符，数字串的开头字符可以是数字，也可以是符号
  public static int findStartIdx(String s, int i) {
    while (i < s.length()) {
      char c = s.charAt(i);
      if (isDigit(c) || (isSign(c) && isValidSign(i, s))) break;
      i++;
    }

    return i;
  }

  // 记录数字串时，只保留最长的数字串
  public static String getAns(String s, int l, int r, String ans) {
    // 如果存在长度相同的连续数字串，返回最后一个。 因此下面判断是>=
    return l < s.length() && r - l >= ans.length() ? s.substring(l, r) : ans;
  }
}

Python算法源码

# 输入获取
s = input()


def isSign(c):
    return c == '+' or c == '-'


def isDot(c):
    return c == '.'


# ”±”仅能出现在开头且其后必须要有数字
def isValidSign(signIdx):
    nxtIdx = signIdx + 1
    return nxtIdx < len(s) and s[nxtIdx].isdigit()


# ”.”的两边必须是数字
def isValidDot(dotIdx):
    preIdx = dotIdx - 1
    nxtIdx = dotIdx + 1
    return preIdx >= 0 and s[preIdx].isdigit() and nxtIdx < len(s) and s[nxtIdx].isdigit()


# 记录数字串时，只保留最长的数字串
def getAns(l, r, ans):
    # 如果存在长度相同的连续数字串，返回最后一个。 因此下面判断是>=
    return s[l:r] if l < len(s) and r - l >= len(ans) else ans


# 从s字符串的start位置开始找数字串的开头字符，数字串的开头字符可以是数字，也可以是符号
def findStartIdx(i):
    while i < len(s):
        c = s[i]

        if c.isdigit() or (isSign(c) and isValidSign(i)):
            break

        i += 1

    return i


# 算法入口
def getResult():
    # 记录题解
    ans = ""

    # 记录数字串中“.”的位置，-1表示数字串中没有点
    dotIdx = -1

    # l 指向数字串的开头
    l = findStartIdx(0)

    # r 用于扫描数字串
    r = l + 1
    while r < len(s):
        # 当前扫描的到的字符
        c = s[r]

        if c.isdigit():
            # c是数字，则继续扫描下一个
            r += 1
        elif isSign(c):
            # c是加减号，则数字串扫描中断，我们需要先记录[l, r-1]范围的数字串
            ans = getAns(l, r, ans)

            if isValidSign(r):
                # 由于加减号可以作为数字串开头，如果r位置的加减号是一个合法数字串开头加减号，则可以当成下一个数字串的开头
                l = r
            else:
                # 否则，从r+1开始继续找下一个数字的开头
                l = findStartIdx(r+1)

            # 新数字串的开头找到后，从l+1开始扫描
            r = l + 1
            # 同时注意重置dotIdx记录
            dotIdx = -1
        elif isDot(c):
            # 由于dot处理比较复杂，这里无论dot是否会中断数字串扫描，都先将[l, r-1]部分的数字串记录下来
            ans = getAns(l, r, ans)

            if isValidDot(r):
                # 如果是合法数字串dot, 则判断当前数字串是否已存在”.“
                if dotIdx != -1:
                    # 如果已存在".", 则当前数字串包含了两个"."，肯定不合法，此时需要舍弃第一个".", 即新数字串开头位置设置在第一个"."后面
                    l = dotIdx + 1

                # 更新dotIdx为第二个"."的位置
                dotIdx = r
                # r继续扫描下一个
                r += 1
            else:
                # 如果不是合法数字串dot，即该dot前后不都是数字，则新数字串不能包含进当前dot位置，新数字串开头需要从r+1开始找
                l = findStartIdx(r+1)
                r = l + 1
                dotIdx = -1
        else:
            # c是其他字符, 则数字串被打断，此时需要先记录[l, r-1]范围的当前数字串， 然后重新寻找下一个数字串的开头
            ans = getAns(l, r, ans)
            l = findStartIdx(r + 1)
            r = l + 1
            dotIdx = -1

    return getAns(l, r, ans)


# 算法调用
print(getResult())