ネクタイネットアルゴリズム学習ノート--283

18268 ワード
アルゴリズム ネクタイネット 配列アルゴリズム アルゴリズムプログラミング
ネクタイネットアルゴリズム学習ノート
このシリーズのアルゴリズムのテーマはネクタイネットから来ます
配列クラスアルゴリズム初日
タイトル:
1つの配列numsが与えられ、1つの関数が記述され、すべての0が配列の末尾に移動し、非ゼロ要素の相対順序を維持する.
例:
  : [0,1,0,3,12]
  : [1,3,12,0,0]

説明:
  • は、追加の配列をコピーできない元の配列で動作する必要があります.
  • 操作回数を最小限に抑える.

    • 解題プロセス:
    考え方一:
    この問題を見た最初の考え方は、0を検出した後、配列の後ろの数を前に移動し、配列の末尾に0を補うことで、元の配列で動作し、追加の配列をコピーしないことを確保することです.
    コードは次のとおりです.
    class Solution {
    public void moveZeroes(int[] nums) {
        //   ，         0，   ，              ，   0     。
        int arraylength = nums.length;              //       
        int arrlength = arraylength;                //       
        for(int i=0;i<arrlength;i++){
            if(nums[i] == 0){           //         0；
                for(int j=i;j<arraylength-1;j++){   //             
                    nums[j]=nums[j+1];
                }
                nums[arraylength-1] = 0;        //     0
                i--;
                arrlength--;
            }
        }
    }
}

    次のことを考えます.
    このコードがネクタイに使用される場合37 ms
    こうすると、配列は1回しか遍歴しないのですが、配列に0が1つも現れず、配列の中の要素を移動する代価(回数)が大きいので、移動しなくてもいいのかと考え、
    考え方2:
    0が現れると私は移動しないで、ただ後ろに読み続け、後ろに読むと0ではないと出会ったとき、データを0の位置に移動します.
    そこで私は0の位置を記録するために変数を定義しましたが、この変数がどのように初期値(つまり、開始0がどこにあるか)を付与するかという新しい問題に直面しました.
    この問題は実は多くて、遍歴するデータは異なって、初めの0の位置も異なって、固定することができなくて、だから私は直接遍歴して、最初の0が現れる時この値を設定します.次に、0ではなく現在位置と交換し、配列が遍歴した後、前の配列長と現在記録されている0の位置の値の差が0を補う個数であるため、0を補うとよい.
    コードは次のとおりです.
    class Solution {
    public void moveZeroes(int[] nums) {
        //            0   ，            0，     0 ，         
        int i = 0;                           //         ，         
        int locationnum = 0;                     //     0      0   
        int arraylength = nums.length;              //       
        for(;i<arraylength;i++){                 //       0   
            if(nums[i]==0){
               locationnum = i;
               break;
            }
        }
        for(i++;i<arraylength;i++){                 //           0
            if(nums[i]!=0){                     //     0，     0     
                nums[locationnum] = nums[i];        //     0        
                locationnum++;
            }
        }
        if(locationnum != 0){
        	for(;locationnum<arraylength;locationnum++){  //    0        ，      0
            	nums[locationnum] = 0;
        	}
        }
    }
}
//   2ms

    ネクタイの上のこの問題の他の高品質の例:
    class Solution {
    public void moveZeroes(int[] nums) {
		int j = 0 ;
		for(int i=0;i<nums.length;i++){
			if(nums[i]!=0){
				int temp = nums[i];
				nums[i] = nums[j];
				nums[j++] = temp;
			}
		}
    }
}
//   1ms

    自己整理:この部分のコードは簡素で、私は第1回が直接気絶したことを見て、第2回はやっと反応して、構想はこのようです:
  • は、
    • を循環するための変数jを定義する.
  • 循環配列
  • は、現在のループ値が0であるか否かを判断する、0でないか否かを判断し、現在の値とループ変数位置の値とを交換する、ループ変数を1ビット
    • だけ前に移動する.
  • 0 0ならば、このコードをスキップして私の優在より最初の0がどこにあるかを探さなくても、直接循環すればOKだと思いますが、大きな配列で、中の0の数が少ないと、このアルゴリズムは時間が長くなり、最適とは言えないと思います.0ではない数がないので、追加の3つの文を実行しなければならないと思います.結局、アルゴリズムに入ったばかりなので、その複雑さはまだ計算できないので、個人的な推測にすぎません.
    class Solution {
    public void moveZeroes(int[] nums) {
        int idx = 0;
		for (int num : nums) {
			if (num != 0) {
				nums[idx++] = num;
			}
		}
		while (idx < nums.length) {
			nums[idx++] = 0;
		}
    }
}
//   2ms
    自己整理:このコードは私より簡潔で、私は拭いて、私が私のコードを最適化するように見えます.この考えははっきりしています.
  • は、0以外の数を記録するための変数を定義する
    • .
  • 0 0ではないデータを保存(ここでは0ではない変数を読み取るだけで、それからずっと保存して、私の前のように後ろのデータがすべて前に移動するわけではありません)
  • 0 0を
    • に揃える
    class Solution {
    public void moveZeroes(int[] nums) {
        int count = 0;
        int nonZeroIndex = 0;
        for(int i = 0;i<nums.length;i++)
        {
            if(nums[i] == 0)
            {
                count++;
            }
            else{
                nums[nonZeroIndex++] = nums[i];
            }
        }
        for(int i = nums.length-count;i<nums.length;i++)
        {
            nums[i] = 0;
        }
    }
}
//   3ms

    自己整理:このアルゴリズムの考え方もはっきりしています.
  • は2つの変数を定義し、1つのレコード0の個数、1つのレコードの現在のデータはすでにその位置に保存されている
    • である.
  • それから配列を循環して、0に出会って、記録0の個数は1をプラスして、0ではありませんて、データを保存して、現在の保存位置の変数を記録して+1
    • になります
  • の後に0
    • を補充します
    自己総括:アルゴリズムは私は簡素化が1本の最適化の道だと思って、しかし簡素化のコードは実行効率が高いことを代表しないで、しかし私の今とても明らかな欠点は:論理はどのようにして、コードはどのように書いて、コードが長すぎることを招いて、この点は私の論理の思考がまだ十分ではありませんことを反応して、まだ鍛える必要があります.
    【実験】ページング記憶管理方式のシミュレーションを要求する
    aのn次方の高速のアルゴリズム、N*N個の桁数はいくらです