文档章节

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

hell0cat
 hell0cat
发布于 2017/12/25 16:47
字数 1771
阅读 128
收藏 0

好吧,我在某公众号看到的一个写算法的,主要是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可以快速实现一个算法。

© 著作权归作者所有

共有 人打赏支持
hell0cat
粉丝 37
博文 48
码字总数 24082
作品 0
徐汇
程序员
私信 提问
GitHub 与 git 笔记

关于本篇 。 其实 GitHub 和 git 的教程网上特别多 ,也很齐全 。写这个笔记出发点在于共享自己的 LeetCode 刷题代码 。所以关于介绍不会特别多 ,主要记录自己从创建仓库到上传代码的过程 ...

技术小能手
2018/07/25
0
0
找出数组中出现次数最多的前k个元素[leetcode题]

Given a non-empty array of integers, return the k most frequent elements For example,Given [1,1,1,2,2,3] and k = 2, return [1,2].https://leetcode.com/problems/top-k-frequent-ele......

hell0cat
2016/07/31
65
0
leetcode 149. Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. 题意:给一个二维平面,上面有好多点,有横纵坐标,找出一条直线,使得这条线上的点...

努力的C
2017/10/19
0
0
[oj.leetcode] 跟leecode的博客旧文说再见

在我目前的博客中,数量最多的就是leecode问题的解答。这些归在leetcode标签之下的文章,其中的绝大部分,基本就是简单一说思路,然后贴代码。 比如这种 它们的共同特征就是结构较简单,讲解...

teaspring
2015/04/12
0
0
关于LeetCode上链表题目的一些trick

最近在刷leetcode上关于链表的一些高频题,在写代码的过程中总结了链表的一些解题技巧和常见题型。 结点的删除 指定链表中的某个结点,将其从链表中删除。 由于在链表中删除某个结点需要找到...

xinyuexy
2018/10/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

cxf框架的介绍

小小小施爷
13分钟前
2
0
35K成功入职:蚂蚁金服面试Java后端经历!

上个月4号通过阿里工作的学长进行内推,7天简历评估,11号接到电话面试,尽管猝不及防回答仓促,但好在前期准备充分,通过。3天后进行现场面试,通知时间为早上10点。当日设了七点闹钟,结果...

别打我会飞
14分钟前
2
0
【HAVENT原创】让 IE6 ~ IE8 浏览器也支持 map 和 filter 方法

Array.prototype 扩展可以让 IE6 ~ IE8 浏览器也支持 map 的方法: if (typeof Array.prototype.map != "function") { Array.prototype.map = function (fn, context) { var arr = [......

HAVENT
14分钟前
2
0
SMSSDK的Unity3D的两种集成方式

SMSSDK的Unity3D插件主要为用户提供了两种集成的方式,一种是通过桥接文件直接调用SMSSDK的原生API,另外一种是集成SMSSDK_Demo中的UI,这两种方式的集成,方便用户根据自己的需要进行不同的...

佳妮
23分钟前
1
0
云计算、大数据、编程语言学习指南下载,100+技术课程免费学!这份诚意满满的新年技术大礼包,你Get了吗?

开发者认证、云学院、技术社群,更多精彩,尽在开发者会场 近年来,新技术发展迅速。互联网行业持续高速增长,平均薪资水平持续提升,互联网技术学习已俨然成为学生、在职人员都感兴趣的“业...

zhaowei121
26分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部