Javascript算法練習(八)

Javascript算法練習(八)

updateInventory,更新庫存,即用新的數組數據去更新老的數組數據

思路:遍歷新數組中的數據

更新老數據:根據名稱去老數組中查找,找到瞭就用對應的數量與老的相加; 添加新數據:如果沒找就將新數組中的數據添加到老數組中;

/**
 * 11. 用第二個數組的數據去更新第一個數組數據(更新庫存)
 * @param  {Array} oldArr 原始數據
 * @param  {Array} newArr 新數據
 * @return {Array}        返回更新後的老數據數組並且根據名稱排序後的二維數組
 *
 * PS: 1. 兩個數組都是二維數組
 *     2. 兩個數組的內容要一致即元素的第一個元素為數量,第二個元素為名稱,
 *         比如:oldArr = [[22, "hello"]], newArr = [[33, "hello"]];  更新後就是:[[55, "hello"]]
 */
ArrayHandler.prototype.updateInventory = function (oldArr, newArr) {

    if (!oldArr || !newArr) return;

    var compare = function (a, b) {
        var ua = a[1].toUpperCase();
        var ub = b[1].toUpperCase();

        if (ua < ub) {
            return -1;
        }

        if (ua > ub) {
            return 1;
        }

        if (ua == ub) {
            return 0;
        }
    };

    if (oldArr.length === 0) return newArr.sort(compare);

    if (newArr.length === 0) return oldArr.sort(compare);

    var findFlag = 0; // 找到存在的庫存標識

    newArr.map(function (newValue) {

        oldArr.map(function (oldValue) {
            if (oldValue[1] == newValue[1]) {
                oldValue[0] += newValue[0]; // 同類產品庫存數累加
                findFlag = 1;
                return;
            }
        });

        // 到這裡表示沒有庫存,直接添加
        if (!findFlag) {
            oldArr.push(newValue);  // 新產品直接添加
        }

        // 復位庫存標識
        findFlag = 0;
    });

    // 排序
    oldArr.sort(compare);

    return oldArr;
}

checkCashRegister:模擬收銀抽屜,給出購買的物品價格及所付金額,算出找零

思路:

先定義好金錢面值(這個與國傢相對應,每個國傢的面值不同,並且基本上不會有所改變,此例以美元為準),這裡需要註意,將所有面值按一美元為單位乘以基數(如:100),避免用浮點數去操作避免因精度問題,最後得到的值不正確; 然後用所付款金額減去購物需付款得到找零金額,最後去面值數組中,從高到底的去取值; 通過對找零金額取餘和取除數,得到相應面值金額所需要找出的張數;

/**
 * 9. 模擬收銀抽屜,給出購買的物品價格及所付金額,算出找零
 * @param  {Number} price 商品價格
 * @param  {Number} cash  所付金額
 * @param  {Array} cid   剩餘金額的二維數組
 * @return {Array}       返回需要找零的金額的二維數組,裡面包含瞭找零對應的面值
 *
 * 最後一個參數cid,即面值剩餘金額數組,必須要和國傢錢幣對應的面值金額相一致,且順序從小到大排
 * 例如:[ 
 *         // 對應1美分(Cent)、5美分(Nickel)、10美分(Dime,一角)、25美分(Quarter)、
 *         // 1美元(ONE)、5美元(FIVE)、10美元(TEN)、20美元(TWENTY)、100美元(ONE HUNDRED)
 *         ["PENNY", 1.01], ["NICKEL", 2.05], ["DIME", 3.10], ["QUARTER", 4.25], 
 *         ["ONE", 90.00], ["FIVE", 55.00], ["TEN", 20.00], ["TWENTY", 60.00], ["ONE HUNDRED", 100.00]
 *       ]
 *
 * TODO:最後可以將dollar數組,當成參數傳進去,與cid數組的內容順序要一致,分別表示錢幣金額面值數,
 *     根據基數base和國傢錢幣面值不同,數組會不相同
 */
