leetcode weekly-contest-354

发布于 2023-07-16  384 次阅读


特殊元素平方和

如果 数组的长度n 能够被 i 整除,即 n % i == 0 ,则认为 num[i] 是一个 特殊元素 ,求所有特殊元素的平方的和

这当然是无脑模拟T1就ok

  class Solution {
  public:
      int sumOfSquares(vector &nums) {
          int ans = 0, n = nums.size();
          for (int i = 0; i < nums.size(); i++)
              if (n % (i + 1) == 0) ans += nums[i] * nums[i];
          return ans;
      }
  };

数组的最大美丽值

对于数组的每个元素$x$都可以被修改为$[x-k,x+k]$的任意一个数,此时我们根据$0<=nums[i]<=10^5$可以知道如果修改为负数,或者修改为大于$10^5$的过程和修改为0和$10^5$的区间是有重叠的,所以最大值一定在端点可知。

由此我们只需要求$[0,10^5]$的数字,每个数字有多少个被修改成的可能。

每个数对他修改区间每个区间$[x-k,x+k]$的贡献度都为1,因此我们可以采用差分的方法得到这个最大值。

  class Solution {
  public:
      int f[100010];

      int maximumBeauty(vector &nums, int k) {
          for (auto &x: nums) {
              f[max(0, x - k)]++;
              f[min(100000, x + k) + 1]--;
          }
          int cnt = 0, ans = 0;
          for (int i = 0; i <= 100000; i++) {
              cnt += f[i];
              ans = max(ans, cnt);
          }
          return ans;
      }
  };

合法分割的最小下标

分割为两个合法区间,保证两个区间超过一半以上次数的值的频率大于区间长度的一半,求最小的分割下标。

对此可以先计算出每个数的情况,先计算出所有数的频率,作为第一次循环,

第二次循环,得到前面区间的频率和后面剩余的频率,只要通过哈希表验证前后区间的值是否成立即可。

关键点:前后两个区间的支配元素一致的情况下。且一定是前一个区间刚加入(后一个区间删除的)的数字

哈希表模拟,不考虑哈希查找的复杂度,整体复杂度$O(n)$

class Solution {
public:
    int minimumIndex(vector<int> &nums) {
        map<int, int> all, cnt;
        for (auto &x: nums) all[x]++;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            all[nums[i]]--;
            cnt[nums[i]]++;
            if (cnt[nums[i]] * 2 > i + 1) 
                if (all[nums[i]] * 2 > (n - (i + 1))) return i;
        }
        return -1;
    }
};

最长合法子字符串的长度

给定一个字符串s和一个字符串数组f,求最长的s不包含f内任意字符串的数组的长度

当我们使用滑动窗口方法解决这个问题时,我们维护了两个指针:l 和 r。初始时,l 和 r 都指向字符串的开头。

我们通过不断移动 r 指针来扩大窗口。在每个位置,我们检查窗口中的子字符串是否有效。如果子字符串出现在 forbidden 数组中,我们就需要更新 l 指针,并缩小窗口的大小。

具体来说,在每个 r 的位置,我们从 r 到 l 的范围内向后遍历,检查子字符串是否在 forbidden 数组中。如果找到了一个子字符串在 forbidden 数组中,我们就将 l 移动到它的后一个位置,并更新窗口的大小。

class Solution {
public:
    int longestValidSubstring(string word, vector<string>& forbidden) {
        set<string> h(forbidden.begin(), forbidden.end());
        int n = word.size(), ans = 0, l = 0;
        for (int r = 0; r < n; r++) {
            for (int i = r; i >= l; i--) {
                if (r - i >= 10) break;
                if (h.count(word.substr(i, r - i + 1))) {
                    l = i + 1;
                    break;
                }
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

绝对不是恋爱脑!