当前位置：首页 > 文章列表 > Golang > Go教程 > 寻找双重存在并应用 Luhn 算法

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

来源：dev.to 2024-10-13 18:22:01 0浏览收藏

亲爱的编程学习爱好者，如果你点开了这篇文章，说明你对《寻找双重存在并应用 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 ，其中包含数字（可能还有其他可以忽略的字符）。最后一位数字被视为有效负载并单独处理。

从右数起，将剩余数字的第一个、第三个等的值加倍。
对于现在大于 9 的每个值，将其数字相加。
正确的校验位是当添加到所有值的总和时，使总模 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
}