字符串

lc13. 罗马数字转整数简单

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

var romanToInt = function(s) {
  const map = new Map()
  map.set('I', 1)
  map.set('V', 5)
  map.set('X', 10)
  map.set('L', 50)
  map.set('C', 100)
  map.set('D', 500)
  map.set('M', 1000)
  let sum = 0
  for(let i = 0; i < s.length; i++) {
    if(s[i] === 'I' && s[i + 1] && (s[i + 1] === 'V' || s[i + 1] === 'X')) {
      sum += (-1 + map.get(s[i + 1]))
      i++
    } else if(s[i] === 'X' && s[i + 1] && (s[i + 1] === 'L' || s[i + 1] === 'C')) {
      sum += (-10 + map.get(s[i + 1]))
      i++
    } else if(s[i] === 'C' && s[i + 1] && (s[i + 1] === 'D' || s[i + 1] === 'M')) {
      sum += (-100 + map.get(s[i + 1]))
      i++
    } else {
      sum += map.get(s[i])
    }
  }
  return sum
};

时间复杂度O(n)

空间复杂度O(1)

lc14. 求最长公共前缀简单hot

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例：

输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

思路一：

1. 要是空数组就返回 ""
2. 要是数组长度为1， 就返回数组的第一位
3. 先按长度排序，然后只用对比第一位和最后一位的字符串，比较一下哪一个字符短，循环判断每一位是不是一样， 一样的话继续下一位判断，时间复杂度为最好On，最坏O(nlogn)

var longestCommonPrefix = function(strs) {
   strs.sort()
  let short = strs[0]
  let long = strs[strs.length - 1]
  let res = ''
  for(let i = 0; i < short.length; i++) {
    if(short[i] === long[i]) res += short[i]
    else return res
  }
  return res
};

思路二：

1. 纵向遍历，先取第一个
2. 然后遍历第一个元素
3. 依次看看数组的每一项是否有这一位

function longestCommonPrefix(strs: string[]): string {
    let first = strs[0];
    for(let i = 0; i < first.length; i++) {
        for(const s of strs) {
            if(s[i] !== first[i] || i === first.length) {
                return first.slice(0, i)
            }
        }
    }

    return first;

};

时间复杂度:O(mn)

空间复杂度O(1)

lc172. 阶乘后的零中等

题目描述

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0

思路

这道题很简单，有多少个5就有多少个0，我们发现只有5的倍数的阶乘，才会产生5, 所以我们需要看看阶层数有多少个5

var trailingZeroes = function (n) {
  let r = 0;
  while (n > 1) {
    n = Math.floor(n / 5);
    r += n;
  }
  return r;
};

lc202. 快乐数简单

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2：

输入：n = 2
输出：false

思路一

采用哈希表

var isHappy = function(n) {
  const getNext = (n) => {
    return n.toString().split("").map( i => i**2).reduce((a,b) => a+b)
  }
  const map = new Map()
  while(n !== 1) {
    map.set(n, 1)
    n = getNext(n)
    if(map.has(n)) return false
  }
  return true
};

时间复杂度:O(n) 空间复杂度:O(n)

思路二

采用快慢指针

var isHappy = function(n) {
  const getNext = (n) => {
    return n.toString().split("").map( i => i**2).reduce((a,b) => a+b)
  }
  let slow = n, fast = getNext(n)
    while(fast !== slow && fast !== 1){
        fast = getNext(getNext(fast));
        slow = getNext(slow);
    }
    return fast == 1

};

时间复杂度:O(n) 空间复杂度:O(1)

lc49. 字母异位词分组中等

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

思路

异位词的单词组成都一样的

var groupAnagrams = function(strs) {
  const map = new Map()
  const res = []
  for(let i = 0; i < strs.length; i++) {
    const s = strs[i].split('').sort().join('')
    if(!map.has(s)) map.set(s, [strs[i]])
    else map.get(s).push(strs[i])
  }
  for(let [key, val] of map) {
    res.push(val)
  }
  return res
};

