PWC 350 好子串 / 洗牌配对

Source: Dev.to

任务 1：好子串

任务描述

给定一个字符串。编写脚本返回该字符串中长度为三的好子串的数量。若子串中没有重复字符，则该子串为好子串。

示例

思考部分

正则表达式可以解决这个问题，但最简单的方法是使用滑动窗口，在字符串上滑动长度为三的窗口，并检查这三个字符是否全部不同。

代码实现

sub goodSubstring($str) {
    my $good = 0;
    my @s = split //, $str;
    for (0 .. $#s - 2) {
        my ($first, $second, $third) = @s[$_, $_+1, $_+2];
        $good++ if $first ne $second && $first ne $third && $second ne $third;
    }
    return $good;
}

注释

• 将字符串拆分为字符列表，便于索引。
• 数组切片 @s[$_, $_+1, $_+2] 提取连续的三个字符。
• 因为只涉及三个字符，成对不等检查非常直接。

任务 2：洗牌配对

任务描述

对于两个整数 A ≤ B，它们由相同的数字组成但顺序不同，我们称它们为洗牌配对，如果存在整数 k 使得 A = B * k。整数 k 是该配对的见证。

编写一个函数，给定 $from、$to 和 $count，返回在区间 $from ≤ i ≤ $to 中属于至少 $count 个不同洗牌配对的整数 i 的数量。

示例

1. 输入: $from = 1, $to = 1000, $count = 1
   输出: 0 – 1000 以下没有洗牌配对。

2. 输入: $from = 1500, $to = 2500, $count = 1
   输出: 3 – 这些数字是 1782 (→ 7128, k=4)、2178 (→ 8712, k=4)、2475 (→ 7425, k=3)。

3. 输入: $from = 1_000_000, $to = 1_500_000, $count = 5
   输出: 2 – 1428570 和 1429857，每个都有五个洗牌伙伴。

4. 输入: $from = 13_427_000, $to = 14_100_000, $count = 2
   输出: 11 – 六个数字有三个伙伴，五个数字有两个伙伴。

5. 输入: $from = 1030, $to = 1130, $count = 1
   输出: 2 – 1035 (→ 3105, k=3) 和 1089 (→ 9801, k=9)。

思考

该问题最好通过暴力搜索并做少量优化来解决：

1. 规范形式：对数字的各位进行排序；如果两个数字的规范形式相同，则它们是彼此的排列。
2. 搜索空间：对于给定的 n，只有乘数 2..9 能保持相同的位数。更大的乘数会导致位数增加，无法成为洗牌配对。
3. 提前退出：
   • 计算相同位数的最大可能值（999…）。
   • 如果乘积的首位或末位不在原数字中，则快速排除。

辅助函数：规范形式

sub canonical($n) {
    join "", sort split //, $n;
}

主解法

sub shufflePair($from, $to, $count) {
    my $answer = 0;

    for my $n ($from .. $to) {
        my $base = canonical($n);
        my $max  = (9 x length($n)) + 0;   # e.g., 999 for a 3‑digit number
        my $pair = 0;

        for my $k (2 .. 9) {
            my $multiple = $n * $k;
            next if $multiple > $max
                 || index($base, substr($multiple, 0, 1)) = $count;
        }
    }
    return $answer;
}

注释

• canonical($n) 对每个 n 缓存为 $base。
• $max 限制搜索范围，使其仍可能保持相同的位数。
• 通过对首位/末位的快速检查（index）避免不必要的排序。
• 当一个数字拥有至少 $count 个洗牌伙伴时，计数器递增。