leetcode初级算法字符串篇

1次阅读

共计 5094 个字符，预计需要花费 13 分钟才能阅读完成。

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;
    }
};

整数反转

解析：

  1. 个位数，间接返回。
  2. 十位数及以上，转换为字符串翻转后，判断是否溢出，不溢出加上符号位返回，溢出返回 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
    }
};

验证回文字符串

解析：回文就是正着写倒着写都一样的文字。

剖析：

  1. 先过滤掉 字母和数字字符 以外的符号；
  2. 转为字符串数组，逆置字符串数组，和逆置前作比拟看是否一样。

代码：

/**
 * @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)

解析：这题就是依照规定进行一步步的过滤和解决。

剖析：

  1. 第一项只能为 +- 号或数字；
  2. 前面的项在没有小数点时能够是小数点，已有小数点就只能是数字；
  3. 判断是否能转换成数字，不能返回 0；
  4. 判断范畴是否在 32 位有符号整数范畴内；
  5. 返回后果。
/**
 * @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；

剖析：

  1. 遍历字符串 haystack；
  2. 截取以后地位到 needle 字符串长度地位的字符串；
  3. 比拟，相等则返回以后地位；
  4. 遍历结束证实不存在，返回 -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. 如何返回一个字符串的形容字符串？
  2. 如何返回给定项的形容字符串？

剖析：

  1. 获取一个形容字符串，遍历这个字符串，把间断雷同的字符的个数存起来，每次遇到不一样的值，更新形容字符串即可；
  2. 返回给定项的形容字符串，每一个形容字符串都是形容上一个字符串的，从 1 开始，始终计算到第 n 个即可；
  3. 能够退出缓存，进步性能，因为第 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
        }
      }
};
正文完
leetcode
发表至： leetcode
2020-07-14
 0
关于leetcode:读者西法记忆化递归究竟怎么改成动态规划啊
Leetcode面试题-0801-三步问题-Python实现
关于leetcode:leetcode树之二叉搜索树的最近公共祖先
关于leetcode:LeetCode-133-克隆图-Python

站内搜索

-「」