剑指offer (opens new window)

1. 187.重复的DNA序列 (opens new window)

解法1:

/**
 * @param {string} s
 * @return {string[]}
 */
 var findRepeatedDnaSequences = function(s) {
    let map = new Map();
     let result = [];
    for (let i = 0; i< s.length; i++) {
        const dna = s.substring(i, i+10);
        if(!map.has(dna)) {
          map.set(dna, 1);
        } else {
            const num = map.get(dna);
            map.set(dna, num+1)
        }
    }
  
    for(let item of map) {
        if(item[1] > 1) {
            result.push(item[0])
        }
    }
    return result;
  };

2. 12. 整数转罗马数字 (opens new window)

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
  const hashMap = [
    [1, "I"],
    [4, "IV"],
    [5, "V"],
    [9, "IX"],
    [10, "X"],
    [40, "XL"],
    [50, "L"],
    [90, "XC"],
    [100, "C"],
    [400, "CD"],
    [500, "D"],
    [900, "CM"],
    [1000, "M"],
  ];
  let res = "";
  const len = hashMap.length - 1;
  for (let i = len; i >= 0; i--) {
    const key = hashMap[i][0];
    let str = hashMap[i][1];
    const value = Math.floor(num / key);
    const _val = new Array(value).fill(str).join("");
    if (num % key !== 0) {
      res += _val;
      num %= key;
    } else {
      res += _val;
      break;
    }
  }
  return res;
};

3. 17.电话号码的字母组合 (opens new window)

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if (!digits) {
      return []
  }
  const hashMap = {
      2: ['a', 'b', 'c'],
      3: ['d', 'e', 'f'],
      4: ['g', 'h', 'i'],
      5: ['j', 'k', 'l'],
      6: ['m', 'n', 'o'],
      7: ['p', 'q', 'r', 's'],
      8: ['t', 'u', 'v'],
      9: ['w', 'x', 'y', 'z'],
  }
  const len = digits.length;
  if (len === 1) {
      return hashMap[digits];
  }
  if (len === 2) {
      const cur = hashMap[digits[0]];
      const next = hashMap[digits[1]];
      return fn(cur, next);
  }
  if (len === 3) {
      const cur = hashMap[digits[0]];
      const next = hashMap[digits[1]];
      const last = hashMap[digits[2]];
      return fn(fn(cur, next), last);
  }
  if (len === 4) {
      const cur = hashMap[digits[0]];
      const next = hashMap[digits[1]];
      const last = hashMap[digits[2]];
      const last3 = hashMap[digits[3]];
      return fn(fn(fn(cur, next), last), last3);
  }
};

function fn(data1, data2) {
    let data = [];
    for (let i = 0; i < data1.length; i++) {
        for (let j = 0; j < data2.length; j++) {
          data.push(data1[i]+data2[j])
        }
    }
    return data;
}

优化：

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
  if (!digits) {
      return []
  }
  const hashMap = {
      2: ['a', 'b', 'c'],
      3: ['d', 'e', 'f'],
      4: ['g', 'h', 'i'],
      5: ['j', 'k', 'l'],
      6: ['m', 'n', 'o'],
      7: ['p', 'q', 'r', 's'],
      8: ['t', 'u', 'v'],
      9: ['w', 'x', 'y', 'z'],
  }
  const len = digits.length;
  if (len === 1) {
      return hashMap[digits];
  }
  let res = hashMap[digits[0]];
  for(let i = 1; i < digits.length; i++) { 
    const cur = hashMap[digits[i]];
    res = fn(res, cur);
  }
  return res;
};

function fn(data1, data2) {
    let data = [];
    for (let i = 0; i < data1.length; i++) {
        for (let j = 0; j < data2.length; j++) {
          data.push(data1[i]+data2[j])
        }
    }
    return data;
}

4. 3. 无重复字符的最长子串 (opens new window)

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  if (!s) {
      return 0;
   }
   if (s.length === 1) {
      return 1;
   }
  let str = s[0];
  let res = s[0]
  let i = 0;
  let j = 1;
  while(j <= s.length -1) {
    const code = s[j];
    if (!str.includes(code)) {
      str += code;
      j++;
    } else {
      res = str.length > res.length ? str : res;
      str = '';
      i++;
      j = i;
      continue;
    }
  }
  return Math.max(res.length, str.length)
};

优化：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  const map = new Map();

  let i = -1;
  let res = 0
   for (let j = 0; j < s.length; j++) {
       if (map.has(s[j])){
           i = Math.max(map.get(s[j]), i)
       }
       map.set(s[j], j);
       res = Math.max(res, j - i);
   }
   return res;
};