LIS最长递增子序列

aimisiyou · 发表于 2021-4-17 16:39:12

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

(defun tt(lst)
(defun f1 (plst j num)
(setq ij -1)
(setq plst (mapcar '(lambda (x) (if (= (setq ij (+ ij 1)) j) num x)) plst))
)
(setq n (length lst) i 0 ans 0 vlst '(nil))
(repeat n (setq vlst (cons nil vlst)))
(while (< i n)
(setq l 0 r ans)
      (while (< l r)
      (setq mid (/ (+ l r) 2))
      (if (<= (nth mid vlst) (nth i lst))
            (setq l (+ mid 1))
               (setq r mid)
         )
      )
(setq vlst (f1 vlst l (nth i lst)))
      (if (= l ans) (setq ans (+ ans 1)))
      (setq i (+ i 1))
)
(setq vlst (reverse (vl-remove nil vlst)) alst (reverse lst) blst (list (+ 1 (car vlst))))
(while  vlst
   (if (and (>= (car alst) (car vlst)) (<= (car alst) (car blst)))
         (progn
         (setq blst (cons (car alst) blst))
         (setq vlst (cdr vlst))
                     (setq alst (cdr alst))
               )
               (setq alst (cdr alst))
      )
)
(reverse (cdr (reverse blst)))
)

_$ (tt '(0 0 2 4 1 5 1 3 1 2 0 8 9 10 4 6))
(0 0 1 1 1 2 8 9 10)
_$  (tt '(0 0 2 4 1 5 1 3 1 2 0 8 9 10 4 6 7))
(0 0 1 1 1 2 4 6 7)
_$ (tt '(5 1 3 2 0 8 9 10 4 6 7))
(1 2 4 6 7)
_$ (tt '(3 5 4 6 10 0 1 9 8 2 7))
(0 1 2 7)
_$ (tt '(0 1 9 10 2 3 4 5 6 8 7))
(0 1 2 3 4 5 6 7)
_$ (tt '(6 1 0 3 11 10 4 5 8 9 2 7))
(0 3 4 5 8 9)
_$

greatxs · 发表于 2021-4-17 18:45:37

1183262116139

aimisiyou · 发表于 2021-4-18 19:52:47

本帖最后由 aimisiyou 于 2024-9-26 17:47 编辑

;;;LCS最长公共字符串
(defun f (str1 str2)
(setq str1lst (vl-string->list str1))
(setq str2lst (vl-string->list str2))
(setq lst (vl-remove nil (apply 'append (mapcar '(lambda (x)
         (progn
                        (setq j -1)
                        (reverse  (mapcar '(lambda (y) (progn (setq j (+ j 1)) (if (= x y) j nil))) str2lst))
                     ))
                     str1lst)))
  )
(defun f1 (plst j num)
(setq ij -1)
(setq plst (mapcar '(lambda (x) (if (= (setq ij (+ ij 1)) j) num x)) plst))
)
(setq n (length lst) i 0 ans 0 vlst '(nil))
(repeat n (setq vlst (cons nil vlst)))
(while (< i n)
(setq l 0 r ans)
      (while (< l r)
      (setq mid (/ (+ l r) 2))
      (if (<= (nth mid vlst) (nth i lst))
            (setq l (+ mid 1))
               (setq r mid)
         )
      )
(setq vlst (f1 vlst l (nth i lst)))
      (if (= l ans) (setq ans (+ ans 1)))
      (setq i (+ i 1))
)
(setq vlst (reverse (vl-remove nil vlst)) alst (reverse lst) blst (list (+ 1 (car vlst))))
(while  vlst
   (if (and (>= (car alst) (car vlst)) (<= (car alst) (car blst)))
         (progn
         (setq blst (cons (car alst) blst))
         (setq vlst (cdr vlst))
                     (setq alst (cdr alst))
               )
               (setq alst (cdr alst))
      )
)
(vl-list->string (mapcar '(lambda (x) (nth x str2lst)) (reverse (cdr (reverse blst)))))
)

yangjian001 · 发表于 2021-4-20 08:45:59

做一个热心并受欢迎的人

账号		自动登录	找回密码
密码			立即注册

[研讨] LIS最长递增子序列

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。