2022年7月24日

695. 岛屿的最大面积

class Solution {
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> vis;
        vis.resize(n, vector<bool>(m));
        int ans = 0;

        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(!vis[i][j]&&grid[i][j]){
                    int cnt = 0;
                    queue<pair<int,int>> q;
                    q.push({i,j});
                    vis[i][j] = true;
                    while(!q.empty()){
                        cnt++;
                        auto t = q.front();q.pop();
                        int a = t.first,b=t.second;
                            for(int k = 0; k < 4; ++k){
                                int x = a+dx[k],y=b+dy[k];
                                if(x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]&&grid[x][y]){
                                //  if(x<0||y<0||x>=n||y>=m||!grid[x][y]||vis[x][y]) continue;
                                    vis[x][y] = true;
                                    q.push({x,y});
                                }
                            }
                    }
                    cout<<cnt<<' ';
                    ans = max(ans,cnt);
                }
            }
        }
        return ans;
    }
};

1388. 3n 块披萨

class Solution {
public:
    int c(vector<int> nums){
        int n = nums.size();
        vector<vector<int>> f(n+1,vector<int>((n+1)/3+1));
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <=(n+1)/3;++j){
                f[i][j] = max(f[i-1][j],(i-2>=0?f[i-2][j-1]:0)+nums[i-1]);
            }
        }
        return f[n][(n+1)/3];
    }

    int maxSizeSlices(vector<int>& slices) {
        vector<int> s1(slices.begin()+1,slices.end());
        vector<int> s2(slices.begin(), slices.end()-1);
        int x = c(s1);
        int y = c(s2);
        return max(x,y);
    }
};

213. 打家劫舍 II

class Solution {
    int c(vector<int> nums){
        int n = nums.size();
        int t1 = nums[0],t2 = max(nums[0],nums[1]);
        for(int i = 2; i < nums.size(); ++i){
            int t = t2;
            t2 = max(t2,t1+nums[i]);
            t1 = t;
        }
        return t2;
    }
public:
    int rob(vector<int>& slices) {
        if(slices.size()==1)    return slices[0];
        if(slices.size()==2)    return max(slices[0],slices[1]);
        vector<int> s1(slices.begin()+1,slices.end());
        vector<int> s2(slices.begin(), slices.end()-1);
        int x = c(s1);
        int y = c(s2);
        return max(x,y);
    }
};

1260. 二维网格迁移

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int n = grid.size(),m = grid[0].size();
        vector<vector<int>> res(n);
        int MOD = n*m;
        for(int i = 0,x=0; i < n; ++i) for(int j = 0; j < m; ++j,++x){
            int y = (x-k%MOD+MOD)%MOD;
            res[i].push_back(grid[y/m][y%m]);
        }
        return res;
    }
};

560. 和为 K 的子数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        map<int,int> mp;
        int pre = 0,ans = 0;
        mp[0] = 1;
        for(auto c:nums){
            pre+=c;
            if(mp[pre-k]) ans+=mp[pre-k];
            mp[pre]++;
        }
        return ans;
    }
};

1074. 元素和为目标值的子矩阵数量

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size(),ans=0;
        vector<vector<int>> f(n+1,vector<int>(m+1));
        for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) f[i][j] = f[i-1][j]+f[i][j-1]+matrix[i-1][j-1]-f[i-1][j-1];
        
        for(int i = 1; i <= n; ++i){
            for(int j = i; j <= n; ++j){
                unordered_map<int,int> mp;
                for(int k = 1; k <= m; ++k){
                    int t = f[j][k]-f[i-1][k];
                    if(target==t) ans++;
                    if(mp.count(t-target)) ans+=mp[t-target];
                    mp[t]++;
                }
            }
        }

        return ans;

    }
};

6127. 优质数对的数目

class Solution {
public:
    long long countExcellentPairs(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        int cnt[30] = {0};
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());
        for(auto c:nums){
            int t = 0;
            while(c) t+=c&1,c>>=1;
            mp[t]++;
            // cnt[t]++;
        }

        long long res = 0;
        for(int i = 0; i < 30; ++i)
            for(int j = 0;  j < 30; ++j)
                if(i+j>=k)
                    res+=(long long) mp[i]*mp[j];
                    // res+=(long long) cnt[i]*cnt[j];
        return res;
    }
};

4498. 指针

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20;
int a[N];

int main()
{
    int n;cin>>n;
    for (int i = 0; i < n; i ++ ) cin>>a[i];
    
    bool flag = false;
    for(int i = 0; i < 1<<n; ++i){
        int s = 0;
        for (int j = 0; j < n; j ++ ){
            // if(1<<j&i) s+=a[i];
            if(i>>j&1) s+=a[j];
            else s-=a[j];
        }
        // cout<<s<<endl;
        if(s%360==0){
            flag = true;
            break;
        }
    }
    if(flag) puts("YES");
    else puts("NO");
    return 0;
}