NumberHandler.prototype.checkCashRegister = function (price, cash, cid) {

    // 剛剛好
    if (price == cash) return "No Need Back";

    // 付款不足
    if (price > cash) return "Need More Money";

    var base        = 100;      // 金額基數
    var change      = (cash - price) * base; // 找零

    var getTotalMoney = function (arr) {
        var totalMoney = 0;
        arr.reduce(function (preV, currV, currIndex, array){
            totalMoney += base * (preV[1] + currV[1]);
            return currV;
        });

        return totalMoney;
    }

    // 餘額不足,沒法找瞭
    var remain = getTotalMoney(cid);

    if (remain == change) { // 零錢剛好找完瞭
        return "Closed";    
    } else if (remain < change) { // 沒錢找瞭
        return "Insufficient Funds - 1";
    }

    // 分別對應,1美分-5美分-1角-25美分-1美元-5美元-10美元-20美元-100美元
    // 這裡還可以進行優化,讓dollar成為參數,而動態獲取相應國傢的金額面值
    // 比如代表中國的:[10, 50, 100, 500, 1000, 2000, 5000, 10000] -> 
    // 對應:1角-5角-1元-5元-10元-20元-50元-100元(以元為單位的基礎上乘以面值基數:base這裡為100)
    var dollar      = [1, 5, 10, 25, 100, 500, 1000, 2000, 10000]; // TODO
    var pay         = {};   // 保存的key:dollar中面值索引,value:要找的此面值的個數
    var currLast    = 0;    // 當前面值所剩餘額
    var currMoney   = 0;    // 當前金錢面額(dollar中對應的值)
    for (var i = dollar.length - 1; i >= 0; i--) {

        // 當前面值剩餘金額
        currLast = cid[i][1] * base;

        // 當前面值的金額剩餘0,跳過
        if (currLast <= 0) { 
            continue;
        }

        // 當前金額面值
        currMoney = dollar[i];

        // 達到找零的面值必須滿足兩個條件:
        // 1. 找零必須大於當前面值
        // 2. 剩餘的當前面值的錢足夠的情況下
        if (change > currMoney) {
            if (change < currLast) { 
                // 找零小於當前面值剩餘金額
                pay[i + ""] = parseInt(change / currMoney);
                change -= currMoney * pay[i + ""];
            } else {
                // 找零大於當前面值剩餘金額,則將所有剩餘金額找出
                pay[i + ""] = parseInt(currLast / currMoney);
                change -= currLast; // 就直接減去當前面值剩餘所有金額
            }
        }
    }

    var res = [];
    // 組織最後需要找零的錢
    var keys = Object.keys(pay);
    var idx = 0;
    for (var j = 0; j < keys.length; j++) {

        // 需要找零的面值索引
        idx = parseInt([keys[j]]);

        // 該面值最後找出的零錢(公式:面值 * 需要找出數量 / 金錢面值基數)
        cid[idx][1] = dollar[idx] * pay[keys[j]] / base;

        console.log("-------- " + cid[idx][1]);
        res.unshift(cid[idx]);

        // total += dollar[idx] * pay[keys[j]]; // 這裡計算的結果應該和最開始需要找零的金額一致
    } 

    // 找到最後,所有能找的面值加起來還不夠
    // 這裡與最開始不同,這裡是過濾掉瞭所有找不開的面值
    // 比如:要找0.05元,但是目前剩餘一張0.01和1元的面值,依舊判定為找不開
    // 而最開始的是所有餘額加起來都不夠找
    if (getTotalMoney(res) < change) {
        return "Insufficient Funds - 2";
    }

    return res;
}

getPermutation:獲取字符串的所有排列結果,返回所有結果組成的字符串數組

思路:這裡主要還是考察到遞歸的使用,還是有點不太明白,雖然整出結果來瞭,還需好好深入遞歸去研究研究下

/**
 * 5. 獲得指定字符串的所有排列結果的數組
 * @return {[type]} [description]
 */
StringHandler.prototype.getPermutation = function () {

    var resArr      = [];

    return function perm(str, start) {


        var permArr     = str.split("");
        var end         = permArr.length;

        for (var j = start; j < end; j++) {

            // 交換數組中兩個索引位置的值
            swap(permArr, j, start);

            // 保存交換後的字符串,如果曾經保存過則過濾掉,避免重復
            var tmpStr = permArr.join("");
            if (resArr.indexOf(tmpStr) == -1) {
                resArr.push(tmpStr);
            }

            // 重置交換起始位置,遞歸直到最後一位字符結束,即:start > end
            perm(tmpStr, start + 1, end);
        }

        return resArr;
    };
}();

總結

最近有點松懈瞭,加上組裡現在整個模塊的業務都讓我一個人搞,老大跑去做維護新系統去瞭,所以最近也很忙(借口總是很多,呸………..!!!),還是要加緊學習,打好基礎,不能松懈瞭。今天整瞭這三個練習,記錄下,還算有點收獲吧。給自己打打氣,加油吧!!!

發佈留言