leetcode解题思路分析（九十五）825 - 831 题

约定不等于承诺〃 2022-09-16 00:15 233阅读 0赞

1.  适龄的朋友  
    人们会互相发送好友请求，现在给定一个包含有他们年龄的数组，ages\[i\] 表示第 i 个人的年龄。当满足以下任一条件时，A 不能给 B（A、B不为同一人）发送好友请求：  
    age\[B\] <= 0.5 \* age\[A\] + 7  
    age\[B\] > age\[A\]  
    age\[B\] > 100 && age\[A\] < 100  
    否则，A 可以给 B 发送好友请求。  
    注意如果 A 向 B 发出了请求，不等于 B 也一定会向 A 发出请求。而且，人们不会给自己发送好友请求。  
    求总共会发出多少份好友请求?

**桶排序之后按年龄遍历即可。**

class Solution { 
    public:
        int numFriendRequests(vector<int>& ages) { 
            int cnt[121];
            memset(cnt, 0 , sizeof(cnt));
            for (int age : ages)
            { 
                ++cnt[age];
            }
    
            int res = 0;
            for (int a  = 0; a <= 120; ++a)
            { 
                int cntA = cnt[a];
                if (cntA == 0)
                { 
                    continue;
                }
                for (int b = 0; b <= 120; ++b)
                { 
                    int cntB = cnt[b];
                    if (cntB == 0)
                    { 
                        continue;
                    }
                    if ((a*0.5+7 >= b) || (b > a) || (a < 100 && 100 < b))
                    { 
                        continue;
                    }
                    { 
                        // cout << cntA << " " << cntB << " " << a << " vs " << b << endl;
                        res += cntA * cntB;
                        if (a == b)
                        { 
                            res -= cntA;
                        }
                    }
                }
            }
        
            return res;
        }
    };

1.  安排工作以达到最大收益  
    有一些工作：difficulty\[i\] 表示第 i 个工作的难度，profit\[i\] 表示第 i 个工作的收益。  
    现在我们有一些工人。worker\[i\] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker\[i\] 的工作。  
    每一个工人都最多只能安排一个工作，但是一个工作可以完成多次。  
    举个例子，如果 3 个工人都尝试完成一份报酬为 1 的同样工作，那么总收益为 $3。如果一个工人不能完成任何工作，他的收益为 $0 。  
    我们能得到的最大收益是多少？

**用哈希表存难度和收益的关系，要点在于收益用前缀和存最大收益以及不同工作难度相同时取最大收益存**

class Solution { 
    public:
        int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) 
        { 
            int                ret  = 0;
            int                nPos = 0;
            int                nSize = difficulty.size();
            std::unordered_map<int, int> ProfitMap;
    
            if (nSize == 0)
            { 
                return ret;
            }
    
            for (int i = 0; i < nSize; i++)
            { 
                int nBefore = 0;
                if (ProfitMap.find(difficulty[i]) != ProfitMap.end())
                { 
                    nBefore = ProfitMap[difficulty[i]];
                }
                ProfitMap[difficulty[i]] = max(profit[i], nBefore);
            }      
    
            sort(difficulty.begin(), difficulty.end());
            sort(worker.begin(), worker.end());
    
            for (int i = 1; i < nSize; i++)
            { 
                ProfitMap[difficulty[i]] = max(ProfitMap[difficulty[i]], ProfitMap[difficulty[i - 1]]);
            }
    
            for (int i = 0; i < worker.size(); i++)
            { 
                while (difficulty[nPos] <= worker[i] && nPos < nSize)
                { 
                    nPos++;
                }
    
                nPos--;
                
                if (nPos < 0)
                { 
                    nPos = 0;
                    continue;
                }
    
                ret += ProfitMap[difficulty[nPos]];
            }
    
            return ret;
        }
    };

1.  最大人工岛  
    给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿 由一组上、下、左、右四个方向相连的 1 形成。

**DFS遍历记录每个岛，然后再DFS遍历海洋进行查询**

#define maxn 250005
    int getIdx(int i,int j,int m){ 
        return i*m+j;
    }
    class UF{ 
    public:
        int fa[maxn],rank[maxn],size[maxn];
        void init(vector<vector<int>>&grid){ 
            int n=grid.size(),m=grid[0].size();
            for(int i=0;i<n*m;i++){ 
                fa[i]=i;
                rank[i]=1;
            }
            for(int i=0;i<n;i++){ 
                for(int j=0;j<m;j++){ 
                    int idx=getIdx(i,j,m);
                    if(grid[i][j]==1)size[idx]=1;
                    else size[idx]=0;
                }
            }
        }
        int find(int x){ 
            return x==fa[x]?x:(fa[x]=find(fa[x]));
        }
        void uni(int i,int j){ 
            int x=find(i),y=find(j);
            if(x==y)return;
            if(rank[x]<rank[y]){ 
                fa[x]=y;
                size[y]+=size[x];
            }else{ 
                fa[y]=x;
                size[x]+=size[y];
            }
            if(rank[x]==rank[y]&&x!=y)rank[y]++;
        }
        int getSize(int i){ 
            int root=find(i);
            return size[root];
        }
    };
    
    class Solution { 
    public:
        int largestIsland(vector<vector<int>>& grid) { 
            int n=grid.size(),m=grid[0].size();
            UF uf;
            uf.init(grid);
            for(int i=0;i<n;i++){ 
                for(int j=0;j<m;j++){ 
                    if(grid[i][j]==1){ 
                        if(i-1>=0&&grid[i-1][j]==1){ 
                            uf.uni(getIdx(i,j,m),getIdx(i-1,j,m));
                        }
                        if(j-1>=0&&grid[i][j-1]==1){ 
                            uf.uni(getIdx(i,j,m),getIdx(i,j-1,m));
                        }
                    }
                }
            }
            int ans=0;
            for(int i=0;i<n;i++){ 
                for(int j=0;j<m;j++){ 
                    if(grid[i][j]==0){ 
                        vector<int>root;
                        if(i-1>=0&&grid[i-1][j]==1){ 
                            root.push_back(uf.find(getIdx(i-1,j,m)));
                        }
                        if(i+1<n&&grid[i+1][j]==1){ 
                            root.push_back(uf.find(getIdx(i+1,j,m)));
                        }
                        if(j-1>=0&&grid[i][j-1]==1){ 
                            root.push_back(uf.find(getIdx(i,j-1,m)));
                        }
                        if(j+1<m&&grid[i][j+1]==1){ 
                            root.push_back(uf.find(getIdx(i,j+1,m)));
                        }
                        sort(root.begin(),root.end());
                        root.erase(unique(root.begin(),root.end()),root.end());
                        int tmpAns=1;
                        for(int i=0;i<root.size();i++){ 
                            tmpAns+=uf.getSize(root[i]);
                        }
                        ans=max(ans,tmpAns);
                    }
                }
            }
            if(ans==0){ 
                if(grid[0][0]==0)return 0;
                if(grid[0][0]==1)return n*m;
            }
            return ans;
        }
    };

