本期有3道题目，类似题型常见于大厂的面试题，涉及到的编程技巧是栈、回文子串的计算、字符串转数字的细节操作等等。
简化路径
LeetCode.71，难度中等
题目
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入："/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入："/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入："/a/./b/../../c/" 输出："/c"
示例 5：
输入："/a/../../b/../c//.//" 输出："/c"
示例 6：
输入："/a//b////c/d//././/.." 输出："/a/b/c"
思路
通过这几个示例可以看出来：在一个路径中遇到'/'和'.'，不用理会；在路径中遇到'..'，则此时的父路径弹出。可以考虑到使用栈的特点，刚好符合路径的先进后出和弹出。 代码如下：
/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function(path) {
if(path === '/')
return path;
let stack = path.split('/');
let res = [];
while(stack.length !== 0) {
const cur = stack.shift();
if(cur !== '..' && cur !== '.' && cur !== '/' && cur !== '') {
res.push(cur);
} else if(cur === '..') {
res.pop();
}
}
return '/' + res.join('/');
};
最长回文子串
LeetCode.5，难度中等
题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd" 输出: "bb"
思路
对于字符串'babad'来说，存在最长回文子串'bab'可以转化为存在一个最长回文子串中心字符'a'，且它的左边的字符和右边的字符相同；因此可以遍历字符串中的每一个字符，并且对每一个字符为中心，来进行两边的延展。 因为要对字符串做一次遍历，且每次遍历中会对中心字符做两边扩展，所以时间复杂度为O(N)。 代码如下：
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if(s.length < 2)
return s;
let res = '';
for(let i = 0;i < s.length;i++) {
const str1 = processCenter(i, i, s);
const str2 = processCenter(i, i+1, s);
const longerStr = str1.length > str2.length ? str1 : str2;
res = longerStr.length > res.length ? longerStr : res;
}
return res;
};
var processCenter = function (left, right, str) {
let L = left, R = right;
while(L >= 0 && R < str.length) {
if(str[L] !== str[R]) {
break;
}
L--;
R++;
}
if(R-1 < L+1)
return '';
return str.substring(L+1, R);
}
更好的思路 可参考Manacher算法：oi-wiki.org/string/mana…
字符串转换整数 (atoi)
腾讯面试中出现过，LeetCode.8，难度中等
题目
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42" 输出: 42
示例 2:
输入: " -42" 输出: -42 解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words" 输出: 4193 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987" 输出: 0 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。
示例 5:
输入: "-91283472332" 输出: -2147483648 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。
思路
通过例子可以看出来，主要有以下几个注意点：
- 最左边的符号位要保留住
- 从左侧开始只保留数字
- 不能超出32位有符号整数范围
代码如下
/**
* @param {string} str
* @return {number}
*/
var myAtoi = function(s) {
s = s.trim();
if(!/[0-9]/.test(s[0]) && s[0] !== '-' && s[0] !== '+')
return 0;
let isNegative = false;
if(s[0] === '-' || s[0] === '+') {
isNegative = s[0] === '-' ? true : false;
s = s.slice(1);
}
let arr = [];
for(let i = 0;i < s.length;i++) {
if(/[0-9]/.test(s[i]))
arr.push(+s[i])
else
break;
}
let res = 0;
for(let i = 0;i < arr.length;i++) {
res = res + arr[i]*Math.pow(10, arr.length-1-i);
}
res = isNegative ? -res : res;
if(res < -Math.pow(2, 31))
return -Math.pow(2,31);
if(res > Math.pow(2, 31)-1)
return Math.pow(2, 31)-1;
return res;
};
欢迎关注公众号前端亚古兽，更多前端和编程知识
