前端刷题路-Day2

罗马数字转整数（题号12）

题目

罗马数字包含以下七种字符: 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 到 3999 的范围内。

示例 1:
输入: "III"
输出: 3

示例 2:
输入: "IV"
输出: 4

示例 3:
输入: "IX"
输出: 9

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

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

提示：

链接

leetcode-cn.com/problems/ro…

解释

首先需要看好题目，这题的题目有两个重点：

1. 通常情况下，罗马数字中小的数字在大的数字的右边
2. 一大堆特例，也就是小数出现在大数前面

第二点就不用多说了，重点需要处理的地方，但是第一点也不能忘，这里的意思是除去特殊情况之外，所有的数字都是从大到小，这样一来，方法就简单很多，因为不需要讨论小数在大数前面但并非是特例的情况了。

自己的答案

var romanToInt = function(s) {
  var kvObj = {
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000
  }
  var sArr = s.split('')

  var res = 0
  for (let i = 0; i < sArr.length; i++) {
    var item = kvObj[sArr[i]]
    if (kvObj[sArr[i]] < kvObj[sArr[i + 1]]) {
      res += kvObj[sArr[i + 1]] - item
      i++
    } else {
      res += item
    }
  }
  return res
};

想法很简单，首先给定每个罗马数字对应的阿拉伯数字，做成一个对象，这里使用Map也是可以的。

之后将罗马数字拆分成数组，如果下一个比前一个大，那么就是特殊情况，特殊情况的规则也就是用大数减去小数的差，那么循环里面的判断就很简单了。

如果下一个数比当前的数大，那么就是特殊情况了，取其差，累加到res上，并且i++，跳过下一次循环；如果不大，那么正常累加即可。

整体逻辑比较简单，但笔者还是发现了一种更好的办法。

更好的方法

var romanToInt = function(s) {
  const table = {
      'I': 1,
      'V': 5,
      'X': 10,
      'L': 50,
      'C': 100,
      'D': 500,
      'M': 1000
  };
  let sum = 0;
  let pre = table[s[0]];
  for (let i = 1; i < s.length; i++) {
      let cur = table[s[i]];
      if (pre < cur) {
          sum -= pre;
      } else {
          sum += pre;
      }
      pre = cur;
  }
  sum += pre;
  return sum;
};

这里可以看出来，原理什么都是一样的，也就是利用一个对象来存储对应的罗马数字和阿拉伯数字的关系，然后开始循环罗马数字的数组。

重点就在循环内部，这里把当前元素和下一个元素的比较换成了当前元素和上一个元素的比较，定义了pre变量，如果下一个元素大于前一个元素，违背了罗马数字从大到小排序的规则，那就证明这种情况是特殊情况。

对于特殊情况的处理就是减去小的那个数，加上那个大的数，于是这里的判断就变成了简单的加减。

感觉比自己的答案逻辑上更简单一点。

不过感觉这种操作不是很好理解，仁者见仁吧。

原答案在这里，感兴趣的可以看看

最长公共前缀（题号14）

题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

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

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

提示：

0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

链接

leetcode-cn.com/problems/lo…

解释

第一眼看到这题应该就会想到答案，正常的循环即可，再遍历每个单词，提取它们的公共部分，循环到最后一个单词是结束，拿到所有单词的公共部分即可。

可这样真的是最好的办法么？显然不是，具体请看更好的方法。

自己的答案（经典暴力查找）

var longestCommonPrefix = function(strs) {
  var res = []
  for (let index = 0; index < strs.length; index++) {
    var sArr = strs[index].split('')
    if (sArr.length === 0) return ''
    if (index === 0) {
      res = sArr
    } else {
      var temp = []
      for (let index = 0; index < sArr.length; index++) {
        if (sArr[index] === res[index]) {
          temp.push(sArr[index])
          if (index + 1 === sArr.length) res = temp
        } else {
          res = temp;
          if (res.length === 0) return ""
          break;
        }
      }
    }
  }
  return res.join('')
};

暴力查找就很简单了，一次次的遍历，然后和公共的res对比，一直对比到最后即可。

更好的方法（排序）

var longestCommonPrefix = function(strs) {
  var res = []
  // 处理特殊情况
  if (strs.length === 0) return ''
  if (strs.length === 1) return strs[0]
  // 对数组进行排序，正序倒序无所谓
  var newArr = strs.sort()
  // 拿到第一个元素和最后一个元素
  var lastArr = newArr[newArr.length - 1].split('')
  var firstArr = newArr[0].split('')
  // 有空字符串的之后返回空
  if (firstArr.length === 0 || lastArr.length === 0) return ''
  // 比较第一个和最后一个元素，取它们的共同前缀即可
  for (let index = 0; index < lastArr.length; index++) {
    if (lastArr[index] === firstArr[index]) {
      res.push(lastArr[index])
    } else {
      break;
    }
  }
	// 返回前缀
  return res.join('')
};

代码写起来很简单，就是想到这一点很难。

首先经典排序，字符串的排序其实是按照字母出现的顺序进行排序的，举个?：

对其进行排序：

var strs = ['fun', 'funny', 'find']
strs.sort()

打印strs：

console.log(strs)	// ["find", "fun", "funny"]

首先对第一个字母进行排序，由于大家都是f开头，所以不管；接下来看第二个字母，分别是u、u和i。

那么排序之后就是["find", "funny", "fun"]。

接下来第三个字母，由于find已经领先剩下两个字母了，所以不用管，大家都是n，会继续比较下一个，然后就这样一点点的比较，可以拿到排序之后的strs。

那么此时拿到的第一个和最后一个就是排好序的字符串了，排序的要求也是按照字母出现的顺序。

现在只要拿最后一个和第一个进行比较，即可得出整个数组的最长公共前缀。

实现确实很简单，难的是想到这一点。