赞
踩
找出峰值
分析:
这是一个很简单的模拟题,直接遍历整个数组,判断每个元素是不是严格大于其相邻元素即可。
代码:
class Solution {
public:
vector<int> findPeaks(vector<int>& mountain) {
vector<int> ans;
for(int i = 1; i < mountain.size() - 1; i ++){
if(mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) ans.push_back(i);
}
return ans;
}
};
需要添加的硬币的最小数量
分析:
不妨定义当前能够表示的硬币的右边界为s,则一开始什么硬币都没有的情况下,能够表示的金额范围是
[
0
,
s
−
1
]
,
s
=
1
[0,s-1],s=1
[0,s−1],s=1,如果此时有一个新的硬币x
,加入后,可以得到
[
x
,
x
+
s
−
1
]
[x,x+s-1]
[x,x+s−1]范围内的所有数。
那么分类讨论一下:
x
之后,合并这两个区间,能够得到
[
0
,
x
+
s
−
1
]
[0,x+s-1]
[0,x+s−1]的所有整数;s
是肯定要加入进来的(加比s
小的数不如加s
好),那么这样可以得到
[
0
,
2
s
−
1
]
[0,2s-1]
[0,2s−1]之间的所有数,然后再继续判断x
和s
的大小,重复上述两个操作。我们考虑一个一个地将数组coins
的面值加入这个区间中,先对coins
数组排序。
代码:
class Solution { public: int minimumAddedCoins(vector<int>& coins, int target) { int n = coins.size(); int ans = 0, s = 1, i = 0; sort(coins.begin(), coins.end()); while(s <= target){ //如果当前coins[i]<=s,那么将coins[i]加入之后,范围从[0,s-1]到[0,coins[i]+s-1] if(i < n && coins[i] <= s){ s += coins[i++]; } //如果当前coins[i]>s,那么肯定要把s加入区间,范围从[0,s-1]到[0,2s-1] else{ s <<= 1; ans++; } } return ans; } };
时间复杂度:
O
(
n
log
n
+
log
t
a
r
g
e
t
)
O(n \log n+ \log target)
O(nlogn+logtarget)
空间复杂度:
O
(
1
)
O(1)
O(1)
分析:
首先,根据完美字符串中所述,相邻字符在字母表中的顺序至多相差2。根据这一点要求,就可以将字符串word
划分为多个组,每个组中是符合这个条件的字符串s
。
再对每一个字符串s
进行判断,符合条件的子串需要满足每个字符恰好出现k 次,一共只有26个字符,所以我们可以枚举一共有m
种字符
1
≤
m
≤
26
1 \le m \le 26
1≤m≤26,这样,这个问题就变成了,有一个大小为
m
×
k
m \times k
m×k的窗口,判断这个窗口种每个字符是否都只出现了
k
k
k次。
代码:
class Solution { int cal(string s, int k){//判断这个子串中有多少个每个字符出现k次的子串 int len = s.size(), res = 0; for(int m = 1; m <= 26; m++){//假设有m个出现k次的字符 int sub_len = m * k; if(sub_len > len)break; int i = 0, j = 0; int cnt[26] = {0};//统计字符数量 function <bool()> check = [&] () -> bool{ for(int i = 0; i < 26; i++){ if(cnt[i] != k && cnt[i] != 0)return false; } return true; }; while(j < sub_len)++cnt[s[j++] - 'a']; if(check())++res; while(j < len){ --cnt[s[i++] - 'a']; ++cnt[s[j++] - 'a']; if(check())++res; } } return res; } public: int countCompleteSubstrings(string word, int k){ int n = word.size(); int l, r = 0, ans = 0; while(r < n){ l = r++;//考虑多个符合第二个条件的子串,[l,r) while(r < n && abs(word[r] - word[r - 1]) <= 2)r++; ans += cal(word.substr(l, r - l), k); } return ans; } };
时间复杂度:
O
(
n
×
26
×
26
)
O(n \times 26 \times 26)
O(n×26×26)
空间复杂度:
O
(
26
)
O(26)
O(26)
其次,还可以进一步进行优化,如果能够在cal
函数中把check函数优化掉,那么可以变得更快,其实每一次统计一个窗口中的字符,是否满足都是出现k
次,可以再定义一个哈希表,这个哈希表的用途是来维护出现次数的次数,只有出现次数为k
的次数是m
,其实意思就是所有的字符都是出现了k
次,因为窗口大小为
k
×
m
k \times m
k×m。
class Solution { int cal(string s, int k){//判断这个子串中有多少个每个字符出现k次的子串 int len = s.size(), res = 0; for(int m = 1; m <= 26; m++){//假设有m个出现k次的字符 int sub_len = m * k; if(sub_len > len)break; int i = 0, j = 0; //维护一个出现次数的出现次数,可以变成O(1)来判断是否满足完美子字符串的条件 int cc[100005] = {0}; int cnt[26] = {0};//统计字符数量 while(j < sub_len){ cc[cnt[s[j] - 'a']]--; cc[++cnt[s[j++] - 'a']]++; } if(cc[k] == m)++res; while(j < len){ cc[cnt[s[i] - 'a']] -= 1; cc[--cnt[s[i++] - 'a']] += 1; cc[cnt[s[j] - 'a']] -= 1; cc[++cnt[s[j++] - 'a']] += 1; if(cc[k] == m)++res; } } return res; } public: int countCompleteSubstrings(string word, int k){ int n = word.size(); int l, r = 0, ans = 0; while(r < n){ l = r++;//考虑多个符合第二个条件的子串,[l,r) while(r < n && abs(word[r] - word[r - 1]) <= 2)r++; ans += cal(word.substr(l, r - l), k); } return ans; } };
时间复杂度:
O
(
n
×
26
)
O(n \times 26)
O(n×26)
空间复杂度:
O
(
26
)
O(26)
O(26)
统计感冒序列的数目
根据题意我们可以有如下讨论的情况。
首先,对于每个小朋友是如何感染的,只可能是从其左边的小朋友传染或者是右边的小朋友传染,那么就是相当于得到一个由L,R组成的序列,意思就是当前操作是往左边感染还是往右边感染。
考虑例一:
n
=
5
,
s
i
c
k
=
[
0
,
4
]
n = 5, sick = [0,4]
n=5,sick=[0,4]
[0,1,2,3,4],那么中间这三个位置可以填入的顺序是什么呢?
不难发现,因为最后一个小朋友,不管是其左边的小朋友感染的还是右边的小朋友感染的,都是没有区别的,所以对于一个这样的序列,感染的方式是 2 m − 1 2^{m-1} 2m−1, m m m是这个序列的长度。
对于每一段(即左右端点都是感冒小朋友的序列),其可以填入的L/R的方案是 2 ( m − 1 ) 2^(m-1) 2(m−1),每一段相互独立,互不影响填入L/R的方式, m m m为这一段的长度,所以最后的答案肯定是需要 2 m 1 × 2 m 2 × 2 m 3 × . . . . . . 2^{m_1} \times 2 ^{m_2} \times 2^{m_3} \times ...... 2m1×2m2×2m3×......,即 2 m 1 + m 2 + m 3 + . . . 2^{m_1+m_2+m_3+...} 2m1+m2+m3+...。
上面所述的都没有考虑感染的时间点,因为题目要求每一秒中, 至多一位还没感冒的小朋友会被传染。所以,对于很多段来说,我们还要考虑的就是每一个时间点,哪个地方会被感染,假设有 n − m n-m n−m个没被感染的人,就有 t = n − m t=n-m t=n−m个时刻,从 t t t时刻中任意选择 m 1 m_1 m1个时刻给第一段感染, C ( t , m 1 ) C(t,m1) C(t,m1),剩下 t − m 1 t-m_1 t−m1个时刻选 m 2 m_2 m2个时刻给第二段感染, C ( t − m 1 , m 2 ) C(t-m1,m2) C(t−m1,m2),依次类推…
对于最左边的感染者再左边的小朋友,最右边感染者再右边的小朋友,其只能填入LLLL和RRRR,所以可填入的方案是1,仅需要考虑填入的时刻。
根据上面所述,本题就变成了一个简单的组合数学问题,因为要取模,所以计算组合数除法时会用到逆元。
const int MOD = 1'000'000'007; const int MX = 100'000; long long q_pow(long long x, int n) { long long res = 1; for (; n > 0; n /= 2) { if (n % 2) { res = res * x % MOD; } x = x * x % MOD; } return res; } // 组合数模板 long long fac[MX], inv_fac[MX]; auto init = [] { fac[0] = 1; for (int i = 1; i < MX; i++) { fac[i] = fac[i - 1] * i % MOD; } inv_fac[MX - 1] = q_pow(fac[MX - 1], MOD - 2); for (int i = MX - 1; i > 0; i--) { inv_fac[i - 1] = inv_fac[i] * i % MOD; } return 0; }(); long long comb(int n, int k) { return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD; } class Solution { public: int numberOfSequence(int n, vector<int>& sick) { /*一个数学问题——排列组合 1.相当于得到一个由L,R组成的序列 2.对于每一段(即左右端点都是感冒小朋友的序列),其可以填入的L/R的方案是2^(m-1),每一段相互独立,互不影响填入L/R的方式 m为这一段的长度 3.对于很多段来说,我们要考虑的就是每一个时间点,哪个地方会被感染,假设有n-m个没被感染的人,就有t=n-m个时刻,从t时刻中任意选择m1个时刻给第一段感染,C(t,m1),剩下t-m1个时刻选m2个时刻给第二段感染,C(t-m1,m2),依次类推...... 4.对于最左边的感染者再左边的小朋友,最右边感染者再右边的小朋友,其只能填入LLLL和RRRR,所以可填入的方案是1,仅需要考虑填入的时刻 */ int m = sick.size(); int total = n - m;//剩下t时刻相当于 long long ans = comb(total, sick[0]) * comb(total - sick[0], n - sick.back() - 1) % MOD;//先考虑上述第四种情况 total -= sick[0] + n - sick.back() - 1; int exp = 0;//维护一下第二点所述的指数一共有多少 for(int i = 0; i < m - 1; i++){ int k = sick[i + 1] - sick[i] - 1;//每一段的小朋友数量 if(k){ exp += k - 1; ans = ans * comb(total, k) % MOD; total -= k; } } return ans * q_pow(2, exp) % MOD; } };
时间复杂度:
O
(
m
)
O(m)
O(m),预处理的时间忽略不计
空间复杂度:
O
(
1
)
O(1)
O(1),预处理的空间忽略不计
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。