力扣热题之技巧

最后一个单元了，冲呀

1.只出现一次的数字

（1）这是我的，用集合做了一下

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_set<int> set;for(int num:nums){if(set.find(num)==set.end()) set.insert(num);else set.erase(num);}int ans;for (int num : set) {ans=num;}return ans;}
};

（2）还有邪修？

用异或 太狠了。。

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

2.多数元素

(1)unordered_map<int,int> 统计频率

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int> umap;for(int num:nums) umap[num]++;int target=nums.size()/2;for(auto& p:umap){if(p.second>target) return p.first;}return 0;}
};

（2）优化

优化就是随时判断，别最后加完了再判断

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int> mp;for(int i=0; i< nums.size();i++){mp[nums[i]]++;if(mp[nums[i]]>nums.size()/2){return nums[i];}}return 0;}
};

3.颜色分类

荷兰国旗问题，背过！！！

class Solution {
public:void swap(vector<int>& nums,int i,int j){int temp=nums[i];nums[i]=nums[j];nums[j]=temp;return;}void sortColors(vector<int>& nums) {int low=0;int mid=0;int high=nums.size()-1;while(mid<=high){if(nums[mid]==0){swap(nums,mid,low);low++;mid++;}else if(nums[mid]==1) mid++;else {swap(nums,mid,high);high--;//不要mid++，因为可能把0换过来了}}}
};

4.下一个排列

记住这个算法步骤，然后理解一下，最后的反转其实是一个sort，升序的sort

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();if (n <= 1) return;// 步骤1：从后向前找到第一个升序的位置int i = n - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}// 如果找到这样的位置if (i >= 0) {// 步骤2：从后向前找到第一个比nums[i]大的数int j = n - 1;while (j >= 0 && nums[j] <= nums[i]) {j--;}// 步骤3：交换nums[i]和nums[j]swap(nums[i], nums[j]);}// 步骤4：反转i+1到末尾的部分reverse(nums.begin() + i + 1, nums.end());}
};

5.寻找重复数

（1）set。。。

（2）快慢指针

这个相当于环形链表2，就是判断有没有环，同时找到环的起点

必须背过，还有这个i--->nums[i]的算法，也极其精妙，服了这些天赋怪，咋想出来的。

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;}
};

注意s是类似指针，s=nums[s] 类似  s=s->next，你和下面一类别就行，要返回s，不要返回nums[s]

上面的是之前写的环形链表2的代码，都搞忘记了，必须复习了。