简化路径
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; };
