Haskell 写几个leetcode题,代码很简单

原创
2017/12/25 16:47
阅读数 2.9K

好吧,我在某公众号看到的一个写算法的,主要是Java、C++、Python等语言,这些语言都不适合描述算法,Haskell、Ruby这样的语言描述要好的多,我看了几篇,用Haskell写了一下,剩下的就没有兴趣去写了,因为Haskell写算法真的好简单,比起C系的要简要的多。写几个实现,习惯了haskell的思维很多问题可以很简单的描述。

1.把数组分成和大小一样的集合

  • [1,5,11,5] => 11 和 1,5,5
  • [1,2,3,5] => 不能
-- 仅需要 Data.List包
import Data.List

代码:

-- 把数组分成和大小一样的集合
eqSubset xs = filter ((==1) . length . nub . (map sum)) $ nubBy (\x y -> x == y || x == (reverse y)) $ ys
            where ys = [[x,y] | x <- subsequences xs, let y = xs \\ x, not(null x) && not(null y)]

测试:

main = do
    print $ eqSubset [1,5,11,5]
    print $ eqSubset [1,2,3,5]

-- 输出 
[[[11],[1,5,5]]]
[]

在线运行结果:https://ideone.com/VW5sdp

代码很简单,就一行,最重要的是 subsequences 函数,获取所有可能的子串,ys为子串的补集,然后判断她们的和是否相等:sum x == sum y,为了避免用参数,使用的是 (==1) . length . nub . (map sum) 形式 。 使用 nubBy 过滤重复的情况:如 [11],[1,5,5]和 [1,5,5],[11]。

2.反转字串中的元音字母

  • hello => holle
  • leetcode => leotcede

代码:

-- 反转字串中的元音字母
reverseVowel ss = xymap ss . vowelXs $ ss
        where
            vowelXs = reverse . (filter isVowel)
            isVowel = flip elem "aeiouAEIOU"
            xymap xs ys = case (xs,ys) of 
                ([],_)  -> [] 
                (xs,[]) -> xs
                (x:xs',y:ys') -> if isVowel x then y:(xymap xs' ys') else x:(xymap xs' (y:ys'))

测试代码:

main = do
    print $ reverseVowel "hello"
    print $ reverseVowel "leetcode"

-- 输出
"holle"
"leotcede"

在线运行结果:https://ideone.com/QFBMsp

整个代码就跟写英语一样,我定义了两个函数 isVowel判断是否为元音,vowelXs过滤出所有元音字母,然后将其反转,生成一个子串。 xymap函数,取两个字符串,xs(原字符串),ys(元音子字符串),过程很简单,挨个取xs中的字符串,判断为元音,则同时取一个xs中的元音字符(已经被反转了的),否则保持不变。

3.重复子字符串模式,判断其是否可由一个子字符串重复多次组成

  • abab => ab (重复2次)
  • abad => 不能

返回布尔值,为了看清楚,这里返回子串,只要子串不为空,即是。

代码:

-- 重复子字符串模式,判断其是否可由一个子字符串重复多次组成
subRepeat xs = filter ((==xs) . reps) $ tail $ init $ tails xs
            where reps x =  let l = length xs 
                                n = length x
                            in  intercalate "" $ replicate (div l n) x

测试:

main = do
    print $ subRepeat "abab"
    print $ subRepeat "abcd"

-- 输出
["ab"]
[]

在线运行结果:https://ideone.com/6bVVzh 这里用 tails 生成所有的连续子串(和subsequences的区别是,tails只生成连续的子串,并且是由开始逐个减少,init 去掉尾空字符串,tail去掉首字符串自身),严格来说,应该是 map reverse $ tail $ init $ tails $ reverse $ xs 但,如果能重复组成,由后开始和由前开始应该一致,所以简要写成tail $ init $ tails xs 结果一致。

4.递增三元组子序列

满足条件 子序列,要掐头去尾,第一个和最后一个不算,然后找连续递增的三个元素。

  • [1, 2, 3, 4, 5] => [2,3,4]
  • [1, 3, 2, 4, 5] => []

