锤击清单

百变鹏仔 5天前 #Python

文章标签清单

每周挑战301：穆罕默德·安瓦尔 (Mohammad Anwar) 的算法挑战

穆罕默德·安瓦尔每周都会发布“每周挑战”，提供练习编程的绝佳机会。他先用 Python 编写解决方案，再转换成 Perl。让我们来看看本周的挑战及其解决方案。

挑战一：最大数字

任务： 给定一个正整数列表，将其中的元素重新排列，使其组成最大的数字。

解决方案： 直接对整数进行排序并连接起来并不总是能得到最大数字（例如，3, 30, 34）。因此，需要一个更巧妙的排序方法。安瓦尔采用了一种自定义排序算法，将两个整数转换为字符串后拼接，比较拼接后的数值大小来决定排序顺序。

Python 代码：

from functools import cmp_to_keydef number_sort(i1: int, i2: int) -> int:    s1 = str(i1)    s2 = str(i2)    c1 = int(s1 + s2)    c2 = int(s2 + s1)    if c1 < c2:        return -1    elif c1 > c2:        return 1    else:        return 0def largest_number(ints: list) -> int:    sorted_ints = sorted(ints, key=cmp_to_key(number_sort), reverse=True)    return int(''.join(map(str, sorted_ints)))

Perl 代码：

sub number_sort {    return "$a$b" cmp "$b$a";}

示例：

$ ./ch-1.py 20 3320$ ./ch-1.py 3 30 34 5 99534330

挑战二：汉明距离

任务： 给定一个整数数组，计算所有整数对之间的汉明距离之和。汉明距离是两个整数二进制表示中不同位数的个数。

解决方案： 安瓦尔计算所有整数对的组合，对每对整数进行异或运算，然后将结果转换为二进制，统计其中1的个数，即为汉明距离。

Python 代码：

def hamming_distance(ints: list) -> int:    solution = 0    for i in range(len(ints) - 1):        for j in range(i + 1, len(ints)):            x = ints[i] ^ ints[j]            solution += bin(x).count('1')    return solution

示例：

$ ./ch-2.py 4 14 26$ ./ch-2.py 4 14 44

安瓦尔还讨论了 Python 和 Perl 在处理整数和字符串以及按位运算方面的差异。 Perl 在较新版本中对按位运算进行了改进，使其处理更一致。

文章推荐

锤击清单

如何在Python中将DateTime转换为整数？

Python - 字典中键的值求和

Python程序向列表中添加元素

Python程序将列表中的所有元素连接成一个字符串

学习起来哪个更容易，SQL还是Python？