leetcode hot100 技巧

如有缺漏谬误，还请批评指正。

1.只出现一次的数字

利用异或运算相同得0的特点。所有出现过两次的数字都会在异或运算累加过程中被抵消。、

class Solution {
public:int singleNumber(vector<int>& nums) {int res=0;for(int i=0;i<nums.size();i++) res^=nums[i];return res;}
};

2.多数元素

        随机取数，然后判断是否是答案。因为众数被选中的概率大于50%，所以时间复杂度虽然理论上可能出现O(∞)的情况，但实际上可以达到O(n)。

class Solution {
public:int majorityElement(vector<int>& nums) {while(true){int candidate=nums[rand()%nums.size()];int count=0;for(int i=0;i<nums.size();i++){if(nums[i]==candidate){count++;if (count>nums.size()/2) return candidate;}}}return -1;}
};

3.颜色分类

        经典的“荷兰国旗”问题。

（1）单指针解法

class Solution {
public:void sortColors(vector<int>& nums) {int i=0;for(int j=0;j<nums.size();j++){if(nums[j]==0){swap(nums[i],nums[j]);i++;}}for(int j=i;j<nums.size();j++){if(nums[j]==1){swap(nums[i],nums[j]);i++;}}}
};

（2）双指针解法

        比单指针少了一趟遍历。

①两个同向指针分别记录0的交换位置和1的交换位置。

class Solution {
public:void sortColors(vector<int>& nums) {int n=nums.size();int ptr0=0,ptr1=0;for(int i=0;i<n;i++){if(nums[i]==0){swap(nums[i],nums[ptr0++]);if(ptr1<ptr0) ptr1++;}if(nums[i]==1) swap(nums[i],nums[ptr1++]);}}
};

②左右指针分别记录0的交换位置和2的交换位置。 

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int r0=0,l2=n-1;  // r0: 0的右边界，l2:2的左边界for(int i=0;i<=l2;i++){       // 必须包含等于，因为nums[r]可能还没处理if(nums[i]==0) swap(nums[i],nums[r0++]);  // 0交换到左边，r0右移//换完后的理想状态：换过后nums[i]是1(1处在0的右边界和2的左边界之间)else if(nums[i]==2){swap(nums[i],nums[l2--]);  // 2交换到右边，l2左移if(nums[i]!=1) i--;  //num[i]==0的情况：2和0换，换过后的0需再换一遍到左边界//num[i]==2的情况：2和2换，换过后的2需重新处理}}}
};

4.下一个排列

三个关键步骤：

• 找到 i：i是第一个破坏从后向前升序的位置，这意味着nums[i]可以增大以得到更大的排列。

• 找到 j：nums[j] 是 i 之后比 nums[i] 大的最小数，交换后 nums[i]增大，但 i 之后的部分仍然降序。

• 反转：反转 i+1之后的部分使其升序，这样这部分最小，确保了整个排列是“下一个”排列。

class Solution {
public:void nextPermutation(vector<int>& nums) {int n=nums.size();int i=n-2;// 1. 找到第一个不符合逆序升的nums[i]while(i>=0&&nums[i]>=nums[i+1]) i--;// 2. 再找第一个比nums[i]大的nums[j]，swap两个数if(i>=0){int j=n-1;while(j>=0&&nums[j]<=nums[i]) j--;swap(nums[i], nums[j]);}// 3.反转 i+1 到末尾的部分（使其升序）reverse(nums.begin()+i+1, nums.end());}
};

5.多数问题

核心思想：将数组视为链表，并利用快慢指针检测环。

相遇的地点是环的入口（即重复数字）：推导如下。

class Solution {
public:int findDuplicate(vector<int>& nums) {// 初始化快慢指针，初始位置在数组的起始位置（索引0）int slow=0,fast=0;// 第一阶段：检测环的存在（Floyd's Tortoise and Hare算法）do{slow=nums[slow];       // 慢指针每次移动一步fast=nums[nums[fast]]; // 快指针每次移动两步} while (slow!=fast);      // 当快慢指针相遇时，说明存在环// 第二阶段：找到环的入口（即重复的数字）slow=0; // 将慢指针重置到起点while(slow!=fast){slow=nums[slow]; // 慢指针每次移动一步fast=nums[fast]; // 快指针每次移动一步}// 最终相遇点就是重复的数字return slow;}
};