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
}
}
};
发表回复