龐果英雄會部分題目解答

一、數(shù)組排序

　　題目鏈接：http://hero.pongo.cn/Question/Details?ExamID=92&ID=94&bsh_bid=281776595

題目詳情：

　　給定一個包含1-n的數(shù)列，我們通過交換任意兩個元素給數(shù)列重新排序。求最少需要多少次交換，能把數(shù)組排成按1-n遞增的順序，其中，數(shù)組長度不超過100。

　　例如：

　　原數(shù)組是3,2,1，我們只需要交換1和3就行了，交換次數(shù)為1，所以輸出1。

　　原數(shù)組是2,3,1，我們需要交換2和1，變成1,3,2，再交換3和2，變?yōu)?，2，3，總共需要的交換次數(shù)為2，所以輸出2。

　　分析：

　　通過示例可以看出，可以用數(shù)組的第一項跟最后一項比較，如果第一項比較大就換順序，然后拿第二項跟最后一項（這時最后一項已經變了）比較，以此類推。這樣最后一項就是最大的了，然后去掉最后一項再次執(zhí)行這個過程。

　　JavaScript代碼如下：　　

function arrSortMincount(arr) {
    var comCount = 0,
        lastItem = 0;
    console.log("sort arr: [" + arr.join(",") + "]");
    if(arr.length == 1) {
        return 0;
    }
    for (var i = 0, j = arr.length; i < j; i++) {
        lastItem = arr[j - 1];
        if (lastItem < arr[i]) {
            console.log("change " + arr[i] + " and " + lastItem);
            arr[j - 1] = arr[i];
            arr[i] = lastItem;
            comCount++;
        }
    }
    if (arr.length > 1) {
        arr.pop();
    }
    return comCount + arrSortMincount(arr);
}

console.log(arrSortMincount([1,2,3]));
console.log(arrSortMincount([3,2,1]));
console.log(arrSortMincount([2,3,1]));
console.log(arrSortMincount([1,3,2]));
console.log(arrSortMincount([9,8,7,6,5,4,3,2,1,0]));

//日志如下：
//sort arr: [1,2,3]
//sort arr: [1,2]
//sort arr: [1]
//0

//sort arr: [3,2,1]
//change 3 and 1
//sort arr: [1,2]
//sort arr: [1]
//1

//sort arr: [2,3,1]
//change 2 and 1
//change 3 and 2
//sort arr: [1,2]
//sort arr: [1]
//2

//sort arr: [1,3,2]
//change 3 and 2
//sort arr: [1,2]
//sort arr: [1]
//1

//sort arr: [9,8,7,6,5,4,3,2,1,0]
//change 9 and 0
//sort arr: [0,8,7,6,5,4,3,2,1]
//change 8 and 1
//sort arr: [0,1,7,6,5,4,3,2]
//change 7 and 2
//sort arr: [0,1,2,6,5,4,3]
//change 6 and 3
//sort arr: [0,1,2,3,5,4]
//change 5 and 4
//sort arr: [0,1,2,3,4]
//sort arr: [0,1,2,3]
//sort arr: [0,1,2]
//sort arr: [0,1]
//sort arr: [0]
//5

　　如有更好算法歡迎討論。

二、字符串消除

　　題目鏈接：http://hero.pongo.cn/Question/Details?ExamID=83&ID=85&bsh_bid=278004606

題目詳情：

定一個字符串，僅由a,b,c 3種小寫字母組成。當出現(xiàn)連續(xù)兩個不同的字母時，你可以用另外一個字母替換它，如

有ab或ba連續(xù)出現(xiàn)，你把它們替換為字母c；

有ac或ca連續(xù)出現(xiàn)時，你可以把它們替換為字母b；

有bc或cb 連續(xù)出現(xiàn)時，你可以把它們替換為字母a。

你可以不斷反復按照這個規(guī)則進行替換，你的目標是使得最終結果所得到的字符串盡可能短，求最終結果的最短長度。

輸入：字符串。長度不超過200，僅由abc三種小寫字母組成。

輸出：按照上述規(guī)則不斷消除替換，所得到的字符串最短的長度。