lc227. 基本计算器 II中等

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

思路

var calculate = function (s) {
  // 分别存储未计算的数字及符号
  const nums = [],
    operators = [];
  const numReg = new RegExp(/[0-9]/);

  /** 用于将nums最后得两个数根据 operators 最后一个符号作运算，将结果存入 nums */
  const calculator = (nums, operators) => {
    const b = nums.pop();
    const a = nums.pop();
    const op = operators.pop();
    switch (op) {
      case "+":
        nums.push(a + b);
        break;
      case "-":
        nums.push(a - b);
        break;
      case "*":
        nums.push(a * b);
        break;
      case "/":
        nums.push(parseInt(a / b));
        break;
    }
  };

  for (let i = 0; i < s.length; i++) {
    if (s[i] === " ") {
      continue;
    }
    if (numReg.test(s[i])) {
      // 若为数字且数字的长度与操作符长度相同，下一个必定是单独的数字
      if (nums.length === operators.length) {
        nums.push(+s[i]);
      } else {
        // 若数字长度与操作符长度不符，下一个数字字符为前一个数字的一部分。
        nums.push(nums.pop() * 10 + +s[i]);
      }
    } else {
      // 若为低优先级运算符，则先将前面的所有运算结算。
      if (s[i] === "+" || s[i] === "-") {
        while (operators.length > 0) {
          calculator(nums, operators);
        }
      } else {
        // 若为高优先级运算符，则如果前一运算符也是高优先级运算符，先计算之前的数字。
        // 因同一优先级运算须从左到右运算，若最后从右往左算结果会有问题。
        const op = operators[operators.length - 1];
        if (op === "*" || op === "/") {
          calculator(nums, operators);
        }
      }
      operators.push(s[i]);
    }
  }
  // 最后如有未计算的运算符
  while (operators.length > 0) {
    calculator(nums, operators);
  }
  return nums[0];
};

lc190. 颠倒二进制位简单

题目描述

颠倒给定的 32 位无符号整数的二进制位。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用二进制补码 (opens new window)记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

思路

// 常规
var reverseBits = function(n) {
  return parseInt(n.toString(2).padStart(32, 0).split('').reverse().join(''), 2)   
};

// 位运算
var reverseBits = function(n) {
    let ans=0;
    for (let i=0;i<32;i++) {
        ans<<=1;//左移
        ans+=n&1;//加n的最低位
        n>>=1;//n右移
    }
    return ans>>>0; 
};

lc394. 字符串解码中等hot

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

思路

遇到这类嵌套结构题目，使用两个栈处理：

• 一个栈保存重复次数（数字）
• 一个栈保存中间字符串（左括号之前的部分）

遍历字符串时：

1. 如果是数字，解析出完整的数字（可能是多位）
2. 如果是字母，就拼接到当前字符串上
3. 如果是 [，把当前的数字和字符串入栈，然后重置
4. 如果是 ]，弹出数字和上一个字符串，把当前字符串重复 k 次拼接上

var decodeString = function(s) {
  const numStack = [];
  const strStack = [];
  let currentNum = 0;
  let currentStr = '';

  for (let ch of s) {
    if (!isNaN(ch)) {
      // 多位数字处理
      currentNum = currentNum * 10 + Number(ch);
    } else if (ch === '[') {
      numStack.push(currentNum);
      strStack.push(currentStr);
      currentNum = 0;
      currentStr = '';
    } else if (ch === ']') {
      const repeatTimes = numStack.pop();
      const lastStr = strStack.pop();
      currentStr = lastStr + currentStr.repeat(repeatTimes);
    } else {
      currentStr += ch;
    }
  }

  return currentStr;
};

时间复杂度：O(n)，遍历字符串每个字符最多处理一次

空间复杂度：O(n)，栈空间最多嵌套 n 层

lc395. 至少有 K 个重复字符的最长子串中等

