第 310 场周赛

比赛链接

A 出现最频繁的偶数元素

模拟，用哈希表记录次数，然后取出现次数最多的最小偶数即可。

C++Python

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        unordered_map<int, int> mp;
        for (auto &x : nums) {
            if (x % 2 == 0) {
                mp[x] ++;
            }
        }
        int cnt = 0, num = 0;
        for (auto &[k, v] : mp) {
            if (cnt < v) {
                cnt = v; 
                num = k;
            } else if (cnt == v) {
                num = min(num, k);
            }
        }
        return cnt == 0 ? -1 : num;
    }
};

class Solution:
    def mostFrequentEven(self, nums: List[int]) -> int:
        c = Counter(nums)
        cnt, num = 0, 0
        for k, v in c.items():
            if k % 2 == 0:
                if cnt < v:
                    cnt = v
                    num = k
                elif cnt == v:
                    num = min(num, k)

        return num if cnt != 0 else -1

B 子字符串的最优划分

使用哈希表记录每个字符上一次的出现位置，对于当前字符 \(ch\), 如果在上一段出现过，那么就应该新起一段，将哈希表置为空，只将 \(ch\) 插入进去作为新的一段的开始。

C++Python

class Solution {
public:
    int partitionString(string s) {
        vector<int> c(26, -1);
        int res = 1;
        for (int i = 0; i < s.size(); i++) {
            int ch = s[i] - 'a';
            if (c[ch] != -1) {
                res ++;
                fill(c.begin(), c.end(), -1);
                c[ch] = i;
            } else {
                c[ch] = i;
            }
        }
        return res;
    }
};

class Solution:
    def partitionString(self, s: str) -> int:
        c = {}
        res = 1
        for i, ch in enumerate(s):
            if ch in c:
                res += 1
                c.clear()
                c[ch] = i
            else:
                c[ch] = i
        return res

C 将区间分为最少组数

将区间按照左端点排序，对于当前区间 \(intervals[i]\) 的 \([l,r]\)，如果可以将它放入之前的某个区间组，从而使得组内区间不重复，那么该组最后一个组件 \([l_k,r_k]\) 必须满足 \(r_k \lt l\)。

因为我们依据左端点排序，因此，在遍历到 \(intervals[i]\) 之前，所有 \(r_k\) 小于 \(l\) 的区间都已经遍历过。我们维护一个最小堆，只需要看当前所有区间组中最小的 \(r_k\) 那个是否满足即可。

为什么这样做可以保证答案最优，因为当前 \(intervals[i]\) 的 \(l\) 是至此以后最小的 \(l\)，我们可以放心的将最小的 \(r_k\) 交给它。

时间复杂度 \(O(n\log n)\)。

C++Python

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        priority_queue<int, vector<int>, greater<int>> q;
        sort(intervals.begin(), intervals.end()) ;
        for (int i = 0; i < intervals.size(); i++) {
            int l = intervals[i][0], r = intervals[i][1];
            if (q.empty()) {
                q.push(r);
            } else if (q.top() < l) {
                q.pop();
                q.push(r);
            } else {
                q.push(r);
            }
        }
        return (int) q.size();
    }
};

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        q = []
        intervals.sort()
        for l, r in intervals:
            if not q:
                heappush(q, r)
            elif q[0] < l:
                heappop(q)
                heappush(q, r)
            else:
                heappush(q, r)
        return len(q)

D 最长递增子序列 II

使用线段树维护每个值作为子序列末尾时，序列长度的最大值。对于当前数字 \(x\)，找到区间 \([x - k, x - 1]\) 中的最大值，然后将其 +1, 更新到 \(x\) 位置上。

时间复杂度为 \(O(val \log val)\) 其中 \(val\) 为 \(nums[i]\) 中的最大值。

C++

template<class Info, class Merge = plus<Info>>
struct SegTree{
  int n;
  Merge merge;
  vector<Info> info;
  SegTree(int n): n(n), merge(Merge()), info(4 * n) {}
  SegTree(int n, vector<Info> &init): SegTree(n) {
    function<void(int,int,int)> build = [&](int p, int l, int r) {
      if(l == r) {
        info[p] = init[l];
        return;
      }
      int m = (l + r) / 2;
      build(2 * p, l, m);
      build(2 * p + 1, m + 1, r);
      pull(p);
    };
    build(1, 0, n - 1);
  }

  void pull(int p) {
    info[p] = move(merge(info[2 * p], info[2 * p + 1]));
  }

  void modify(int p, int l, int r, int x, const Info &v) {
    if(l == r) {
      info[p] = v;
      return;
    }
    int m = (l + r) / 2;
    if(x <= m) modify(p * 2, l, m, x, v);
    else modify(2 * p + 1, m + 1, r, x, v);
    pull(p);
  }

  void modify(int p, const Info &v) {
    modify(1, 0, n - 1, p, v);
  }

  Info rangeQuery(int p, int l, int r, int x, int y) {
    if(l > y || r < x) {
      return Info();
    }
    if(l >= x && r <= y) return info[p];
    int m = (l + r) / 2;
    return merge(rangeQuery(p * 2, l, m, x, y), rangeQuery(p * 2 + 1, m + 1, r, x, y));
  }

  Info rangeQuery(int l, int r) {
    return rangeQuery(1, 0, n - 1, l, r);
  }
};

struct Info {
  int mx;
  Info() { mx = 0; }
  Info(int mx): mx(mx) {}
};
struct Merge {
  Info operator () (const Info &l, const Info &r) const {
    Info t;
    t.mx = max(l.mx, r.mx);
    return t;
  }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums, int k) {
        SegTree<Info, Merge> seg(100010);
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            int val = seg.rangeQuery(x - k, x - 1).mx;
            seg.modify(x, Info(val + 1));
        }
        return seg.rangeQuery(1, 100000).mx;
    }
};

本文访问 次