Доступный независимый его локальный охват - PullRequest
Новая
       47

Доступный независимый его локальный охват

0 голосов
/ 06 января 2020

Я попытался решить проблему twoSum с примитивными инструментами car и cdr

Учитывая массив целых чисел, вернуть индексы двух чисел так, чтобы они складывались в заданную c цель .

Вы можете предположить, что у каждого входа будет только одно решение, и вы не можете использовать один и тот же элемент дважды.

Пример:

При заданных числах = [2, 7 , 11, 15], target = 9,

Поскольку nums [0] + nums [1] = 2 + 7 = 9, возвращаем [0, 1].

Идея состоит в том, чтобы взять x из nums, а затем проверить, является ли дополнение x (target -x) членом набора nums-x

Ключ логики c равен 

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)) должны оставаться неизменными и независимыми от локальных область действия let.

Как можно получить такие числа?

memberp и `remove-first '

(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)))))

1 Ответ

1 голос
/ 06 января 2020

Вот простая рекурсивная функция для вычисления индексов: 

(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, а в последующих вызовах он увеличивается на единицу, так что он отслеживает индекс текущего элемента списка.

Первое условие проверяет, содержит ли список менее двух элементов: если он пуст (или его cdr пуст), результат равен nil, поскольку решение невозможно (обратите внимание, что в Common Lisp (cdr nil) nil).

В противном случае мы вычисляем позицию «дополнения» числа в остальной части списка (обратите внимание, что position является примитивной функцией, поэтому я назвал my-position ее переписыванием) , Если элемент присутствует, мы возвращаем как pos, так и (+ pos p) (поскольку найденная позиция относительно текущей позиции), в противном случае (my-position возвращает nil, когда элемент не найден), мы возвращаемся к остальной части список.

Обратите внимание, что при использовании этого метода нет необходимости каждый раз рассматривать все элементы списка.

...