反转字符串
题目：请编写一个函数，其功能是将输入的字符串反转过来。示例：
输入：s = "hello"
返回："olleh"
分析：js字符串可以通过调用split转换成数组，然后通过调用数组reverse方法反转，最后再调用join将字符串转换成数组。
代码：
/**
* @param {string} s
* @return {string}
*/
var reverseString = function(s) {
return s.split("").reverse().join("");
};
执行时间：100ms
完成日期：2018-05-08
leetcode案例
/**
* @param {string} s
* @return {string}
*/
var reverseString = function(s) {
return s.split('').reduce((total, value) => value + total, '');
};
执行时间：84ms
分析：reduce方法接收一个函数作为累加器，数组中的每个值（从左到右）开始缩减，最终计算为一个值。上述代码中的函数实际上是return total = value + total， total初始值是数组第1个元素，value从第2个元素开始遍历数组。
颠倒整数
分析：做法和翻转字符串的方法相似，只不过多做了一次数字转换字符串和字符串转换数字，并判断翻转后是否在合理范围里。
代码：
/**
* @param {number} x
* @return {number}
*/
var reverse = function(x) {
const MIN_VAL = -Math.pow(2,31);
const MAX_VAL = -MIN_VAL;
var reNum;
var flg = x > 0 ? true : false; // 正负标志位
reNum = parseInt(x.toString().split("").reduce((total, value) => value + total));
if (reNum >= MIN_VAL && reNum <= MAX_VAL) {
return flg ? reNum : -reNum;
} else {
return 0;
}
};
执行时间：96ms
完成日期：2018-05-08
leetcode案例
/**
* @param {number} x
* @return {number}
*/
var reverse = function(x) {
var res = 0;
var symbol = x > 0;
x = x > 0?x:-x
while(x != 0){
res = res * 10 + Math.floor(x) % 10;
x = Math.floor(x / 10)
}
if(res>Math.pow(2,31)-1) return 0;
return symbol?res:-res;
};
执行时间：72ms
分析：对数字模十取余可得到它的最低位。每次将结果的十倍与x最低位相加。
字符串中的第一个唯一字符
分析：先声明一个对象，对象的结构是：
{
str:[flg,index]
}
我们可在遍历字符串的同时，将字符串中的字符出现次数做一个统计，出现次数超过1次的记为false，出现1次的记为true，并且记录下索引。最后再遍历对象，找到第一个flg = true的元素并返回其索引。
代码：
/**
* @param {string} s
* @return {number}
*/
var firstUniqChar = function(s) {
var countObj = {};
var index;
for (var i = 0; i < s.length; i++) {
if (countObj[s[i]]) {
countObj[s[i]] = [false, i];
} else {
countObj[s[i]] = [true, i];
}
}
for(var key in countObj) {
if (countObj[key][0]) {
index = countObj[key][1];
break;
}
}
return index == undefined ? -1 : index;
};
执行时间：124ms
完成日期：2018-05-10
leetcode案例
/**
* @param {string} s
* @return {number}
*/
var firstUniqChar = function(s) {
var str = s.toLowerCase();
for(var i=0;i<str.length;i++){
var ch = str.charAt(i);
//如果ch后面没有该字符，且ch前面也没有出现过
if(str.indexOf(ch,i+1) == -1 && str.indexOf(ch) == i){
return i;
}
}
return -1;
};
执行时间：92ms
分析：indexOf(searchvalue, start) 方法可返回某个指定的字符串值在字符串中首次出现的位置。
- searchvalue：必需。规定需检索的字符串值。
- start：可选的整数参数。规定在字符串中开始检索的位置。它的合法取值是 0 到 string Object.length - 1。如省略该参数，则将从字符串的首字符开始检索。
有效的字母异位
分析：比较简洁的思路是直接遍历两个字符串，统计字符串中字符出现的次数，然后对比每个字符出现的次数是否一致即可。（此法对于字符串包含unicode字符同样适用）
代码：
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function(s, t) {
if (s.length == t.length) {
let objS = {};
let objT = {};
// 统计每个字符出现次数
for (let i = 0; i < t.length; i++) {
if (objT.hasOwnProperty(t[i])) {
objT[t[i]]++;
} else {
objT[t[i]] = 0;
}
if (objS.hasOwnProperty(s[i])) {
objS[s[i]]++;
} else {
objS[s[i]] = 0;
}
}
for (var key in objS) {
if (objS[key] != objT[key]) {
return false;
}
}
return true;
} else {
return false;
}
};
执行时间：128ms
完成日期：2018-05-11
leetcode案例
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function (s, t) {
var len = s.length;
const map = {
a: 0, b: 0, c: 0, d: 0, e: 0, f: 0, g: 0, h: 0, i: 0, j: 0, k: 0, l: 0, m: 0, n: 0, o: 0, p: 0, q: 0, r: 0, s: 0, t: 0, u: 0, v: 0, w: 0, x: 0, y: 0, z: 0
};
if (len !== t.length) {
return false;
}
for (let i = 0; i < len; i++) {
map[s[i]]++;
map[t[i]]--;
}
for (let k in map) {
if (map[k] !== 0) {
return false;
}
}
return true;
};
执行时间：68ms
分析：此处用的也是计数法，不同的是操作的是同一个对象。同字符次数相抵消，只要最后map中每个字符的个数与声明时保持一致即为true。不过此方法不适用于字符串包含unicode字符的情况。
验证回文字符串
分析一：回字符串是一个正读和反读都一样的字符串，比如level或者noon等等。不知道我对题目的理解有偏差还是题目有些问题，题中特意点明：将空字符串定义为有效的回文串。 我理解为空字符串也会考虑在内，但是显然与示例1相悖。所以我们此处只考虑字符串中的数字和字母即可。
首先，我们将字符串转换成小写，然后通过正则表达式过滤，只保留数字和字母。接着利用split、reverse、join方法把字符串翻转，最后对比翻转后的字符串即可。
代码：
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
//var newS = s.toLowerCase().replace(/[^a-z0-9 ]/g,''); // 若空格视为回文一部分时使用。
var newS = s.toLowerCase().replace(/[^a-z0-9]/g,'').split("").reverse().join("");
if (newS === s.toLowerCase().replace(/[^a-z0-9]/g,'')) {
return true;
} else {
return false;
}
};
执行时间：112ms
分析二：使用match方法，对匹配到的字符会以数组形式返回。
代码：
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// 将字符串转换小写，并用正则只保留字母、数字和空格
//s = s.toLowerCase().match(/[a-z0-9 ]/g,'');
var newS = s.toLowerCase().match(/[a-z0-9]/g);
if (newS) {
if (newS.reverse().join("") === s.toLowerCase().match(/[a-z0-9]/g).join("")) {
return true;
} else {
return false;
}
}
return true;
};
执行时间：156ms
完成日期：2018-05-12
leetcode案例
案例一：
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
s = s.toLowerCase().replace(/\W|\s+/g,"");
console.log(s);
for (var i = 0; i < Math.ceil(s.length/2); i++) {
if (s[i] != s[s.length-i-1]) {
return false;
}
}
return true;
};
执行时间：72ms
分析：根据回文的定义，我们可知：
第1个元素 = 第n个元素
第2个元素 = 第n-1个元素
第3个元素 = 第n-2个元素
第4个元素 = 第n-3个元素
......
所以n个元素比较的次数：n/2 (若为回文，2必定整除n)。
显然，以上若有一个是不相等，必定不是回文，所以此算法比之前两个算法少了一些不必要的计算。
正则表达式：
\W 元字符用于查找非单词字符。单词字符包括：a-z、A-Z、0-9，以及下划线。
\s 元字符用于查找空白字符
案例二：
var isPalindrome = function (s) {
s = s.replace(/[^\w]/g, "")
if (s.length == 0) return true
var start = 0, end = s.length - 1
while (start < end) {
if (!s[start] || !s[end]) {
return false
}
if (s[start].toLowerCase() != s[end].toLowerCase()) {
return false
}
start++
end--
}
return true
};
执行时间：68ms
分析：此案例的思想同上。
正则表达式：
\w 元字符用于查找单词字符。
单词字符包括：a-z、A-Z、0-9，以及下划线, 包含 _ (下划线) 字符。
字符串转整数（atoi）
分析： 首先判断传入字符串是否包含数字，不包含直接返回0，若包含，则去掉字符串两端空字符串（减少遍历次数）。接着判断处理好的字符串首位是否为正负号、数字，符合条件则开始从字符串第二位开始遍历，若为数字则累加，反之中断循环。最后将原字符串首位与结果字符串result拼接，并转换成数字，判断范围。
代码：
/**
* @param {string} str
* @return {number}
*/
var myAtoi = function(str) {
// 判断字符串是否包含数字
let regx = /\d/;
if (regx.test(str)) {
const INT_MIN = -2147483648;
const INT_MAX = 2147483647;
// 去掉两端空字符串
str = str.trim();
let result = "";
if (str[0] == "-" || str[0] == "+" || regx.test(str[0])) {
for (let i = 1; i < str.length; i++) {
if (regx.test(str[i])) {
result+= str[i];
} else {
break;
}
}
result = Number(str[0] + result);
if (result < INT_MIN) {
return INT_MIN;
} else if (result > INT_MAX) {
return INT_MAX;
} else {
return result ? result : 0;
}
} else {
return 0;
}
} else {
return 0;
}
};
执行时间：104ms
完成日期：2018-05-16
leetcode案例
/**
* @param {string} str
* @return {number}
*/
var myAtoi = function (str) {
let i = 0
while (str[i] == " ") i++
let sign = 1
if (str[i] == "-" || str[i] == "+") {
if (str[i] == "-") sign = -1
i++
}
let num = 0
while (i < str.length) {
if (str.charCodeAt(i) >= 48 && str.charCodeAt(i) <= 57) {
num = num * 10 + parseInt(str[i])
i++
} else {
break
}
}
num *= sign
let max = 2
for (let n = 0; n < 30; n++)
max *= 2
if (num >= max)
return max - 1
if (num <= -max)
return -max
return num
};
执行时间：80ms
分析：从头开始遍历，通过sign标志位判断正负，str.charCodeAt(i) >= 48 && str.charCodeAt(i) <= 57 在unicode编码48-57的为数字。最后通过循环判断是否符合整数范围。
实现strStr()
分析一：直接利用js字符串的indexOf方法
代码：
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
return haystack.indexOf(needle);
};
执行时间：58ms
分析二：先判断是否为空字符串，再判断是否两个字符串相同。最后若haystack包含needle，则利用正则表达式和replace方法，将needle及其后的所有字符全部去掉，所以haystack剩余字符串的长度即为我们所需结果。
代码：
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
let regx = /\s/;
if (regx.test(needle)) {
return 0;
}
if (haystack === needle) {
return 0;
}
// 若haystack包含needle
if (haystack.includes(needle)) {
let patt = new RegExp(`${needle}[a-zA-Z]*`);
haystack = haystack.replace(patt, "");
return haystack.length;
} else {
return -1;
}
};
执行时间：76ms
完成日期：2018-05-17
leetcode案例
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function (haystack, needle) {
const slen = haystack.length
const plen = needle.length
if (slen == plen) {
return haystack == needle ? 0 : -1
}
for (let i = 0; i <= slen - plen; i++) {
let j
for (j = 0; j < plen; j++) {
if (haystack[i + j] != needle[j]) {
break
}
}
if (j == plen) return i
}
return -1
};
执行时间：52ms
分析：暴力法，通过两阶for循环，逐一比较haystack和needle，i 指向haystack 的起始，j 指向 needle 的起始；首先 i 向后走，直至haystack[i] == needle [j]; 然后 j 往后走，如果haystack[i+j] != needle [j] 跳出，如果能走 m 步，即存在相同，返回i；如果存在不匹配，则haystack 后移后，从needle[0]重新比较。此处时间复杂度是O(slen * plen)，但是执行时间却是52m（用时较短），leetcode给这个时间我就不吐槽了。
数数并说
分析：
1. 1
2. 11
3. 21
4. 1211
5. 111221
6. 312211
7. 13112221
8. 1113213211
9. 31131211131221
10. 13211311123113112211
并说：超过1个相同的数字连在一起时，并说，也就是”几个几“。
不并说：前后数字不同时，不并说，需要单说，也就是”一个几“。
所以我们的思路是：从1开始数，一直数到目标数。
代码：
/**
* @param {number} n
* @return {string}
*/
var countAndSay = function(n) {
// 当前结果从 1 开始
let result = "1";
// 数的结果
let tempResult = '';
// 从1开始数
for (let i = 1; i < n; i++) {
// 记录值
let val = result[0];
// 当前记录值连续个数（包含本身）
let count = 1;
tempResult = '';
// 遍历当前结果
for (let j = 1; j < result.length; j++){
// 若连续
if (result[j] == val) {
count++;
} else {
// 将当前数的结果累加
tempResult += count + val;
// 记下新记录值
val = result[j];
// 重置记录数
count = 1;
}
}
// 将 1 到 n-1 数的结果累加
tempResult += count + val;
// 传值
result = tempResult;
}
return result;
};
执行时间：72ms
完成日期：2018-05-17
leetcode案例
案例一：
/**
* @param {number} n
* @return {string}
*/
var countAndSay = function(n) {
let ans = "1"
let i = 1
while(i < n) {
ans = say(ans)
i++
}
return ans
};
function say(s){
let curChar = s[0]
let curCount = 1
let ans = ""
for (let i = 1; i < s.length; i++){
if (s[i] == curChar){
curCount++
} else {
ans += curCount + curChar
curChar = s[i]
curCount = 1
}
}
ans += curCount + curChar
return ans
}
执行时间：60ms
分析：思路同上。
案例二：
/**
* @param {number} n
* @return {string}
*/
const countAndSay = function(n) {
let
num = '1',
times = n,
counter = []
while(times > 1) {
`${num}`.split('').map(val => {
const lastIndex = counter.length - 1
if(counter[lastIndex] && counter[lastIndex].val === val) {
counter[lastIndex].count++
}
else {
counter.push({
count: 1,
val
})
}
})
num = counter.map(obj => `${obj.count}${obj.val}`).join('')
counter = []
times--
}
return num
};
执行时间：56ms
分析：第一个.map是在遍历num，实际上可以用forEach替换。
counter.map(obj => `${obj.count}${obj.val}`) // 拼接累加的结果。
思路同上。
最长公共前缀
分析：公共前缀最大长度 = 字符串最小长度，找出该长度，我们直接拿strs首个字符串与剩下的字符串逐位比较即可。
代码：
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
if (strs.length == 0) {
return "";
}
// 先找出最小长度
let minLength = Math.min.apply(null,strs.map(val => val.length));
let temp = "";
for (let i = 0; i < minLength; i++) {
// str第一个元素第i位
temp += strs[0][i];
// 遍历数组逐位比较
for (let j = 1; j < strs.length; j++) {
if (temp[i] != strs[j][i]) {
temp = temp.substr(0, temp.length - 1);
break;
}
}
}
return temp.length == "0" ? "" : temp;
};
执行时间：80ms
完成日期：2018-05-21
leetcode案例
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
//先找到最短的字符串
let shortest = "";
var len = strs.length;
if( len === 0 ){
return shortest;
}
let min = strs[0].length;
let index_min = 0;
strs.forEach((val,index)=>{
if( min > val.length ){
min = val.length;
index_min = index;
}
});
shortest = strs[index_min];
var common_pr = "";
//再开始遍历寻找公共前缀
for(var i = min ;i >= 0; i-- ){
var flag = false;
common_pr = shortest.slice(0, i );
for( var j = 0; j < len; j++ ){
let item = strs[j];
if( item.indexOf(common_pr ) === 0 ){
flag = true;
}else{
flag = false;
break;
}
}
if( flag ){
break;
}else{
common_pr = "";
}
}
return common_pr;
};
执行时间：52ms
分析：该题思路类似，只不过找到最短字符串长度的同时，将字符串也找出来，然后以最短字符串作为参照，与剩余字符串逐位比较。