2.二的幂数组中查询范围内的乘积
解法1. 暴力枚举
n最大是1e9，未超出int表示范围，最多有30个2的幂
查询数组最大是1e5
暴力枚举的最差时间复杂度就是\(3e6\)，不会超时
时间复杂度
- 求2的幂,\(O(\log_2^n)\)
- m次查询,每次查询最多花费\(O(\log_2^n)\),总的时间复杂度
\(O(\log_2^n + m * \log_2^n)\) = \(O(m * \log_2^n)\)
class Solution {
public:
vector<int> productQueries(int n, vector<vector<int>>& queries) {
vector<int> exp;
int mod = 1e9 + 7;
for(int i = 1; i <= n; i *= 2)
if(i & n) exp.push_back(i);
vector<int> ans;
for(auto &query : queries)
{
long long res = 1;
while(query[0] <= query[1])
res = res * exp[query[0]++] % mod;
ans.push_back(res);
}
return ans;
}
};
解法2. 暴力枚举 + 预处理
在解法1的基础上,预处理出所有可能的query,之后再查询时,时间复杂度就是O(1)
解法1已知最多有30个2的幂,query可能的选择有\(30+29+28+....+1 = 30*31/2\)种
时间复杂度
- 求2的幂, \(O(\log_2^n)\)
- 预处理\(O((\log_2^n * \log_2^n) / 2) = O((\log_2^{2n}) / 2)\)
class Solution {
public:
vector<int> productQueries(int n, vector<vector<int>>& queries) {
vector<int> exp;
int mod = 1e9 + 7;
vector<vector<int>> pre(31, vector<int>(31));
for(int i = 1; i <= n; i *= 2)
if(i & n) exp.push_back(i);
for(int i = 0; i < exp.size(); i++)
{
long long base = 1;
for(int j = i; j < exp.size(); j++)
{
base = base * exp[j] % mod;
pre[i][j] = base;
}
}
vector<int> ans;
for(auto &query : queries)
ans.push_back(pre[query[0]][query[1]]);
return ans;
}
};
解法3. 幂次的前缀和
-
所有的乘子都是2的幂,所以可以转换成求出2的幂次
比如例1的第三个查询\(1*2*4*8 = 2^0*2^1*2^2*2^3 = 2^6\)
class Solution {
public:
vector<int> productQueries(int n, vector<vector<int>> queries) {
vector<int> exp;
int mod = 1e9 + 7;
exp.push_back(0);
for(int i = 1, base = 0; i <= n; i *= 2)
{
if(i & n) exp.push_back(base);
++base;
}
for(int i = 1; i < exp.size(); i++)
exp[i] += exp[i - 1];
vector<int> ans;
for(auto &query : queries)
{
int l = query[0] + 1, r = query[1] + 1;
long long res = 1, tmp = 2;
for(int pow = exp[r] - exp[l - 1]; pow > 0; pow >>= 1)
{
if(pow & 1) res = (res * tmp) % mod;
tmp = tmp * tmp % mod;
}
ans.push_back(res);
}
return ans;
}
};
3. 最小化数据中的最大值
解法1. 枚举 + 二分
check函数逻辑
根据给出的target值, 从后向前枚举, 设置num[i] <= target ,最后根据nums[0]判断这个target是否满足check要求
时间复杂度
target最大取值为1e9, 二分check用时O(n), 二分用时\(O(\log_2^{1e9})\),总的时间复杂度是
\(O(30*n)\)
class Solution {
public:
bool check(vector<int>& nums, int target)
{
long long extra = 0;
for(int i = nums.size() - 1; i >= 1; i--)
if(extra + nums[i] > target) extra += nums[i] - target;
else extra = max(0, (int)extra - target - nums[i]);
return nums[0] + extra <= target;
}
int minimizeArrayValue(vector<int>& nums) {
int l = 0, r = 1e9 + 10, n = nums.size();
while(l < r)
{
int mid = (l + r) >> 1;
if(check(nums, mid)) r = mid;
else l = mid + 1;
}
return l;
}
};
解法2 求平均数
首先可以明确, 右边的值可以转移到左边任意位置,
可以将初始的nums想象为拥有一个不同浪高的海, 后边的浪可以向前滚动,显然当浪高不同时,会发生流动,当海浪平静, 即浪高相同时就能得到最小的最大浪高,即最小最大值
因此可以从前向后求每一点的平均值,这里的平均值需要向上取整,求\(val/x\),且向上取整的结果是\(\frac{val+(x-1)}{x}\)
class Solution {
public:
int minimizeArrayValue(vector<int> nums) {
int ans = 0;
long long tmp = 0;
for(int i = 0; i < nums.size(); i++){
tmp += nums[i];
ans = max(ans, (int)((tmp + i)/(i + 1)));
}
return ans;
}
};
2440. 创建价值相同的连通块
https://www.bilibili.com/video/BV1cV4y157BY/?vd_source=016995e9e676ce29a2a00ff61948cbc5
const int N = 1e6 + 10;
int h[N], val[N], ne[N], idx;
class Solution {
public:
int target = 0;
vector<int> w;
void add(int a, int b)
{
val[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int p, int fa)
{
int weight = w[p];
for(int i = h[p]; i != -1; i = ne[i])
{
int j = val[i];
if(j == fa) continue;
int tmp;
if((tmp = dfs(j, p)) == -1)
return -1;
weight += tmp;
}
if(weight > target) return -1;
if(weight == target) return 0;
return weight;
}
int componentValue(vector<int> nums, vector<vector<int>> edges) {
memset(h, -1, sizeof h);
w = nums;
for(auto &edge: edges)
{
int a = edge[0], b = edge[1];
add(a, b), add(b, a);
}
int total = 0;
for(auto & num : nums)
total += num;
for(int i = 1; i <= total; i++)
if(total % i == 0)
{
target = i;
if(dfs(0, -1) != -1) return total / i - 1;
}
return 0;
}
};