11日剣指offer-JavaScript版-8日目


文書ディレクトリ

  • 43、左旋回文字列
  • タイトル説明
  • 構想
  • コード
  • 44、反転単語順シーケンス
  • タイトル説明
  • 構想一
  • コード
  • 構想二
  • コード
  • 45、トランプ順子
  • タイトル説明
  • 構想
  • コード
  • 46、子供たちのゲーム(丸の中で最後に残った数)
  • タイトル説明
  • 構想一
  • コード
  • 構想2-より詳細な解釈がある
  • コード
  • 47、1+2+3+...+n
  • を求めます
  • タイトル説明
  • 構想
  • コード
  • 48、加算
  • を加算しない
  • タイトル説明
  • 構想
  • コード
  • 43、左回転文字列


    タイトルの説明


    アセンブリ言語にはループ左シフト(ROL)というシフト命令があり、文字列でこの命令の演算結果をシミュレートする簡単なタスクがあります.与えられた文字シーケンスSについては、Kビットを左シフトしたシーケンス出力をループしてください.例えば、文字列S="abcXYZdef"は、3ビット左シフト後の結果である"XYZdefabc"の出力を要求する.簡単じゃないの?OK、やれ!

    構想


    文字列を切り分けることで、後の文字列を前の文字列の前に貼り付け、nullかどうかを判断して長さ0かを判断することを覚えておく.

    コード#コード#

    function LeftRotateString(str, n)
    {
        if(str == null || str.length == 0) return '';
        if(n > str.length) n -= str.length;
        //substr()             start             。
        var str1 = str.substr(0,n);
        var str2 = str.substr(n);
        var result = str2 + str1;
        return result;
    }
    

    44、単語の順序を反転する


    タイトルの説明


    牛客は最近新入社員のFishが来て、毎朝いつも英語の雑誌を持って、ノートに文を書いています.同僚のCatはFishが書いた内容に興味を持ち、ある日Fishに借りてめくったが、意味が読めなかった.たとえば、「student.a am I」です.後になって、こいつはもともと文の単語の順番を反転していたことに気づいた.正しい文は「I am a student.」だったはずだ.Catはこれらの単語の順序を一つ一つ反転してはいけません.彼を助けることができますか.

    考え方1


    Arrayでカプセル化された関数reverse()

    コード#コード#

    function ReverseSentence(str)
    {
        var array = str.split(' ');
        //reverse()               。
        return array.reverse().join(' ');
    }
    

    考え方2


    先頭ポインタが指す要素を交換します.

    コード#コード#

    function ReverseSentence(str)
    {
        // write code here
        //trim()               ,         。
        if(!str || !str.trim()) return str;
        var strArray = str.split(' '), //      
        len = strArray.length;
        var start = 0, end = len - 1, tem;//      
    
        while(start < end){
            tem = strArray[start];//    
            //             
            strArray[start] = strArray[end];
            strArray[end] = tem;
            start++;
            end--;
        }
        return strArray.join(' ').trim();
    }
    

    45、トランプの順子


    タイトルの説明


    LL今日の気持ちはとても良くて、彼がトランプを买いに行ったため、中に意外にも2人の王がいることを発见して、2人の王(1枚の札はもともと54枚です_)...彼はランダムに中から5枚の札を抜いて、自分の手加減を測って、順子を抽選できるかどうかを見て、もし抽選したら、彼はスポーツ宝くじを買うことにしました.へへへ!!「赤いハートA、黒桃3、王さん、王さん、角片5」、「Oh My God!」顺子ではない……LLは不機嫌になって、彼は考えて、大きい王さんがいかなる数字を见ることができることを决めて、しかもAは1と见て、Jは11で、Qは12で、Kは13です.上の5枚のカードは「1,2,3,4,5」(大きさの王はそれぞれ2と4と見なしている)、「So Lucky!」になります.LLはスポーツ宝くじを買うことにしました.今、このカードを使って上の過程をシミュレートして、LLの運を教えてください.便宜上、王さんは0だと思います.

    構想


    まずソートして、サイズ王の数を統計して、それから遍歴して、どれだけの数が欠けているかを見て連続することができて、サイズ王の数を超えると失敗します.

    コード#コード#

    function IsContinuous(numbers)
    {
        if(numbers == null || numbers.length <= 0) return false;
        //        
        numbers.sort(function(a,b){
            return a - b;
        })
        var numOf0 = 0, numOfGap = 0, len = numbers.length;
        //       
        numbers.forEach(function(item){
            if(item == 0){
                numOf0++;
            }
        })
        var small = numOf0, big = small + 1;
        while(big < len){
          //       
            if(numbers[small] == numbers[big]){
                return false;
            }//     ,     
            numOfGap += numbers[big]-numbers[small]-1;
            small = big;
            big++;
        }
        return (numOfGap > numOf0) ? false : true;
    }
    

    46、子供たちの遊び(丸の中で最後に残った数)


    タイトルの説明


    毎年6月1日の子供の日、牛客は孤児院の子供を見舞いに行く小さな贈り物を用意しています.今年もそうです.HFは牛客のベテラン元老として、もちろん小さなゲームも用意されています.その中で、まず、子供たちを大きな輪に囲ませるゲームがあります.そして、彼はランダムに数mを指定し、0番の子供にカウントを開始させた.m-1を叫ぶたびにその子供は歌を歌って、それから贈り物箱の中で任意の贈り物を選ぶことができて、しかももう輪の中に戻らないで、彼の次の子供から、0...m-1の新聞数を続けます....このままでは...最后の1人の子供が残るまで、演技をしなくてもいいし、牛客の名高い「名探侦コナン」の典蔵版を手に入れることができます(定員は限られていますよ!!).どの子がこの贈り物をもらうか考えてみてください.(注:子供の番号は0からn-1まで)

    考え方1


    配列を作成し、m-1の位置に着くたびに配列内の要素を削除し、位置計0を再開します.

    コード#コード#

    function LastRemaining_Solution(n, m)
    {
        if(n < 1 || m < 1) return -1;
        var arr = [];
        var index = 0;
        var start = 0;
        for(var i = 0 ; i < n ; i++){
            arr.push(i);
        }//     n   
        while(arr.length > 1){
            for(var i = 1 ; i < m ; i++){
                index = (index + 1) % arr.length;
            }
            //splice()    /      /    ,          。
            //index   /       ,1        
            arr.splice(index,1);
        }
        return arr[0];//       
    }
    
    

    考えの2——もっと詳しい解釈があります


    n=1の場合f(n,m)=0;n>1のときf(n,m)=[f(n−1,m)+m]%n

    コード#コード#

    function LastRemaining_Solution(n, m)
    {
        if(n < 1 || m < 1) return -1;
        var last = 0;
        for(var i = 2 ; i <= n ; i++){
            last = (last + m) % i;
        }
        return last;
    }
    

    47、1+2+3+...+nを求めます


    タイトルの説明


    1+2+3+…+nを求めて、乗除法、for、while、if、else、switch、caseなどのキーワードと条件の判断文(A?B:C)を使うことができないことを要求します.

    構想


    for,ifなどで境界を判断することはできないので,短絡演算で判断するしかない.

    コード#コード#

    function Sum_Solution(n)
    {
        var result = n;
        //  
        var a = (n != 0) && (result += Sum_Solution(n-1))
        return result;
    }
    

    48、加減乗除しない加算


    タイトルの説明


    1つの関数を書いて、2つの整数の和を求めて、関数の体内で+、-、*、/の4つの演算記号を使用してはいけないことを要求します.

    構想


    例えば5(101)+2(011)で計算すると、まず進位せずに直接加算(101+011=001)してから進位(001+100=101)を加算し、進位を考慮せずに直接加算することで、1+0=1、1+1=0、0+0=0という異様な操作が見られます(^)、0、0に1、1に0を加算しても進位は発生せず、1に1を加算した場合のみ、前に1つの進位が発生します.このとき,2つの数が先にビットと演算を行い,それから左に1つ移動することを想像できる.

    コード#コード#

    function Add(num1, num2)
    {
        var sum, carry;
        do{
            sum = num1 ^ num2;
            carry =( num1 & num2 ) << 1;//     
            num1 = sum;
            num2 = carry;
        }while(num2 != 0)
        return sum;
    }