遇到的問題都有解決的方案，希望我的博客可以為你提供一些幫助
一、不同字符數量最多為 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，返回累加結果
時間復雜度：
空間復雜度：?
編碼實現（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?
時間復雜度：
空間復雜度：?
?編碼實現（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;}
};提交結果(c++)：?
)
