记一次失败的大厂笔试（字符串处理算法，附带答案）
最近忙于找新工作，所以各种投简历，作为一个程序员，应该都有一颗想去大厂的心，所以我也硬着头皮投了一下华为的简历。于是乎，收到了一个笔试，其实就是一个算法题，总分200分，达到120分算合格。在做题之前，还收到了友情提示，多刷牛客网上的题，可以提高通过率。但自己当时求职心切，哪听得进去，去牛客网看了五道题左右，实在没心思看下去了，就放弃了，第二天直接开始做题。
题目是这样的，给定一个字符串，找出其中由一个字母组成的连续出现的次数最长的字符串，如果有多个长度相同的，就返回其中ASCII 码最小的字母组成的那个。
比如下面两个字符串：
|
1 2 3 |
str1 = 'aaaaabbbbbbbbbccccccdddddd' str2 = 'aaaaabbbbbbbbbccccccbbbbbbbbbbbbbbbbddddddeeeeeeeeeeeeeeee' |
第一个返回 ‘bbbbbbbbb’，因为b 连续出现的次数最多，第二个返回 ‘eeeeeeeeeeeeeeee’，虽然 b 第二次连续出现的长度跟 e 相等，但 b 的 ASCII 码 小于 e 的。
说实话，当时给的解题时间是90分钟，包括看答题规则，读题时间和做题时间，但我却没做得出来，很大的一个原因就是我当时的解题思路出了问题（但按我的解题思路来做，是行得通的），这也是我写本文做这个记录的原因。
先说一下我当时的解题思路：首先，从大的层面来讲，我们先定义一个对象，然后循环处理字符串，以出现的不同的字母为属性名，字母连续出现的次数作为属性值进行存储，比如，就上面第一个字符串来说，我们处理完后，会得到这样一个对象
|
1 2 3 4 5 6 |
obj1 = { a:5, b:9, c:6, d:6 } |
当字符串处理完成后，去找我们存储对象里面的属性值最大的那个key，如果有多个，再比较 ASCII 码，这样便能解题。我想，刚看到题目的时候，跟我一个解题思路的肯定还有其他人。
大致思路有了后，再来说说我当时的具体实现逻辑：
1、声明一个空对象 obj，一个空字符串 pre；
2、让 pre 等于第一个字母，循环字符串，当下一个字母跟pre相等时， pre 长度加一，当下一个字符串 next 不等于pre 时，说明第一个出现的字母连续已经中断，这时便能知道 pre 的连续长度，存入 obj，同时让 pre 等于 next；
3、如果遇到某个字母 N 在 obj 的属性中已经存在，则声明一个临时变量来存 N 的长度，当 N 循环结束后，看临时变量的长度和 obj 里的 N 的长度哪个大，让 obj 里的 N 的长度等于大的那个即可；
4、循环执行 2，3， 直到字符串处理完成，得到完整的 obj；
5、从 obj 里找最长，多个最长时取 ASCII 码最小即可。
我自认为我的思路是行得通的，但当时在 2 和 3 步骤时花了太多时间，前期也走了一些弯路，导致最终在限制的时间里连代码都没来得及提交，所以以失败告终。
考试结束后，我又重新思考了一遍问题，发现了几个我当时忽略的点。
1、既然最终返回的字符串只有一个，那我用一个临时字符串变量即可，每次都保存最长的且 ascll 最小的，减少空间复杂度；
2、字符串的处理不要用循环，改成正则匹配，那么对于连续出现的字符串，减少时间复杂度；
趁今天做离职交接，手上没事，所以打算重新做一遍，果然，方向还是很重要的，理清思路后，几分钟搞定。附上实现代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
function findLongSingle(str){ var lastStr = '' while(str.length){ var firstLetter = str.charAt(0) // 这个地方用 new 的方式创建，得到的正则类似于 /^a+/， // 用+ 不用 * 的原因，是字母来自字符串第一个，一定会出现一次 var reg = new RegExp('^' + firstLetter + '+') var matchStr = str.match(reg)[0] // 后一个比前一个更长时 if(matchStr.length > lastStr.length){ lastStr = matchStr } // 其实这里的判断可以和上面的放在一个 if 里 // 两个一样长时，比较 ascll 码 if(matchStr.length === lastStr.length && firstLetter.charCodeAt() < lastStr.charAt(0).charCodeAt()){ lastStr = matchStr } str = str.slice(matchStr.length) } return lastStr } var str1 = 'aaaaabbbbbbbbbccccccdddddd' var str2 = 'aaaaabbbbbbbbbccccccbbbbbbbbbbbbbbbbbbbbbbdddddd' var str3 = 'aaaaabbbccccccbbbbbbbbbbbbbbbbddddddeeeeeeeeeeeeeeee' console.log(findLongSingle(str1)) // bbbbbbbbb console.log(findLongSingle(str2)) // bbbbbbbbbbbbbbbbbbbbbb console.log(findLongSingle(str3)) // bbbbbbbbbbbbbbbb |
啊，简直了，真为自己失去的机会感到可惜，虽然后面面试也不一定会过。
有时间把我说的第一种思路再实现一遍，到时候补充在这里。
———————————
更新于2020年4月10日14:10:48，第一种思路的实现。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
// 遍历字符串，获取各个字母的最长字符串 function findLongLetter(str){ var prev = str.charAt(0) var obj = { [prev]:prev } var tempLetter = '' var tempStr = '' for(var i = 1; i<str.length; i++){ var letter = str.charAt(i) // 特别注意，当一个字母不是首次出现时，一定要判断 tempLetter != letter if(letter === prev && tempLetter != letter){ obj[prev] = obj[prev] + letter }else{ // 一旦字母跟上一个不一样 prev = letter // 同时处理临时字符串 if(tempLetter && tempLetter != letter){ if(tempStr.length > obj[tempLetter].length){ obj[tempLetter] = tempStr } tempLetter = '' tempStr = '' } // 看是否已经在 obj 中 if(obj[letter]){ // 如果在，存入临时变量 tempLetter = letter tempStr += letter }else{ // 如果不在 obj[letter] = letter // 添加新key } } } return(obj) } // 遍历对象，取最长字符串 function findBestLong(str){ var obj = findLongLetter(str) var tempStr = '' for(var k in obj){ if(obj[k].length > tempStr.length){ tempStr = obj[k] } if(obj[k].length === tempStr.length && k.charCodeAt() < tempStr.charAt(0).charCodeAt()){ tempStr = obj[k] } } return tempStr } |
运行结果和上面一致，虽然做出来了，但逻辑确实有点绕，不知道有没有遗漏的点，如果发现，还望告知。
———————————
发表评论