iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 5
1
Software Development

你總是躲不掉的,不如放膽面對 LeetCode 吧!系列 第 5

Day 05: Array

MDN 怎麼定義

Arrays are list-like objects whose prototype has methods to perform traversal and mutation operations. Neither the length of a JavaScript array nor the types of its elements are fixed. Since an array's length can change at any time, and data can be stored at non-contiguous locations in the array.

上述描述可以知道幾個特性:

  • List-like,似列表,數個元素排列成有限序列。
  • 可以從第一個元素開始,遍歷整個元素。
  • 元素內的資料可以修改。
  • 元素內的資料型別不用一致。
  • 非固定長度,可以在任何時間修改。
  • 資料儲存的位置並不一定要相鄰。

是的,這些都是習以為常的基本知識。

C 的角度,該怎麼重新理解?

JS 不同之處在於:

  • 元素內的資料型別要一致。
  • 固定長度,宣告時就要決定好。

首先要知道的是,為什麼 Array 的設計是線性排列?在於記憶體的使用方式,宣告 Array 長度與型別,同時表示該 Array 將跟記憶體要求一個連續的區塊,好預留足夠的空間可以存放元素。目的是為了能夠有效運用記憶體而不浪費。

玩味的地方在於,因為 Array 的長度可能很長(意味著佔用大量的記憶體),所以使用 Array 時,傳遞該 Array記憶體位置(使用指標取得)遠比重新複製一個新 Array 來得快速許多,同時也能節省記憶體的消耗。這也就是為什麼 JSArrayObject 會是 by reference,為了節省記憶體的消耗。

String

有了 C 的概念後,那 String 講白了就是宣告資料型別為字元的 Array 。因為長度固定,所以 C 在開發字串上蠻麻煩的。這點 Java 已經看出來,因此開發出 class String 來因應字串經常更改 Array 長度。

CRUD 相關操作

對於一位 JS 工程師而言,Array 的基本 CRUD 是必備的技能。這邊要提一點,部分內建函式對 Array 內的元素進行更動,此時要思考三點:

  • 長度是否改變?長度增加時,可能記憶體區塊空間不足,要重新跟記憶體要求一塊,造成時間與資源的浪費。
  • 元素的順序是否更動?最可怕的莫過於 Array.prototype.shift(),所有元素的 index 都會變更,肯定會造成記憶體的消耗。
  • 菜雞時期喜歡用內建的 Array 函式,使用越多越覺得自己很厲害,一下 Array.prototype.map()、一下 Array.prototype.filter(),說穿了,都是 for-loop 的語法糖,使用上沒有對錯,端看需求。
    • 前端來說,現在流行 Immutable Data 好簡化控制介面上許許多多的狀態與資料,因此流行使用 Array.prototype.map()Array.prototype.filter() 等製造出新的 Array
    • 後端來說,尤其強調效率的場合,建議減少內建 Array 函式的使用,盡可能 for-loop 完成。原因在於每一個 Array 內建函式幾乎都在跑 for-loop,減少使用增進效率。

刷題:11. Container With Most Water

題目

連結

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

Related Topics: Array, Two Pointer

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Imgur

思考

首先觀察題目的圖片,思考中間的數字比兩側還大時,是不是有影響到?無法判斷的情況下點擊 Hint 1,可以得知題目沒有要思考這麼細,單純比較頭尾的高度後,再藉由頭尾之間的距離算出面積,最後比較哪一組的面積最大即可。

這邊最快速的做法是 Two Pointer,一種適合用在 Array 的解題技巧,粗略來講,遍歷 Array 時,除了從頭遞增,同時從尾巴遞減,頭尾互相計算、運作後,可以得到一個最終答案。詳細操作之後討論。

解題

JS

/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = (height) => {
    let max = 0, start = 0, end = height.length - 1;

    while (start < end) {
      let width = end - start;
      let high = 0;

      if (height[start] < height[end]) {
        high = height[start];
        start++;
      } else{
        high = height[end];
        end--;
      }

      let temp = width * high;

      if (temp > max) {
        max = temp;
      }
    }

    return max;
};

Java

class Solution {
    public int maxArea(int[] height) {
        int max = 0, start = 0, end = height.length - 1;

        while (start < end) {
            int width = end - start;
            int high = 0;

            if (height[start] < height[end]) {
                high = height[start];
                start++;
            } else {
                high = height[end];
                end--;
            }

            int temp = width * high;

            if (temp > max) {
                max = temp;
            }
        }

        return max;
    }
}

C

int maxArea(int *height, int heightSize)
{
    int max = 0, start = 0, end = heightSize - 1;

    while (start < end)
    {
        int width = end - start;
        int high = 0;

        if (height[start] < height[end])
        {
            high = height[start];
            start++;
        }
        else
        {
            high = height[end];
            end--;
        }

        int temp = width * high;

        if (temp > max)
        {
            max = temp;
        }
    }

    return max;
}

看法

這題個人歸類在腦經急轉彎的類型,想通後三種語言的實作皆十分相似。

結論

Array 是基本功中的基本功,JS 的工程師要補充 C 如何定義 Array 即可。至於其他解題技巧留在之後的文章內討論。


上一篇
Day 04: 從資料結構談起
下一篇
Day 06: Linked List
系列文
你總是躲不掉的,不如放膽面對 LeetCode 吧!31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言