1.  统计子串中唯一的字符  
    我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。  
    例如：s = “LEETCODE” ，则其中 “L”, “T”,“C”,“O”,“D” 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。  
    本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。  
    由于答案可能非常大，请将结果 mod 10 ^ 9 + 7 后再返回。

**字符数就26个，挨个统计区间即可**

class Solution { 
    public:
        int uniqueLetterString(string s) { 
            int len=s.length();
            vector<int> left(len,-1);
            vector<int> right(len,-1);
    
            //求左端点
            vector<int> prev(26,-1);
            for(int i=0;i<len;i++){ 
                left[i]=prev[s[i]-'A'];
                prev[s[i]-'A']=i;
            }
    
            //求右端点
            for(int i=0;i<26;i++){ 
                prev[i]=len;
            }
            for(int i=len-1;i>=0;i--){ 
                right[i]=prev[s[i]-'A'];
                prev[s[i]-'A']=i;
            }
    
            //根据区间计算各字符的贡献
            long long int ans=0;
            for(int i=0;i<len;i++){ 
                ans=(ans+(i-left[i])*(right[i]-i))%1000000007;//计算
            }
            return ans;
        }
    };

1.  连续整数求和  
    给定一个正整数 N，试求有多少组连续正整数满足所有数字之和为 N?

**数学题：列出公式N = x + (x + 1) + … + (x + k)，合并找规律，由于k <= 2N，所以计算x 满足非负整数则得到一个解。另外通过挖掘条件，可以只用找k < 根号2N**

class Solution { 
    public:
        int consecutiveNumbersSum(int n) { 
            while ((n & 1) == 0) 
                n >>= 1;
            int ans = 1, d = 3;
    
            while (d * d <= n) { 
                int e = 0;
                while (n % d == 0) { 
                    n /= d;
                    e++;
                }
                ans *= e + 1;
                d += 2;
            }
    
            if (n > 1) ans <<= 1;
            return ans;
        }
    };

830.较大分组的位置  
在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。  
例如，在字符串 s = “abbxxxxzyy” 中，就含有 “a”, “bb”, “xxxx”, “z” 和 “yy” 这样的一些分组。  
分组可以用区间 \[start, end\] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 “xxxx” 分组用区间表示为 \[3,6\] 。  
我们称所有包含大于或等于三个连续字符的分组为 较大分组 。  
找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

**遍历记录分组长度并判断即可**

class Solution { 
    public:
        vector<vector<int>> largeGroupPositions(string s) { 
            vector<vector<int>> ret;
            int n = s.size();
            int num = 1;
            for (int i = 0; i < n; i++) { 
                if (i == n - 1 || s[i] != s[i + 1]) { 
                    if (num >= 3) { 
                        ret.push_back({ i - num + 1, i});
                    }
                    num = 1;
                } else { 
                    num++;
                }
            }
            return ret;
        }
    };

1.  隐藏个人信息  
    给你一条个人信息字符串 S，它可能是一个 邮箱地址 ，也可能是一串 电话号码 。提供的信息正确隐藏后返回。

**字符串简单运用**

class Solution { 
    public:
        string maskPII(string s) { 
            if(s.find('@')==string::npos)//电话
            { 
                for(int i=0;i<s.size();++i)//删除所有非数字的字符
                { 
                    if(isdigit(s[i]))continue;
                    s.erase(s.begin()+i);
                    --i;
                }
                s.replace(s.begin(),s.end()-4,s.end()-s.begin()-4,'*');//replace(起始位置，结束位置，新字符串长度，新字符)
                s.insert(s.end()-4,'-');
                s.insert(s.end()-8,'-');
                if(s.size()>12)
                { 
                    s.insert(s.end()-12,'-');
                    s.insert(s.begin(),'+');
                }
    
            }
            else//邮箱
            { 
                transform(s.begin(),s.end(),s.begin(),::tolower);//全部变小写
                /*另一种方法 for(char& c : s) tolower(c); */
                s.replace(1,s.find('@')-2,"*****");//replace(起始位置，字符串长度，新字符串)
            }
            return s;
        }
    };