贵阳网站建设的公司,ui界面设计师,福州专业网站建设怎么做,网站需要多大宽带遇到的问题都有解决的方案#xff0c;希望我的博客可以为你提供一些帮助 一、不同字符数量最多为 K 时的最少删除数 #xff08;哈希表空间换时间#xff09;
不同字符数量最多为 K 时的最少删除数 - 力扣 (LeetCode) 竞赛https://leetcode.cn/contest/weekly-contest-449/… 遇到的问题都有解决的方案希望我的博客可以为你提供一些帮助 一、不同字符数量最多为 K 时的最少删除数 哈希表空间换时间
不同字符数量最多为 K 时的最少删除数 - 力扣 (LeetCode) 竞赛https://leetcode.cn/contest/weekly-contest-449/problems/minimum-deletions-for-at-most-k-distinct-characters/
思路分析
题干要求是删除最少的元素以保证剩下的字符串中最多有k种不同的元素每种元素可以有重复的并返回删除的元素的个数
问题分解
问题一如何去确定要删除哪些元素问题二如何去确定重复种类元素的个数呢问题三如何保证最多有k种元素呢
针对问题一我们需要保证删除最少的元素如果需要删除某些种类元素首先被删除的元素种类一定是出现次数最少的而不是较多的。那么我们需要先知道每一种元素出现的次数其次如果需要删除某些种类的元素需要逐次删除出现次数最小的。
针对问题二可以看成一个经典的问题如何在一个无序序列中统计每一个元素的频率。即构建如下的映射结构 元素出现次数可以采用哈希表来解决。
针对问题三将问题二中的哈希表的大小与k进行比较即可。
问题解决
数据结构哈希表
算法设计
利用哈希表统计每个元素的出现次数按出现次数升序排序比较k与哈希表的大小l 如果lk 直接返回 0如果lk 不断移除排序后序列的队首(实际上是不断累加首位元素出现的次数)直到lk返回累加结果
时间复杂度
空间复杂度
编码实现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_csorted(char_count.items(),keylambda 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_mapchar,int char_count;for(auto c :s){char_count[c];}// 将哈希表元素存入 vectorvectorpairchar,int sorted_c(char_count.begin(),char_count.end());// 按值升序排序sort(sorted_c.begin(),sorted_c.end(),[](const auto a,const auto b){return a.secondb.second;});//计算结果if (sorted_c.size()k){return accumulate(sorted_c.begin(),sorted_c.end()-k,0,[](int count,const auto b){return countb.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
时间复杂度
空间复杂度 编码实现python)
class Solution:def canPartitionGrid(self, grid: List[List[int]]) - bool:#计算二维数组总和sum_g0for row in grid:sum_gsum(row)if sum_g%2!0:return False#按行划分sum_r0;for row in grid:sum_rsum(row)if sum_r sum_g/2:return Trueif sum_rsum_g/2:#剪枝break#按列划分sum_c0list_c[sum(row[i] for row in grid) for i in range(len(grid[0]))]for c in list_c:sum_ccif sum_csum_g/2:return Trueif sum_csum_g/2:breakreturn False提交结果(python) 编码实现c)
class Solution {
public:bool canPartitionGrid(vectorvectorint grid) {//求总和long long sum_g0;for (auto row:grid){sum_gaccumulate(row.begin(),row.end(),0LL);}// coutsum_gendl;//剪枝if (sum_g%2!0){return false;}//行划分long long sum_r0;for (auto row:grid){sum_raccumulate(row.begin(),row.end(),0LL);coutsum_rendl;if(sum_rsum_g/2)return true;if (sum_rsum_g/2)break;}//列划分long long sum_c0;for(int i0;igrid[0].size();i){for(int j0;jgrid.size();j)sum_cgrid[j][i];// coutsum_cendl;if (sum_csum_g/2)return true;if (sum_csum_g/2)break;}return false;}
};
提交结果(c)
