参赛话题:算法题解
🎃学习算法可能是为了面试也可能是为了竞赛,记录自己写下的题目,整理成一篇精美的题解,不仅能加深自己的印象,还能帮助学习算法的他人,更主要是为了检验自己是否掌握了这道题,今天就给大家分享两道与字符串有关的题.
🎨题目描述
题目一描述
对于一个长度为 n 字符串,我们需要对它做一些变形。首先这个字符串中包含着一些空格,就像Hello World"一样,然后我们要做的是把这个字符串中由空格隔开的单词反序,同时反转每个字符的大小写。比如"Hello World"变形后就变成了"wORLD hELLO"。
数据范围: 1 ≤ n ≤ 10^6 , 字符串中包括大写英文字母、小写英文字母、空格。
进阶:空间复杂度 O(n)O(n) , 时间复杂度 O(n)O(n)
输入描述:
给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)
返回值描述:
请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。
题目二描述
给你一个大小为 n 的字符串数组 strs ,其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀,返回这个公共前缀。
数据范围: 0 ≤ n ≤ 5000, 0 ≤ len(strs) ≤ 5000
进阶:空间复杂度 O(1)O(1),时间复杂度 O(n*len)O(n∗len)
示例1
输入:
[“abca”,“abc”,“abca”,“abc”,“abcc”]
返回值:
“abc”
👑题目链接
题目二
🥁思路讲解
- 题目一
步骤一: 先通过空格将字符切割反转,然后放进一个反转数组,在将数组拼接成一个字符串
步骤二: 对字符串逐一排查,利用大小写对应的ASCII码范围判断判断字符的大小写并进行转换
- 题目二
- 步骤: 有字符串数组[“abca”,“abc”,“abca”,“abc”,“abcc”],将它的子字符串想象成如下图的结构,每一行是字符串数组的元素,每一列是要比较的字符。当我们求公共前缀时,可以用任意一个子字符串与其他子字符串比较,从第一个字符开始,逐位比较,即可找最长公共前缀。
🥉模板代码
//题目一 function trans(s, n){ //输入为空时 if(!s || !n) { return '' } let transWord = '' // 翻转 const revStrArr = s.split(' ').reverse() ;//空格分割成一个反向数组 const reverStr = revStrArr.join(' '); //通过空格连接成一个字符串 // 大小写转换 for(let i = 0;i < reverStr.length;i++){ const code = reverStr.charCodeAt(i); if(code >= 97 && code <= 122){ transWord += reverStr[i].toUpperCase() } else if(code >= 65 && code <=90){ transWord += reverStr[i].toLowerCase() } else{ transWord += ' ' } } return transWord }
//题目二 /** * * @param strs string字符串一维数组 * @return string字符串 */ function longestCommonPrefix(strs) { // write code here // 判断字符串的长度 if(!strs.length){ return ''; } let maxLeng = ''; // 以数组中第一个字符串为基准 for(let i = 0;i < strs[0].length;i++){ let j = 0; // 数组中其他字符串与第一位字符串进行逐位比较是否相等 while(j < strs.length-1){ if(strs[j][i] == strs[j+1][i]){ j++; } else{ return maxLeng; // console.log(maxLeng) } } maxLeng += strs[0][i] } return strs[0] }
🏀感想
算法非常考验一个人的逻辑和思维,所以当我们看到一个算法题的时候,不可盲目下笔,首先应该思考应该用那种方法来解决合适,同时我们也要考虑到解决这个问题会用到api文档中的那些方法,然后我们可以用注释的方式
先把步骤写下来,最后在一步步的写下代码,这样的方式来写代码,有步骤,报错也好找源头.
✨✨看完有收获的小伙伴们,来一个一键三连哦🥰