1.反转字符串

image.png
方法1：前后指针交换法
关键：以Math.floor(s.length / 2)作为分界线，交换s[i]与s[s.length - i - 1]的值

  1. var reverseString = function (s) {
  2.   let mid = Math.floor(s.length / 2);
  3.   for (let i = 0; i < mid; i++) {
  4.     console.log(s[i], s[s.length - i - 1]);
  6.     let temp = s[i];
  7.     s[i] = s[s.length - i - 1];
  8.     s[s.length - i - 1] = temp;
  9.   }
  10.   return s;
  11. };

方法2：reverse()

  1. s.reverse()

2.整数反转

image.png
思路：双指针，前后交换，while循环遍历
注意：如果是负数开头，那么left从1开始

  1. function(x) {
  2.   // 替换 left 和 right 的值
  3.   // 注意负数开头
  4.   let arr = x.toString().split('')
  5.   let right = arr.length - 1
  6.   let left = x < 0 ? 1 : 0
  7.   while(left < right) {
  8.     let temp = arr[left]
  9.     arr[left] = arr[right]
  10.     arr[right] = temp
  11.     right--
  12.     left++
  13.   }
  14.   // 判断是否在 [-2^31, 2^31-1]内
  15.   let num = Number(arr.join(''))
  16.   if (num < -(Math.pow(2, 31)) || num > (Math.pow(2, 31) - 1)) {
  17.     return 0
  18.   }
  19.   return num
  20. };

3.字符串中的第一个唯一字符

image.png
方法1：

  1. 遍历一遍数组，通过hashMap记录item以及count次数

  2. 再遍历一遍hashMap找到第一个count为1的item

    1. var firstUniqChar = function(s) {
    2. let arr = s.split('')
    3. let map = new Map()
    4. for(let i = 0; i < arr.length; i++) {
    5.  let count = map.get(s[i])
    7.  if (count) {
    8.    map.set(s[i], ++count)
    9.  } else {
    10.    map.set(s[i], 1)
    11.  }
    12. }
    13. for (let [key, value] of map) {
    14.  if (value === 1) {
    15.    return arr.indexOf(key)
    16.  }
    17. }
    18. return -1
    19. };

    方法2：通过indexOf以及lastIndexOf相等来判断第一个不重复的item

    1. function(s) {
    2. let arr = s.split("")
    3. for (let i = 0; i < s.length; i++) {
    4.  if (arr.indexOf(s[i]) === arr.lastIndexOf(s[i])) {
    5.    return arr.indexOf(s[i])
    6.  }
    7. }
    8. return -1
    9. };

    4.有效的字母异位词（两个字符串出现数量是否相同）

    image.png
    方法1：hashMap方式

  3. 遍历s，记录item以及出现的次数

  4. 遍历t，消除hashMap上的count，如果最后的时候还存在count，说明不相等

补充：需要先判断length一致

  1. var isAnagram = function(s, t) {
  2.   let map = new Map()
  3.   if (s.length !== t.length) {
  4.     return false
  5.   }
  6.   for (let i = 0; i < s.length; i++) {
  7.     let count = map.get(s[i])
  8.     if (count) {
  9.       map.set(s[i], ++count)
  10.     } else {
  11.       map.set(s[i], 1)
  12.     }
  13.   }
  14.   for (let i = 0; i < t.length; i++) {
  15.     let count = map.get(t[i])
  16.     if (count) {
  17.       map.set(t[i], --count)
  18.     }
  19.   }
  20.   for (let [key, value] of map) {
  21.     if (value > 0) {
  22.       return false
  23.     }
  24.   }
  25.   return true
  26. };

方法2：通过for循环t+replace的方法，清空s数组，看看剩余s的长度

  1. function(s, t) {
  2.   if (s.length !== t.length) return false
  3.   for(let i = 0; i < t.length; i++) {
  4.     s = s.replace(t[i], "")
  5.   }
  6.   return !Boolean(s.length)
  7. };

5.验证回文字符串

image.png.
思路：

  1. 先通过正则/[^a-zA-Z0-9]/g替换掉非字母和数字的字符串

  2. 通过双指针方式，对比前后的字符串是否一致，只要有一个不一致则return false

    1. /**
    2. * @param {string} s
    3. * @return {boolean}
    4. */
    5. var isPalindrome = function(s) {
    6. if (!s) return true
    7. // 将非字符串和数字的清除掉
    8. s = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase()
    9. for (let i = 0; i < s.length / 2; i++) {
    10.  if (s[i] === s[s.length - i - 1]) {
    11.    continue
    12.  } else {
    13.    return false
    14.  }
    15. }
    16. return true
    17. }

    7.实现strStr()（字符串搜索）

    image.png
    方法1：采用 indexOf或者 search api

    1. var strStr = function (haystack, needle) {
    2. return haystack.indexOf(needle)
    3. };

    方法2：遍历+双指针比对

  3. 遍历 haystack，记录指针 i

  4. 每次遍历 haystack 时，比对 haystack后面几项是否与 needle相等
    1. function(haystack, needle) {
    2. if (needle === "") return 0
    3. let i = 0 // haystack 指针
    4. let j = 0 // needle 指针
    5. while(i < haystack.length) {
    6.  // 如果找到开始的相等的字符串，就继续往后比对
    7.  if (haystack[i] === needle[j]) {
    8.    i++
    9.    j++
    10.  } else {
    11.    // 否则，将 i 重置到开始相等的下一位
    12.    i = i - j + 1
    13.    j = 0
    14.  }
    15.  // 如果全部相等
    16.  if (j === needle.length) {
    17.    return i - j
    18.  }
    19. }
    20. return -1
    21. };

方法3(推荐)：遍历 haystack，截取后面的needle.length项，比对是否相同

  1. function(haystack, needle) {
  2.   if (needle === "") return 0
  3.   let len = needle.length
  4.   for (let i = 0; i < haystack.length; i++) {
  5.     let str = haystack.substr(i, len)
  6.     if (str === needle) {
  7.       return i
  8.     }
  9.   }
  10.   return -1
  11. };

9.最长公共前缀

找到传入字符串数组的最长公共前缀
最长公共前缀

  1.  var longestCommonPrefix = function(strs) {
  2.   let res = ""
  3.   // 找到最短的 str
  4.   let minStr = ""
  5.   for(let i = 0; i < strs.length; i++) {
  6.     if (minStr) {
  7.       if (strs[i].length < minStr.length) {
  8.         minStr = strs[i]
  9.       }
  10.     } else {
  11.       minStr = strs[i]
  12.     }
  13.   }
  14.   for (let i = 0; i < minStr.length; i++) {
  15.     for (let j = 0; j < strs.length; j++) {
  16.       if (strs[j][i] !== minStr[i]) {
  17.         return res
  18.       }
  19.     }
  20.     res += minStr[i]
  21.   }
  22.   return res
  23. };