文章目录
K 进制表示下的各位数字总和
题目链接
题目描述
给你一个整数
n
n
n（10 进制）和一个基数
k
k
k ，请你将
n
n
n 从 10 进制表示转换为
k
k
k 进制表示，计算并返回转换后各位数字的 总和 。
转换后，各位数字应当视作是 10 进制数字，且它们的总和也应当按 10 进制表示返回。
样例描述
输入：n = 34, k = 6
输出：9
解释：34 (10 进制) 在 6 进制下表示为 54 。5 + 4 = 9 。
提示：
1
≤
n
≤
100
1 \leq n \leq 100
1≤n≤100
2
≤
k
≤
10
2 \leq k \leq 10
2≤k≤10
class Solution {
public:
int sumBase(int n, int k) {
string ans = "";
while(n)
{
ans += (char)(n%k + '0');
n /= k;
}
int tot = 0;
for(int i = 0; i < ans.size(); i++)
tot += (int)(ans[i] - '0');
return tot;
}
};
最高频元素的频数
题目链接
题目描述
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组
n
u
m
s
nums
nums 和一个整数
k
k
k 。在一步操作中，你可以选择
n
u
m
s
nums
nums 的一个下标，并将该下标对应元素的值增加 1 。
执行最多
k
k
k 次操作后，返回数组中最高频元素的 最大可能频数 。
样例描述
输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，
此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。
提示：
1
≤
n
u
m
s
.
l
e
n
g
t
h
≤
1
0
5
1 \leq nums.length \leq 10^5
1≤nums.length≤105
1
≤
n
u
m
s
[
i
]
≤
1
0
5
1 \leq nums[i] \leq 10^5
1≤nums[i]≤105
1
≤
k
≤
1
0
5
1 \leq k \leq 10^5
1≤k≤105
解题思路当时把这个题想成了 2019 年沈阳站那个二分题目，二分区间内
m
i
n
min
min ~
m
a
x
max
max，找到一个值，让更多区间内的数花费最小代价得到一个出现次数最多的数。
正确二分思路就是先把所有的数求一遍前缀和，二分给出二分左边端点 l l l 和 右边端点 r r r，通过每次放缩的 m i d mid mid 确定最终的区间左端点，因为枚举的时候是从左往右枚举，右端点总是确定的，二分求的只是为了确定左端点的那个数，然后每次二分更新一下最大值即可。
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
typedef long long ll;
int len = nums.size();
vector<ll> s(len+1);
for(int i = 1; i <= len; i++)
s[i] = s[i-1] + nums[i-1];
int ans = 0;
for(int i = 1; i <= len; i++)
{
int l = 1, r = i;
while(l < r)
{
int mid = (l + r)>>1;
ll t = (nums[i - 1]*(ll)(i - mid + 1));
if(t - s[i] + s[mid - 1] <= k) r = mid;
else l = mid + 1;
}
if(i - r + 1 > ans) ans = i - r + 1;
}
return ans;
}
};
所有元音按顺序排布的最长子字符串
题目链接
题目描述
当一个字符串满足如下条件时，我们称它是 美丽的 ：
所有 5 个英文元音字母
（
′
a
′
，
′
e
′
，
′
i
′
，
′
o
′
，
′
u
′
）
（'a' ，'e' ，'i' ，'o' ，'u'）
（′a′，′e′，′i′，′o′，′u′） 都必须 至少 出现一次。
这些元音字母的顺序都必须按照 字典序 升序排布（也就是说所有的
′
a
′
'a'
′a′ 都在
′
e
′
'e'
′e′ 前面，所有的
′
e
′
'e'
′e′ 都在
′
i
′
'i'
′i′ 前面，以此类推）
比方说，字符串
"
a
e
i
o
u
"
"aeiou"
"aeiou" 和
"
a
a
a
a
a
a
e
i
i
i
i
o
o
u
"
"aaaaaaeiiiioou"
"aaaaaaeiiiioou" 都是 美丽的 ，但是
"
u
a
e
i
o
"
"uaeio"
"uaeio" ，
"
a
e
o
i
u
"
"aeoiu"
"aeoiu" 和
"
a
a
a
e
e
e
o
o
o
"
"aaaeeeooo"
"aaaeeeooo" 不是美丽的 。
给你一个只包含英文元音字母的字符串
w
o
r
d
word
word ，请你返回
w
o
r
d
word
word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串，请返回 0
子字符串 是字符串中一个连续的字符序列。
样例描述
输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
输出：13
解释：最长子字符串是 "aaaaeiiiiouuu" ，长度为 13 。
解题思路
枚举找最长的含有
a
e
i
o
u
aeiou
aeiou 的升序序列即可, 注意处理边界问题。
class Solution {
public:
int longestBeautifulSubstring(string word) {
string p = "aeiou";
int len = word.size();
int ans = 0;
for(int i = 0; i < len; i++)
{
int j = 0, s = i, ok = 1;
if(word[i] != 'a') continue;
while(i < len)
{
if(word[i] == p[j]) i++;
else
{
if(word[i] == p[j+1]) j++,i++;
else ok = 0;
}
if(!ok) break;
}
if(j == 4) ans = max(ans, i - s);
i--;
}
return ans;
}
};
最高建筑高度
题目链接
题目描述
在一座城市里，你需要建
n
n
n 栋新的建筑。这些新的建筑会从 1 到
n
n
n 编号排成一列。
这座城市对这些新建筑有一些规定：
每栋建筑的高度必须是一个非负整数。
第一栋建筑的高度 必须 是 0 。
任意两栋相邻建筑的高度差 不能超过 1 。
除此以外，某些建筑还有额外的最高高度限制。这些限制会以二维整数数组
r
e
s
t
r
i
c
t
i
o
n
s
restrictions
restrictions 的形式给出，其中
r
e
s
t
r
i
c
t
i
o
n
s
[
i
]
restrictions[i]
restrictions[i] =
[
i
d
i
,
m
a
x
H
e
i
g
h
t
i
]
[id_i, maxHeight_i]
[idi,maxHeighti] ，表示建筑
i
d
i
id_i
idi 的高度 不能超过
m
a
x
H
e
i
g
h
t
i
maxHeight_i
maxHeighti 。
题目保证每栋建筑在 restrictions 中 至多出现一次 ，同时建筑 1 不会 出现在
r
e
s
t
r
i
c
t
i
o
n
s
restrictions
restrictions 中。
请你返回 最高 建筑能达到的 最高高度 。
样例描述
输入：n = 5, restrictions = [[2,1],[4,1]]
输出：2
解释：上图中的绿色区域为每栋建筑被允许的最高高度。
我们可以使建筑高度分别为 [0,1,2,1,2] ，最高建筑的高度为 2 。
解题思路
首先将
[
1
,
0
]
[1, 0]
[1,0] 这个点插入，然后从小到大排序，处理区间右端点，看右端点是否等于
n
n
n，因为题目是说
1...
n
1...n
1...n 栋楼从左到右排列且第一幢楼的高度是 0 ，所以对于区间左端点和右边端点分别是 1 和
n
n
n，如果
n
n
n 不在集合中，那么插入即可，高度可以赋
i
n
t
int
int 类型的最大值。
设直线 :
l
1
l_1
l1:
y
y
y =
x
1
x_1
x1 +
b
1
b_1
b1
l
2
l_2
l2:
y
y
y =
x
2
x_2
x2 +
b
2
b_2
b2
求截距
b
1
b_1
b1 和
b
2
b_2
b2
因为集合中 0 号位置就是
x
x
x 轴的 1 号点，所以
b
1
[
0
]
=
−
1
b{_1}[0] = -1
b1[0]=−1，
b
2
[
0
]
=
1
b{_2}[0] = 1
b2[0]=1。
直线
l
1
l_1
l1 方向左上方，对于每个点的截距只需要和前一个点的截距取一个
m
i
n
min
min 即可。
直线
l
2
l_2
l2 方向左下方，对于每个点的截距只需要和后一个点的截距取一个
m
i
n
min
min 即可。
直线
l
1
l_1
l1 和 和
l
2
l_2
l2 的交点判断交点是否合法。
h
[
i
]
[
0
]
=
x
h[i][0] =x
h[i][0]=x
h
[
i
]
[
1
]
=
y
h[i][1] = y
h[i][1]=y
交点坐标
m
i
d
mid
mid =
b
1
[
i
−
1
]
b{_1}[i-1]
b1[i−1] +
b
2
[
i
]
b{_2}[i]
b2[i] >> 1
以直线
l
2
l2
l2 为例:
y
′
y'
y′ =
−
x
′
-x'
−x′ +
b
2
b_2
b2 ==>
x
′
x'
x′ =
b
2
b_2
b2 -
y
y
y
x
′
x'
x′ 是否在
h
[
i
−
1
]
[
0
]
h[i-1][0]
h[i−1][0] 和
h
[
i
]
[
0
]
h[i][0]
h[i][0] 区间内，若在则更新一下最大值即可
最后更新一下最大值 和 直线
l
1
l_1
l1 和
l
2
l_2
l2 取
m
i
n
min
min 的最大值即可。
class Solution {
public:
int maxBuilding(int n, vector<vector<int>>& h) {
h.push_back({1,0});
sort(h.begin(),h.end());
if(h.back()[0] != n) h.push_back({n,n-1});
int len = h.size();
typedef long long ll;
vector<ll>L(len+1,1e18), R(len+1,1e18);
//h[0][0] = 1 截距 -1
L[0] = -1;
for(int i = 1; i < len; i++) // y = x + b
{
int x = h[i][0], y = h[i][1];
L[i] = min(L[i-1],(ll)(y-x));
}
//h[0][0] = 1 截距 1
R[0] = 1;
for(int i = len - 1; i; --i) // y = -x + b
{
int x = h[i][0], y = h[i][1];
R[i] = min(R[i+1],(ll)(x+y));
}
ll ans = 0;
for(int i = 0; i < len; i++)
{
int x = h[i][0];
if(i) // y = -x + b
{
ll Y = (L[i-1]+R[i]) >> 1;
ll X = R[i] - Y;
if(X >= h[i-1][0] && X <= h[i][0])
ans = max(ans,Y);
}
ans = max(ans,min(x+L[i],-x+R[i]));
}
return ans;
}
};
总结
最后一个题不会，然后就是第二题思路想的是二分， 只是二分思路想偏了，补了第二题和第四题，第四题建议动手画图，然后码代码思路就清晰了。