理解题目
最近在看算法的问题比较多,希望能以一道小题,来记录算法分析的过程。题目是: Pig Latin
- Pig Latin is a way of altering English Words. The rules are as follows:
- If a word begins with a consonant, take the first consonant or consonant cluster, move it to the end of the word, and add “ay” to it.
- If a word begins with a vowel, just add “way” at the end.
遇到这种描述比较少的题,第一反应是题目描述越简单,隐藏条件就会多。不慌先看维基百科 对于 Pig Latin 的解释: 猪拉丁 。我喜欢在看题目的时候,先看看维基百科,会了解下题目的背景和渊源,让自己更好的理解题目的同时,让解题也有些趣味性。简单解析下规则:当一个单词以辅音字母开头,将辅音字母移到最后,并添加 ay 比如
元音字母: a、e、i、o、u
当单词以元音字母开头的时候直接在单词后面添加way 比如
题目分析完了,我们还需要通过阅读测试用例来检查是否有遗漏,看最后一条:
- Should handle words without vowels. translatePigLatin(“rhythm”) should return “rhythmay”.
这个规则其实满足第一种情况,当找不到元音的时候,直接在后面加 ay
分析过程
当我们拿到一道算法题目的时候,按照几个套路来「攻城」
1.算法分类,这道题是字符串题,对于字符串的操作无非有两种:
a.按索引遍历
b.replace,replace 中尤其以正则不讲武德。
2.由浅入深:
a.就是上来先根据给出的条件,按照暴力的方向去写伪代码
b.在根据逻辑找关键循环因子 和 优化手段
c.尝试优化
伪代码
先写伪代码,这部分代码比较糙,主要用于整理分析过程
- VAR STR
- VAR vowelLetters = ['a','e','i','o','u']
- // 以元音开头
- IF STR[0] in vowelLetters
- return STR + 'way'
- // 在STR中找到元音索引
- FOR (S, INDEX) in STR
- IF S IN vowelLetters
- return STR.slice(INDEX) + STR.slice(0,INDEX) + 'ay'
- // 单词中没有元音
- renturn STR + ay
- 复制代码
分析过程有了我们可以写JavaScript代码了
- function translatePigLatin(str) {
- // 先准备需要的元音数组
- const vowelLetters = ['a','e','i','o','u']
- // 特殊情况:如果以元音开头
- if(vowelLetters.includes(str[0])) return `${str}way`
- // 正常情况
- for (let i = 0; i < str.length; i++) {
- if(vowelLetters.includes(str[i])) {
- return `${str.slice(i)}${str.slice(0, i)}ay`
- }
- }
- // 如果前面拦不住 说明没有元音
- return `${str}ay`
- }
- translatePigLatin("consonant");
- 复制代码
Review 上面👆代码,已经可以通过测试了,那么分析如何优化 。从代码中分析到整个核心的逻辑就落在 ${str.slice(i)}${str.slice(0, i)}ay 那么关键点在于找到 第一个元音的索引那么我们改代码
- function translatePigLatin(str) {
- // 直接找索引
- let index = str.split('').findIndex(s => /[aeiou]/.test(s))
- if(index < 0)return `${str}ay`
- if (index === 0)return `${str}way`
- return `${str.slice(index)}${str.slice(0, index)}ay`
- }
- translatePigLatin("consonant");
- 复制代码
代码简化一些,逻辑更清晰了
另一条路
从分析过程的路上来看,已经用循环遍历的方法完成了,那么另一条路(replace)应该如何实现?第一种方法的结果来看,需要用到正则分组的方法来调换位置。思路是分两组第一组是开头到元音,第二组是元音到结尾。然后将这两组顺序调换后,添加后缀。在开发和调试正则的时候,推荐 regex101.com/ 来调试正则表达式
通过调试器来完成这个正则:/([^aeiou]*)(\w*)/ 解释下
完成代码
- function translatePigLatin(str) {
- return str.replace(/([^aeiou]*)(\w*)/, '$2$1ay')
- }
- translatePigLatin("consonant");
- 复制代码
通过测试,👆上面的代码已经,除了元音在开头的情况没有覆盖,其他两种情况是包含的。元音在开头的时候,需要加的后缀为way, 也就是当 ([^aeiou]*) 匹配的不到的 $1 为空的时,后缀变成 ay 顺着这个思路完善,JavaScript 字符串 replace 方法第二个参数是支持函数的 String.prototype.replace() - JavaScript | MDN
- function translatePigLatin(str) {
- return str.replace(/([^aeiou]*)(\w*)/, (_, p1, p2) => `${p2}${p1||'w'}ay`)
- }
- translatePigLatin("consonant");
- 复制代码
总结
总结下 当拿到一道算法题的基本套路是
最后给个小建议:如果你是短期想突破面试,刷leetcode。同时推荐:https://www.codewars.com/,相比之下codewars 更注重当前编程语言的实操,而不是以最优算法为目的,里边有很多「意外惊喜」。会被很多「奇技淫巧|黑暗魔法」所折服。据坊间流传 codewars 的难度上限更高。
1. 背景 Proxy服务负责消费CKafka消息并解析,并分发消息至不同的CKafka topic。...
在十年之后,人们的生活可能发生很多变化,但与十年之后科技的变化相比就会显得...
是什么让云上流量管控如此与众不同? 一起看下原生环境的云安全不同之处! 当流...
为什么人们用手机时间的这么长?香港《南华早报》网站1月19日刊文解析原因,现将...
2020年注定是个不平凡的一年,新冠肺炎疫情全球蔓延,对全球经济发展、科技进步...
TOP云 (west.cn)12月13日消息,据米友曝料,继拿下双拼 域名 weixin.com以后,...
1.我的一生只有两件事不会,这也不会,那也不会。 2.下辈子我要做洋葱,谁欺负...
2020年11月,数据猿推出了数智跃新,破浪而出大数据的2020,我的2021大型年度主题策...
操作场景 创建裸金属服务器后,您可以通过多种方式进行登录。本文介绍在管理控制...
科学技术的不断发展,互联网信息技术的不断革新,大数据时代已经到来,大数据收...