我不明白为什么 4clojure问题 150上的回文数谜题在我发布我的解决方案时会超时。在我本地的 REPL 上,一切都非常快。我找到了这个解决方案并且它有效,但它的性能与我的解决方案相似。我知道这是很多代码,但问题并不容易。希望评论有助于理解。
(defn palindrome [n]
(let [ ;; given a number return a string
digits (fn [^String x] (String/valueOf x))
;; given a string return the length
digits-count (fn [^String x] ( .length x) )
;; given an input sequence of digits, return a number. e.g. (seqstr (seq "1234")) => 1234
seqstr #(Long/parseLong (apply str %))
;; true when the given string has an even number of digits:
even-digits? #(even? (digits-count %))
;; return the left middle of a string. For even-digit strings returns the 'real' left part, for odd-digit strings returns one digit more.
;; e.g. (left-middle "12345678") => "1234"
;; e.g. (left-middle "1234567") => "1234"
left-middle #(if (even-digits? %)
(subs % 0 (quot (digits-count % ) 2) )
(subs % 0 (inc (quot (digits-count % ) 2))))
;; mirror a given number.
;; (mirror [1234 :even] ) => 12344321
;; (mirror [1234 :odd] ) => 1234321
mirror (fn [[num dig]]
(let [ d (seq (digits num))]
(if (= :even dig) (seqstr (concat d (reverse d)))
(seqstr (concat d (drop 1 (reverse d)))))))
;; initialize loop given a string. Returns a vector given a starting point.
;; (init "12345678") => [1234 :even 10000]
;; (init "1234567" ) => [1234 :odd 10000]
;; the first item in the vector contains the number we start the iteration with.
;; the flag indicates whether we should mirror it to an even or odd-digit number
;; the goal (power of 10) indicates when the next switch between odd/even-digit numbers will occur
init #(let [s (left-middle %)]
(vector (Long/parseLong s)
(if (even-digits? %) :even :odd)
(long (Math/pow 10 (digits-count s)))))
;; given a vector (see structure above), determine the next step
;;(next [999 :even 1000] ) => [1000 :odd 10000] . When finished mirroring even-digit numbers of length 3, continue with mirroring 4-digit odd-digit numbers
;;(next [9999 :odd 10000] ) => [1000 :even 10000]. When finished mirroring odd-digit numbers of length 4, continue with mirroring 4-digit even-digit numbers
;;(next [123 :odd 1000]) => [124 :odd 1000]. The normal case.
next (fn [[num even goal]]
(let [m (inc num)]
(if (= m goal)
(if (= even :even)
[goal :odd (* 10 goal)]
[(/ goal 10) :even goal])
[m even goal] )))
i (init (digits n))
palindromes (iterate next i) ]
(filter (partial <= n ) (map mirror palindromes))))
如果您将上面的代码粘贴到 REPL 中,您将能够评估以下单元测试:
(= (take 26 (palindrome 0))
[0 1 2 3 4 5 6 7 8 9
11 22 33 44 55 66 77 88 99
101 111 121 131 141 151 161])
(= (take 16 (palindrome 162))
[171 181 191 202
212 222 232 242
252 262 272 282
292 303 313 323])
(= (take 6 (palindrome 1234550000))
[1234554321 1234664321 1234774321
1234884321 1234994321 1235005321])
(= (first (palindrome (* 111111111 111111111)))
(* 111111111 111111111))
(= (set (take 199 (palindrome 0)))
(set (map #(first (palindrome %)) (range 0 10000))))
(= true
(apply < (take 6666 (palindrome 9999999))))
(= (nth (palindrome 0) 10101)
9102019)
对于“最慢”测试(第 5 位),我得到以下性能:
user=> (time (= (set (take 199 (palindrome 0)))
(set (map #(first (palindrome %)) (range 0 10000)))))
"Elapsed time: 66.509472 msecs"
我真的不明白 4clojure 主页上的“超时”标准是什么。在我看来,低于 1 秒的一切都应该有效。我在 JRE 7 上使用了 Clojure 1.5.1,在 JRE 6 上使用了 clojure 1.2.1。
这是我第四次尝试解决这个难题,我的大多数解决方案都在测试 5 中遇到了困难,但我没有清楚地看到说它很慢的意义。我是否使用了太多的内存?递归?我是这种语言的新手,任何很酷的提示将不胜感激:
我的第一个解决方案有点慢,但在我的机器上大约需要 600 毫秒。
(defn palindrome [n]
(let [
digits #(seq (str %)) ;; given a number return a seq of its digits
digits-count #(count (digits %)) ;; given a number return how many digits it has
seqstr #(Long/parseLong (apply str %)) ;; seq to number
start (seqstr (take (/ (digits-count n) 2) (digits n)))
digits-range #(map long (range (max (Math/pow 10 (dec %)) start) (Math/pow 10 %))) ;; return all numbers of given digits length
mirror #(let [d (digits %1)]
(if (true? %2) (seqstr (concat d (reverse d))) ;; mirror 1234 true => 12344321 even number of digits
(seqstr (concat d (drop 1 (reverse d)))))) ;; mirror 1234 false => 1234321 odd number of digits
digits-seq #(drop (/ (digits-count %) 2) (range)) ;; e.g. when input number has 10 digits, result is a seq: 5, 6, 7, 8, ....
;; when input number has 9 digits, result is a seq: 5, 6, 7, 8, ....
input-even (even? (digits-count n))
]
(filter #(<= n %) (cons 0 (mapcat #(concat (map (fn [x] (mirror x false)) (if (and input-even (* 2 %)) [] (digits-range %)))
(map (fn [x] (mirror x true )) (digits-range %)) ) (digits-seq n) )))))