(新卷,100分)- 在字符串中找出连续最长的数字串(含“+-”号)（Java JS Python）-深圳市維司達科技有限公司

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

题目描述

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

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

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

注意：

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

输入描述

无

输出描述

无

用例

输入	1234567890abcd9.+12345.678.9ed
输出	+12345.678
说明	无

题目解析

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

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

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

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

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

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

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

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

如果R+1位置是数字，则下一个数字串的开头L=R，因为数字串可以以加减号开头，只要加减号后面跟着数字，之后R++继续扫描
如果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())