题目描述

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1：

输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2：

输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

思路：递归

var longestSubstring = function (s, k) {
  if (s.length < k) return 0; //如果s长度小于k，提前退出 返回长度0
  const cache = new Map();
  for (let i = 0; i < s.length; i++) {
    cache.set(s[i], cache.has(s[i]) ? cache.get(s[i]) + 1 : 1);
  }
  for (const [key, val] of cache) {
    if (val < k) {
      //数量小于k的字符，那么该字符串必不合格 处理如下
      let res = 0;
      for (const i of s.split(key)) {
        //按照个数小于k的字符划分字符串 分治！
        res = Math.max(res, longestSubstring(i, k)); //对划分的字符串继续递归判断
      }
      return res;
    }
  }
  return s.length; //如果s中所有字符个数都大于k，返回s的长度
};

时间复杂度:O(n)

空间复杂度:O(n ^ n)

剑指 Offer 50. 第一个只出现一次的字符简单

题目描述

在字符串 s中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = "abaccdeff"
输出：'b'

示例 2:

输入：s = "" 
输出：' '

var firstUniqChar = function(s) {
  for(let i of s) {
    if(s.indexOf(i)===s.lastIndexOf(i)) return i
  }
  return ' '
};

lc415. 字符串相加/大数相加简单hot

题目描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

示例 2：

输入：num1 = "456", num2 = "77"
输出："533"

示例 3：

输入：num1 = "0", num2 = "0"
输出："0"

var addStrings = function(num1, num2) {
  num1 = num1.split('')
  num2 = num2.split('')
  let carry = 0
  let sum = ''
  while(num1.length || num2.length || carry) {
    let n1 = num1.length ? num1.pop() : 0 
    let n2 = num2.length ? num2.pop() : 0 
    let curSum = (+n1) + (+n2) + carry
    carry = Math.floor(curSum / 10)
    sum = curSum % 10 + sum
  }
  return sum
};

43. 字符串相乘/大数相乘中等hot

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

思路

num1[i] * num2[j] 会加到 res[i + j] 和 res[i + j + 1] 上

res[i + j + 1] 存储当前乘积的个位；

res[i + j] 存储进位（上一位）；

这个是最难理解的点，我们下面讲清楚它。

function multiply(num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";

  const m = num1.length, n = num2.length;
  const res = new Array(m + n).fill(0);

  for (let i = m - 1; i >= 0; i--) {
    const digit1 = num1.charCodeAt(i) - 48;

    for (let j = n - 1; j >= 0; j--) {
      const digit2 = num2.charCodeAt(j) - 48;

      const mul = digit1 * digit2;
      const p1 = i + j, p2 = i + j + 1;

      const sum = mul + res[p2];
      res[p2] = sum % 10;
      res[p1] += Math.floor(sum / 10);
    }
  }

  // 去除前导 0
  let result = res.join('').replace(/^0+/, '');
  return result.length === 0 ? "0" : result;
}

时间复杂度:O(mn)

空间复杂度:O(m + n)

lc1360. 日期之间隔几天简单

题目描述

请你编写一个程序来计算两个日期之间隔了多少天。

日期以字符串形式给出，格式为 YYYY-MM-DD，如示例所示。

示例 1：

输入：date1 = "2019-06-29", date2 = "2019-06-30"
输出：1

示例 2：

输入：date1 = "2020-01-15", date2 = "2019-12-31"
输出：15

提示：

• 给定的日期是 1971 年到 2100 年之间的有效日期。

/**
 * @param {string} date1
 * @param {string} date2
 * @return {number}
 */
var daysBetweenDates = function(date1, date2) {
  return Math.abs((+new Date(date1)) - (+new Date(date2))) / (60 * 60 * 1000 * 24)
};

lc8. 字符串转换整数 (atoi)简单hot

题目描述

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

1. 读入字符串并丢弃无用的前导空格
2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
5. 如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
6. 返回整数作为最终结果。

