7162271784

Committed 11 Dec 2023 02:45AM UTC coverage: 81.778% (+0.06%) from 81.717%

Build # 7162271784

Build Type

push

github

Committed by

yi-ge

Commit Message

add: 最小体力消耗路径

Run Details

2864 of 4341 branches covered (0.0%)

Branch coverage included in aggregate %.

25 of 26 new or added lines in 1 file covered. (96.15%)

1 existing line in 1 file now uncovered.

6493 of 7101 relevant lines covered (91.44%)

33396.09 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

76.92

/src/array/online_majority_element_in_subarray.cpp

// 子数组中占绝大多数的元素
// https://leetcode.cn/problems/online-majority-element-in-subarray
// INLINE  ../../images/array/online_majority_element_in_subarray.jpeg
// 官方题解

#include <headers.hpp>
#include <random>

class MajorityChecker {
public:
  // 构造函数，将数组中每个元素的位置存储到哈希表中
  MajorityChecker(vector<int> &arr) : arr(arr) {
    for (int i = 0; i < arr.size(); ++i) {
      loc[arr[i]].push_back(i);
    }
  }

  // 查询函数，随机从[left, right]范围内选择k个数，统计每个数在子数组中出现的次数，如果有数出现次数超过threshold，则返回该数，否则返回-1
  int query(int left, int right, int threshold) {
    int length = right - left + 1;
    uniform_int_distribution<int> dis(left, right);

    for (int i = 0; i < k; ++i) {
      int x = arr[dis(gen)]; // 随机选择一个数
      vector<int> &pos = loc[x]; // 获取该数在数组中出现的位置
      int occ = upper_bound(pos.begin(), pos.end(), right) - // 统计该数在子数组中出现的次数
                lower_bound(pos.begin(), pos.end(), left);
      if (occ >= threshold) { // 如果该数在子数组中出现的次数超过threshold，则返回该数
        return x;
      } else if (occ * 2 >= length) { // 如果该数在子数组中出现的次数小于threshold，但是在子数组中占比超过1/2，则返回-1
        return -1;
      } // LCOV_EXCL_LINE
    }   // LCOV_EXCL_LINE

    return -1; // LCOV_EXCL_LINE
  }

private:
  static constexpr int k = 20; // 随机选择数的个数

  const vector<int> &arr; // 存储原始数组
  unordered_map<int, vector<int>> loc; // 哈希表，存储每个数在数组中出现的位置
  mt19937 gen{random_device{}()}; // 随机数生成器
};

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker* obj = new MajorityChecker(arr);
 * int param_1 = obj->query(left,right,threshold);
 */

1	// 子数组中占绝大多数的元素
2	// https://leetcode.cn/problems/online-majority-element-in-subarray
3	// INLINE ../../images/array/online_majority_element_in_subarray.jpeg
4	// 官方题解
5
6	#include <headers.hpp>
7	#include <random>
8
9	class MajorityChecker {
10	public:
11	// 构造函数，将数组中每个元素的位置存储到哈希表中
12	MajorityChecker(vector<int> &arr) : arr(arr) {	2✔
13	for (int i = 0; i < arr.size(); ++i) {	14✔
14	loc[arr[i]].push_back(i);	12!
15	}	12✔
16	}	2✔
17
18	// 查询函数，随机从[left, right]范围内选择k个数，统计每个数在子数组中出现的次数，如果有数出现次数超过threshold，则返回该数，否则返回-1
19	int query(int left, int right, int threshold) {	6✔
20	int length = right - left + 1;	6✔
21	uniform_int_distribution<int> dis(left, right);	6✔
22
23	for (int i = 0; i < k; ++i) {	6!
24	int x = arr[dis(gen)]; // 随机选择一个数	6✔
25	vector<int> &pos = loc[x]; // 获取该数在数组中出现的位置	6✔
26	int occ = upper_bound(pos.begin(), pos.end(), right) - // 统计该数在子数组中出现的次数	12✔
27	lower_bound(pos.begin(), pos.end(), left);	6✔
28	if (occ >= threshold) { // 如果该数在子数组中出现的次数超过threshold，则返回该数	6✔
29	return x;	4✔
30	} else if (occ * 2 >= length) { // 如果该数在子数组中出现的次数小于threshold，但是在子数组中占比超过1/2，则返回-1	2!
31	return -1;	2✔
32	} // LCOV_EXCL_LINE
UNCOV 33	} // LCOV_EXCL_LINE	×
34
35	return -1; // LCOV_EXCL_LINE	×
36	}	6✔
37
38	private:
39	static constexpr int k = 20; // 随机选择数的个数
40
41	const vector<int> &arr; // 存储原始数组
42	unordered_map<int, vector<int>> loc; // 哈希表，存储每个数在数组中出现的位置
43	mt19937 gen{random_device{}()}; // 随机数生成器	2!
44	};
45
46	/**
47	* Your MajorityChecker object will be instantiated and called as such:
48	* MajorityChecker* obj = new MajorityChecker(arr);
49	* int param_1 = obj->query(left,right,threshold);
50	*/

yi-ge / cpp-practice / 7162271784

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous