当前位置：首页 > news >正文

LeetCode百题刷003（449周赛一二题）

news 2025/5/14 11:24:28

遇到的问题都有解决的方案，希望我的博客可以为你提供一些帮助

一、不同字符数量最多为 K 时的最少删除数（哈希表空间换时间）

不同字符数量最多为 K 时的最少删除数 - 力扣 (LeetCode) 竞赛https://leetcode.cn/contest/weekly-contest-449/problems/minimum-deletions-for-at-most-k-distinct-characters/

思路分析：

题干要求是删除最少的元素以保证剩下的字符串中最多有k种不同的元素（每种元素可以有重复的）并返回删除的元素的个数

问题分解：

问题一：如何去确定要删除哪些元素？
问题二：如何去确定重复种类元素的个数呢？
问题三：如何保证最多有k种元素呢？

针对问题一，我们需要保证删除最少的元素，如果需要删除某些种类元素，首先被删除的元素种类一定是出现次数最少的而不是较多的。那么，我们需要先知道每一种元素出现的次数；其次，如果需要删除某些种类的元素需要逐次删除出现次数最小的。

针对问题二，可以看成一个经典的问题：如何在一个无序序列中统计每一个元素的频率。即构建如下的映射结构 元素：出现次数，可以采用哈希表来解决。

针对问题三，将问题二中的哈希表的大小与k进行比较即可。

问题解决：

数据结构：哈希表

算法设计：

利用哈希表统计每个元素的出现次数
按出现次数升序排序
比较k与哈希表的大小l
如果l<=k 直接返回 0
如果l>k 不断移除排序后序列的队首(实际上是不断累加首位元素出现的次数)，直到l=k，返回累加结果

时间复杂度： $O(nlogn)$

空间复杂度： $O(n)$

编码实现（python)：

class Solution:def minDeletion(self, s: str, k: int) -> int:#记录元素出现次数的哈希表char_count={}for char in s:char_count[char]=char_count.get(char,0)+1#排序sorted_c=sorted(char_count.items(),key=lambda item : item[1])if len(sorted_c)>k:return sum([x[1] for x in  sorted_c[:len(sorted_c)-k]])else:return 0

提交结果(python)：

编码实现（c++)：

class Solution {
public:int minDeletion(string s, int k) {//哈希表：记录每种元素出现次数unordered_map<char,int> char_count;for(auto c :s){char_count[c]++;}// 将哈希表元素存入 vectorvector<pair<char,int>> sorted_c(char_count.begin(),char_count.end());// 按值升序排序sort(sorted_c.begin(),sorted_c.end(),[](const auto &a,const auto &b){return a.second<b.second;});//计算结果if (sorted_c.size()>k){return accumulate(sorted_c.begin(),sorted_c.end()-k,0,[](int count,const auto &b){return count+b.second;} );}else{return 0;}}
};

提交结果(c++)：

二、等和矩阵分割 I

等和矩阵分割 I - 力扣 (LeetCode) 竞赛https://leetcode.cn/contest/weekly-contest-449/problems/equal-sum-grid-partition-i/

思路分析（这是我当时先想到的一个思路）：

题干要求是进行一次水平或者垂直划分，使划分后的二维数组的两部分（非空）的和相等。如果相等返回True，否则返回False

问题分解：

问题一：水平或者垂直划分如何实现？
问题二：如何对划分后的部分进行比较?
问题三：如何判断最终的返回结果？

针对问题一：二维数组有行和列，将每一行看成一个整体，对行操作就是实现水平划分；同理对列操作就是垂直划分

针对问题二和三：题干要求划分后两部分需要相等，直接比较两部分会比较困难因为我们不知道需要在哪一行或者那一列进行划分，如果枚举出所有可能再筛选时间耗费巨大，这时候不妨思考反面，我可不可以先求出总和（遍历二维数组一次），再按行为单位或者列为单位去遍历二维数组并记录累加和，如果当前累加和等于总和的一半说明划分正确否则不正确。

问题解决：

数据结构：二维数组

算法设计：

遍历数组计算总和
按行为单位或者列为单位去遍历二维数组并记录累加和
比较当前累加和与总和1/2的大小，如果等于则返回True否则返回False

时间复杂度： $O(n*m)$

空间复杂度： $O(n)$

编码实现（python)：

class Solution:def canPartitionGrid(self, grid: List[List[int]]) -> bool:#计算二维数组总和sum_g=0for row in grid:sum_g+=sum(row)if sum_g%2!=0:return False#按行划分sum_r=0;for row in grid:sum_r+=sum(row)if sum_r== sum_g/2:return Trueif sum_r>sum_g/2:#剪枝break#按列划分sum_c=0list_c=[sum(row[i] for row in grid) for i in range(len(grid[0]))]for c in list_c:sum_c+=cif sum_c==sum_g/2:return Trueif sum_c>sum_g/2:breakreturn False

提交结果(python)：

编码实现（c++)：

class Solution {
public:bool canPartitionGrid(vector<vector<int>>& grid) {//求总和long long  sum_g=0;for (auto row:grid){sum_g+=accumulate(row.begin(),row.end(),0LL);}// cout<<sum_g<<endl;//剪枝if (sum_g%2!=0){return false;}//行划分long long sum_r=0;for (auto row:grid){sum_r+=accumulate(row.begin(),row.end(),0LL);cout<<sum_r<<endl;if(sum_r==sum_g/2)return true;if (sum_r>sum_g/2)break;}//列划分long long   sum_c=0;for(int i=0;i<grid[0].size();i++){for(int j=0;j<grid.size();j++)sum_c+=grid[j][i];// cout<<sum_c<<endl;if (sum_c==sum_g/2)return true;if (sum_c>sum_g/2)break;}return false;}
};