1. Leetcode 3085 成为 K 特殊字符串需要删除的最少字符数
本题思考的关键点:
① 在字符串处理放到 cnt[26] 数组中,
枚举删除字母后,字母出现的最少次数
② 逆向思维,直接求最多保留多少个字母
- 本题示例代码如下:
class Solution {
public:
int minimumDeletions(string word, int k) {
int cnt[26] = {0};
for (auto x : word)
cnt[x - 'a'] ++;
sort(cnt, cnt + 26);
int max_sum = 0; // 逆向思维,求出最多保留多少个字母的数量
// 第一层枚举保留的字母 出现的最少次数
for (int i = 0; i < 26; i ++)
{
int sum = 0;
// 比字母 i 对应的次数小的字母都要删除
for (int j = i; j < 26; j ++)
{
sum += min(cnt[j], cnt[i] + k);
}
max_sum = max(max_sum, sum);
}
return word.length() - max_sum;
}
};
2. Leetcode 846 一手顺子
本题思考的关键点:[双指针 + 枚举
]
① 从小到大进行枚举,枚举当前组的第一个数
② 不断的维护当前的个数即可
- 本题示例代码如下:
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int groupSize) {
if (hand.size() % groupSize != 0)
return false;
sort(hand.begin(), hand.end());
unordered_map<int, int> mymap;
for (auto x : hand)
mymap[x] ++;
// 枚举当前组的第一个数
for (int i = 0; i < hand.size(); i ++)
{
if (mymap[hand[i]] <= 0) continue;
int j = hand[i];
int cnt = 0;
while (cnt < groupSize)
{
cnt ++;
if (mymap[j] > 0)
{
mymap[j] --;
j ++;
}
else
return false;
}
}
return true;
}
};
3. Leetcode 2044 统计按位或能得到最大值的子集数目
本题思考的关键点:[回溯 + 暴搜]
①
如何枚举,将所有子集的情况都统计进去
② 先把最大的子集异或值求出来,然后想清楚剩下的有多少种
③ 这个暴搜考虑的是选或者不选的
- 本题示例代码如下:
// 数据范围: n ≤ 30,指数级别, 所以用 dfs + 剪枝
class Solution {
public:
int ans = 0;
int countMaxOrSubsets(vector<int>& nums) {
// 首先算出子集按位或得出的最大值
int mmax = 0;
for (auto x : nums)
mmax |= x;
// 进行暴搜,注意:此时的 cur 为 0
dfs(nums, mmax, 0, 0);
return ans;
}
void dfs(vector<int>& nums, int mmax, int index, int cur)
{
// 剪枝
if (cur == mmax)
{
ans += (1<<(nums.size() - index));
return ;
}
if (index == nums.size())
return ;
dfs(nums, mmax, index + 1, cur | nums[index]);
dfs(nums, mmax, index + 1, cur);
}
};