LeetCode力ボタンブラシ問題記録熱問題HOT 100(46,48,49,53,55)問題+アルゴリズム分析+Cpp解答

GitHubリンク:https://github.com/WilliamWuLH/LeetCode
いいと思うなら⭐StarとFork❤
46.Permutations
遡及法:
遡及法を用いる.
追加のスペースオーバーヘッドはmap useで、どの要素が使用されているかを記録します.

class Solution {
public:
    vector> ans;
    vector temp;
    map use;
    vector> permute(vector& nums) {
        dfs(0, nums);
        return ans;
    }
    void dfs(int count, vector& nums){
        if(count == nums.size()){
            ans.push_back(temp);
            return;
        }
        for(int i=0; i < nums.size(); i++){
            if(use[i] != 1){
                temp.push_back(nums[i]);
                use[i] = 1;
                dfs(count+1, nums);
                temp.pop_back();
                use[i] = 0;
            }
        }
    }
};

48.Rotate Image
補助行列+直接回転を作成するには、次の手順に従います.

class Solution {
public:
    void rotate(vector>& matrix) {
        vector> temp = matrix;
        int len = matrix.size();
        for(int i=0; i nums = temp[i];
            for(int j=0; j

49.Group Anagrams
ビルドアルファベット統計アルファベット個数+ビルドハッシュマッチングアルファベット個数:

class Solution {
public:
    vector> groupAnagrams(vector& strs) {
        int len = strs.size();
        int count = 0;
        vector

文字列のソート+ハッシュ表を作成する文字列と答えに対応する場所:

class Solution {
public:
    vector> groupAnagrams(vector& strs) {
        int len = strs.size();
        map match;
        vector> ans;
        for(int i=0; i add;
                add.push_back(strs[i]);
                ans.push_back(add);
            }
        }
        return ans;
    }
};

53.Maximum Subarray
動的計画:

class Solution {
public:
    int maxSubArray(vector& nums) {
        vector dp;
        int len = nums.size();
        int ans = nums[0];
        dp.push_back(nums[0]);
        for(int i=1; i dp[i])
                dp[i] = dp[i-1] + nums[i];
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

55.Jump Game
貪欲法:
配列の末尾から前を探して、最後の位置に到達できる、最初の位置に最も近い位置を見つけます.
最後に,この位置が配列の最初の位置であるか否かを判断する.

class Solution {
public:
    bool canJump(vector& nums) {
        int len = nums.size();
        int pos = len-1;
        for(int i=len-1; i>=0; i--){
            if(i+nums[i] >= pos)
                pos = i;
        }
        return pos == 0;
    }
};