LeetCodeアルゴリズム練習-配列編

並べ替え配列から重複を削除
ソート配列を指定すると、繰り返し表示される要素を元の場所(元の場所アルゴリズム)で削除し、各要素が一度だけ表示され、削除後の配列の新しい長さを返す必要があります.余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
例

     nums = [1,1,2], 
           2,       nums            1, 2。 
                   。

説明

// nums   “  ”     。    ，         
int len = removeDuplicates(nums);
//                    。
//            ,                    。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

構想

1.    
2. (  )      ，      ，       ，       ，            

コード#コード#

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

株式売買のベストタイミングII
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.
あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.
ps:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
例

  : [7,1,5,3,6,4]
  : 7
  :    2  （     = 1）     ，   3  （     = 5）     ,            = 5-1 = 4 。  ，   4  （     = 3）     ，   5  （     = 6）     ,            = 6-3 = 3 。

構想

                  ，               

コード#コード#

class Solution {
    public int maxProfit(int[] prices) {
        //                  ，               
        int m = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) m += prices[i] - prices[i - 1];
        }
        return m;
    }
}

かいてんはいれつ
n個の要素を含む配列を右にkステップ回転します.
n=7,k=3の場合,所与の配列[1,2,3,4,5,6,7],右回転後の結果は[5,6,7,1,2,3,4]であった.
ps:注意要求空間複雑度O(1)
構想

  K     ，                  ，          1 

コード#コード#

class Solution {
    public void rotate(int[] nums, int k) {
       int len = nums.length;
        while (k > 0) {
            int cache = nums[len - 1];//         
            for (int x = len - 2; x >= 0; x--) {
                nums[x + 1] = nums[x];//                  
            }
            nums[0] = cache;
            --k;//      
        }
    }
}

重複の存在
整数配列を指定し、重複要素が存在するかどうかを判断します.
任意の値が配列に少なくとも2回現れる場合は、関数はtrueを返します.各要素が異なる場合はfalseを返します.
例

[5,3,1,2,4,2,6,10]       2       2      true

構想

//               

コード#コード#

class Solution {
    public boolean containsDuplicate(int[] nums) {
        //               
        Arrays.sort(nums);
        for (int x = 1; x < nums.length; x++) {
            if (nums[x] == nums[x-1]) return true;
        }
        return false;
    }
}

一度しか現れない数字
整数配列が与えられ、ある要素が1回しか現れない以外は、各要素が2回現れます.それが一度しか現れなかった要素を見つけます.ps:あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?
構想

//          
// a ^ b = b ^ a
// a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;

コード#コード#

class Solution {
    public int singleNumber(int[] nums) {
        int len = nums.length;
        if (len == 1) return nums[0];
        int result = nums[0];
        for (int i = 1; i < len; i++) {
            result ^= nums[i];//          
           // a ^ b = b ^ a
           // a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
        }
        return result;
    }
}

2つの配列の交差II
2つの配列を指定し、交差を計算する方法を書きます.
例えば、nums 1=[1, 2, 2, 1]、nums 2=[2, 2]とする、[2, 2]を返す.
に注意

1.              ，                 。
2.              。
3.             ？          ？
4.   nums1      nums2    ，      ？
5.  nums2         ，      ，                ，     ？

構想

        ，   nums1       ，       nums2       ，            1，           。                  O(n)。     HashMap   

コード#コード#

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        ArrayList<Integer> temp = new ArrayList<>();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            Integer value = hashMap.get(nums1[i]);
            hashMap.put(nums1[i], (value == null ? 0 : value) + 1);
        }
​
        for (int i = 0; i < nums2.length; i++) {
            if (hashMap.containsKey(nums2[i]) && hashMap.get(nums2[i]) != 0) {
                temp.add(nums2[i]);
                hashMap.put(nums2[i], hashMap.get(nums2[i]) - 1);
            }
        }
        int[] result = new int[temp.size()];
        for (int i = 0; i < temp.size(); i++) {
            result[i] = temp.get(i);
        }
        return result;
    }
}

プラス1
非負の整数からなる非空の配列を指定し、その数に1を加えて新しい配列を返します.
最上位の数値は配列の先頭に格納され、配列内の各要素には1つの数値しか格納されません.
整数0を除いて、この整数はゼロで始まると仮定できます.
例

  : [1,2,3]
  : [1,2,4]
  :          123。
​
  : [4,3,2,1]
  : [4,3,2,2]
  :          4321。

構想

                    
​
    +1  ，       9
​
    +1  ，       9，      carry，           。      ，     9.
​
    +1  ，       9，      carry，           ，      ，       9，      ，     9。
​
              ：
1.     
2.      
​
      
//      ，           9，  1   0，          (lenght+1)    ，0   1    
​
       
//       ，          ，            

コード#コード#

class Solution {
    public int[] plusOne(int[] digits) {
       int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            if (carry == 0) {
                return digits;
            }
            int tmp = digits[i] + carry;
            carry = tmp / 10;
            digits[i] = tmp % 10;
        }
        if (carry != 0) {
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            return result;
        }
        return digits;
    }
}

移動ゼロ
配列numsが与えられ、非ゼロ要素の相対順序を維持しながら、関数を記述して、すべての0をその末尾に移動する.
例えば、nums = [0, 1, 0, 3, 12]が定義され、関数が呼び出された後、numsは[1, 3, 12, 0, 0]であるべきである.
注意事項
新しい配列に余分なスペースを割り当てないで、元の配列で操作する必要があります.
操作総数を最小限に抑える.
構想

1.    ，               ，       
2.  0             0           0   

コード#コード#

class Solution {
    public void moveZeroes(int[] nums) {
        int unZeroCount = 0;//       0     ，       
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                nums[unZeroCount] = nums[i];
                ++unZeroCount;
            }
        }
        //         0     
        int zeroCount = len - unZeroCount;
        for (int i = len - 1; i > 0; i--) {
            if (zeroCount == 0) return;
            nums[i] = 0;
            --zeroCount;
        }
    }
}

両数の和
整数配列とターゲット値を指定し、配列とターゲット値の2つの数を見つけます.
入力ごとに1つの答えしか対応せず、同じ要素が再利用できないと仮定できます.
例

   nums = [2, 7, 11, 15], target = 9
   nums[0] + nums[1] = 2 + 7 = 9
     [0, 1]

構想

     O(n)          。   O(n)        a   target-a         ，  Hash ；      ，        Hash  ，          O(1)，        O(n)。

コード#コード#

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) map.put(nums[i], i);
        for (int i = 0; i < nums.length; i++) {
            int value = target - nums[i];
            //                        6-3=3        
            if (map.containsKey(value) && map.get(value) != i) {
                int index = map.get(value);
                if (i < index) return new int[]{i, index};
                return new int[]{index, i};
            }
        }
        return new int[0];
    }
}

画像を回転
nを与える× nの2次元行列は1つの画像を表す.
画像を時計回りに90度回転させます.
説明

//          ，                  。               。

例

   matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],
​
        ，    :
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
​
   matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 
​
        ，    :
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]
​

構想

    (   )
90°（      270°）：a[i][j]=b[j][n-i-1];
//         
        ：b[i][j] = a[j][i];
           ，                 90°    

コード#コード#

class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        int length = matrix.length;
        for (int i = 0; i < length / 2; i++) {
            for (int j = 0; j < (length + 1) / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[length - j - 1][i];
                matrix[length - j - 1][i] = matrix[length - i - 1][length - j - 1];
                matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
                matrix[j][length - i - 1] = tmp;
            }
        }
    }
}