LeetCode問題の難易度レベル

風船を突く困難な原理はこの文章を参考にします.https://leetcode-cn.com/problems/burst-balloons/solution/c-dong-tai-gui-hua-qu-jian-dp-mo-ban-ti-by-wilson7/

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(),1); nums.push_back(1);
        //dp[i][j]   i  j                
        vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0));   
        for(int r=2; r<nums.size(); r++)        //r     
            for(int i=0; i<nums.size()-r; i++){ //i    
                int j = i + r;                  //j    
                for(int k=i+1; k<j; k++)
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j]);
            }
        return dp[0][nums.size()-1];
    }
};

編集距離が難しくて思いついたら思いつく、思いつかないなら思いつかない、できるだけ理解しましょう

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        int dp[m + 1][n + 1];
        for (int i = 0; i <= m; i++) 
            dp[i][0] = i;
        for (int j = 1; j <= n; j++) 
            dp[0][j] = j;
        for (int i = 1; i <= m; i++) 
            for (int j = 1; j <= n; j++) {
                if (word1[i - 1] == word2[j - 1]) //      
                    dp[i][j] = dp[i - 1][j - 1];
                else // 、 、      
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        return dp[m][n];
    }
};

最長連続シーケンスが困難で、セットを調べて初期化するときは、まず配列内の各要素を次の数に初期化します.そして、彼が到着できる最も遠い数字を探せばいいです.

class Solution {
public:
    unordered_map<int,int> a;
    int find(int x){
        return a.count(x) ? a[x]=find(a[x]) : x;
    }
    int longestConsecutive(vector<int>& nums) {
        for(auto i:nums)
            a[i] = i+1;
        int ans = 0;
        for(auto i:nums){
            int y = find(i+1);
            ans = max(ans, y-i);
        }
        return ans;
    }
};

ハッシュ表法

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,int> a;
        for(auto i:nums)
            a[i] = i;
        int ans = 0;
        for(int i=nums.size()-1; i>=0; --i){
            if(!a.count(nums[i]-1)){
                int cur = nums[i];
                while(a.count(cur+1)){
                    ++cur;
                }
                ans=max(ans,cur-nums[i]+1);
            }
        }
        return ans;
    }
};

ツリーのシーケンス化と逆シーケンス化が困難

class Codec {//    ，              ，        ，      
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s(root, res);
        return res;
    }
    //             
    void dfs_s(TreeNode* root, string& res) {
        if (!root) {
            res += "null ";
            return;
        }
        res += to_string(root->val) + ' ';
        dfs_s(root->left, res);
        dfs_s(root->right, res);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        //       
        int u = 0;
        return dfs_d(data, u);
    }
    TreeNode* dfs_d(string& data, int& u) {
        if (u >= data.size()) return NULL;
        if (data[u] == 'n') {//  null
            u = u + 5;
            return NULL;
        }
        int val = 0, sign = 1;
        if (data[u] == '-') sign = -1, u ++ ;
        while(data[u] != ' '){val = val * 10 + data[u] - '0'; u++;}
        val *= sign;
        u = u + 1 ;
        auto root = new TreeNode(val);
        root->left = dfs_d(data, u);
        root->right = dfs_d(data, u);
        return root;
    }
};

スライドウィンドウの最大値が困難この問題はdequeで、キューヘッダを常に最大値に保つ

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> que;
        int left=0, right=0;
        for (auto num:nums){
            while(!que.empty() && que.back() < num){
                que.pop_back();
            }
            que.push_back(num);
            right++;
            if (right-left >=k){
                res.push_back(que.front());
                if (nums[left] == que.front())
                    que.pop_front();
                left++;
            }
        }
        return res;
    }
};

最初の正数を失うのは難しい

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if (nums.empty()) return 1;
        vector<int> vec(nums.size(), 0);
        for (auto num:nums){
            if (num > 0 && num <= nums.size())
                vec[num-1] = 1;
        }
        int res = -1;
        for (int i=0; i<vec.size(); i++){
            if (vec[i] == 0){
                res = i+1;
                break;
            }
        }
        if (res == -1) return nums.size()+1;
        return res;
    }
};

剣指Offer 51.配列内の逆シーケンスの困難

class Solution {
    int res = 0;
    void mergeSort(vector<int>& nums, vector<int>& temp, int l, int r){
        if (l >= r) return;
        int mid = (l + r) / 2;
        mergeSort(nums, temp, l, mid);
        mergeSort(nums, temp, mid+1, r);
        int i=l, j=mid+1; int t=0;
        while (i<=mid && j<=r){
            if (nums[i] <= nums[j]){
                res += (j - (mid + 1));//      
                temp[t++] = nums[i++];
            }
            else 
                temp[t++] = nums[j++];
        }
        while (i <= mid) {temp[t++] = nums[i++]; res += (j-(mid+1));}//      
        while (j <= r) temp[t++] = nums[j++];
        t = 0;
        for (int i=l; i<=r; i++)
            nums[i] = temp[t++];
    }
public:
    int reversePairs(vector<int>& nums) {
        vector<int> temp(nums.begin(), nums.end());
        mergeSort(nums, temp, 0, nums.size()-1);
        return res;
    }
};

逆ポーランド式評価(スタック実装)中等

class Solution {
public:
    int ans;
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int str_mid1, str_mid2;
        for (auto v_mate : tokens) {
            if (v_mate == "+") {
                str_mid1 = stk.top();
                stk.pop();
                str_mid2 = stk.top();
                stk.pop();
                stk.push(str_mid2 + str_mid1);
            }
            else if (v_mate == "-") {
                str_mid1 = stk.top();
                stk.pop();
                str_mid2 = stk.top();
                stk.pop();
                stk.push(str_mid2 - str_mid1);
            }
            else if (v_mate == "*") {
                str_mid1 = stk.top();
                stk.pop();
                str_mid2 = stk.top();
                stk.pop();
                stk.push(str_mid2 * str_mid1);
            }
            else if (v_mate == "/") {
                str_mid1 = stk.top();
                stk.pop();
                str_mid2 = stk.top();
                stk.pop();
                stk.push(str_mid2 / str_mid1);
            }
            else stk.push(atoi(v_mate.c_str()));
        }
        ans = stk.top();
        return ans;
    }
};

辞書順のK番目の小さな数字は難しい

class Solution {
public:
    int findKthNumber(int n, int k) {
        int cur = 1;
        --k;
        while (k > 0){
            //first     , last      
            long long first=cur, last=cur+1, step=0;
            while(first <= n){
                //                 
                step += min((long long)n+1,last) - first;
                first *= 10;
                last *= 10;
            }
            if(step <= k){
                k -= step;
                cur++;
            }
            else{
                k--;
                cur *= 10;
            }
        }
        return cur;
    }
};