独立于其本地范围的变量

Question

我尝试用car和cdr的原始工具解决twoSum问题

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

想法是从 nums 中取出 x，然后检查 x 的补集（目标 -x）是否是集合 nums-x

的成员

关键逻辑是

if ((memberp complement (remove-first x nums)) 
then  (list x complement))

从辅助函数开始 try nums

(defun two-sum (nums target)
 (try nums))

主要功能：

(defun try (nums)
  (let ((x (car nums))
        (complement (- target x)))
    (cond
     ((null x) '())
     ((memberp complement (remove-first x nums))
      (list x complement))
     (t (try (cdr nums)))
     )))

然后我意识到 ((memberp complement (remove-first x nums)) 中的 nums 应该保持不变并且独立于 let 的本地范围。

怎么会得到这样的数字？

memberp 和“先删除”

(defun remove-first (item sequence)
  (filter (lambda (x) (not (= x item)))
          sequence))

(defun filter (predicate sequence)
  (cond ((null sequence) nil)
        ((funcall predicate (car sequence))
         (cons (car sequence)
               (filter predicate
                       (cdr sequence))))
        (t  (filter predicate
                    (cdr sequence)))))

(defun memberp(item x)
  (cond ((null x) 'false)
        ((equal item (car x)) x)
        (t (memq item (cdr x)))))

Answer 1

这是一个计算索引的简单递归函数：

(defun two-sum (list target &optional (pos 0))
  (if (null (cdr list))
      nil
      (let ((p (my-position (- target (car list)) list)))
        (if p
            (list pos (+ pos p))
            (two-sum (cdr list) target (1+ pos))))))

(defun my-position (element list &optional (pos 0))
  (cond ((null list) nil)
        ((eql element (car list)) pos)
        (t (my-position element (cdr list) (1+ pos)))))

该函数最初是用列表和目标调用的。最初没有传递给函数的参数 pos 自动赋值为 0，在后续调用中它会加 1，以便它跟踪列表当前元素的索引。

第一个条件检查列表是否少于两个元素：如果它是空的（或者它的 cdr 是空的）结果是 nil 因为没有解决方案是可能的（注意在Common Lisp (cdr nil) 是 nil).

否则我们计算数字“补码”在列表其余部分的位置（注意position是一个原始函数，所以我称my-position它为重写）。如果元素存在，我们 return 同时 pos 和 (+ pos p) （因为找到的位置是相对于当前位置的），否则 (my-position returns nil 当没有找到元素时）我们在列表的其余部分重复。

请注意，使用此方法无需每次都考虑列表的所有元素。

独立于其本地范围的变量

A varaible independent its local scope

lisp

elisp