算法学习——LeetCode力扣补充篇1

在这里插入图片描述

1365. 有多少小于当前数字的数字

1365. 有多少小于当前数字的数字 - 力扣（LeetCode）

描述

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例 3：

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

提示

2 <= nums.length <= 500
0 <= nums[i] <= 100

代码解析

暴力法

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> result(nums.size() ,0);

        for(int i=0 ; i<nums.size() ;i++)
        {
            for(int j=0 ; j<nums.size();j++)
            {
                if(nums[j] < nums[i]) result[i]++;
            }
        }
        return result;
    }
};

map法

class Solution {

public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> result = nums;
        sort(result.begin() , result.end());
        map<int,int> my_map;

        for(int i=result.size()-1 ; i >= 0 ;i--)
            my_map[result[i]] = i;
        
        // for(auto it:my_map)
        //     cout<<it.first<<' '<<it.second<<endl; 

        for(int i=0 ; i<nums.size() ;i++)
        {
           result[i] = my_map[nums[i]];
        }
        return result;
    }
};

941. 有效的山脉数组

941. 有效的山脉数组 - 力扣（LeetCode）

描述

给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。

让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：

arr.length >= 3
在 0 < i < arr.length - 1 条件下，存在 i 使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]

在这里插入图片描述

示例

示例 1：

输入：arr = [2,1]
输出：false

示例 2：

输入：arr = [3,5,5]
输出：false

示例 3：

输入：arr = [0,3,2,1]
输出：true

提示

1 <= arr.length <= 104
0 <= arr[i] <= 104

代码解析

暴力法

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if(arr.size() <= 2) return false;
        int arr_flag = 0;
        for(int i=1 ;i<arr.size();i++)
        {
            if(arr_flag == 0 && arr[i] > arr[i-1]) arr_flag = 1;
            if(arr_flag == 1 && arr[i] > arr[i-1]) continue;
            else if(arr_flag == 1 && arr[i] == arr[i-1])  return false;
            else if(arr_flag == 1 && arr[i] < arr[i-1])  arr_flag += 1;

            if(arr_flag == 2 && arr[i] < arr[i-1]) continue;
            else return false;
        }
        if(arr_flag == 2) return true;
        else return false;
    }
};

双指针

class Solution {
public:
    bool validMountainArray(vector<int>& arr) {
        if(arr.size()<=2) return false;
        int left = 0;
        int right = arr.size()-1;

        while( left<arr.size() && arr[left] < arr[left+1]) 
            left++;

        while(right > 0 && arr[right] < arr[right-1])
            right--;
        
        // cout<<left<<' '<<right;
        if(left == right && left!=0 && right!=arr.size()-1) return true;
        else return false;
    }
};

1207. 独一无二的出现次数

1207. 独一无二的出现次数 - 力扣（LeetCode）

描述

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例

示例 1：

输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

输入：arr = [1,2]
输出：false

示例 3：

输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

提示

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000

代码解析

双map

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        map<int ,int> my_map;
        map<int ,int> my_map2;

        for(int i=0 ;i<arr.size() ;i++)
            my_map[arr[i]]++;
        
        for(auto it:my_map)
            my_map2[it.second]++;
        
        for(auto it:my_map2)
            if(it.second != 1) return false;
        
        return true;
    }
};

283. 移动零

283. 移动零 - 力扣（LeetCode）

描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

代码解析

队列法

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        queue<int> myqueue;
        for(int i=0 ; i<nums.size() ;i++)
            if(nums[i] != 0) myqueue.push(nums[i]);

        for(int i=0 ; i<nums.size() ;i++)
        {
             if(myqueue.size()!=0)
            {
                nums[i] = myqueue.front();
                myqueue.pop();
            }else nums[i] = 0;
        }     
    }
};

双指针

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left =0;
        for(int right = 0 ; right < nums.size() ;right++)
        {
            if(nums[right] != 0)
            {
                nums[left] = nums[right];
                left++;
            }
        }
        for(int i=left ; i<nums.size() ;i++)
            nums[i] = 0;
    }
};

189. 轮转数组

189. 轮转数组 - 力扣（LeetCode）

描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

代码解析

暴力差值法（超时）

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        
        while(k--)
        {
            int tmp = nums[nums.size()-1];
            nums.erase(nums.end()-1);
            nums.insert(nums.begin(),tmp);
        }
    }
};

转换双向数组

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        deque<int> my_deque(nums.begin(),nums.end());
        
        while(k--)
        {
            int tmp = my_deque.back();
            my_deque.pop_back();
            my_deque.push_front(tmp);
        }
        nums.clear();
        nums.assign(my_deque.begin(),my_deque.end());
    }
};

翻转法

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        deque<int> my_deque(nums.begin(),nums.end());
        
        reverse(nums.begin() , nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};