leetcode高级算法(字符串篇)
注：点题目能够查看对应的题目，本文代码均应用Javascript编写。代码不肯定是最优解，仅供参考，如仁兄有更好的实现，欢送交换。
反转字符串
解析：要原地扭转数组，第一次循环替换第一个和数组最初一个值，第二次替换第二个和数组倒数第二个值，顺次类推。每次替换两个值，循环数组长度的1/2次即可。其实用javascript内置办法reverse，一行代码就搞定了，然而这毕竟是算法题，不本人想进去也没啥必要练了。
代码：
/** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */var reverseString = function(s) { var len = s.length; for(var i = 0; i < len / 2; i++){ var temp = s[i]; s[i] = s[len - 1 - i]; s[len - 1 - i] = temp; }};整数反转
解析：
- 个位数，间接返回。
- 十位数及以上，转换为字符串翻转后，判断是否溢出，不溢出加上符号位返回，溢出返回0。
代码：
/** * @param {number} x * @return {number} */var reverse = function(x) { var absX = Math.abs(x); // 取绝对值 // 个位数间接返回 if(absX >= 0 && absX <= 9){ return x; } var reverse = absX.toString().split('').reverse().join(''); // 转换成字符串数组，反转数字，在变回字符串 if(+reverse > 2 ** 31 - 1){ // 溢出返回0 return 0; }else{ // 加上原来的符号返回 if(x > 0){ return +reverse; }else{ return -reverse; } }};字符串中的第一个惟一字符
解析：每次取一个字符和其余字符进行比拟，比拟完没有反复则返回索引，所有字符都比拟完都没有呈现不反复的，则返回-1。
代码：
/** * @param {string} s * @return {number} */var firstUniqChar = function(s) { var repeatItems= {}; var len = s.length; for(var i = 0; i < len; i++){ var cur = s[i]; // 以后值 var hasRepeat = false; // 以后索引的值已比拟过，是有反复的值，无需进行再次比拟 if(repeatItems[i]){ continue; } // 顺次和原字符串的每一个值做比拟 for(var j = 0; j < len; j++){ // 跳过和本人比拟 if(i === j){ continue; } // 发现有反复的值，标记以后值有反复，记录反复值索引，下次无需再次比拟 if(s[j] === cur){ repeatItems[j] = true; hasRepeat = true; } } // 比拟实现后没有反复的值，返回索引 if(!hasRepeat){ return i; } } return -1;};无效的字母异位词
解析：解释一下字母异位词，同样的几个字母，只是字母摆放程序不同的词。
剖析：
1. 字母异位词数组长度肯定是一样的； 2. 字母异位词蕴含的字母也是一样的，不会存在一个字母在第一个词中有，第二个词中没有的状况。代码：
/** * @param {string} s * @param {string} t * @return {boolean} */var isAnagram = function(s, t) { if(s.length !== t.length){ // 长度不一样间接返回false return false; }else{ var arrT = t.split(''); // 将字符串t转为数组 for(var i = 0; i < s.length; i++){ var index = arrT.indexOf(s[i]); // 查找t中和以后字母雷同的索引 if(index === -1){ // 找不到一样的值返回false return false; }else{ arrT.splice(index, 1); // 删除t中找过的值，避免问题 } } return true; // 比拟完还没有发现找不到的值，返回true }};验证回文字符串
解析：回文就是正着写倒着写都一样的文字。
剖析：
- 先过滤掉字母和数字字符以外的符号；
- 转为字符串数组，逆置字符串数组，和逆置前作比拟看是否一样。
代码：
/** * @param {string} s * @return {boolean} */var isPalindrome = function(s) { if(s === null || s === undefined){ return false; } // 空字符串和空串返回true if(s === ' ' || s === ''){ return true; } // 只有一个字符返回true if(s.length === 1){ return true } var strArr = s.toLowerCase().match(/[a-zA-Z0-9]/g); // 对立转换成小写，过滤符号 // 过滤完之后数字字符之后是空返回true if(!strArr){ return true; } var reverseStr = strArr.slice(0, strArr.length).reverse().join(''); // 逆置字符串 if(strArr.join('') === reverseStr){ // 比拟逆置前后是否相等 return true; }else{ return false; }};字符串转换整数 (atoi)
解析：这题就是依照规定进行一步步的过滤和解决。
剖析：
- 第一项只能为+-号或数字；
- 前面的项在没有小数点时能够是小数点，已有小数点就只能是数字；
- 判断是否能转换成数字，不能返回0；
- 判断范畴是否在32 位有符号整数范畴内；
- 返回后果。
/** * @param {string} str * @return {number} */var myAtoi = function(str) { var res = ''; var reg = /[0-9\+-]/; // 匹配数字和+-号 var INT_MIN = 2147483648; // 32位有符号整数范畴 for(var i = 0; i < str.length; i++){ var cur = str[i]; // 以后字符 if(res.length === 0){ // 判断第一项 if(reg.test(cur)){ // 能够为数字或+-号 res += cur; } if(!reg.test(cur) && cur !== ' '){ // 遇到不是数字和+-号和空格的，跳出循环 break; } }else{ // 判断后续项 if((cur === '.' && !res.includes('.')) || /[0-9]/g.test(cur)){ // 没有小数点时能够为小数点或数字，有小数点只能是数字 res += cur; } if(!/[0-9]/g.test(cur)){ // 不是数字的时候跳出循环 break; } } } var res = +res; // 将字符串转为数字 if(isNaN(res)){ // 转换不胜利返回0 return 0; } if(res < -INT_MIN){ // 溢出判断 return -INT_MIN; }else if(res > INT_MIN - 1){ return INT_MIN - 1; } return res;};实现 strStr()
解析：查找一个字符串haystack中是否蕴含另一个字符串needle，有则返回呈现在haystack的地位，没有则返回-1，如果needle为空字符串，返回0；
剖析：
- 遍历字符串haystack；
- 截取以后地位到needle字符串长度地位的字符串；
- 比拟，相等则返回以后地位；
- 遍历结束证实不存在，返回-1。
代码：
/** * @param {string} haystack * @param {string} needle * @return {number} */var strStr = function(haystack, needle) { if(needle === ''){ // 空字符串返回0 return 0; }else{ var index = 0; // 记录找到的地位 var needleLen = needle.length; for(var i = 0; i < haystack.length; i++){ // 在以后地位截取和needle字符串长度雷同的子串和needle进行比拟，相等则返回以后地位 if(haystack.slice(i, i + needleLen) === needle){ return i; } } return -1; // 遍历实现，找不到雷同的字符串，返回-1 }};外观数列
解析：能够分为两个子问题
- 如何返回一个字符串的形容字符串？
- 如何返回给定项的形容字符串？
剖析：
- 获取一个形容字符串，遍历这个字符串，把间断雷同的字符的个数存起来，每次遇到不一样的值，更新形容字符串即可；
- 返回给定项的形容字符串，每一个形容字符串都是形容上一个字符串的，从1开始，始终计算到第n个即可；
- 能够退出缓存，进步性能，因为第n项的形容字符串依赖第n-1个字符串，如果缓存第n-1个字符串，则无需从头开始计算。
// 给一个字符串，返回形容这个字符串的字符串function getDescriptionString(str){ var curStr = str[0]; // 取字符串第一字符为以后形容字符 var curCount = 1; // 以后形容字符呈现的次数，一开始必定有一个 var describeStr = ''; // 初始化形容字符串 for(var i = 1; i < str.length; i++){ // 从字符串第二项开始比拟 if(curStr === str[i]){ // 如果和以后形容字符雷同 curCount++; // 以后形容字符的个数加1 }else{ // 如果和以后形容字符不同 describeStr += curCount + curStr; // 形容字符串加上累加后的以后形容字符 curStr = str[i]; // 更新以后形容字符 curCount = 1; // 充值以后形容字符个数 } } describeStr += curCount + curStr; // 加上最初一次形容字符和他的个数 return describeStr;}var descriptions = ['1']; // 缓存已形容的数据/** * @param {number} n * @return {string} */var countAndSay = function(n) { if(descriptions[n-1]){ // 如果缓存数组中存在以后项的形容字符串，间接返回 return descriptions[n-1]; }else { for(var i = descriptions.length; i < n; i++){ // 如果不存在，从缓存字符串的最初一项开始，获取到第n项形容字符串 const desctiptionStr = getDescriptionString(descriptions[i-1]); // 依据上一项的形容字符，获取以后的形容字符串 descriptions.push(desctiptionStr); // 缓存 if(i === n - 1){ // 返回后果 return desctiptionStr; } } }};最长公共前缀
解析：初始化公共前缀为空字符串，判断每一个字符长的第i位，如果相等，公共前缀加上第i位的字符，如果有一个不相等，返回公共前缀。
/** * @param {string[]} strs * @return {string} */var longestCommonPrefix = function (strs) { if(!strs || strs.length === 0){ // 严谨性判断，传入空或空字符串间接返回 return ""; } var result = ""; // 最长公共前缀 var index = 0; // 最长公共前缀的索引 while (1) { var char = strs[0][index]; // 以第一个字符为基准字符串 if (!char) { // 如果以后字符不存在 return result; } else { for (var i = 1; i < strs.length; i++) { if (!strs[i][index] || strs[i][index] !== char) { // 如果有一个字符中的第index个字符不存在或者不等于以后基准字符，跳出循环 return result; } } result += char; // 退出以后在所有字符串中都存在的字符 index++; // 索引加1 } }};