LeetCodeの配列問題(一)

1.正しいプログラムを書き出す方法：

変数の意味を明確にする

サイクル不変量

小データ量テスト

ビッグデータ量テスト

2.LeetCode:283移動ゼロ

問題の説明:
配列numsが与えられ、非ゼロ要素の相対順序を維持しながら、関数を記述して、すべての0をその末尾に移動する.
例えば、nums = [0, 1, 0, 3, 12]が定義され、関数が呼び出された後、numsは[1, 3, 12, 0, 0]であるべきである.
注意事項:

は、新しい配列に余分なスペースを割り当てないで、元の配列で動作する必要があります.

操作総数を最小限に抑える.

考え方:

問題の制限に注意して、余分な空間を使うことができなくて、元の配列の上で操作しなければなりません

非ゼロ要素の相対順序

を保持する.
コードディスプレイ

package algorithm.interview;

public class MoveZeroClass {
    // O(n)
    // O(1)
    public void moveZeroes(int[] nums) {
        if (nums==null||nums.length<=0) {
            return;
        }
        int zeroNum=0;// 0 
        int len=nums.length;
        for(int i=0;iif (nums[i]!=0) 
                swap(nums,i,i-zeroNum);
            else 
                zeroNum++;
        }
    }
    public void moveZeroes2(int[] nums) {
        if (nums==null||nums.length<=0){
            return;
        }
        int len=nums.length;
        int k=0;//nums [0,k) 0 
        // i ， [0,i] 0 
        //d [0,k) 
        for (int i=0;iif (nums[i] != 0)
                nums[k++] = nums[i];
        // nums 0
        for (int i=k;i0;
    }
    public  void moveZeros3(int [] nums){
        int k=0;
        for (int i=0;iif (nums[i]!=0)
                if (i!=k)// 
                    swap(nums[i],nums[k++],nums);
                else
                    k++;
        }
    }
}

3.LeetCode :27

問題の説明
配列numsと値valを指定すると、valに等しいすべての数値の要素をその場で除去し、除去後の配列の新しい長さを返す必要があります.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
要素の順序は変更できます.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
例1:

  nums = [3,2,2,3], val = 3,

  2,   nums   2。

 。

例2:

  nums = [0,1,2,2,3,0,4,2], val = 2,

  5,   nums   0, 1, 3, 0, 4。

 。

 。

考え方:
クラスは前の問題よりいいですが、この問題は特定の数で、前の問題は0で、本質は同じです.
コード#コード#

class Solution {
    public int removeElement(int[] nums, int val) {
        int k=0;
        for (int i=0;iif (nums[i]!=val)
                if (i!=k)
                    swap(nums,i,k++);
                else
                    k++;
        }
        return  k;
    }
    private void swap(int[] nums, int index1, int index2) {
        int temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;

    }
}

4.LeetCode :26

問題の説明
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が1回だけ表示されるようにして、削除後の配列の新しい長さを返します.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
例1:

  nums = [1,1,2], 

  2,   nums   1, 2。 

 。

コードディスプレイ

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums==null||nums.length<=0)
            return 0;
        int n=nums.length;
        int k=0;//[0,k] 
        for (int i=1;iif (nums[i]!=nums[k])
                nums[++k]=nums[i];
        }
        return  k+1;
    }
}

5.LeetCode :80

問題の説明
ソート配列を指定すると、重複する要素をその場で削除し、各要素が最大2回表示され、削除後の配列の新しい長さを返す必要があります.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
例1:

  nums = [1,1,1,2,2,3],

  length = 5,   1, 1, 2, 2, 3 。

 。

例2:

  nums = [0,0,1,1,1,1,2,3,3],

  length = 7,   0, 0, 1, 1, 2, 3, 3 。

 。

考え方:
次の問題は同じですが、ここにカウンターを1つつければいいだけです.
コードディスプレイ

package com.antfin.leetcode;

import com.utils.CommonUtils;

public class RemoveDuli {
    public int removeDuplicates(int[] nums) {
        if (nums==null||nums.length<=0)
            return 0;
        int k=0;// 
        int times=0;
        for (int i=1;iif (nums[i]==nums[k]) {
                times++;
                if (times==1) {
                    nums[++k] = nums[i];// 
                }
            }
            if (nums[i]!=nums[k])// 
            {
                nums[++k] = nums[i];
                times=0;// 
            }

        }
        return k+1;
    }

    public static void main(String[] args) {
        RemoveDuli r=new RemoveDuli();
        int [] arr={0,0,1,1,1,1,2,3,3};
        int i = r.removeDuplicates(arr);
        System.out.println(i);
        CommonUtils.printArr(arr);
    }
}