LeetCode Hot 100：技巧

LeetCode Hot 100：技巧

136. 只出现一次的数字

思路 1：哈希表

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_map<int, int> hashMap;for (int& num : nums)hashMap[num]++;for (auto& [x, cnt] : hashMap)if (cnt == 1)return x;return -1;}
};

思路 2：异或

class Solution {
public:int singleNumber(vector<int>& nums) {int ans = 0;for (int& x : nums)ans ^= x;return ans;}
};

思路 3：排序

class Solution {
public:int singleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());for (int i = 0; i < nums.size() - 1; i += 2) {if (nums[i] != nums[i + 1])return nums[i];}return nums.back();}
};

169. 多数元素

思路 1：哈希表

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int, int> hashMap;for (int& num : nums)hashMap[num]++;for (auto& [x, cnt] : hashMap)if (cnt > nums.size() / 2)return x;return -1;}
};

思路 2：排序

class Solution {
public:int majorityElement(vector<int>& nums) {sort(nums.begin(), nums.end());return nums[nums.size() / 2];}
};

思路 3：摩尔投票算法（Boyer–Moore majority vote algorithm）

class Solution {
public:int majorityElement(vector<int>& nums) {int count = 0;int candidate = nums[0];for (int &num : nums) {if (count == 0)candidate = num;if (candidate == num)count++;elsecount--;}return candidate;}
};

75. 颜色分类

思路 1：三指针

class Solution {
public:void sortColors(vector<int>& nums) {if (nums.size() < 2)return;// all in [0, zero) = 0// all in [zero, i) = 1// all in [two, nums.size() - 1] = 2int zero = 0, i = 0, two = nums.size();while (i < two) {if (nums[i] == 0) {swap(nums[zero], nums[i]);zero++;i++;} else if (nums[i] == 1)i++;else {two--;swap(nums[i], nums[two]);}}}
};

31. 下一个排列

思路 1：next_permutation

class Solution {
public:void nextPermutation(vector<int>& nums) {next_permutation(nums.begin(), nums.end());}
};

思路 2：两遍扫描

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();// Step 1: 找到一个尽量靠右的「较小数」int i = n - 2;while (i >= 0 && nums[i] >= nums[i + 1])i--;// Step 2: 找到一个在「较小数」右侧尽可能小的「较大数」if (i >= 0) {int j = n - 1;while (j > i && nums[j] <= nums[i])j--;// Step 3: 交换「较小数」和「较大数」swap(nums[i], nums[j]);}// Sterp 4: 「较大数」右边的数需要按照升序重新排列reverse(nums.begin() + i + 1, nums.end());}
};

思路 1：哈希表

class Solution {
public:int findDuplicate(vector<int>& nums) {unordered_map<int, int> hashMap;for (int& num : nums)hashMap[num]++;for (auto& [x, cnt] : hashMap)if (cnt >= 2)return x;return -1;}
};

287. 寻找重复数

思路 1：哈希表

class Solution {
public:int findDuplicate(vector<int>& nums) {unordered_map<int, int> hashMap;for (int& num : nums)hashMap[num]++;for (auto& [x, cnt] : hashMap)if (cnt >= 2)return x;return -1;}
};

思路 2：二分查找

class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size();int left = 0, right = n - 1;int ans = -1;while (left <= right) {int mid = left + (right - left) / 2;int count = 0;for (int& num : nums)if (num <= mid)count++;if (count <= mid)left = mid + 1;else {right = mid - 1;ans = mid;}}return ans;}
};

思路 3：二进制

class Solution {
public:int findDuplicate(vector<int>& nums) {int n = nums.size();// 确定二进制下最高位是多少int bit_max = 31;while (!((n - 1) >> bit_max))bit_max -= 1;int ans = 0;for (int bit = 0; bit <= bit_max; bit++) {int x = 0, y = 0;for (int i = 0; i < n; i++) {if (nums[i] & (1 << bit))x += 1;if (i >= 1 && (i & (1 << bit)))y += 1;}if (x > y)ans |= 1 << bit;}return ans;}
};

思路 4：快慢指针

class Solution {
public:int findDuplicate(vector<int>& nums) {int slow = 0, fast = 0;do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);slow = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
};