LeetCode新手一枚，還請多多指教~

第一題：有多少小于當前數(shù)字的數(shù)字

解題思路

先對數(shù)組進行排序，比最小的數(shù)字還小的個數(shù)自然為0，比次小的數(shù)字還小的個數(shù)為最小的數(shù)字的個數(shù)，以此類推。

解法1

先對數(shù)組進行排序，然后遍歷數(shù)組，在考慮有相同數(shù)字的情況下，依次統(tǒng)計數(shù)組中比當前數(shù)字更小的數(shù)字的個數(shù)。

var smallerNumbersThanCurrent = function (nums) {
    let arr = nums.slice().sort();
    let obj = {};

    arr.forEach((num, index) => {
        obj[num] = (obj[num] === undefined) ? index : obj[num];
    });

    return nums.map((num) => obj[num]);
};

let input = [8, 1, 2, 2, 3];
console.log('NASA: input', input);
console.log('NASA: output', smallerNumbersThanCurrent(input));

解法2

根據(jù)題目的說明，數(shù)組中的數(shù)字是0到100的整數(shù)，所以有個取巧的辦法：直接利用數(shù)組來對其進行排序。代碼如下：

var smallerNumbersThanCurrent = function (nums) {
    let arr = [];
    let obj = {};

    nums.forEach((num) => {
        arr[num] = (arr[num] || 0) + 1
    });

    let count = 0;
    arr.forEach((item, index) => {
        if (item != undefined) {
            obj[index] = count;
            count += item;
        }
    });

    return nums.map((num) => obj[num]);
};

let input = [8, 1, 2, 2, 3];
console.log('NASA: input', input);
console.log('NASA: output', smallerNumbersThanCurrent(input));

第二題：通過投票對團隊排名

解題思路

根據(jù)題目的說明，最終各個team是一定會有一個先后順序排名的，即便是投票上完全打成平手，也會根據(jù)字母順序進行排序。所以，這一題我的解題思路是：
1、使用一個正方形的二維數(shù)組來存儲每個字母在每個位置上的得票數(shù)；
2、考慮到最終有可能會完全平票，所以在每個數(shù)組的末尾添加當前字母的CharCode值的反碼。所謂反碼是指“如果是A就添加Z - A = 25，如果是Z就添加Z - Z = 0，方便最后的排序操作。
3、為二維數(shù)組中的子數(shù)組中的每個數(shù)值做前置補0處理，方便最后的排序操作。
4、對二維數(shù)組進行排序，排序的數(shù)值就是每個子數(shù)組的元素join之后的字符串。
說了這么多，我估計我也沒講明白，還是看代碼吧：

var rankTeams = function(votes) {
    const getCharCode = (input) => input.charCodeAt(0);
    const fill0 = (input = 0) => ('0'.repeat(4) + input).slice(-4);

    let obj = {};
    let dualArr = [];
    let codeZ = getCharCode('Z');
    let len = votes[0].length;


    for (const vote of votes) {
        for (let index = 0; index < vote.length; index++) {
            let letter = vote[index];
            let arr = (obj[letter] = obj[letter] || []);
            arr[index] = (arr[index] || 0) + 1;
        }
    }

    for (const [letter, arr] of Object.entries(obj)) {
        for (let index = 0; index < len; index++) {
            arr[index] = fill0(arr[index]);
        }
        arr.push(fill0(codeZ - getCharCode(letter)));
        dualArr.push(arr);
    }

    dualArr.sort((a, b) => b.join('') - a.join(''));

    return dualArr.map((arr) => String.fromCharCode(codeZ - arr.pop())).join('');
};

let votes = ["ABC", "ACB", "ABC", "ACB", "ACB"];
console.log(`NASA: (${rankTeams(votes)})`);

第三題：二叉樹中的列表

解題思路

這道題的考點有兩個，一個是如何通過root數(shù)組構(gòu)造二叉樹，另一個是如何在二叉樹上匹配head數(shù)組。

先說第一個考點：如何通過root數(shù)組構(gòu)造二叉樹。首先要注意，這里的樹并不是完全二叉樹（筆者一開始看錯了，準備構(gòu)造完全二叉樹來著，結(jié)果發(fā)現(xiàn)不太對）。構(gòu)造這棵二叉樹要在root數(shù)組上使用兩個index，分別是指向當前正在構(gòu)造的樹節(jié)點的index（treeIndex）以及數(shù)組的index（rootIndex）。兩個index都從0開始，treeIndex所到之處都將root數(shù)組中的對應數(shù)字元素（必須是非null值，如果是null值就繼續(xù)往后找）直接替換成相應的new TreeNode對象，然后rootIndex加1來構(gòu)造剛剛創(chuàng)建的TreeNode對象的左子節(jié)點，同理再+1來構(gòu)造剛剛創(chuàng)建的TreeNode對象的右節(jié)點，這一步完成后treeIndex繼續(xù)尋找root數(shù)組的下一個非null值（注意：此時的非null值一定是一個TreeNode對象或者treeIndex直接超出root數(shù)組的邊界，原因你自己想一下吧??），如此反復直至treeIndex或者rootIndex超出root數(shù)組的邊界。

再說第二個考點：如何在二叉樹上匹配head數(shù)組。這個其實就很簡單了，直接用遞歸的思想就可以了。從二叉樹的根節(jié)點開始處理，head數(shù)組能在二叉樹上匹配成功的規(guī)則就是：如果head數(shù)組的第一個值跟當前樹節(jié)點的值相同，那么匹配成功的條件就是“head數(shù)組刨除第一個值后的數(shù)組能在當前樹節(jié)點的左子節(jié)點或者右子節(jié)點匹配成功”，否則“head數(shù)組自身能在當前樹節(jié)點的左子節(jié)點或者右子節(jié)點匹配成功”。（PS：我這里沒用它提供的ListNode函數(shù)，因為沒必要）
好了，思路已經(jīng)說完了，配合代碼一起看會更清楚哦~

