刷题日记-2

写个模型，让LLM完成初筛图片？。

Q1-用栈实现队列

link

思路：如果只是维护一个栈，那么在每次pop/peek的时候都需要把主栈倒一下。加入另外一个栈，以空间换时间，不用在每次pop/peek的时候都要while循环了。

class MyQueue {
private:
    stack<int> in,out;

    void in2out(){
        while(!in.empty()){
            out.push(in.top());
            in.pop();
        }
    }
public:
    MyQueue() {
    }
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        if(out.empty()){in2out();}
        int pop_num = out.top();out.pop();
        return pop_num;
    }
    
    int peek() {
        if(out.empty()){in2out();}
        int pop_num = out.top();
        return pop_num;
    }
    
    bool empty() {
        return in.empty()&&out.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

Q2-查找和最小的k对数字

link

TLE的版本：因为两个for循环。

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        auto cmp=[&nums1,&nums2](const pair<int,int>& a,const pair<int,int>& b){
            return nums1[a.first]+nums2[a.second]>nums1[b.first]+nums2[b.second];
        };
        int m=nums1.size();
        int n=nums2.size();
        vector<vector<int>> ans;
        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp);

        for(int i=0;i<min(m,k);i++){
            for(int j=0;j<nums2.size()&&j<k;j++){
                pair<int,int> num(i,j);
                pq.push(num);
            }
        }
        while(k>0){
            auto [i, j] = pq.top();
            pq.pop();
            ans.push_back({nums1[i], nums2[j]});
            k--;
        }
        return ans;
    }
};

AC版：修改了两个for训练为一个，然后对应修改while循环。考虑到比[i,j]第一大的只可能是[i,j+1]或者[i+1,j]，因为我们已经固定了向下的方向(所有的向右走的入口j=0)，所以只需要不断向右扩展就好。

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        auto cmp=[&nums1,&nums2](const pair<int,int>& a,const pair<int,int>& b){
            return nums1[a.first]+nums2[a.second]>nums1[b.first]+nums2[b.second];
        };
        int m=nums1.size();
        int n=nums2.size();
        vector<vector<int>> ans;
        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp);

        for(int i=0;i<min(m,k);i++){
            pair<int,int> num(i,0);
            pq.push(num);
        }
        while(k--){
            auto [i, j] = pq.top();
            pq.pop();
            ans.push_back({nums1[i], nums2[j]});
            if(j+1<n){
                pair<int,int> num(i,j+1);
                pq.push(num);
            }
        }
        return ans;
    }
};

Q3-多次求和构造目标数组⚠️⚠️⚠️

link

class Solution {
public:
    bool isPossible(vector<int>& target) {
        priority_queue<int>q;
        long long sum_value=accumulate(target.begin(),target.end(),0LL);
        for(int i:target)q.push(i);
        while (q.top()>1){
            //这个判定条件？
            int max_value = q.top();
            sum_value -= max_value;
            q.pop();

            if(sum_value==0||max_value<=sum_value)return false;
            max_value = (max_value-1)%sum_value+1;
            sum_value+=max_value;
            q.push(max_value);
        }
        return true;
    }
};

Q4-旋转字符串

link

思路：一开始我的想法就是这个goal的串是部分有序的，所以重点在找到那个变换点。但是后续就不知道如何操作。看到题解，了解到直接枚举s中的每个下标。

class Solution {
public:
    bool rotateString(string s, string goal) {
        if(s.size()!=goal.size())return false;
        for(int i=0;i<s.size();i++){
            string s1=s.substr(0,i);
            string s2=s.substr(i,s.size());
            if(s2+s1==goal)return true;
        }
        return false;
    }
};

但是有更加简单的方法，也就是直接字符串s+s中会包含goal，就说明是可以旋转的子串。

class Solution {
public:
    bool rotateString(string s, string goal) {
        return (s.size()==goal.size())&&(s+s).find(goal)!=string::npos;
    }
};

Q5-重复叠加字符串匹配

link

思路：a大部分情况是b的子串，但是对a进行重复叠加得到字符串s，b是s的子串。我要知道，到底是对a进行了多少次的重复叠加。

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        string s;
        int cnt=0;
        while(s.size()<b.size()){
            s+=a;
            cnt++;
        }
        if(s.find(b)!=string::npos)return cnt;
        else if((s+a).find(b)!=string::npos)return cnt+1;
        else return -1;

    }
};