scheme - Lisp中最长的元素链

Question

语句:找出最长的字符链并返回。 例如:输入:'(1 2 2 3 3 3 4 4 4 4 5 6 ) 输出:'(4 4 4 4)

问题:我可以设法识别列表中的所有不同组并比较它们，但无法让函数返回正确的子集列表。它仅返回最后分析的组。

代码:

(define finalL (list))
(define (sameNum liste) 
  (if (or (null? liste) (null? (cdr liste)))
      ;; true
      '()
      ;; false
      (let ([lcdr (sameNum (cdr liste))]) 
        (if (eqv? (car liste) (car(cdr liste)) )
            ;; true
            (if (= (length liste) 2)
                ;; true
                (cons (car liste) (cons (car(cdr liste)) lcdr)) 
                ;; false
                (if (or (not(eqv? (car(cdr liste)) (car(cdr (cdr liste))) )) (null? (cdr liste)) )
                    (cons (car liste) (cons (car(cdr liste)) lcdr)) ;true
                    (cons (car liste) lcdr))) ; false
             ;; false
            (if (let ((x (length lcdr)) (y (length finalL))) (< x y))
                ;; true
                (crushL finalL lcdr)
                ;; false
                finalL)))))
;; crush L1 and replace by value of L2
(define (crushL L1 L2)
  (if (null? L1)
      ;; true
      (cons L2 L1)
      ;; false
      (crushL (cdr L1) L2)))

Answer 1

诀窍是在您浏览列表时保留四件事:

• 当前链(注意:您可以向后构建这些链，因为所有元素都是相同的!)；
• 有多长；
• 您见过的最长的链条；
• 那是多久了。

然后，您根据正在查看的元素是否与当前链中的第一个元素相同(仍在构建相同的链)或不同(开始一个新链)做出决定，并且如果您仍在构建相同的链，无论该链现在是否是最长的。

像这样:

(define (longest-chain l)
  (let lc-loop ([tail l]
                [current-length 0]
                [current-chain '()]
                [longest-length 0]
                [longest-chain '()])
    (cond [(null? tail)
           ;; we're done: return the longest chain
           longest-chain]
          [(and (not (null? current-chain))
                (eqv? (first tail) (first current-chain)))
           ;; building on a current chain
           (let ([chain (cons (first tail) current-chain)]
                 [chain-length (+ 1 current-length)])
             (if (> chain-length longest-length)
                 ;; the current chain is now the longest
                 (lc-loop (rest tail)
                          chain-length chain
                          chain-length chain)
                 ;; it's not the longest yet
                 (lc-loop (rest tail)
                          chain-length chain
                          longest-length longest-chain)))]
          [else
           ;; starting a new chain
           (lc-loop (rest tail)
                    1 (list (first tail))
                    longest-length longest-chain)])))

额外加分:如果有多个最长链，该函数返回哪一个？你如何改变它，让它做出另一个选择？甚至是随机选择!

---

请注意，上述版本的函数使用 named let ，这是Scheme 中的标准构造。如果您不想使用它，可以将其变成显式函数:

(define (longest-chain l)
  (define (lc-loop tail
                   current-length current-chain
                   longest-length longest-chain)
    (cond [(null? tail)
           ;; we're done: return the longest chain
           longest-chain]
          [(and (not (null? current-chain))
                (eqv? (first tail) (first current-chain)))
           ;; building on a current chain
           (let ([chain (cons (first tail) current-chain)]
                 [chain-length (+ 1 current-length)])
             (if (> chain-length longest-length)
                 ;; the current chain is now the longest
                 (lc-loop (rest tail)
                          chain-length chain
                          chain-length chain)
                 ;; it's not the longest yet
                 (lc-loop (rest tail)
                          chain-length chain
                          longest-length longest-chain)))]
          [else
           ;; starting a new chain
           (lc-loop (rest tail)
                    1 (list (first tail))
                    longest-length longest-chain)]))
  (lc-loop l 0 '() 0 '()))

这与上面的版本完全等效。如果您对内部 define 不满意，那么您可以将 lc-loop 转换为顶级定义。