例如：輸入cab，輸出2。因為我們可以把它變?yōu)閎b或者變?yōu)閏c。

輸入bcab，輸出1。盡管我們可以把它變?yōu)閍ab -> ac -> b，也可以把它變?yōu)閎bb，但因為前者長度更短，所以輸出1。

　　分析：

　　通過分析，可以發(fā)現(xiàn)從字符串開始替換，然后判斷結果中是否還可以替換，如果有再進行這個過程。

　　JavaScript代碼：

function getMinLength(str){
    console.log("Test: ", str);
    var m = new RegExp("ab|ac|bc|ba|ca|cb", "g");
    str = str.replace(m, function(s){
        var reg = new RegExp(s.split("").join("|"), "g"),
            changeTo = "abc".replace(reg, "");
        console.log("replace " + s + " to " + changeTo);
        return changeTo;
    });
    if (m.test(str)) {
        return getMinLength(str);
    } else {
        console.log("Result: ", str);
        return str.length;
    }
}

console.log(getMinLength("cab"));
console.log(getMinLength("bcab"));
console.log(getMinLength("abccbaabccba"));
/*
Test: cab
replace ca to b
Result: bb
2

Test: bcab
replace bc to a
replace ab to c
Test: ac
replace ac to b
Result: b
1

Test: abccbaabccba
replace ab to c
replace cb to a
replace ab to c
replace cb to a
Test: ccaaccaa
replace ca to b
replace ac to b
replace ca to b
Test: cbbba
replace cb to a
replace ba to c
Test: abc
replace ab to c
Result: cc
2
*/

　　如有更好算法歡迎討論。

三、倒水

　　題目鏈接：http://hero.pongo.cn/Question/Details?ID=70&ExamID=68

題目詳情：

有兩個容器，容積分別為A升和B升，有無限多的水，現(xiàn)在需要C升水。

我們還有一個足夠大的水缸，足夠容納C升水。起初它是空的，我們只能往水缸里倒入水，而不能倒出。

可以進行的操作是：

把一個容器灌滿；

把一個容器清空（容器里剩余的水全部倒掉，或者倒入水缸）；

用一個容器的水倒入另外一個容器，直到倒出水的容器空或者倒入水的容器滿。

問是否能夠通過有限次操作，使得水缸最后恰好有C升水。
輸入：三個整數(shù)A, B, C，其中 0 < A , B, C <= 1000000000

輸出：0或1，表示能否達到要求。

　　分析：先求出由A升和B升可以得到幾升（小于A和B中較大值），結果為一個數(shù)組，記為D（從大到小排列），然后用C對D逐項求余判斷是否為0即可。

　　如A=10，B=7，則D = [10, 9, 7, 6, 3]

　　JavaScript代碼：

function can(a, b, c) {
    var allContainer = getAllContainers(a, b);
    console.log(allContainer);
    for(var i = 0, j = allContainer.length; i < j; i++) {
        c = c % allContainer[i];
        if (c == 0 ) {
            break;
        }
    }
    return  c == 0 ? 1 : 0;
}

function getAllContainers(a, b) {
    if (a == b) {
        return [a];
    } else {
        var min = Math.min(a, b),
            max = Math.max(a, b),
            result = [];
        a = max;
        b = min;
        while(max - min < a) {
            result.push(max - min);
            min = b - (max - min);
        }
        result.push(b, a);
        return result.sort(function(a, b){
            return b - a;
        });
    }
}

console.log(can(10,7,3));
console.log(can(9,3,121));
console.log(can(11,7,22));
/*
[10, 9, 7, 6, 3]
1

[9, 6, 3]
0

[11, 8, 7, 4]
1
*/

　　如有更好算法歡迎討論。

posted @ 2013-09-11 10:16 artwl 閱讀(772) 評論(0) 收藏舉報

刷新頁面返回頂部

var ME = { "name": "土豆/Artwl", "job": "coding", "languages": [ "JS", "HTML", "CSS", "jQuery" "MVC",".NET", "設計模式" ], "hobby": [ "閱讀", "旅游", "音樂", "電影" ] }

龐果英雄會部分題目解答

公告

個人簡介