用到了is_sorted来判断是否升序排列

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        for (int i=0; i < nums.size()-1; i++){
            if (nums[i] > nums[i+1]){
                
                int temp = nums[i];
                //
                // "erase" nums[i], then check if nums is sorted without nums[i]
                //
                nums[i] = nums[i+1];
                if (is_sorted(nums.begin(), nums.end())) { return true; }
                
                //
                // "erase" nums[i+1], then check if nums is sorted without nums[i+1]
                //
                nums[i+1] = nums[i] = temp;
                if (is_sorted(nums.begin(), nums.end())) { return true; }
                
                //
                // nums is NOT sorted (without nums[i] XOR without nums[i+1])
                //
                return false;
            }
        }
        return true;
    }
};

利用set的自动排序和去除重复元素来解决问题。

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        set<int> result;
        for (int num:nums) {
            result.insert(num);
            if (result.size()>3) {
                result.erase(result.begin());
            }
        }
        return result.size()<3? *result.rbegin():*result.begin();
    }
};

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k<0) {
            return 0;
        }
        unordered_set<int> result;  //用集合避免重复
        unordered_map<int, int> hash;   //hash表来映射所需数值
        for (int i = 0; i<nums.size(); i++) {
            if (hash.count(nums[i]+k)) {
                result.insert(nums[i]+k);
            }
            if (hash.count(nums[i]-k)) {
                result.insert(nums[i]);
            }
            hash[nums[i]] += 1;
        }
        return result.size();
    }
};

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sortNums = nums;
        sort(sortNums.begin(), sortNums.end());
        int str = 0,end = nums.size()-1;
        while (nums[str]==sortNums[str]) {
            if (str==end) {
                return 0;
            }
            str++;
        }
        while (nums[end]==sortNums[end]) {
            end--;
        }
        return end-str+1;
    }
};

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

第一种：3格的滑动窗口

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int str = 0 ,end = 2;
        int tol = 0;
        if (flowerbed.size()==1&&flowerbed[0]==0) {
            tol++;
        }else if(flowerbed[0]==0&&flowerbed[1]==0) {
            flowerbed[0]=1;
            tol++;
        }
        
        while (end<=flowerbed.size()-1) {
            if (!(flowerbed[str]||flowerbed[str+1]||flowerbed[end])) {
                flowerbed[str+1] = 1;
                tol++;
            }
            str++;
            end++;
        }
        if (flowerbed.size()>=3&&flowerbed[flowerbed.size()-1]==0&&flowerbed[flowerbed.size()-2]==0) {
            tol++;
        }
        return tol>=n?1:0;
    }
};

第二种：

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for (int i = 0; i < flowerbed.size(); i++) {
            if (!flowerbed[i] && (i == 0 || !flowerbed[i - 1]) && (i == flowerbed.size() - 1 || !flowerbed[i + 1])) {
                flowerbed[i] = 1;
                n--;
            }
        }
        return n <= 0;
    }
};

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

判断数组中是否有重复的元素，并且下标之差不超过k。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for (int i=0; i<nums.size(); i++) {
            if (hash.find(nums[i])!=hash.end()&&i-hash[nums[i]]<=k) {
                return 1;
            }else{
                hash[nums[i]] = i;
            }
        }
        return 0;
    }
};