第103场双周赛

929code / 2023-05-03 / 原文

1. K 个元素的最大和

送分题

``` class Solution { public: int maximizeSum(vector& nums, int k) { int num = *max_element(nums.begin(),nums.end()); int res = 0; while(k--!=0){ res+=num; num++; } return res; } }; ```

2. 找到两个数组的前缀公共数组

双哈希表

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> C(n);
        map<int,int> m1;
        map<int,int> m2;
        for(int i=0;i<A.size();i++){//遍历B
            if(B[i]==A[i]){
                C[i] = i==0?1:C[i-1]+1;//直接多一位
                continue;
            }
            C[i] = i==0?0:C[i-1];
                
            if(m1.count(B[i]))
                C[i]++;
            if(m2.count(A[i]))
                C[i]++;
            
            m1[A[i]]++;//对应值增加
            m2[B[i]]++;
        }
        return C;
    }
};

3. 网格图中鱼的最大数目

深度优先+标记

class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int res = 0;
        for(int i=0;i<m;i++)
            for(int j =0;j<n;j++)
                if(grid[i][j]>0){
                 int cur = search(grid,i,j);
                 res = max(res,cur);
            }
        return res;
    }
    int search(vector<vector<int>>& grid,int i,int j){
        if(grid[i][j]==0) return 0;//捕不到
        int res = grid[i][j];//捕鱼
        grid[i][j]= 0;//不再遍历
        if(i<grid.size()-1&&grid[i+1][j]>0) res+=search(grid,i+1,j); //往下
        if(j<grid[0].size()-1&&grid[i][j+1]>0) res+=search(grid,i,j+1); //往右
        if(i>0&&grid[i-1][j]>0) res+=search(grid,i-1,j);//往上
        if(j>0&&grid[i][j-1]>0)   res+=search(grid,i,j-1);//往左
        return res;
    }
};