头像




离线:6个月前


最近来访(39)
用户头像
SUPERDOGE
用户头像
notyour_yei
用户头像
D.Y.L.
用户头像
七酱
用户头像
3C81yyn1a3F
用户头像
soccoder
用户头像
阿兔
用户头像
蕴意
用户头像
a-smiling
用户头像
khalil
用户头像
赵以恒
用户头像
丕定
用户头像
柠檬贝司
用户头像
R_U_OK
用户头像
只吃虾仁大雪菜
用户头像
ZQCa
用户头像
锦木千束
用户头像
RADWIMPS
用户头像
什么时候刷完基础课
用户头像
Hearer



7个月前

模拟+哈希表+双向链表

思路

见: https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/

代码

struct linknode//定义了一个链表结点结构体
{
    int key,value;
    linknode *prev;
    linknode *next;
    linknode():key(0),value(0),prev(nullptr),next(nullptr){}
    linknode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};
class LRUCache {
private:
    unordered_map<int,linknode*> cache;
    linknode* head;
    linknode* tail;
    int size;//记录实际大小
    int capacity;//记录容量
public:
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        head = new linknode();
        tail = new linknode();
        head->next=tail;
        tail->prev=head;
    }

    int get(int key) {
        if(!cache.count(key))
        return -1;
        linknode* node=cache[key];
        movetohead(node);
        return node->value;
    }

    void put(int key, int value) {
        if(!cache.count(key))
        {
            linknode* node =new linknode(key,value);
            cache[key]=node;
            addtohead(node);
            size++;
            if(size>capacity)
            {
                linknode* removed = removetail();
                cache.erase(removed->key);
                delete removed;
                size--;
            }
        }
        else
        {
            linknode* node=cache[key];
            node->value=value;
            movetohead(node);
        }
    }
    void addtohead(linknode* node)
    {
        node->prev=head;
        node->next=head->next;
        head->next->prev=node;
        head->next=node;
    }
    void removenode(linknode* node)
    {
        node->next->prev=node->prev;
        node->prev->next=node->next;
    }
    void movetohead(linknode* node)
    {
        removenode(node);
        addtohead(node);
    }
    linknode* removetail()
    {
        linknode* node=tail->prev;
        removenode(node);
        return node;
    }
};




8个月前

线性DP

思路

见: https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

代码

class Solution {
public:
    const static int N=3e4+10;
    int dp[N];
    int longestValidParentheses(string s) {
        int n=s.size();
        int ans=0;
        for(int i=1;i<n;i++)
        {
            if(s[i]==')')
            {
                if(s[i-1]=='(')
                dp[i]=(i>=2?dp[i-2]:0)+2;
                else if(i-dp[i-1]-1>=0&&s[i-dp[i-1]-1]=='(')
                dp[i]=dp[i-1]+(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0)+2;
            }
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};




8个月前

二分+思维+细节

思路

见: https://leetcode-cn.com/problems/divide-two-integers/solution/liang-shu-xiang-chu-by-leetcode-solution-5hic/

代码

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend==INT_MIN)//越界判断
        if(divisor==-1)
        return INT_MAX;
        else if(divisor==1)
        return INT_MIN;

        bool flag=false;
        if(dividend>0)
        {
            flag=!flag;
            dividend=-dividend;
        }
        if(divisor>0)
        {
            flag=!flag;
            divisor=-divisor;
        }

        int left=0,right=INT_MAX;
        while(left<right)
        {
            int mid=left+1+((right-left-1)>>1);
            if(quick(dividend,divisor,mid)){
                left=mid;
            }
            else
            right=mid-1;
        }
        if(flag)
        return -left;
        return left;
    }
    bool quick(int x,int y,int z)
    {
        int result=0,add=y;
        while(z)
        {
            if(z&1)
            {
                if(result<x-add)
                return false;
                result+=add;
            }
            if(z!=1)//正常来说z=1以后就结束了,add翻不翻倍无所谓,但是由于这里面有个影响结果的条件判断,所以必须加上这个z!=1的条件判断
            {
                if(add<x-add)
                return false;
                add+=add;
            }
            z>>=1;
        }
        return true;
    }
};




8个月前

哈希表+思维

思路

见: https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/

代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> ust;

        for(auto num:nums)
        ust.insert(num);

        int len=0;

        for(auto num:ust)
        {
            if(!ust.count(num-1))
            {
                int current_num=num;
                int now_len=1;
                while(ust.count(current_num+1))
                {
                    now_len++;
                    current_num++;
                }
                len=max(len,now_len);
            }
        }

        return len;
    }
};




8个月前

链表

思路

第一次做链表的题,熟悉一下格式操作,别的都没啥难的
见: https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode-solution/

