Python和对从文本文件

2022-01-30 14:47:36 标签 python

我得到一个正整数和一个数字X的有序数组,我需要打印出所有和等于X的数字对,只打印出唯一的对,而且这些对应该是升序的。

但是,程序需要从标准输入中读取文本行,其中每一行包含一个逗号分隔的排序数字列表,后面跟着一个分号,后面跟着整数X。

如测试输入:12346;5

输出:14;23

我有试过

但我得到

list1 = []
for line in sys.stdin:
    for n in line:
        list1.append(n)
        strlist = [ x for x in list1 if x.isdigit() ]
        numlist = list(map(int, strlist))
    sum = numlist[-1]
    res = []
    while numlist:
        num = numlist.pop()
        diff = sum - num
        if diff in numlist:
            res.append((diff, num))     
    res.reverse()
    print(res, end="")

测试输入:12346;5

预期的输出:14;23

我的输出:[(2 3)(1 4)]

###这可能不是最有效的,但我想出了这个工作。

将test_case替换为sys。Stdin并删除test_case应该可以工作。

抱歉,如果这看起来很糟糕,这是我第一次张贴在stackoverflow上。

输出:14;23

test_case = ["1,2,3,4,6;5"]
for line in test_case:
    line = line.split(";")
    numbers = line[0].split(",")
    pairs = []
    for number in numbers:
        difference = int(line[1]) - int(number)
        difference = str(difference)
        if  difference in numbers and difference != number:
            pair = ",".join((number, difference))
            pairs.append(pair)
del pairs[len(pairs)//2:len(pairs)]
print(";".join(pairs))

# # #解决方案1:

O(n2)的时间复杂度。这是基于最初的解决方案。所作的更正如下:

字符串的迭代和每个字符的解析对于2位数字(或更多)是行不通的。

因此它是不正确的。而且效率也不高。而不是手动迭代每个字符检查12 thus it is incorrect. Also it is not efficient. Instead of manually iterating each character checking 然后对整个列表的下一个数字重新做一遍只是用字符分割字符串.isdigit() and then redoing it again for the next number for the whole list just split the string by the characte和; and and then transform them to int.然后把它们转换成整数。 and 在您的原始逻辑中,目标和将是列表中的最后一个元素

. 但是您正在考虑这个数字作为总和(因为它将是第一个弹出的数字)。你应该在进入while循环之前先弹出它。numlist. But you are considering that number for the sum (since it will be the firs对的顺序将从最高的数字开始(弹出,直到列表为空)。所以最大的数就是最小的数。

1 is to 4 then 2 is to 3 thus no need to call .reverse() as it will do the opposite.然后4 then <是2 is to因此没有必要打电话3 thus n因为它会适得其反。.reverse() as it will do the opp解决方案2:

for input_text in [
    "1,2,3,4,6;5",
    "5,10,15,20,25,30,35,40,45;50",
    "0,2,4,6,8,10,12,14;12",
]:
    num_str, sum_str = input_text.split(';')
    num_list = list(map(int, num_str.split(',')))
    target_sum = int(sum_str)
    res = []
    while num_list:
        num = num_list.pop()
        diff = target_sum - num
        if diff in num_list:
            res.append((diff, num))     
    res_formatted = ";".join(map(lambda pair: f"{pair[0]},{pair[1]}", res))
    print(f"{input_text}\n\t{res}\n\t{res_formatted}")

O(n)的时间复杂度。因为我们已经有了排序的数据,而不是遍历整个列表寻找另一个将到达每个数字的目标总和的数字,只需使用2个指针,一个在开始/左边的lhs,一个在结束/右边的rhs。

如果总和低于目标,这意味着我们需要向前/右移

. 为什么?因为如果我们已经把它和最大值相加lhs. Why? Because if we already added it to the maximum number which is rhs the那就没有必要用其他数来试了。我们需要的是增加rhs then there is no point of trying it with the other numbers. What we 看看下一个结果。lhs and see the next result.如果总和高于目标,则意味着我们需要向后/向左移动

. 为什么?和上面一样,如果和已经高了,那么我们就不能用这个数rhs. Why? Same point as above If the sum was already higher then we can't use the nu因为即使加上最小的数,它也太高了rhs as it is too high even if added with the smallest number lhs thus move it t因此把它移到下一个更小的数。lhs thus move it to the next smaller number.如果和等于目标和,那么我们在结果中包含由所指向的数字

lhs and rhs. Then we move both pointers respectively.. 然后我们分别移动两个指针。rhs. The输出

def sum_pairs(numbers, target_sum):
    lhs = 0
    rhs = len(numbers) - 1
    pairs = []
    while lhs < rhs:
        current_sum = numbers[lhs] + numbers[rhs]
        if current_sum == target_sum:
            pairs.append((numbers[lhs], numbers[rhs]))
            lhs += 1
            rhs -= 1
        elif current_sum > target_sum:
            rhs -= 1
        else:
            lhs += 1
    return pairs
for input_text in [
    "1,2,3,4,6;5",
    "5,10,15,20,25,30,35,40,45;50",
    "0,2,4,6,8,10,12,14;12",
]:
    num_str, sum_str = input_text.split(';')
    num_list = list(map(int, num_str.split(',')))
    target_sum = int(sum_str)
    res = sum_pairs(num_list, target_sum)
    res_formatted = ";".join(map(lambda pair: f"{pair[0]},{pair[1]}", res))
    print(f"{input_text}\n\t{res}\n\t{res_formatted}")

1,2,3,4,6;5
    [(1, 4), (2, 3)]
    1,4;2,3
5,10,15,20,25,30,35,40,45;50
    [(5, 45), (10, 40), (15, 35), (20, 30)]
    5,45;10,40;15,35;20,30
0,2,4,6,8,10,12,14;12
    [(0, 12), (2, 10), (4, 8)]
    0,12;2,10;4,8
阅读全文

▼ 版权说明

相关文章也很精彩
推荐内容
更多标签
相关热门
全站排行
随便看看

错说 cuoshuo.com —— 程序员的报错记录

部分内容根据CC版权协议转载;网站内容仅供参考,生产环境使用务必查阅官方文档

辽ICP备19011660号-5

×

扫码关注公众号:职场神器
发送: 1
获取永久解锁本站全部文章的验证码