头像

你可以永远相信夫赖

Huya.赖神粉丝团


访客:2369

在线 


活动打卡代码 LeetCode 57. 插入区间

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& b) {
        vector<vector<int> >res;
        int k = 0;
        while(k<a.size() && b[0] > a[k][1]) 
        res.push_back(a[k++]);
        if(k<a.size())
        {
            b[0] = min(b[0] , a[k][0]);
            while(k<a.size() && b[1] >= a[k][0])
            b[1] = max(b[1],a[k++][1]);     
        }
        res.push_back(b);
        while(k<a.size())
        res.push_back(a[k++]);
        return res;
    }
};


活动打卡代码 LeetCode 56. 合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        if(intervals.empty())
        return ans;
        sort(intervals.begin(),intervals.end());
        int right = intervals[0][1];
        for(int i=0;i<intervals.size() ; i++)
        {
            int j = i+1;
            right = max(right , intervals[i][1]);
            while(j<intervals.size() && right>=intervals[j][0])
            {
                right = max(right,intervals[j][1]);
                j++;
            }
            ans.push_back({intervals[i][0],right});
            i = j - 1;
        }
        return ans;
    }
};


活动打卡代码 LeetCode 55. 跳跃游戏

class Solution {
public:
    int n;
    bool canJump(vector<int>& nums) {
        n = nums.size();
        vector<int>f(n);
        f[0]=true;
        for(int i=1,j=0;i<n;i++)
        {
            while(j<i && nums[j]+j < i) j++;
          //  cout << i<< ' '<<j<<endl;
            if(j == i ) continue;
            f[i] |= f[j];
        }
        return f[n-1];
    }
};


活动打卡代码 LeetCode 54. 螺旋矩阵

class Solution {
public:
    int dx[4]={0,1,0,-1};
    int dy[4]={1,0,-1,0};
    int n,m;
    vector<int>order;
    vector<vector<bool>> st;
    vector<vector<int>>mm;
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
            n=matrix.size();
            if(!n)
            return order;
            m =matrix[0].size();
            mm = matrix; 
            st= vector<vector<bool>>(n+1,vector<bool>(m+1));
            dfs(0,0,0,0);
            return order;
    }
   bool flag = false;
    void dfs(int cnt,int x,int y,int dir)
    {
        if(flag)
        return ;
            if(cnt==n*m)
            {
            flag =true;
            return ;}
            st[x][y]      =true;
            order.push_back(mm[x][y]);
            if(x+dx[dir]>=0 && x+dx[dir]<n && 
            y+dy[dir]>=0 && y+dy[dir]<m && !st[x+dx[dir]][y+dy[dir]])
            dfs(cnt+1,x+dx[dir],y+dy[dir],dir);
            else 
            {
                if(!(x+dx[dir]>=0 && x+dx[dir]<n && 
            y+dy[dir]>= 0 && y+dy[dir]<m && !st[x+dx[dir]][y+dy[dir]]))
                {
                    dir++;
                if(dir==4)
                dir=0;
                }
                dfs(cnt+1,x+dx[dir],y+dy[dir],dir);
            }
    }
};


活动打卡代码 LeetCode 53. 最大子序和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res=INT_MIN;
        int n=nums.size();
        vector<int>f(n);
        for(int i=0;i<nums.size();i++)
        {
            if(!i)
            {
                f[i]=nums[i];
                continue;
            }
            f[i]=max(nums[i],nums[i]+f[i-1]);
        }
        for(auto x:f)
        res=max(res,x);
        return res;
    }
};


活动打卡代码 LeetCode 52. N皇后 II

class Solution {
public:
    int n;
    int cnt;
    vector<vector<string>> ans;
    vector<bool>dg,g;
        vector<bool>col;
    int totalNQueens(int _n) {
        n = _n;
        dg = g = vector<bool>(2*n);
        col = vector<bool>(n);
        dfs(0);
        return cnt;
    }
    void dfs(int u)
    {
        if(u==n)
        {
            cnt++;
            return ;
        }
        for(int j=0;j<n;j++)
        {
            if(!col[j] && !dg[u+j] && !g[u-j+n])
            {
                col[j]=dg[u+j]=g[u-j+n]=true;
                dfs(u+1);
                col[j]=dg[u+j]=g[u-j+n]=false;

            }
        }
    }
};


活动打卡代码 LeetCode 51. N 皇后

class Solution {
public:
    int n;
    vector<vector<string>> ans;
    vector<bool>dg,g;
        vector<bool>col;
    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        dg = g = vector<bool>(2*n);
        col = vector<bool>(n);
        vector<string>path(n,string(n,'.'));
        dfs(0,path);
        return ans;
    }
    void dfs(int u,vector<string>&path)
    {
        if(u==n)
        {
            ans.push_back(path);
            return ;
        }
        for(int j=0;j<n;j++)
        {
            if(!col[j] && !dg[u+j] && !g[u-j+n])
            {
                col[j]=dg[u+j]=g[u-j+n]=true;
                path[u][j]='Q';
                dfs(u+1,path);
                col[j]=dg[u+j]=g[u-j+n]=false;
                path[u][j]='.';
            }
        }
    }
};


活动打卡代码 LeetCode 42. 接雨水

class Solution {
public:
    int trap(vector<int>& height) {
        int res=0;
        stack<int>stk;
        for(int i=0;i<height.size();i++)
        {
            int last=0;
            while(stk.size() && height[i]>=height[stk.top()])
            {
                res += (i - stk.top() - 1)*( -last +height[stk.top()]);
                last = height[stk.top()];
                stk.pop();
            }
            if(stk.size())  res+=(height[i]-last)*(i-stk.top()-1);
            stk.push(i);
        }
        return res;
    }
};


活动打卡代码 LeetCode 48. 旋转图像

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



class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<string> back=strs;
        for(auto &x: back)
        sort(x.begin(),x.end());
        int n=strs.size();

        unordered_map<string,int>mp;
        int cnt=0;
        for(int i=0;i<strs.size();i++)
        if(!mp.count(back[i]))
            mp[back[i]]=cnt++;
        vector<vector<string>>ans(cnt);
        for(int i=0;i<strs.size();i++)
        ans[mp[back[i]]].push_back(strs[i]);
        return ans;
    }
};