今日学习的视频和文章
- 代码随想录 四数相加
- 代码随想录 赎金信
- 代码随想录 三数之和
- 代码随想录 四数之和II
LeetCode454 四数相加II
- 初见题目时的想法：由于只需要计算元组的个数，而不需要返回具体的元组，因此，只需要通过枚举来求“和为零的四元组”的个数
n。- 将四个整数数组分为两组，用
nums1和nums2来求num[i] + nums[j]的值及出现的次数，并保存在unordered_map中。 - 然后再枚举
nums3和nums4中的nums[k] + nums[l]的和，如果其相反数为unordered_map中保存的key，则n += unordered_map[- nums[k] - nums[l]]。 - 其实这里也有二分的思想，将四个数组平分成两组，每组两层循环，时间复杂度就是
O(n^2)；如果两组不平分，一组包含三个数组，另一组包含一个数组，那就会出现三层循环，时间复杂度就时O(n^3)了。
- 将四个整数数组分为两组，用
初见的题解代码如下：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int count = 0;
unordered_map<int, int> mapSum12;
for (auto& i : nums1) {
for (auto& j : nums2) {
mapSum12[i + j]++;
}
}
for (auto& k : nums3) {
for (auto& l : nums4) {
if (mapSum12.count(- k - l)) {
count += mapSum12[- k - l];
}
}
}
return count;
}
};
LeetCode383 赎金信
- 初见题目时的想法：
- 啪的就是一个
unordered_map，很快啊。key存字母，val存出现次数，将magazine中字母出现次数的信息存储为一个unordered_map。 - 然后遍历
ransomNote，每出现一个在unordered_map中的字母，则该字母对应的val值-1，最后遍历unordered_map的val值是否都大于等于零。
- 啪的就是一个
初见题目时的题解代码
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (magazine.length() < ransomNote.length()) {
return false;
}
unordered_map<char, int> magazineMap;
for (auto& iter : magazine) {
magazineMap[iter]++;
}
for (auto& iter : ransomNote) {
if (--magazineMap[iter] < 0) {
return false;
}
}
return true;
}
};
- 看了讲解之后：
- 还是不能太依赖
STL - 遇到
key值连续分布且范围不是很大，且哈希函数非常简单的情况，应该直接使用数组作为哈希表，这道题的key在[a-z]上连续分布，哈希函数为letter - 'a'，也不用处理哈希碰撞。直接用数组作为哈希表，效率当然要比使用STL高。
- 还是不能太依赖
使用数组作为哈希表的题解代码如下：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (magazine.length() < ransomNote.length()) {
return false;
}
array<int, 26> magazineMap({ 0 });
for (auto& iter : magazine) {
magazineMap[iter - 'a']++;
}
for (auto& iter : ransomNote) {
if (--magazineMap[iter - 'a'] < 0) {
return false;
}
}
return true;
}
};
LeetCode15 三数之和
- 初见题目时的想法：先将数组非降序排序，用外层循环来枚举
a，内层循环来枚举b和c。- 由于枚举的数在数组中的位置应为
a < b < c，且不能使用重复的元素，所以可以在内层循环中一起枚举b和c。 - 在内层循环中，用
numSet来保存可能的c，当枚举到可能的c时，将当前的三元组以mutiset的类型存入resSet - 然后利用
set<mutiset<int>>来进行结果的去重
- 由于枚举的数在数组中的位置应为
初次尝试的题解代码，我没有办法自己完善去重的逻辑进行剪枝，尝试使用STL实现，但最后还是没能通过所有用例。逻辑是对的，但是方法确实不够好，学了STL是为了使用更好的方法，把这段有一个测试用例超时的代码贴上来提醒自己多学习多思考吧。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
if (nums[0] > 0) {
return res;
}
int n = nums.size();
set<multiset<int>> resSet;
for (int i = 0; i < n; i++) {
int a = nums[i];
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
unordered_set<int> numSet;
for (int j = i + 1; j < n; j++) {
int b = nums[j];
int c = 0 - nums[i] - nums[j];
if (numSet.find(c) != numSet.end()) {
resSet.insert({nums[i], nums[j], c});
numSet.erase(c);
}
else {
numSet.insert(nums[j]);
}
}
}
for (auto& iter : resSet) {
res.push_back({iter.begin(), iter.end()});
}
return res;
}
};
image.png
image.png
- 看了讲解后的理解：
-
关键还是对于如何去重的理解
if (nums[i] == nums[i + 1]) continue; // 这会直接影响到结果集里一个元组中的元素，使得元组的中的元素不能重复 /* * 因为这样剪枝的话，相当于当前枚举到的元素和下一个未被枚举的元素重复，因而跳过了这次的循环，这个逻辑和我们要的去重 * 是不一样的 */if (i > 0 && nums[i] == nums[i - 1]) continue; // 这样才能正确让结果集里的元组不重复 /* * 这样剪枝的话，相当于上一个已经被枚举了的元素的所在的元组已经插入了结果集，而当前枚举的元素与上一个已经被枚举的元素 * 相同，这就意味着接下来得到的元组是和上一个已经被枚举了的元素所在的元组是一样的，所以跳过本次循环可以对结果集中的元 * 组进行去重 */
-
这道题其实很考察编程的思维，对于待处理的数据的观察、分析、思考，显然我的能力还是不够的。将数组元素排序后，就可以利用数组元素的非降序排列进行剪枝，如何利用数组元素的顺序等特性进行剪枝，是我以后要多多学习思考的。
- 元素非降序排列，意味着
a <= b <= c，那么a + b + c可以有几种情况呢？-
a > 0，则由不等式的传递性c >= b >= a > 0，显然a + b + c > 0，此时可以直接进行剪枝。 -
a + b + c > 0时，应该如何调整其中的数让a + b + c == 0呢？缩小其中一个数，可以达到这个目的。 -
a + b + c < 0时，应该放大其中一个数，让a + b + c == 0。
-
- 元素非降序排列，意味着
再结合代码随想录的讲解，思路是这样的，外层循环枚举
a，然后内层循环用来枚举b和c，我们规定a <= b <= c，当a + b + c > 0时，缩小c；当a + b + c < 0时，放大b。这体现在代码实现里就是双指针朝彼此移动来枚举三元组。
-
使用双指针法的题解代码如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
if (nums[0] > 0) {
return res;
}
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
continue;
}
else if (sum > 0) {
right--;
continue;
}
else {
res.push_back({nums[i], nums[left], nums[right]});
}
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right - 1] == nums[right]) {
right--;
}
left++;
right--;
}
}
return res;
}
};
LeetCode18 四数之和
- 初见题目时的想法：
- 这道题可以转化为已知的方法，即上一道题的双指针法。
- 规定
a <= b <= c <= d，第一层循环枚举a，第二层循环枚举b，然后第三层循环使用双指针枚举c和d。 - 不能沿用的剪枝方法：
-
a > target，如果target为负数，这种剪枝方法是不合逻辑的，负数相加越加越小。
-
初见题目时的题解
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n; i++) {
int a = nums[i];
if (i > 0 && nums[i] == nums[i - 1]){
continue;
}
for (int j = i + 1; j < n; j++) {
int b = nums[j];
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = n - 1;
while (left < right) {
int c = nums[left];
int d = nums[right];
long sum = (long)a + b + c + d;// 注意 int 相加可能会溢出
if (sum > target) {
right--;
continue;
}
else if (sum < target) {
left++;
continue;
}
else {
res.push_back({a, b, c, d});
}
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right - 1] == nums[right]) {
right--;
}
left++;
right--;
}
}
}
return res;
}
};
- 听了讲解之和添加的剪枝条件
- 根据
target的正负来剪枝：target >= 0 && a > target时直接break。 - 还是只有
target为非负时能进行剪枝，target >= 0 && a + b > target
- 根据
完整题解代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n; i++) {
int a = nums[i];
if (target >= 0 && a > target) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]){
continue;
}
for (int j = i + 1; j < n; j++) {
int b = nums[j];
if (target >= 0 && a + b > target) {
break;
}
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = n - 1;
while (left < right) {
int c = nums[left];
int d = nums[right];
long sum = (long)a + b + c + d;
if (sum > target) {
right--;
continue;
}
else if (sum < target) {
left++;
continue;
}
else {
res.push_back({a, b, c, d});
}
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right - 1] == nums[right]) {
right--;
}
left++;
right--;
}
}
}
return res;
}
};