var isSubPath = function (head, root) {
    function TreeNode(val) {
        this.val = val;
        this.left = this.right = null;
    }

    const getTree = (root) => {
        let treeIndex = 0;
        let rootIndex = 0;
        let rootLen = root.length;

        root = root.slice(0);

        let treeNode = root[rootIndex] = new TreeNode(root[rootIndex]);

        while ((rootIndex < rootLen) && (treeIndex < rootLen)) {
            if ((++rootIndex < rootLen) && (root[rootIndex] !== null)) {
                treeNode.left = root[rootIndex] = new TreeNode(root[rootIndex]);
            }
            if ((++rootIndex < rootLen) && (root[rootIndex] !== null)) {
                treeNode.right = root[rootIndex] = new TreeNode(root[rootIndex]);
            }

            while ((++treeIndex < rootLen) && (root[treeIndex] == null)) continue;
            treeNode = root[treeIndex];
        }

        return root[0];
    };

    const gotyou = (treeNode, head) => {
        if (head.length === 0) return true;
        if (treeNode === null) return false;

        let next = head.slice(1);
        return (treeNode.val === head[0]) ? (gotyou(treeNode.left, next) || gotyou(treeNode.right, next)) : (gotyou(treeNode.left, head)) || (gotyou(treeNode.right, head));
    };

    let rootNode = getTree(root);
    return gotyou(rootNode, head);
};

let head = [1, 4, 2, 6];
let root = [1, 4, 4, null, 2, 2, null, 1, null, 6, 8, null, null, null, null, 1, 3];
console.log(`NASA: (${isSubPath(head, root)})`);

第四題：使網(wǎng)格圖至少有一條有效路徑的最小代價

解題思路

首先，這道題千萬不要試圖去想有什么方法是能夠最快（最小代價）地抵達右下角終點站的（比如說從起點開始一直往右下方向走），因為由于單元格內(nèi)方向的隨機性，所以任何奇奇怪怪的最小代價路徑都是有可能的。那么這道題的解題思路是怎樣的呢？首先，我們需要一只蟲子！對，就是一只小蟲子:)

1. 從起點(0, 0)開始，有只第0代小蟲子開始沿著箭頭方向在單元格內(nèi)爬行，所爬過的單元格內(nèi)都留下它的蟲卵（這是第0代蟲卵），小蟲子一直爬到爬不動然后就消失了（也許是因為即將越過邊界，也許是因為路徑堵住了，也許是因為直接爬到了終點）。
2. 這時蟲卵開始孵化，向它的上下左右單元格內(nèi)散布第1代小蟲子，前提是單元格內(nèi)既沒有蟲卵也沒有蟲子，然后第1代小蟲子繼續(xù)沿襲第0代小蟲子的做法。
3. 就這樣一直下去，直至有第N代小蟲子抵達右下角的終點站為止，此時的N就是最小代價。

為什么要這么做呢？因為從第0代小蟲子開始，它能夠爬過的單元格就是代價為0即可抵達的單元格，如果它此時沒有到達終點的話，那么所有它經(jīng)過的單元格都能1的代價調(diào)轉(zhuǎn)方向抵達它上下左右的任意一個單元格，然后再從這些所有代價為1的單元格去尋找抵達終點的路徑……以此類推，最終就一定能抵達終點，同時求得此時的最小代價。
最后是代碼實現(xiàn)部分，請君笑納：

var minCost = function (grid) {
    let ti = grid.length - 1;
    let tj = grid[0].length - 1;

    grid = grid.map((row, i) => row.map((value, j) => ({ i, j, cost: -1, value })));

    let bugArr = [grid[0][0]];
    let curCost = 0;
    let targetCost = -1;
    let footArr = []

    const getBlankCell = (i, j) => (i >= 0) && (j >= 0) && (i <= ti) && (j <= tj) && (grid[i][j].cost === -1) && grid[i][j];

    while (true) {
        for (const cell of bugArr) {
            let cur = cell;
            let ni = cell.i;
            let nj = cell.j;

            if (cur.cost !== -1) continue;

            while (true) {
                cur.cost = curCost;
                footArr.push(cur);

                if (ni === ti && nj === tj) {
                    targetCost = curCost;
                    break;
                }

                switch (cur.value) {
                    case 1:
                        nj += 1;
                        break;
                    case 2:
                        nj -= 1;
                        break;
                    case 3:
                        ni += 1;
                        break;
                    case 4:
                        ni -= 1;
                        break;
                }

                let next = getBlankCell(ni, nj);

                if (next) {
                    cur = next;
                } else {
                    break;
                }
            }
        }

        if (~targetCost) break;

        bugArr = [];
        for (const cell of footArr) {
            let blank;

            if (blank = getBlankCell(cell.i, cell.j + 1)) {
                bugArr.push(blank);
            }

            if (blank = getBlankCell(cell.i, cell.j - 1)) {
                bugArr.push(blank);
            }

            if (blank = getBlankCell(cell.i + 1, cell.j)) {
                bugArr.push(blank);
            }

            if (blank = getBlankCell(cell.i - 1, cell.j)) {
                bugArr.push(blank);
            }
        }

        curCost += 1;
        footArr = [];
    }

    return targetCost;
};

let grid = [[1, 1, 1, 1], [2, 2, 2, 2], [1, 1, 1, 1], [2, 2, 2, 2]];
console.log('NASA: ', minCost(grid));