本文共 3557 字，大约阅读时间需要 11 分钟。

leetcode -11 盛最多水的容器

• 題目描述

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

• 解 : 雙重指針

這題的想法是，最一開始有兩個指針(left, right)，一個指向最左邊的高度，另一個指向最右邊的高度。並在二者中取 min 作為實際高度，寬度也可以求得，以這樣的寬高去計算面積，當作目前最大的面積。

接著，由比較矮的那個元素的指針開始向另一方移動，因為寬度不斷在減少，所以只有高度增加才有可能使面積更大。因此，基於這樣的思路，只有當較矮的指針遇到更高的元素時，才重新計算面積看看是否需要更新先前的最大面積。大概就是這樣一個思路。

/** * @param {number[]} height * @return {number} */let maxArea = function(height) {
       let left = 0    let right = height.length-1    let max = 0    while(left < right) {
           const area = (right-left) * Math.min(height[left], height[right])        if(area > max) {
               max = area        }        if(height[left] < height[right]) {
               let lastLeft = height[left]            left++            while(height[left] <= lastLeft && left < right) {
                   left++            }        }else {
               let lastRight = height[right]            right--            while(lastRight >= height[right] && right > left) {
                   right--            }        }    }    return max}

leetcode -12 整数转罗马数字

• 題目描述

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

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 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 的范围内。

• 解一 : 反正就是傻傻的枚舉，這邊就不多說，代碼很醜，又臭又長。

/** * @param {number} num * @return {string} */let intToRoman = function(num) {
       let res = ''    const s = num.toString()    let len = s.length    let i = 0    while(len > 0) {
           let val = Math.pow(10, len-1) * parseInt(s.charAt(i))        switch (val) {
               case 4:                res += 'IV'                break            case 5:                res += 'V'                break            case 9:                res += 'IX'                break            case 40:                res += 'XL'                break            case 50:                res += 'L'                break            case 90:                res += 'XC'                break            case 400:                res += 'CD'                break            case 500:                res += 'D'                break            case 900:                res += 'CM'                break            default:                let s1 = val.toString()                switch(s1.length) {
                       case 1:                        if(val > 5) {
                               res += 'V'                            val -= 5                            for(let i=0; i
   
     50) {
                               res += 'L'                            val -= 50                            for(let i=0; i
    
      500) {
                               res += 'D'                            val -= 500                            for(let i=0; i
    
   

• 解二 : 哈希表驅動，推薦。

/** * @param {number} num * @return {string} */let 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 = ''    for(let key of Object.keys(hashMap).reverse()) {
           if(num >= parseInt(key)) {
               const count = parseInt(num/parseInt(key))            for(let i=0; i