title: 【每日一题】周末问题合并帖
tags:

  • leetcode
  • 每日一题
  • 算法
    abbrlink: 455ad351
    date: 2021-04-18 17:34:15

【周六】LeetCode 220. 存在重复元素 III

思路

这题请教了一下学长，确定就是一个滑动窗口的延伸，也是动态的查询一个区间，每次都判断区间边界一边的点是否符合，如果不符合，再看看边界另一边的点是否符合，如果两者有一个符合，则可以直接返回true，否则的话就继续向下寻找，直到找出符合条件的值即可

C++代码

  1. class Solution {
  2. public:
  3.     bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
  4.         typedef long long ll;
  5.         multiset<ll> s;
  6.         s.insert(1e18); s.insert(-1e18);
  7.         for(int i=0,j=0;i<nums.size();i++)
  8.         {
  9.             if(i-j>k)   s.erase(s.find(nums[j++]));
  10.             int x=nums[i];
  11.             auto it =s.lower_bound(x);
  12.             if(*it -x<=t)   return true;
  13.             --it;
  14.             if(x-*it<=t)    return true;
  15.             s.insert(x);
  16.         }
  17.         return false;
  18.     }
  19. };

【周日】LeetCode 26. 删除有序数组中的重复项

思路

这题是个纯模拟题，直接暴力枚举判定出来把符合条件的数存进一个新的数组（空间换时间）即可

C++代码

  1. class Solution {
  2. public:
  3.     int removeDuplicates(vector<int>& nums) {
  4.         int k=0;
  5.         for(int i=0;i<nums.size(); i++)
  6.             if(!i || nums[i] != nums[i-1])
  7.                 nums[k++]=nums[i];
  8.         return k;
  9.     }
  10. };