Day20力扣打卡

Day20力扣打卡

打卡记录

数组中两个数的最大异或值（位运算）

链接

二进制位上从高位向低位进行模拟，看数组中是否有满足此情况的数字。具体题解

class Solution {
public:int findMaximumXOR(vector<int>& nums) {int mx = *max_element(nums.begin(), nums.end());int max_bit = 0, mask = 0, ans = 0;for (int i = 0; i != 32 && (1 << i) <= mx; i++) max_bit = i;unordered_set<int> st;for (int i = max_bit; i >= 0; --i) {st.clear();mask |= 1 << i;int new_ans = ans | (1 << i);for (int x : nums) {x &= mask;if (st.count(new_ans ^ x)) {ans = new_ans;break;}st.insert(x);}}return ans;}
};

四数之和（双指针）

链接

排列数组之后，遍历前两个数字的选取，对后两个数字的选取使用双指针算法，将 O ( n 4 ) O(n^4) O(n4) 优化为 O ( n 3 ) O(n^3) O(n3)，类似于三数之和的算法思路。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());vector<vector<int>> ans;int n = nums.size();for (int a = 0; a < n - 3; ++a) {if (a > 0 && nums[a - 1] == nums[a]) continue;if ((long long)nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break;if ((long long)nums[a] + nums[n - 3] + nums[n - 1] + nums[n - 2] < target) continue;for (int b = a + 1; b < n - 2; ++b) {if (b > a + 1 && nums[b] == nums[b - 1]) continue;if ((long long)nums[a] + nums[b] + nums[b + 1] + nums[b + 2] > target) break;if ((long long)nums[a] + nums[b] + nums[n - 1] + nums[n - 2] < target) continue;int c = b + 1, d = n - 1;while (c < d) {long long sum = (long long)nums[a] + nums[b] + nums[c] + nums[d];if (sum == target) {ans.push_back({nums[a], nums[b], nums[c++], nums[d--]});while (c < d && nums[c] == nums[c - 1]) c++;while (c < d && nums[d] == nums[d + 1]) d--;}else if (sum > target) d--;else c++;}}}return ans;}
};

有效三角形的个数（双指针）

链接

由于数组排列，所以从左到右选取 a, b, c 三点，必有 a <= b <= c，则只需要满足 a + b > c 这个条件即可构成有效三角形。类似于三数之和的思路，这里我们将 c 点作为循环遍历的点，a 与 b 的选取使用双指针来进行，若使用 a 作为循环遍历的点，则会导致 nums[a] + nums[b] > nums[c] 情况下b++，c–都会导致结果依旧为
nums[a] + nums[b] > nums[c] 。

class Solution {
public:int triangleNumber(vector<int>& nums) {int n = nums.size(), ans = 0;if (n < 3) return ans;sort(nums.begin(), nums.end());for (int c = 2; c < n; ++c) {int a = 0, b = c - 1;while (a < b) {if (nums[a] + nums[b] > nums[c]) {ans += b - a;b--;}else a++;}}return ans;}
};