2020-02-21

给定数组 [‘1a’,'2b','3c','5a'] ，输出出现次数最多的字母前数字之和: 6。

// 或许会有类似这样 "11ad" 的元素 ？ 不会，每个元素中只会有一个字母，case可作为边界条件考虑

// let calculateSum = (list = []) => {
//   const reg = /^(\d+)([a-zA-Z]+)/;
//   let wordMap = new Map();

//   for (let i = 0; i < list.length; i++) {
//     const item = list[i];
//     if (reg.test(item)) {
//       const res = reg.exec(item);
//       const number = Number(res[1]);
//       const word = res[2];

//       if (word.length !== 1) {
//         console.error(`输入数组的第 ${i + 1} 个数据项格式错误，请更正！`)
//         break;
//       }
//       const val = wordMap.get(word);
//       wordMap.set(word, {
//         appearCount: val ? val.appearCount + 1 : 1, // 字母出现次数
//         sumNumber: val ? val.sumNumber + number : number, // 该字母前的数字之和
//       });
//     } else {
//       console.error(`输入数组的第 ${i + 1} 个数据项格式错误，请更正！`)
//       break;
//     }
//   }

//   console.log(wordMap);
//   let maxCount = 0, maxSum = 0;
//   wordMap.forEach((item) => {
//     const { appearCount, sumNumber } = item;
//     if (appearCount > maxCount) { // 对比出现次数
//       maxCount = appearCount;
//       maxSum = sumNumber;
//     }
//   })

//   console.log(maxSum);
//   return maxSum;
// }

// calculateSum(['1a', '2b', '3c', '5a']);

// 第一次跑失败：node 执行文件 路径错误
// 第二次跑失败：输出15，发现加和时 发生了字符串拼接
// 第三次跑成功：时间复杂度 O(2n)，空间复杂度 O(n)，开始优化：

let calculateSum = (list = []) => {
  const reg = /^(\d+)([a-zA-Z]+)/;
  let wordMap = new Map(), maxCount = 0, maxSum = 0;

  for (let i = 0; i < list.length; i++) {
    const item = list[i];
    if (reg.test(item)) {
      const res = reg.exec(item);
      const number = Number(res[1]);
      const word = res[2];

      if (word.length !== 1) {
        console.error(`输入数组的第 ${i + 1} 个数据项格式错误，请更正！`)
        break;
      }
      const val = wordMap.get(word);
      wordMap.set(word, {
        appearCount: val ? val.appearCount + 1 : 1, // 字母出现次数
        sumNumber: val ? val.sumNumber + number : number, // 该字母前的数字之和
      });

      const { appearCount, sumNumber } = wordMap.get(word);
      if (appearCount > maxCount) { // 对比出现次数
        maxCount = appearCount;
        maxSum = sumNumber;
      }
    } else {
      console.error(`输入数组的第 ${i + 1} 个数据项格式错误，请更正！`)
      break;
    }
  }
  console.log(wordMap);
  console.log(maxSum);
  return maxSum;
}

calculateSum(['1a', '2b', '3c', '5a']);

// 第四次跑成功：优化成功，合并为一次循环，时间复杂度 O(n)，空间复杂度 O(n)

// 考虑到多个字母出现次数相同的case，如：
calculateSum(['1a', '2b', '3c', '9a', '23b']);

// 该测试用例中 a 和 b 都出现两次，输出了 a 前面的数字加和。
// 原因是：a先遍历加和完成，根据条件 if (appearCount > maxCount) 会输出a的结果

考虑将空间复杂度降为 O(1)？哪位大侠写出来给留个言吧，我实现不了了😫