注意：

• 本题中的空白字符只包括空格字符 ' ' 。
• 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。

示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。

示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

var myAtoi = function(s){
    let limit = Math.pow(2,31);
    let num = parseInt(s);

    if(isNaN(num)){
        num = 0;
    }

    if(num < - limit){
        num = -limit;
    }
    if(num > limit - 1){
        num = limit - 1;
    }

    return num;
};

KMP算法

lc28. 实现strStr() 简单

题目描述

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例 3：

输入：haystack = "", needle = ""
输出：0

思路：KMP算法

正常的暴力解法是O(m * n),而KMP算法是O(m + n)

直接举例：
 * haystack：   aabaabaafa
 * needle：     aabaaf

 * 
 * needle：
 *  前缀：不包含末尾的所有字符串
 *  后缀：不包含开头的所有字符串
 * 
 * 前缀：               后缀：
 *   a,                  f,
 *   aa,                 af,
 *   aab,                aaf,  
 *   aaba,               baaf,
 *   aabaa,              abaaf,
 *   aabaaf, ❌          aabaaf, ❌           这一行不是前缀也不是后缀
 * 
 * 最长相等的前后缀：
 *   a          0  只有一个，0
 *   aa         1  前缀：a。后缀：a
 *   aab        0  前缀：a、aa。后缀：b、ab。
 *   aaba       1  前缀：a、aa、aab。后缀：a、ba、aba。
 *   aabaa      2  前缀：a、aa、aab、aaba。后缀：a、aa、baa、abaa。
 *   aabaaf     0  ....
 *  
 *  next = 【 0,1,0,1,2,0 】，next就是needle的前缀表。
 * 
 *  1. next中的值代表着该子串的最长相等前后缀的长度，
 *  2. 因为数组是从0开始的，该值还表示子串最长相等前后缀的下一项的索引
 * 
 *  例如： next[4] = 2， 其对应的子串是aabaa，前缀和后缀相等的只有a、aa，长度为2。 
 *        needle[2] === b 恰好等于下一项的索引。
 * 

var strStr = function(haystack, needle) {
    let n = haystack.length
    let m = needle.length
    if(m === 0) return 0

    let next = new Array(m).fill(0)
    for(let i = 1, j = 0; i < m; i++){
      // i：当前子串的后缀末尾
      // j：上一项子串最长相等前后缀的下一项 或者 0 ，并且也是 上一项子串最长相等前后缀的长度
        while(j > 0 && needle[i] !== needle[j]){
          // 如果不同，我们要从未匹配好的地方开始继续匹配。
          // 未匹配好的位置是那里呢？ 👇
          // 我们知道 next 数组的值就代表每一次子串匹配好的长度，
          // 因为数组是从0开始的，所以j - 1就指向了上一个子串未匹配好的位置。
          // 当j === 0时，说明要从头开始重新匹配了
            j = next[j - 1]
        }
        if(needle[i] === needle[j]){
            j++
        }
        next[i] = j
    }

    // 搞懂上面的，下面的也就懂了
    for(let i = 0, j = 0; i < n; i++){
        // 如果当前i 和 j不一致，就回退到上一个相等的位置的下一个看看是否匹配
        // 会不断回退，0为回退到边界，当回退到0意味着要重新从头开始匹配
        while(j > 0 && haystack[i] !== needle[j]){
            j = next[j - 1]
        }
        if( haystack[i] === needle[j]){
            j++
        }
        // 当j 和 m 的长度相等时，就说明存在
        if(j === m){
            return i - m + 1
        }
    }
    return -1
};

思路二

也可以用截取字符串的长度来解

var strStr = function (haystack, needle) {
  if (needle === "") return 0
  for (var i = 0; i < haystack.length; i++) {
      if (haystack[i] === needle[0]) {
          if (haystack.substring(i, i + needle.length) === needle) return i;
      }
  }
  return -1
};

#