代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head=nullptr,*tail=nullptr;
        int cnt=0;
        while(l1||l2)
        {
            int n1=0,n2=0;
            if(l1)
            n1=l1->val;
            if(l2)
            n2=l2->val;
            int sum=n1+n2+cnt;
            if(!head)
            head=tail=new ListNode(sum%10);
            else
            {
                tail->next=new ListNode(sum%10);
                tail=tail->next;
            }
            if(l1)
            l1=l1->next;
            if(l2)
            l2=l2->next;
            cnt=sum/10;
        }
        if(cnt)
        tail->next=new ListNode(cnt);
        return head;
    }
};




8个月前




8个月前

滑动窗口+有序序列(multiset)

思路

以后需要维护一个区间的最大值和最小值就用multiset,时间复杂度为logn
见: https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/jue-dui-chai-bu-chao-guo-xian-zhi-de-zui-5bki/

代码

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int left=0,right=0,max_len=0,n=nums.size();
        multiset<int> mst;
        for(;right<n;right++)
        {
            mst.insert(nums[right]);
            while(*mst.rbegin()-*mst.begin()>limit)
            {
                mst.erase(mst.find(nums[left]));
                left++;
            }
            max_len=max(max_len,right-left+1);    
        }
        return max_len;
    }
};




8个月前

找规律。。。感觉不是什么DP

思路


见: https://leetcode-cn.com/problems/rotate-function/solution/c-zhao-gui-lu-by-mountain-ocean-3zon/

代码

class Solution {
public:
    const static int N=1e5+10;
    int f[N];
    int maxRotateFunction(vector<int>& nums) {
        int n=nums.size();
        int sum=0;
        for(int i=0;i<n;i++)
        {
            f[0]+=i*nums[i];
            sum+=nums[i];
        }
        int ans=f[0];
        int j=n-1;
        for(int i=1;i<n;i++)
        {
            f[i]=f[i-1]-(n-1)*nums[j]+sum-nums[j];
            j--;
            ans=max(f[i],ans);
        }
        return ans;
    }
};




8个月前

分类讨论去模拟

思路

见: https://leetcode-cn.com/problems/push-dominoes/solution/chao-yue-559de-yong-hu-by-wwwtttjjj-2/

代码

class Solution {
public:
    string pushDominoes(string s) {
        int left=0,right=0,len=s.size();
        for(int i=0;i<len;i++)
        {
            if(s[i]!='.')
            {
                left=right;
                right=i;
                if(s[left]=='.'&&s[right]=='L')
                for(int j=left;j<=right;j++)
                s[j]='L';
                else if(s[left]==s[right])
                for(int j=left;j<=right;j++)
                s[j]=s[left];
                else if(s[left]=='R'&&s[right]=='L')
                {
                    int mid=(left+right)/2;
                    if((left+right)%2==0)
                    {
                        for(int j=left;j<mid;j++)
                        s[j]='R';
                        for(int j=mid+1;j<=right;j++)
                        s[j]='L';
                    }
                    else
                    {
                        for(int j=left;j<=mid;j++)
                        s[j]='R';
                        for(int j=mid+1;j<=right;j++)
                        s[j]='L';
                    }
                }
            }
        }
        if(s[right]=='R')
        for(int i=right;i<len;i++)
        s[i]='R';
        return s;
        }
};




8个月前

dfs+bfs

思路

见: https://leetcode-cn.com/problems/shortest-bridge/solution/bfs-tian-hai-zao-lu-ti-jie-si-lu-by-carp-6w8j/

代码

class Solution {
public:
    typedef pair<int,int> PII;
    queue<PII> q;
    int m,n;
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
    int g[110][110];
    void dfs(int x,int y,vector<vector<int>> &grid)
    {
        grid[x][y]=2;
        g[x][y]=0;
        q.push({x,y});
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1)
            dfs(nx,ny,grid);
        }
    }
    int shortestBridge(vector<vector<int>>& grid) {
        m=grid.size(),n=grid[0].size();
        memset(g,127,sizeof g);
        int flag=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            if(grid[i][j])
            {
                dfs(i,j,grid);
                flag=1;
                break;
            }
            if(flag)
            break;
        }
        int ans=INT_MAX;
        while(!q.empty())
        {
            int x=q.front().first,y=q.front().second;
            q.pop();
            for(int i=0;i<4;i++)
            {
                int nx=x+dx[i],ny=y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n)
                {
                    if(grid[x][y]==2&&grid[nx][ny]==0&&g[x][y]+1<g[nx][ny])
                    {
                        g[nx][ny]=g[x][y]+1;
                        q.push({nx,ny});
                    }
                    else if(((grid[x][y]==2&&grid[nx][ny]==1)||(grid[x][y]==0&&grid[nx][ny]==1))&&g[x][y]+1<ans)
                    ans=g[x][y]+1;
                    else if(grid[x][y]==0&&grid[nx][ny]==0&&g[x][y]+1<g[nx][ny])
                    {
                        g[nx][ny]=g[x][y]+1;
                        q.push({nx,ny});
                    }
                }
            }
        }
        return ans-1;
    }
};