当次伸手党~ Two Sum - LeetCode 看了各种题解，要么是for遍历数组要么是hashmap，不考虑性能的话，有没有更加primitive一点的lisp/scheme解法（用recursion ）
⎕IO←0
ts←{⊃(⍵⍳⍨,∘.+⍨⍺)⌷(,⍳2/≢⍺),⊂⍬}
2 7 11 15 ts 9
0 1
(define (ts vec n)
(let ([l (vector-length vec)])
(let rec ([i1 0])
(and (< i1 l)
(or
(let rec2 ([i2 0])
(and (< i2 l)
(if (= (+ (vector-ref vec i1)
(vector-ref vec i2))
n)
(list i1 i2)
(rec2 (1+ i2)))))
(rec (1+ i1)))))))
> (ts (vector 2 7 11 15) 9)
(0 1)
你会发现用 recursion 和用 for 沒什么实质区別。用 outer product 和用 hash map 本质上也一样的。
3 个赞
哇, 用scheme解算法题,
泰山压顶, 还主动拷上手链脚链.
scheme用来指导思路, 写psudocode, 用来实现, 一年半载, 觉着你做不到第十道题目.
Python呗
1)两遍遍历
import unittest
from typing import List
class Solution1:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)-1): #
complement = target - nums[i]
for j in range(i+1, len(nums)):# linear search
if complement == nums[j]:
return [i, j]
return None
- hashtable-1 (构建与查询分开)
# Two Pass hash table
class Solution2():
def twoSum(self, nums: List[int], target: int) -> List[int]:
lookup = {nums[i]:i for i in range(len(nums))}
for i in range(len(nums)):
complement = target - nums[i]
j = lookup.get(complement) #hash table to search
if j != None and j != i: # 不与前面的重复
return [i, j]
return []
3)hashtable-2 (构架与查询同时进行)
# One pass solution
class Solution3: #Single Pass Approach
def twoSum(self, nums, target) -> List[int]:
# error case
if len(nums) < 1:
return -1
lookup = {}
# 逆向的方法.
for i in range(len(nums)):
complement = target - nums[i]
if complement in lookup:
return [i, lookup[complement]]
else:
lookup[nums[i]] = i #构建lookup
# return []
1 个赞
elisp:
(defun two-sum (target nums i j)
(if (= target (+ (aref nums i) (aref nums j)))
(vector i j)
(if (< j (1- (length nums)))
(two-sum target nums i (1+ j))
(two-sum target nums (1+ i) (+ i 2)))))
(two-sum 9 [2 7 11 15] 0 1)
;; => [0 1]
3 个赞
Abstract Algebra: A Computational Approach 有个 function ssub。取 {0,1…,N} 的 K-element subset。
⎕IO←0
2 ssub 4
0 1
0 2
1 2
0 3
1 3
2 3
⎕vr 'ssub'
∇ ssub←{
[1] ⍝ LISTS ALL K-ELEMENT SUBSETS OF ⍳N. ORIGIN DEPENDENT.
[2] S←derr∧/(⍺≥0),(⍺≤⍵),(1=⍴⍺),(1=⍴⍵),(N=⌊N←,⍵),K=⌊K←,⍺
[3] K{
[4] ∨/⍺=0 1:⍺((!,⊣)⍴∘⍳⊢)⍵
[5] X←(⍳N)∘.>⍨⎕IO⌷⍉T←1+(⍺-1)∇ N←⍵-1
[6] ((,X)/(⍴,X)⍴⍳N),(+/X)⌿T
[7] }N
[8] }
这样可以写成
ts←{(⍵∊⍨+/⍺[I])/[0]I←2 ssub≢⍺}
作为练习, 将题目修改成返回数字结果[2, 7], 而非index[0, 1]
运用集合的思路: 设列表nums为集合S, 从中取出一个元素x, 然后验证x’complement(target-x), 是否在子集合S-x中.
用python实现
def two_sum(nums, target):
for x in nums:
complement = target - x
sub_nums = nums.copy()
sub_nums.remove(x)
if sub_nums.__contains__(complement):
return [x, complement]
two_sum([2, 7, 11, 15], 9)
上面python解法的hashatable1与hashtable2本质上是这个思路.
试着用elisp的primitive实现
(defun two-sum (nums target)
(try nums)
)
(defun try (nums)
(let ((copy nums)
(x (car nums))
(complement (- target x)))
(cond
((null x) '())
((memberp complement (remove-first x copy))
(list x complement))
(t (try (cdr nums)))
)))
关键逻辑是一句
((memberp complement (remove-first x copy))
将代码补全:
(defun two-sum (nums target)
(try nums)
)
(defun try (nums)
(let ((copy nums)
(x (car nums))
(complement (- target x)))
(cond
((null x) '())
((memberp complement (remove-first x copy))
(list x complement))
(t (try (cdr nums)))
)))
(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)))))
(defvar nums (list 2 7 11 15))
(defvar target 9)
(two-sum nums target)
测试运行,
let: Symbol’s value as variable is void: x
let的用法或者上面的解法有什么问题?
这里要用let*吧
1 个赞
考虑到performance，所有hashmap的实现好像都要维护一个state的，如果想要纯函数式一点，lisp/Racket中有没有实现dictionary （key-value）功能的替代品啊，就是插入key-value能返回一个新的dict
ref: hashtable - How does one implement hash tables in a functional language? - Stack Overflow
里面有提到finger tree，我还没研究
ST Monad/Single Threaded Object 了解一下。Racket 本身性能就差，还玩个几把纯函数式
嘿嘿，我这就去看看，玩Racket是因为DrRacket体验太好了，在windows下面
- 如果真的拒绝状态，想要「纯函数式」，Racket 里有 immutable hash（性能比 mutable hash 略差）；当然，你甚至还可以用 assoc list。而且它们都实现了 gen:dict 这个 generic。
- 即使是「纯函数式」语言里，ST Monad 这种也依然是状态。
- 个人愚见：two sum 这种高度面向刷题的问题，关键就是用 hashmap 降低时间复杂度吧。 如果一定要所谓的纯正函数式体验，那就递归走起，用 naive 的 O(n^2) 算法呗，这个本来就很自然。
如果是 Scheme 的话，srfi-42 eager comprehension 可以让你的编程体验好一些；如果是用 Racket 的话，用 for/first + in-indexed（针对这题）体验会好不少。
1 个赞
你这要求用前缀树就可以。
有点疑惑你学习的路径, two-sum是leetcode的第一题, 后面有对应的题目.
嘿嘿，我确实没有多明确的学习路径，只是最近工作量少了，想找个东西 摸鱼 提升自己。
leetcode我之后找工作时会用cc刷一遍的，现在用racket写纯属放松下 
厉害了, O(∩_∩)O
放松一下可以玩 Codewars / HackerRank / Project Euler 啊
1 个赞
Project Euler 太赞了！
emm… 边看common lisp文档边写的
(defun two-sum (lst tar)
(let ((ht (make-hash-table))
(l (length lst))
(n nil))
(do ((i 0 (+ i 1)))
((> i l) nil)
(setf n (gethash (- tar (car lst)) ht))
(if (numberp n)
(return-from two-sum (list n i)))
(setf (gethash (car lst) ht) i)
(pop lst))))
引理: Mathematica 是 lisp.
不考虑性能：
TwoSum[array_, target_] :=
SelectFirst[Subsets[Range[Length[array]], {2}],
Total[Part[array, #]] == target &] - 1
考虑性能 (fold 代替 recursive) :
TwoSum[array_, target_] :=
Fold[Replace[#1[target - #2], {
_?MissingQ :> Append[#1, {
#2 -> #1["length"],
"length" -> #1["length"] + 1
}],
res_ :> Throw[{res, #["length"]}]
}] &, <|"length" -> 0|>, array] // Catch