理解题目
最近在看算法的问题比较多,希望能以一道小题,来记录算法分析的过程。 题目是: Pig Latin
遇到这种描述比较少的题,第一反应是题目描述越简单,隐藏条件就会多。不慌先看维基百科 对于 Pig Latin 的解释: 猪拉丁 。 我喜欢在看题目的时候,先看看维基百科,会了解下题目的背景和渊源,让自己更好的理解题目的同时,让解题也有些趣味性。
简单解析下规则:
当一个单词以辅音字母开头,讲辅音字母已到最后,并添加 ay
比如
california
→aliforniacay
:c
移动到最后然后添加ay
paragraphs
→aragraphspay
:p
移动到最后然后添加ay
glove
→oveglay
:gl
移动到最后然后添加ay
⚠️ 这里是找到第一个元音字母之前的所有辅音字母
当单词以元音字母开头的时候直接在单词后面添加way
比如
algorithm
→algorithmway
:a
是元音字母所以在单词后添加way
eight
→eightway
:e
是元音字母所以在单词后添加way
题目分析完了,我们还需要通过阅读测试用例来检查是否有遗漏,看最后一条:
这个规则其实满足第一种情况,当找不到元音的时候,直接在后面加 ay
分析过程
当我们拿到一道算法题目的时候,按照几个套路来「攻城」
- 算法分类,这道题是字符串题,对于字符串的操作无非有两种:
- 按索引遍历
- replace,replace 中尤其以正则不讲武德。
- 由浅入深:
- 就是上来先根据给出的条件,按照暴力的方向去写伪代码
- 在根据逻辑找关键循环因子 和 优化手段
- 尝试优化
伪代码
先写伪代码,这部分代码比较糙,主要用于整理分析过程
分析过程有了我们可以写JavaScript代码了
Review 上面?代码,已经可以通过测试了,那么分析如何优化 。
从代码中分析到整个核心的逻辑就落在 ${str.slice(i)}${str.slice(0, i)}ay
那么关键点在于找到 第一个元音的索引那么我们改代码
代码简化一些,逻辑更清晰了
另一条路
从分析过程的路上来看,已经用循环遍历的方法完成了,那么另一条路(replace)应该如何实现?
第一种方法的结果来看,需要用到正则分组的方法来调换位置。
思路是分两组第一组是开头到元音,第二组是元音到结尾。然后将这两组顺序调换后,添加后缀。
在开发和调试正则的时候,推荐 regex101.com/ 来调试正则表达式
通过调试器来完成这个正则:/([^aeiou]*)(\w*)/
解释下
- 用两个括号,分成两组
([^aeiou]*)
表示匹配不是(^
)aeiou 的0到多个字符。(\w*)
剩下字符是一组
完成代码
通过测试,?上面的代码已经,除了元音在开头的情况没有覆盖,其他两种情况是包含的。元音在开头的时候,需要加的后缀为way
, 也就是当 ([^aeiou]*)
匹配的不到的 $1
为空的时,后缀变成 ay
顺着这个思路完善,JavaScript 字符串 replace 方法第二个参数是支持函数的 String.prototype.replace() - JavaScript | MDN
总结
总结下 当拿到一道算法题的基本套路是
- 分类,是那一类的题,分完类后基本上能确定方向,比如树的题大部分都要用到递归,如果你想刻意训练递归,可以在树分组下训练。
- 先分析题目逻辑,先用简单粗暴的方法把逻辑的伪代码写出来,然后再突破优化。
- Review 其他方向上是否有更优解。
最后给个小建议:如果你是短期想突破面试,刷leetcode。同时推荐:https://www.codewars.com/ ,相比之下codewars 更注重当前编程语言的实操,而不是以最优算法为目的,里边有很多「意外惊喜」。会被很多「奇技淫巧|黑暗魔法」所折服。 据坊间流传 codewars 的难度上限更高。
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!