剣指Offer毎日6題(JavaScript版)--7日目

37、剣指offer–数字が並べ替え配列に出現する回数
テーマの説明:並べ替え配列における1つの数字の出現回数を統計します.
考え方1:私が一番好きな暴力解決法は、考え方2:二分検索方法:まず中間要素を見てkと比較して、左半分より小さくて、右半分より大きいです.
コード:

//1、
function GetNumberOfK(data, k)
{
    var count=0;
    data.forEach(function(a){
        if(a==k) count++;
        if(a>k) return count;
    })
    return count
}
//2、
function GetNumberOfK(data, k)
{
    var l = 0, r = data.length, mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(k > data[mid]){
            while(data[mid] == data[mid + 1]){
                mid++;
            }
            l = ++mid;
        }else if(k < data[mid]){
            while(data[mid] == data[mid - 1]){
                mid--;
            }
            r = --mid;
        }else{
            var sign1 = mid, sign2 = mid;
            while(sign1 > l && data[sign1] == data[sign1 + 1]){
                sign1++;
            }
            while(sign2 < r && data[sign2] == data[sign2 - 1]){
                sign2--;
            }
            return sign1 - sign2 + 1
        }
    }
    return 0;
}

38、剣指offer–二叉樹の深さ
本の二叉の木を入力して、この木の深さを求めます.ルートの結点から葉の結点まで順次通る結点(根、葉の結点をくわえます)は木の1本のパスを形成して、最も長いパスの長さは木の深さです.
考え方:再帰的に左のサブツリーと右のサブツリーの深さを求めて、そして比較して、最終的に最大値を返して1をプラスします.
コード:

function TreeDepth(pRoot)
{
    if(pRoot == null) return 0;
    var left = TreeDepth(pRoot.left);
    var right = TreeDepth(pRoot.right);
    return (left > right) ? left+1 :right+1;
}

39、剣指offer–バランス二叉樹
タイトル:一本の二叉の木を入力して、この二叉の木が平衡二叉の木かどうかを判断します.
考え:1本の空の木か、左右の2つのサブツリーの高さの差の絶対値は1を超えないで、しかも左右の2つのサブツリーはすべて1本の平均二叉の木です.左のサブツリーと右のサブツリーの深さを遍歴して、両者の差を比較します.
コード:

function IsBalanced_Solution(pRoot)
{
    if(pRoot == null) return true;
    var left = TreeDepth(pRoot.left);
    var right = TreeDepth(pRoot.right);
    if(left - right > 1 || left - right < -1){
        return false;
    }
    return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}
function TreeDepth(root){
    if(root == null) return 0;
    var left = TreeDepth(root.left);
    var right = TreeDepth(root.right);
    return (left > right) ? left+1 : right+1;
}

40、剣指offer–行列に一度しか現れない数字
題目の説明:一つの整体行列には二つの数字以外に、他の数字は二回も現れました.この二つは一回だけの数字を見つけてください.
考え方:配列をデバックした配列と比較し、配列中の要素の出現回数を求めます.
コード:

Array.prototype.uniq = function(){
    var res = [];
    var json = {};
    for(var i = 0 ; i < this.length ; i++){
        if(!json[this[i]]){
            res.push(this[i]);
            json[this[i]] = 1;
        }
    }
    return res;
}
function FindNumsAppearOnce(array)
{
    // return list,   [a,b]，  ab          
    var a = array;
    var b = a.uniq();
    var result = [];
    var k = 0;
    for(var i = 0 ; i < b.length ; i++){
        for(var j = 0 ; j < a.length ; j++){
            if(b[i] == a[j]){
                k++;
            }
        }
        if(k == 1){
            result.push(b[i])
        }
        k = 0;
    }
    return result;
}

41、剣指offer–とSの連続正数シーケンス
数学が大好きで、ある日彼は数学の宿題をする時、9～16の和を計算するように求めました.彼はすぐに正しい答えを書きました.しかし、彼はこれに満足していません.どれぐらいの連続的な正数系列があるかということと、100(少なくとも2つの数を含む)であるかを彼は考えています.まもなく、彼は他の組の連続正数と100のシーケンスを獲得します.18,19,20,21,22.今は問題をあなたに任せます.すべてとSの連続正数シーケンスをすぐに見つけられますか?Good Luck出力説明:すべてとSの連続正数シーケンスを出力します.シーケンス内では、小さいときから大きな順に、シーケンス間で開始数字に従って小さいときから大きい順に並べられています.
考え方:2つのポインタを設定します.sumより大きい場合、左のポインタは後ろにシフトします.小さい場合、右のポインタは後ろにシフトします.二つのポインタがくっついたら、左のポインタはずっとsumの半分より小さいです.
コード:

function FindContinuousSequence(sum)
{
    if(sum < 2) return [];
    var result = [];
    var a = 1, b = 2, s = 3;
    while(a <= Math.floor(sum / 2)){
        if(s < sum){
            b++;
            s += b;
        }else if(s > sum){
            s -= a;
            a++;
        }else{
            var tem = [];
            for(var i = a ; i <= b ; i++){
                tem.push(i);
            }
            result.push(tem);
            if(a + 1 < b){
                s -= a;
                a++
            }else{
                break;
            }
        }
    }
    return result;
}

42、剣指offer–とSの2つの数字
題目の説明:インクリメント順序の配列と一つの数字Sを入力して、配列の中で2つの数を探します.彼らの和がちょうどSである場合、複数のペアの数字の和がSに等しい場合、2つの数の積が一番小さいものを出力します.出力説明:各テストケースに対応して、二つの数を出力し、小さい方は先に出力します.
考え方1:暴力的解決.考え方2:両端積が最小なので、二つのポインタは、一つは頭から始まり、一つは後ろからそれぞれ遍歴しています.初めて現れた時とSの時に、積が最小になります.
コード:

//1、
function FindNumbersWithSum(array, sum)
{
    if(array.length < 2) return [];
    var res = [];
    for(var i = 0 ; i < array.length ; i++){
        for(var j = 0 ; j < array.length ; j++){
            if(array[i] + array[j] == sum){
                res.push(array[i],array[j]);
            }
        }
    }
    return res.slice(0,2);
}
//2、
function FindNumbersWithSum(array, sum)
{
    if(array.length < 2) return [];
    var start = 0, end = array.length - 1;
    while(start < end){
        var s = array[start] + array[end];
        if(s < sum){
            start++;
        }else if(s > sum){
            end--;
        }else{
            return [array[start],array[end]];
        }
    }
    return [];
}

剣指Offer毎日6題(JavaScript版)-シリーズ記事参考コラム:JavaScript版剣指offer