未末 发布的文章

华为OD机试第一题。

题目描述:

给一个数组,逗号隔开的,然后统计每个数字出现的次数,输出结果按大到小排序,次数相同的,按原来在数组里的左右顺序排。

解答:

这个题似乎是做过的,但是一时短路,只好用笨方法统计,手动排了下。

import sys 
for line in sys.stdin:
    nums = line.strip().split(",")
    res = []
    res2 = []
    for index, num in enumerate(nums):
        num = int(num)
        if num in res:
            res2[res.index(num)] += 1
        else:
            res.append(num)
            res2.append(1)
    length = len(res)
    _res = []
    for i in range(length):
        max_index = res2.index(max(res2))
        _ = res2.pop(max_index)
        _res.append(str(res.pop(max_index)))
    print(",".join(_res))

华为OD机试第二题

题目描述:

将一个数展开为连续的自然数之和。

解答:

一开始还没平静下来,然后后面很快就想起了1+...+100这个事情了,然后弄个公式反推即可(等差数列)。

多个连续自然数相加=(首项+末项)×项数÷2

项数k从1开始,所以下面有个减一

N = min + (min+1) + ... + (min+k-1) = (min + (min+k-1))*k/2

然后得到第一个数
min = (N / k * 2 + 1 - k) / 2

最后判断min是不是一个整数即可

import sys 
for line in sys.stdin:
    num = int(line.strip())
    c = 0
    k = 1
    while True:
        _min = (num / k * 2 + 1 - k) / 2
        if _min <= 0: break
        if (_min % 1 > 0) is False:
            c += 1
            text = str(num) + "=" + "+".join([str(int(_min)+_*1)  for _ in range(k)])
            print(text)
        k += 1
    print("Result:" + str(c))

华为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

坑太多.exe

用例

  • 1010+8-6-2+10-7+1+8+(1+6+(99)*8+1) 768
  • 3+2{1+2[-4/(8-6)+7]} 25

思路

  1. 把输入的字符串处理为数字和运算符组成的列表
  2. 循环遍历列表 找到左括号时 进行递归 直到没有不再遇到左括号
  3. 按乘除优先级高于加减 进行运算 并将结果覆盖参与运算的后者
  4. 删除 参与运算的前者和运算符 返回前删除左右括号
  5. 子一级,也就是括号内的结果运算完成 则把当前这一级进行同样的运算
  6. 再次返回给上一级 或者发现列表被删除只剩一个 也就是最终运算结果 跳出
  7. 得到最终计算结果
def convert(texts: str) -> list:
    tmp = ""
    _text = []
    texts = texts.replace(" ", "").replace("{", "(").replace("}", ")").replace("[", "(").replace("]", ")")
    for index, char in enumerate(texts):
        if char == "(":
            pass
        elif char == ")":
            if tmp != "":
                _text.append(int(tmp))
                tmp = ""
        elif char in ["+", "-", "*", "/"]:
            if texts[index - 1] == "(":
                _text.append(0)
            if tmp != "":
                _text.append(int(tmp))
                tmp = ""
        else:
            tmp += char
            continue
        _text.append(char)
    if tmp != "":
        _text.append(int(tmp)) 
    return _text

def calc(text: list, offset: int):
    while True:
        if text[offset] == "(":
            text = calc(text, offset+1)
        prepop = []
        _offset = offset
        while _offset >= offset and _offset < len(text) - 1: # 处理乘除
            if _offset in prepop: continue # 已经参与过运算 跳过
            if text[_offset + 1] == "(": # 当前位置的下一位是左括号 那么进行递归
                text = calc(text, _offset + 1 + 1) # 递归的起始offset是左括号后一位
            # 当前符号是乘或除 那么将符合前后进行运算 将结果放到后者
            if text[_offset] == "*":
                text[_offset + 1] = text[_offset - 1] * text[_offset + 1]
            elif text[_offset] == "/":
                text[_offset + 1] = text[_offset - 1] / text[_offset + 1]
            else:
                _offset += 1 # 不是乘或除一律跳过
                if text[_offset] == ")": # 括号结束 要跳出
                    break
                continue
            prepop.append(_offset - 1) # 已经参与了运算的元素
            prepop.append(_offset)
            _offset += 1
        text = [_ for index, _ in enumerate(text) if index not in prepop] # 去掉参与了运算的元素
        prepop = []
        _offset = offset # 遍历起始位置_offset重置为offset 
        while _offset >= offset and _offset < len(text) - 1: # 处理加减
            if _offset in prepop: continue
            if text[_offset] == "+":
                text[_offset + 1] = text[_offset - 1] + text[_offset + 1]
            elif text[_offset] == "-":
                text[_offset + 1] = text[_offset - 1] - text[_offset + 1]
            else:
                _offset += 1
                if text[_offset] == ")": # 右括号 说明运算结束
                    offset = _offset - len(prepop) # offset位置就是右括号
                    break
                continue
            prepop.append(_offset - 1)
            prepop.append(_offset)
            _offset += 1
        text = [_ for index, _ in enumerate(text) if index not in prepop]
        if len(text) == 1:
            return text[0] # 最终结果 直接返回结果
        else:
            # 还没运算完  返回上一级
            _ = text.pop(offset) # offset 是右括号位置 删除右括号
            _ = text.pop(offset - 1 - 1) # 删除左括号
            return text
        
while True:
    try:
        texts = input()
    except:
        break
    if texts == "":
        break
    texts = convert(texts)
    res = calc(texts, 0)
    print(res)