字符的统计

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

思路

用map存储第一次出现时候的index，然后遍历map找到第一个只出现1次的字符

代码

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
  let obj = {};
  for(let i = 0; i < s.length; i ++) {
    let cur = s[i];
    if (!obj[cur]) {
      obj[cur] = {
        index: i,
        count: 1
      }
    } else {
      obj[cur].count += 1;
    }
  }
  for(let [key, {index, count}] of Object.entries(obj)) {
    if (count === 1) {
      return index
    }
  }
  return -1;
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29)

389. 找不同

思路

使用map将t中的char对应的count存起来，然后遍历s一个个减去 ，留下最后多出来的字符

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
  let obj = {};
  for(let i = 0; i < t.length; i ++) {
    let cur = t[i]
    obj[cur] = (obj[cur] || 0) + 1
  }
  for(let i = 0; i < s.length; i ++) {
    let cur = s[i]
    obj[cur] = obj[cur] - 1
    if (obj[cur] === 0) {
      delete obj[cur]
    }
  }
  for(let key in obj) {
    return key
  }
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29)

383. 赎金信

思路

先用map将ransomNote中的char-count 存起来，然后遍历magazine减去，如果最后map空了，则可以包含

代码

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
  let obj = {}
  for(let i = 0; i < ransomNote.length; i ++) {
    let cur =ransomNote[i];
    obj[cur] = (obj[cur] || 0) + 1
  }
  for(let i = 0; i < magazine.length; i ++) {
    let cur = magazine[i];
    if (obj[cur]) {
      obj[cur] = obj[cur] - 1;
    }
    if (obj[cur] === 0) {
      delete obj[cur]
    }
  }
  return Object.keys(obj).length === 0
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29)

242. 有效的字母异位词

思路

先用map存储key-count，然后再遍历t看能否使得map为空

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  let obj = {}
  for(let i = 0; i < s.length; i ++) {
    let cur = s[i];
    obj[cur] = (obj[cur] || 0) + 1
  }
  for(let i = 0; i < t.length; i ++) {
    let cur = t[i];
    if (obj[cur] === undefined) return false;
    obj[cur] = obj[cur] - 1
    if (obj[cur] === 0) {
      delete obj[cur]
    }
  }
  return Object.keys(obj).length === 0
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29)

49. 字母异位词分组

思路

异位词排序后是相等的;
另一种思路：用1组26个质数代表26个字母，然后对每个字符串进行相乘，乘积相等则为异位词，还需要考虑乘积越界的处理

代码

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
  let map = new Map();
  for(let i = 0; i < strs.length; i ++) {
    let cur = strs[i];
    let curStr = cur.split('').sort().join('')
    if (map.has(curStr)) {
      let val = map.get(curStr)
      map.set(curStr, [...val, cur])
    } else {
      map.set(curStr, [cur])
    }
  }
  return [...map.values()]
};

复杂度分析

时间复杂度 #card=math&code=O%28N%5E2logN%29)
空间复杂度 #card=math&code=O%28N%29)

451. 根据字符出现频率排序

思路

先用map存储key-count，然后再对count倒序排序再拼接

代码

var frequencySort = function(s) {
  let obj = buildTargetObject(s);
  const arr = getTargetSort(obj);
  return buildStr(arr)
};
function buildTargetObject(str) {
  const obj = {}
  for(let i = 0; i < str.length; i ++) {
    let cur = str[i];
    obj[cur] = (obj[cur] || 0) + 1
  }
  return obj
}
function getTargetSort(obj) {
  const arr = Object.entries(obj)
  return arr.sort((a, b) => b[1] - a[1])
}
function buildStr(arr) {
  let str = '';
  for(let i = 0; i < arr.length; i ++) {
    let [key, value] = arr[i]
    str += key.repeat(value)
  }
  return str
}

复杂度分析

时间复杂度 #card=math&code=O%28NlogN%29)
空间复杂度 #card=math&code=O%28N%29)

423. 从英文中重建数字

657. 机器人能否返回原点

思路

用map存储 key-count，然后判断L和R，U和D是否相等

代码

/**
 * @param {string} moves
 * @return {boolean}
 */
var judgeCircle = function(moves) {
  let obj = {}
  for(let i = 0; i < moves.length; i ++) {
    let cur = moves[i];
    obj[cur] = (obj[cur] || 0) + 1
  }
  return obj['U'] === obj['D'] && obj['L'] === obj['R']
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%28N%29)

551. 学生出勤记录 I

思路

记录A 和 L的次数，看看是不是符合要求

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var checkRecord = function(s) {
  let aCount = 0, lCount = 0, aFlag = 0, lFlag = 0, visitLast = false, len = s.length;
  for(let i = 0; i < len - 1; i ++) {
    if (s[i] === 'A') {
      aCount += 1;
    }
    if (s[i] === 'L') {
      lCount = 1;
      while(s[i] === s[i+1]) {
        lCount += 1;
        i ++;
        if (i === len - 1) {
          visitLast = true
        }
        if (lCount >= 3) {
          lFlag = 1
        }
      }
    }
  }
  if (!visitLast && s[len - 1] === 'A') {
    aCount += 1;
  }
  if (aCount > 1) {
    aFlag = 1
  }
  return (aFlag + lFlag) < 1
};

复杂度分析

时间复杂度 #card=math&code=O%28N%29)
空间复杂度 #card=math&code=O%281%29)

696. 计数二进制子串

467. 环绕字符串中唯一的子字符串

535. TinyURL 的加密与解密