leetcode初級アルゴリズム配列(C++)

きほんアルゴリズムはいれつ
1.並べ替え配列から重複を削除
ソート配列を指定すると、繰り返し表示される要素をその場で削除し、各要素が1回だけ表示されるようにして、削除後の配列の新しい長さを返します.余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
例1:与えられた配列nums=[1,1,2]では、関数は新しい長さ2を返すべきであり、元の配列numsの最初の2つの要素は1,2に変更される.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
例2:nums=[0,0,1,1,2,2,3,4]が与えられ、関数は新しい長さ5を返し、元の配列numsの最初の5つの要素は0,1,2,3,4に変更されるべきである.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
構想
テーマを手に入れて、重複項目を見て、最初に思いついたのはsetです.直接遍歴して挿入すればいいです.しかしテーマは空間複雑度がO(1)であるため,スライド小標で実現する.

class Solution {
public:
    int removeDuplicates(vector& nums) {
        if(nums.empty())return 0;
        int n = 0;
        for(int i = 1;i

2.株の売買に最適なタイミングII
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
例1:入力:[7,1,5,3,6,4]出力:7解釈:2日目(株価=1)に購入し、3日目(株価=5)に売却し、この取引所は利益=5-1=4を得ることができる.その後、4日目(株価=3)に購入し、5日目に購入する(株価=6)の時に売って、この取引所は利益=6-3=3を得ることができます.
例2:入力:[1,2,3,4,5]出力:4解釈:1日目(株価=1)に購入し、5日目(株価=5)のときに売ると、この取引所は利益=5-1=4になります.1日目と2日目に株を相次いで購入してから売ることはできないことに注意してください.これは複数の取引に同時に参加しているので、再購入前に前の株を売却しなければなりません.
例3:入力:[7,6,4,3,1]出力:0解釈:この場合、取引が完了しないため、最大利益は0
構想:隣接する2日間の差を計算して、ただ儲けただけを買います

class Solution {
public:
    int maxProfit(vector& prices) {
        auto n = prices.size();
        if(n == 1)
            return 0;
        auto earn=0;
        for(auto i = 1;i0)earn+=prices[i]-prices[i-1];
        }
        return earn;
    }
};

3.回転配列
配列を指定し、配列内の要素をk個の位置に右に移動します.ここで、kは負ではありません.
例1:入力:[1,2,3,4,5,6,7]およびk=3出力:[5,6,7,1,2,3,4]解釈:右回転1ステップ:[7,1,2,3,4,5]右回転2ステップ:[6,7,1,2,3,4,5]右回転3ステップ:[5,6,7,1,2,3,4]
例2:入力:[-1,-100,3,99]およびk=2出力:[3,99,-1,-100]解釈:右へ1ステップ回転:[99,-1,-100,3]右へ2ステップ回転:[3,99,-1,-100]
説明:できるだけ多くの解決策を考え出して、少なくとも3つの異なる方法でこの問題を解決することができます.空間的複雑度がO(1)のその場アルゴリズムの使用が要求される.
構想
[原句]K回右シフトすれば終わり

class Solution {
public:
    void rotate(vector & nums,int k){
        if (nums.empty() || (k %= nums.size()) == 0) return;
        k %= nums.size();
        for(int i = 0 ;i& nums){
        int lastVal = nums.front();
        for(int i = 1;i

でもnums.size()が大きくなるとタイムアウトになるので、方法を変えなければなりません
2.利用vector::push_back(),vector::erase()シミュレーション左シフト
右シフトk回(k

class Solution {
public:
    void rotate(vector & nums,int k){
        if (nums.empty() || (k %= nums.size()) == 0) return;
        k %= nums.size();
        k = nums.size()-k;
        for(int i = 0 ;i

それともタイムアウト??wtf
3.考え方は、まず前のn-k個の数字を反転してから、後のk個の数字を反転して、最後に配列全体を反転することです.

class Solution {
public:
    void rotate(vector& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int n = nums.size();
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

4.重複がある
整数配列を指定し、重複要素が存在するかどうかを判断します.任意の値が配列に少なくとも2回現れる場合、関数はtrueを返します.配列内の各要素が異なる場合はfalseを返します.
例1:入力:[1,2,3,1]出力:true
例2:入力:[1,2,3,4]出力:false
例3:入力:[1,1,3,3,4,3,2,4,2]出力:true
考え方:並べ替え、同じ戻りfalseを繰り返し見る

class Solution {
public:
    bool containsDuplicate(vector& nums) {
        int i;
        if(nums.size() <= 1) return false;
        sort(nums.begin(),nums.end());
        for(i = 1;i < nums.size();i++){
            if(nums[i] == nums[i-1])return true;
        }
        return false;
    }
};

4.一度しか出てこない数字
空でない整数配列が与えられ、ある要素が1回しか現れない以外は、各要素が2回現れます.それが一度しか現れなかった要素を見つけます.
説明:あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?
例1:入力:[2,2,1]出力:1
例2:入力:[4,1,2,1,2]出力:4
考え方:異種または操作、同じものは0に相殺されます.

class Solution {
public:
    int singleNumber(vector& nums) {
        return accumulate(nums.begin(),nums.end(),0,bit_xor());// begin end initialVal operator
    }
};

5.両配列の交差II
2つの配列を指定し、関数を記述して交差を計算します.
例1:入力:nums 1=[1,2,2,1]、nums 2=[2,2]出力:[2,2]
例2:入力:nums 1=[4,9,5]、nums 2=[9,4,9,8,4]出力:[4,9]
説明:

出力結果の各要素の出現回数は、要素が2つの配列に現れる回数と一致する必要があります.

出力結果の順序を考慮しなくてもいいです.

ステップ:

与えられた配列が順序付けされている場合?アルゴリズムをどのように最適化しますか?

nums 1のサイズがnums 2よりずっと小さい場合、どの方法が優れていますか?

nums 2の要素がディスクに格納されている場合、ディスクメモリは限られており、すべての要素を一度にメモリにロードすることはできません.どうすればいいですか?

考え方:小さい配列を遍歴して、大きい中で同じものを探して、大きい配列からこの要素を削除します

class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        vector result;
        if(nums1.size()

6.プラス1
整数からなる非空配列で表される非負の整数を与え、その数に1を加える.最上位の数値は配列の先頭に格納され、配列内の各要素には1つの数値しか格納されません.整数0を除いて、この整数はゼロで始まると仮定できます.
例1:入力:[1,2,3]出力:[1,2,4]解釈:入力配列は数値123を表す.
例2:入力:[4,3,2,1]出力:[4,3,2,2]解釈:入力配列は数字4321を表す.
考え方は、簡単で、後ろから前へ行けばいいです.

class Solution {
public:
    vector plusOne(vector& digits) {
        bool c_flag = false;
        int i = (int)digits.size()-1;
        do{
            digits[i] = digits[i]+1;
            if(digits[i]>=10){
                digits[i]=digits[i]-10;
                c_flag = true;
            } else c_flag= false;
            i = i-1;
        }while (c_flag&&i>=0);
        if(i<0&&c_flag)digits.insert(digits.begin(),1);
        return digits;
    }
};

7.移動ゼロ
配列numsが与えられ、ゼロ以外の要素の相対的な順序を維持しながら、すべての0を配列の末尾に移動する関数が記述される.
例:入力:[0,1,0,3,12]出力:[1,3,12,0]
説明:追加の配列をコピーするには、元の配列で操作する必要があります.操作回数をできるだけ減らす.
考え方は、やはり前の削除と同じように、スライドダウンを利用する方法です

class Solution {
public:
    void moveZeroes(vector& nums) {
        if(nums.size()<2)return;
        int n = 0;
        for(int i = 0;i

8.両数の和
整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、その配列の下付きを返します.入力ごとに1つの答えしか対応しないと仮定できます.しかし、この配列の同じ要素を繰り返し利用することはできません.
例:nums=[2,7,11,15]が与えられ、target=9はnums[0]+nums[1]=2+7=9であるため[0,1]を返す
考え方、2つのforループネスト遍歴

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        vector result;
        for (int i = 0; i < nums.size(); i++)
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        return result;
    }
};

9.有効な数独
9 x 9の数独が有効かどうかを判断します.以下のルールに従って、入力した数字が有効であるかどうかを検証するだけです.数字1～9は、行ごとに1回しか表示されません.数字1～9は列ごとに1回しか表示されません.数字1〜9は、太い実線で区切られた3 x 3子宮内では1回しか現れない.
例1:［5］,［3］,［.］と入力し、".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]出力:true
例2:入力:[[8],[3],[.]".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",「.」,「7」,「9」]出力:false解釈:最初の行の最初の数字が5から8に変更された以外は、スペース内の他の数字は例1と同じである.しかし左上隅に位置する3 x 3宮内には2つの8が存在するため,この数独は無効である.
考えは、直接行、列、ブロックをチェックすればいいです.

class Solution {
public:
    bool isValidSudoku(vector>& board) {
        for(int i = 0;i<9;i++){
            if(!ValidSudoRow(board,i))return false;
            if(!ValidSudoColum(board,i))return false;
        }
        for(int i =0;i<3;i++)
            for(int j = 0;j<3;j++){
                if(!ValidSudoCell(board,i,j))return false;
            }
        return true;
    }

    bool ValidSudoRow(vector>& board,int row){
        set test;
        for(int i = 0;i<9;i++){
            if(board[row][i]=='.')continue;
            if(!board[row][i]>='1' && board[row][i]<='9')return false;
            if(test.find(board[row][i]-'0')==test.end()){
                test.insert(board[row][i]-'0');
            } else return false;
        }
        return true;
    }

    bool ValidSudoColum(vector>& board,int colum){
        set test;
        for(int i = 0;i<9;i++){
            if(board[i][colum]=='.')continue;
            if(!board[i][colum]>='1' && board[i][colum]<='9')return false;
            if(test.find(board[i][colum]-'0')==test.end()){
                test.insert(board[i][colum]-'0');
            } else return false;
        }
        return true;
    }
    
    bool ValidSudoCell(vector>& board,int row_i,int col_i){
        set test;
        for(int i = 0;i<3;i++)
            for(int j = 0;j<3;j++){
                if(board[i+row_i*3][j+col_i*3]=='.')continue;
                if(!board[i+row_i*3][j+col_i*3]>='1' && board[i+row_i*3][j+col_i*3]<='9')return false;
                if(test.find(board[i+row_i*3][j+col_i*3]-'1')==test.end()){
                    test.insert(board[i+row_i*3][j+col_i*3]-'1');
                } else return false;
            }
        return true;
    }
};

10.画像を回転
nを与える× nの2次元行列は1つの画像を表す.画像を時計回りに90度回転させます.説明:画像をその場で回転する必要があります.これは、入力した2 Dマトリクスを直接修正する必要があることを意味します.別のマトリクスを使用して画像を回転させないでください.
例1:matrix=[[1,2,3],[4,5,6],[7,8,9],
入力行列を[7,4,1],[8,5,2],[9,6,3]になるようにその場で回転する.
例2: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]のようにその場で回転させる.
構想
まず対角線を軸として反転し,次にx軸の中で上下に反転すると結果が得られる.

class Solution {
public:
    void rotate(vector > &matrix) {
        int n = matrix.size();
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < n - i; ++j) {
                swap(matrix[i][j], matrix[n - 1- j][n - 1 - i]);
            }
        }
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - 1 - i][j]);
            }
        }
    }
};

この方法はまず元の配列に対してその回転行列を取り,それから各行の数字を反転して結果を得ることができる.

class Solution {
public:
    void rotate(vector > &matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};