寻找双重存在并应用 Luhn 算法

亲爱的编程学习爱好者，如果你点开了这篇文章，说明你对《寻找双重存在并应用 Luhn 算法》很感兴趣。本篇文章就来给大家详细解析一下，主要介绍一下，希望所有认真读完的童鞋们，都有实质性的提高。

在本文中，我们将解决 perl weekly challenge #290 中的两个引人入胜的任务：检查数组中是否存在双重存在并实现 luhn 算法进行验证。我们将在 perl 和 go 中实现解决方案。

目录

• 双重存在
• 卢恩算法
• 结论

双重存在

第一个任务涉及查找是否存在两个索引 $i 和 $j 使得：

1. $i != $j
2. 0 <= ($i, $j) < scalar @ints
3. $ints[i] = 2 * $ints[j]

任务描述

输入： 整数数组，@ints。

输出： 如果满足条件则为 true；否则，错误。

示例：

input: @ints = (6, 2, 3, 3)
output: true

for $i = 0, $j = 2
$ints[$i] = 6 => 2 * 3 =>  2 * $ints[$j]

input: @ints = (3, 1, 4, 13)
output: false

input: @ints = (2, 1, 4, 2)
output: true

for $i = 2, $j = 3
$ints[$i] = 4 => 2 * 2 =>  2 * $ints[$j]

解决方案

perl 实现
在 perl 实现中，我们使用哈希来跟踪看到的整数，并检查哈希中是否存在当前数字的一半或两倍。

sub double_exist {
    my %seen;

    foreach my $num (@_) {
        return 1 if exists $seen{$num / 2} || exists $seen{$num * 2};
        $seen{$num} = 1;
    }

    return 0;
}

go 实施
go 实现遵循类似的逻辑，使用映射来跟踪唯一整数。

func doubleexist(ints []int) bool {
    seen := make(map[int]bool)

    for _, num := range ints {
        if (num%2 == 0 && seen[num/2]) || seen[num*2] {
            return true
        }
        seen[num] = true
    }

    return false
}

卢恩算法

第二个任务涉及实施 luhn 算法来验证数字字符串，忽略非数字字符。最后一位数字被单独视为有效负载。

任务描述

给你一个字符串 str ，其中包含数字（可能还有其他可以忽略的字符）。最后一位数字被视为有效负载并单独处理。

1. 从右数起，将剩余数字的第一个、第三个等的值加倍。
2. 对于现在大于 9 的每个值，将其数字相加。
3. 正确的校验位是当添加到所有值的总和时，使总模 10 为零的位。

如果有效负载等于正确的校验位，则返回 true；否则，返回 false。

示例：

input: "17893729974"
output: true

payload is 4.

digits from the right:

7 * 2 = 14, sum = 5
9 = 9
9 * 2 = 18, sum = 9
2 = 2
7 * 2 = 14, sum = 5
3 = 3
9 * 2 = 18, sum = 9
8 = 8
7 * 2 = 14, sum = 5
1 = 1

sum of all values = 56, so 4 must be added to bring the total mod 10 to zero. the payload is indeed 4.

input: "4137 8947 1175 5904"
output: true

input: "4137 8974 1175 5904"
output: false

解决方案

perl 实现
perl 实现处理输入字符串以忽略非数字字符，然后应用 luhn 算法来验证数字。

sub luhn_check {
    my ($str) = @_;
    $str =~ s/[^0-9]//g;

    my $payload = substr($str, -1);
    my $sum = 0;
    my $length = length($str);

    for (my $i = 0; $i < $length - 1; $i++) {
        my $digit = substr($str, $length - 2 - $i, 1);
        if ($i % 2 == 0) {
            $digit *= 2;
            $digit -= 9 if $digit > 9;
        }
        $sum += $digit;
    }

    my $check_digit = (10 - ($sum % 10)) % 10;

    return $payload == $check_digit ? 1 : 0;
}

go 实施
go 版本实现了相同的逻辑，利用 unicode 包过滤掉非数字字符。

func luhnCheck(str string) bool {
    sum := 0
    payload := 0
    digits := []int{}

    for _, char := range str {
        if unicode.IsDigit(char) {
            digit := int(char - '0')
            digits = append(digits, digit)
        }
    }

    if len(digits) == 0 {
        return false
    }

    payload = digits[len(digits)-1]

    for i := 0; i < len(digits)-1; i++ {
        digit := digits[i]
        if (len(digits)-2-i)%2 == 0 {
            digit *= 2
            if digit > 9 {
                digit -= 9
            }
        }
        sum += digit
    }

    checkDigit := (10 - (sum % 10)) % 10

    return payload == checkDigit
}

结论

在本文中，我们探讨了两个有趣的编程挑战：查找数组中的双重存在以及实现 luhn 算法进行验证。这些任务强调了不同的编程语言如何用自己独特的方法解决类似的问题。我希望这些例子能够激励您更深入地研究 perl 和 go！

您可以在 github 上找到完整的代码，包括测试。

好了，本文到此结束，带大家了解了《寻找双重存在并应用 Luhn 算法》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多Golang知识！