Clojure LeetCode Online Judge: Largest Number

@_sg · Регистрация: 12.05.2012

Студворк — интернет-сервис помощи студентам

Дан список положительных целых чисел. Организовать их так, чтобы они образовали наибольшее число. Например, если дан список (3 30 34 5 9), то наибольшее число - 9534330.

@Memex · 01.02.2015, 13:49

Далеко не самый честный (используется встроенная сортировка), быстрый (формат и построение строки) и красивый метод:

Lisp
1
2
3
4
5
6
7
8
9
10
11
(defun bnum (nums)
  (let ((out ""))
    (dolist (x nums (parse-integer (sort out #'char>)))
      (setf out (concatenate 'string out (format nil "~A" x)))))) 
 
[15]> (bnum '(4 7 9 0 8 9 8 10 88))
99888874100 ;
11
[16]> (bnum '(3 7 1 76 8 4 8 10 88 770))
888877776431100 ;
15

@_sg · 01.02.2015, 14:13 **[ТС]**

Memex,

Lisp
1
2
3
> (largest-number '(3 7 1 76 8 4 8 10 88 770))
888877707643110
15

?

Добавлено через 4 минуты

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defun largest-number (w)
  (parse-integer
   (apply #'concatenate 'string
          (selection-sort (mapcar #'write-to-string w)))))
 
(defun selection-sort (w)
  (when w (let ((m (reduce #'mx w)))
            (cons m (selection-sort (remove m w :count 1))))))
 
(defun mx (a b)
  (if (> (parse-integer (concatenate 'string a b))
         (parse-integer (concatenate 'string b a)))
      a
      b))
 
> (largest-number '(3 30 34 5 9))
9534330
7

@Memex · 01.02.2015, 14:17

Точно, у меня не то получилось, так как входные числа нельзя расщеплять на составные символы.

@_sg · 01.02.2015, 14:19 **[ТС]**

вариант bnum:

Lisp
1
2
3
4
5
6
7
8
9
10
(defun bnum (w)
  (parse-integer
   (sort (apply
          #'concatenate
          'string (mapcar #'write-to-string  w))
         #'char>)))
 
> (bnum '(3 7 1 76 8 4 8 10 88 770))
888877776431100
15

@Memex · 01.02.2015, 14:24

Скоро год, как я впервые познакомился с Лиспом, а до сих пор пользовался форматом для создания строк из атомов... Некрасиво вышло, есть же write-to-string!

@castorsky · 01.02.2015, 19:11

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
;; racket-lang.org
(define (let-sort-it lst)
  (sort lst (lambda (x y) (string>? (string-append x y) (string-append y x)))))
 
(define (foo lst)
  (string->number
   (apply string-append (let-sort-it (map number->string lst)))))
 
(foo '(123 43 22 1 9 7))
;9743221231
(foo '(3 30 34 5 9))
;9534330

Не по теме:

Сообщение от Memex

Скоро год, как я впервые познакомился с Лиспом

мы с Вами ровесники :)

@ur_naz · 01.02.2015, 19:59

HomeLisp...Ничего не предвещало беды...но сортировка подвела...

Lisp
1
2
(defun test (w)
  (implode (qsort-b (apply 'append (mapcar 'explode w)) '>)))

Lisp
1
2
3
4
5
==> test
(test '(3 7 1 76 8 4 8 10 88 770))
 
 
==> 111346777777777777777888888888888888

@_sg · 01.02.2015, 21:08 **[ТС]**

ur_naz,

Сообщение от Memex

входные числа нельзя расщеплять на составные символы

@Catstail · 01.02.2015, 22:04

HomeLisp:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(defun strComp (s1 s2)
  (cond ((eq s1 s2) 0)
        (t (let* ((l1 (strlen s1))
                  (l2 (strlen s2))
                  (l  (min l1 l2))
                  (q1 (strLeft s1 l))
                  (q2 (strLeft s2 l)))
                 (cond ((plusp (strCmp q1 q2)) 1)
                       ((minusp (strCmp q1 q2)) -1)
                       ((< l l1) (strCmp (strMid s1 (+ l 1) 1) (strMid s1 l 1)))
                       ((< l l2) (strCmp (strMid s2 (+ l 1) 1) (strMid s2 l 1))))))))
 
(defun task (lst)
 (let* ((lsts (mapcar 'fix2str lst))
        (slsts (qsort-b lsts #'(lambda (x y) (<= (strComp x y) 0)))))
       (str2fix (apply 'strCat slsts))))
 
(task '(3 30 34 5 9))
 
==> 9534330
 
(task '(3 7 1 76 8 4 8 10 88 770))
 
==> 888877707643110

Добавлено через 4 минуты
Есть тонкость: лексикографическое сравнение строк дает "30" > "3", но в данной задаче "3" должно идти раньше... Для этого и написана функция strComp. Она сравнивает строки почти обычным образом, но для строк "***nk" и "***n", вторая будет меньше, если k < n.

@_sg · 02.02.2015, 18:16 **[ТС]**

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defun largest-number (w)
  (parse-integer
   (apply #'concatenate 'string
          (selection-sort (mapcar #'write-to-string w)))))
 
(defun selection-sort (w)
  (when w (let ((m (reduce #'mx w)))
            (cons m (selection-sort (remove m w :count 1))))))
 
(defun mx (a b
           &aux
           (ab (parse-integer (concatenate 'string a b)))
           (ba (parse-integer (concatenate 'string b a))))
  (if (> ab ba) a b))
 
> (largest-number '(3 30 34 5 9))
9534330
7

Добавлено через 17 секунд

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(defun largest-number (w)
  (parse-integer
   (apply #'concatenate 'string
          (selection-sort (mapcar #'write-to-string w)))))
 
(defun selection-sort (w)
  (when w
    (let ((m (reduce
              #'(lambda (a b)
                  (if (> (parse-integer (concatenate 'string a b))
                         (parse-integer (concatenate 'string b a)))
                      a
                      b))
              w)))
      (cons m (selection-sort (remove m w :count 1))))))
 
> (largest-number '(3 30 34 5 9))
9534330
7

Добавлено через 19 секунд

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(defun largest-number (w)
  (parse-integer
   (apply #'concatenate 'string
          (selection-sort (mapcar #'write-to-string w)))))
 
(defun selection-sort (w)
  (when w
    (let ((m (reduce #'(lambda (a b) (if (> (glue a b) (glue b a))
                                         a
                                         b))
                     w)))
      (cons m (selection-sort (remove m w :count 1))))))
 
(defun glue (a b)
  (parse-integer (concatenate 'string a b)))
 
> (largest-number '(3 30 34 5 9))
9534330
7

@smoke853 · 02.02.2015, 18:47

Clojure:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(ns aeon.core)
 
(defn task [coll]
  (->> (sort #(compare (str %2 %) (str % %2)) coll)
       (apply str)
       bigint))
;; => #'aeon.core/task
 
(task '(123 43 22 1 9 7))
;; => 9743221231N
(task '(3 30 34 5 9))
;; => 9534330N
(task '(3 7 1 76 8 4 8 10 88 770))
;; => 888877707643110N

@korvin_ · 04.02.2015, 13:27

Сообщение от Memex

быстрый (формат

Насколько я помню, формат как раз в CL довольно медленный.

@helter · 04.02.2015, 15:28

Сообщение от Memex

(setf out (concatenate 'string out (format nil "~A" x)))

Это плохо, причём не только в лиспе. При каждом вызове concatenate создаётся новая строка, так что в итоге много мусора. Например, объединяем строки "1", "2", ..., "9", в качестве промежуточных возникают всё более и более длинные строки "12", "123", ..., "123456789", которые все не нужны.

В качестве приличной по эффективности альтернативы можно было бы печатать всё в строку:

Lisp
1
2
3
(with-output-to-string (out)
  (dolist (x sorted-nums)
    (princ x out)))

Форматом короче:

Lisp
1
(format nil "~{~A~}" sorted-nums)

@Memex · 05.02.2015, 00:10

Сообщение от korvin_

Насколько я помню, формат как раз в CL довольно медленный.

Ага, тут так и написано:

Сообщение от Memex

Далеко не самый

@korvin_ · 05.02.2015, 00:53

Не по теме:

Сообщение от Memex

Ага, тут так и написано:

А, не подумал, что «не самый» относится ко всем эпитетам.

@_sg · 07.02.2015, 13:34 **[ТС]**

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun largest-number (w)
  (parse-integer
   (format nil "~{~a~}"
           (selection-sort
            (mapcar #'write-to-string w)))))
 
(defun selection-sort (w)
  (when w (let ((m (reduce #'mx w)))
            (cons m (selection-sort
                     (remove m w :count 1))))))
 
(defun mx (a b)
  (if (> (glue a b) (glue b a)) a b))
 
(defun glue (a b)
  (parse-integer (concatenate 'string a b)))
 
> (largest-number '(3 30 34 5 9))
9534330
7

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(defun largest-number (w)
  (parse-integer
   (format nil "~{~a~}"
           (selection-sort
            (mapcar #'write-to-string w)))))
 
(defun selection-sort (w)
  (when w (let ((m (reduce #'mx w)))
            (cons m (selection-sort
                     (remove m w :count 1))))))
 
(defun mx (a b)
  (if (> (glue a b) (glue b a)) a b))
 
(defun glue (a b)
  (parse-integer (format nil "~{~a~}" (list a b))))
 
> (largest-number '(3 30 34 5 9))
9534330
7

@nullxdth · 10.02.2015, 23:52

Сообщение от korvin_

Насколько я помню, формат как раз в CL довольно медленный.

Можно ускорить, если заранее скомпилировать.

transformator.t · 11.02.2015, 15:13

Сообщение от korvin_

Насколько я помню, формат как раз в CL довольно медленный.

в чём конкретно проявляется медленность?

тыц

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
INSOMNIA> (time (repeat 1000000 (format nil "~A~v@{~A~:*~}" 'lisp 5 #\*)))
Evaluation took:
  1.574 seconds of real time
  1.572000 seconds of total run time (1.572000 user, 0.000000 system)
  [ Run times consist of 0.011 seconds GC time, and 1.561 seconds non-GC time. ]
  99.87% CPU
  3,768,113,964 processor cycles
  639,990,608 bytes consed
  
"LISP*****"
INSOMNIA> (time (repeat 1000000 
                  (with-output-to-string (out)
                    (funcall (formatter "~A~v@{~A~:*~}") out 'lisp 5 #\*))))
Evaluation took:
  1.497 seconds of real time
  1.496000 seconds of total run time (1.496000 user, 0.000000 system)
  [ Run times consist of 0.019 seconds GC time, and 1.477 seconds non-GC time. ]
  99.93% CPU
  3,583,343,268 processor cycles
  592,007,312 bytes consed
  
"LISP*****"
INSOMNIA> (time (repeat 1000000 
                  (format ()
                    (formatter "~A~v@{~A~:*~}") 'lisp 5 #\*)))
Evaluation took:
  1.556 seconds of real time
  1.555000 seconds of total run time (1.555000 user, 0.000000 system)
  [ Run times consist of 0.016 seconds GC time, and 1.539 seconds non-GC time. ]
  99.94% CPU
  3,724,401,449 processor cycles
  639,975,040 bytes consed
  
"LISP*****"

Добавлено через 1 минуту
sbcl x64 - если что.

@korvin_ · 11.02.2015, 15:37

Сообщение от nullxdth

Можно ускорить, если заранее скомпилировать.

Гм... Что-то не ускоряется:

transformator.t, ну сравни с with-output-to-string + princ:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(defmacro repeat (n &body body)
  `(loop :repeat ,n :do ,@body))
 
(defun test ()
  (let ((n 1000000))
    (time (repeat n
            (format nil "~A~v@{~A~:*~}" 'lisp 5 #\*)))
    (time (let ((fmt (formatter "~A~v@{~A~:*~}")))
            (repeat n
              (with-output-to-string (out)
                (funcall fmt out 'lisp 5 #\*)))))
    (time (let ((fmt (formatter "~A~v@{~A~:*~}")))
            (repeat n
              (format () fmt 'lisp 5 #\*))))
    (time (repeat n
            (with-output-to-string (out)
              (princ 'lisp out)
              (princ (make-string 5 :initial-element #\*) out))))
    nil))

⇒

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Timing the evaluation of (REPEAT N (FORMAT NIL "~A~v@{~A~:*~}" (QUOTE LISP) 5 #\*))
User time    =        7.004
System time  =        0.000
Elapsed time =        7.004
Allocation   = 88 041 360 bytes
0 Page faults
 
Timing the evaluation of (LET ((FMT (FORMATTER "~A~v@{~A~:*~}"))) (REPEAT N (WITH-OUTPUT-TO-STRING (OUT) (FUNCALL FMT OUT (QUOTE LISP) 5 #\*))))
User time    =        7.347
System time  =        0.000
Elapsed time =        7.355
Allocation   = 136 011 384 bytes
0 Page faults
 
Timing the evaluation of (LET ((FMT (FORMATTER "~A~v@{~A~:*~}"))) (REPEAT N (FORMAT NIL FMT (QUOTE LISP) 5 #\*)))
User time    =        7.207
System time  =        0.000
Elapsed time =        7.226
Allocation   = 100 013 692 bytes
0 Page faults
 
Timing the evaluation of (REPEAT N (WITH-OUTPUT-TO-STRING (OUT) (PRINC (QUOTE LISP) OUT) (PRINC (MAKE-STRING 5 :INITIAL-ELEMENT #\*) OUT)))
User time    =        2.308
System time  =        0.000
Elapsed time =        2.308
Allocation   = 48 006 624 bytes
0 Page faults

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

Clojure LeetCode Online Judge: Largest Number

Решение

Решение

Решение

Решение

@_sg 4708 / 4403 / 380 Регистрация: 12.05.2012 Сообщений: 3,101

	Clojure LeetCode Online Judge: Largest Number 01.02.2015, 13:09. Показов 2830. Ответов 23 Метки нет (Все метки) Дан список положительных целых чисел. Организовать их так, чтобы они образовали наибольшее число. Например, если дан список (3 30 34 5 9), то наибольшее число - 9534330. 1

@Memex 146 / 65 / 3 Регистрация: 07.05.2014 Сообщений: 38
	01.02.2015, 14:17
	Точно, у меня не то получилось, так как входные числа нельзя расщеплять на составные символы. 1

@Memex 146 / 65 / 3 Регистрация: 07.05.2014 Сообщений: 38
	01.02.2015, 14:24
	Скоро год, как я впервые познакомился с Лиспом, а до сих пор пользовался форматом для создания строк из атомов... Некрасиво вышло, есть же write-to-string! 1