尝试 Racket 解题 leetcode

在读 wangyin 文章怎样写一个解释器时，选用的实现工具便是 Racket。我已简单了解 Lisp 语法基础，同时也苦于寻找各种 Lisp 的实战场景，再加上一些被影响的对 Lisp 语法的偏爱，Racket 解题的想法便产生了。

两数之和

选择 LeetCode 第一题两数之和，简述如下：

给定一个整数数组 nums 和一个整数目标值 target，请返回和为目标值的两个整数的下标

输入：nums = [2,7,11,15], target = 9 输出：[0,1]

Racket 解题框架

平台为你提供的 define/contract 限制了合约内的参数与返回值的类型：

(define/contract (two-sum nums target)
  (-> (listof exact-integer?) exact-integer? (listof exact-integer?))

  )

接下来你需要做的就是像使用 C 或 Go 一样地去编写算法逻辑。

解法一：借助 hash 存储数组下标

在 hash 中以 target 与当前项的差为 key，以当前项的 index 为 value；迭代目标数组，若 key 出现则返回 value 与当前 index 值：

(define/contract (two-sum nums target)
  (-> (listof exact-integer?) exact-integer? (listof exact-integer?))

  (let ([want-h (make-hash)])
    ; key: 可相加为 target 的值
    ; value: 结果加数的索引
    (define (iter lst index)
      (cond
        ((hash-has-key? want-h (car lst))
         (list (hash-ref want-h (car lst)) index))
        (else
         (hash-set! want-h (- target (car lst)) index)
         (iter (cdr lst) (+ 1 index)))))
    (iter nums 0)))

解法二：待索引的双重循环

外层循环以 target 差当前项去构造目标需求值，二层循环寻找该目标值，只是需要在每次循环中主动传递自增 index 做记录：

(define/contract (two-sum nums target)
  (-> (listof exact-integer?) exact-integer? (listof exact-integer?))

  (define (iter-inner lst stop-key index-cnt)
    (cond
      ([empty? lst] lst)
      ([= stop-key (car lst)] index-cnt)
      (else
       (iter-inner (cdr lst) stop-key (+ 1 index-cnt)))))

  (define (iter-outer lst index-cnt)
    (let ([candidate (iter-inner (cdr lst) (- target (car lst)) (+ 1 index-cnt))])
      (cond ([empty? candidate]
             (iter-outer (cdr lst) (+ 1 index-cnt)))
            (else
             (list candidate index-cnt)))))

  (iter-outer nums 0))