算法笔记——寻找一个字母和数字组成的最长子串

1263天前 · 分享 · 621次阅读

华为OD机试第三题。

题目描述:

(大意)给定一个只有数字字母的字符串,找出最长的数字子串,子串必须有一个字母。

解答:

一时没有想到什么好办法,只好遍历统计数字和字母的小分段分别的长度,然后根据【符合题意的最长子串一定在最长纯数字子串处产生】这个思路下手,分别讨论。

import sys 
for line in sys.stdin:
    text = line.strip()
    if text.isdigit():
        print(-1)
        continue
    if text.isalpha():
        print(-1)
        continue
    # 最长子串必定在最长连续的数字字符串旁产生
    last = None
    _text = []
    _length = []
    _tmp = ""
    for char in text:
        if char.isalpha():
            if last is None or last == "num":
                _text.append(_tmp)
                _length.append(len(_tmp))
                _tmp = char
                last = "alpha"
                continue
            else:
                _tmp += char
        else:
            if last is None or last == "alpha":
                _text.append(_tmp)
                _length.append(len(_tmp))
                _tmp = char
                last = "num"
                continue
            else:
                _tmp += char
    _text.append(_tmp)
    _length.append(len(_tmp))
    _text = _text[1:]
    _length = _length[1:]
    # print(_text)
    # print(_length)
    max_length = 0
    for _index, _len in enumerate(_length):
        if _text[_index].isdigit() and max_length <= _len:
            max_length = _len
            max_index = _index
    # 分情况
    # if len(_length) == 1:
    #     # 全数字 全字母排除后 理论上不会 出现这种情况
    #     pass
    if len(_length) == 2:
        # 字符串只能分为两个部分 那最长就是数字长度+1
        print(max_length+1)
        continue
    # 分为三个部分的时候 在最左边和最右边一起讨论
    if max_index == 0:
        if _length[max_index+1] == 1:
            # 在最左边 相邻的是一位字母 那么字母左边必定是数字
            # 三者和为符合题意的最长子串
            print(max_length+1+_length[max_index+1+1])
            continue
        else:
            # 只能是数字加一个字符的长度为最长了
            print(max_length+1)
            continue
    elif max_index == len(_length)-1:
        if _length[max_index-1] == 1:
            print(max_length+1+_length[max_index-1-1])
            continue
        else:
            print(max_length+1)
            continue
    else:
        # 最长数字子串在中间
        if _length[max_index+1] == 1:
            max_right = max_length+1+_length[max_index+1+1]
        else:
            max_right = max_length+1
        if _length[max_index-1] == 1:
            max_left = max_length+1+_length[max_index-1-1]
        else:
            max_left = max_length+1
        print(max(max_left, max_right))
        continue
👍 1

none

最后修改于1263天前

评论

贴吧 狗头 原神 小黄脸
收起

贴吧

狗头

原神

小黄脸

目录

avatar

未末

迷失

126

文章数

275

评论数

7

分类