这题目,两行代码,没什么要分析的:

threeAscSub (a:b:c:d:e:xs) = if b < c && c < d then [b,c,d]:(threeAscSub (b:c:d:e:xs)) else threeAscSub (b:c:d:e:xs)
threeAscSub _ = []

测试:

main = do
    print $ threeAscSub [1, 2, 3, 4, 5]
    print $ threeAscSub [1, 3, 2, 4, 5]

-- 输出
[[2,3,4]]
[]

在线运行结果:https://ideone.com/I6EyC9 真的没什么好分析的,太简单了。

5.岛的周长

以二维整数网格的形式给出地图,1代表陆地,0代表水。网格单元水平/垂直连接(不包含对角)。整张地图被水完全包围,并且有一个岛(即一个或多个连接的陆地单元)。 岛上没有“湖泊”(里面的水没有连接到岛外的水)。一个单元格是边长为1的正方形。 网格为矩形,确定岛屿的周长。 岛矩阵:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

周长: 16


import Data.List

-- 计算岛屿周长

{-
输入:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
周长:16
-}
-- 定义 series 返回一个列表中连续多个1的个数(至少2个)
-- merged 表示总共有多少个边合并被合并(每合并一条边,减少2个边)

islandLen mt = 4 * sum (map sum mt) - 2 * merged mt - 2 * merged (transpose mt)
            where 
                merged xs = sum $ map (sum . series) xs
                series xs = [y| x<- group xs, let y = length x - 1, all (==1) x && y > 0]

测试代码:


main = do
    print $ islandLen [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]

-- 输出:
16

在线运行:https://ideone.com/wHKgPo

代码的注释已经很简单了。series函数计算连续的1,比如(1, 1)这里算1个连续的1,(1,1,1)则算2个连续1。利用group将相等的值分组,然后过滤都为1,并且有连续的, merged的计算合并了的边个数,transpose将横竖交换后,继续计算合并的。每一个1代表一个岛,1个岛4个边,去掉横向合并的岛边、竖向合并的岛边,即可。

6.Snapchat面试题-青蛙跳

一只青蛙正在过河。河被分成了x段并且每一段都可能存在或不存在一个石头。这只青蛙可以跳至石头上,但不能跳进水里。

现有一个石头位置的升序列表,判断这只青蛙能否能够跳至最后一个石头,从而过河。最初青蛙在第一块石头上并且假定第一跳只能跳一段。

如果这只青蛙之前一次跳了k段,那么它的下一跳必须是k-1、k或k+1段。注意该青蛙只能向前跳。

这个题目要先准备一个小函数,用来计算前一段跳的步和余下的列表是否能继续跳,并返回所有可以跳掉最后的步骤。

import Data.List

jump k xs = case xs of
    [] -> [[]] 
    [x] -> [[]]
    (x:xs) -> concatMap (\n -> map (n:) (jump n (dropWhile (/=x+n) xs))) ys 
                where ys = map (subtract x) $ intersect [ v + x | v <- [k-1,k,k+1], v > 0 ] xs

测试该函数:

main = do
    print $ jump 1 [1,3,5]
    print $ jump 1 [1,3,4,5,6,8,12,17]

-- 输出:
[[2,2]]
[[2,2,3,4,5]]

现在只要在准备一个函数,计算第一步跳,即可: 最终函数:

frogjump [] = []
frogjump [x] = []
frogjump (x:y:xs) 
    | y - x == 1 =  let ys = jump 1 (y:xs) in if null ys then ys else map (1:) ys 
    | otherwise = []

最终结果:

main = do
    print $ frogjump [0, 1, 3, 5, 6, 8, 12, 17]
    print $ frogjump [0, 1, 2, 3, 4, 8, 9, 11]
-- 输出
[[1,2,2,3,4,5]]
[]

在线运行结果:https://ideone.com/cssMUS

这个题目主要疑点在于可以跨越跳,所以存在多种可能跳的结果。

用C、Java等命令式语言写的代码就非常冗长,而且不易读懂,而Haskell可以快速实现一个算法。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部