题目1：字母在字符串中的百分比
字母在字符串中的百分比
标签
字符串
思路
遍历一遍字符串，统计目标字符的个数，然后先乘100再除以字符串的大小。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int percentageLetter(string s, char letter) {
int n = s.size();
float num = 0;
for(int i = 0; i < n; i++){
if(s[i] == letter)
num ++;
}
return num * 100 / n;
}
};
|
- 时间复杂度：O(n)，其中 n 为字符串 s 的大小
- 空间复杂度：O(1)
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.9 MB, 在所有 C++ 提交中击败了50.00%的用户
通过测试用例：85 / 85
题目2：装满石头的背包的最大数量
装满石头的背包的最大数量
标签
数组、排序
思路
先计算出每个背包剩余的空间并保存至一个数组中，然后将该数组从小到大进行排序，遍历一遍，若当前位置的元素小于额外的石头数量，并且额外的石头数量大于0，则将 additionalRocks -= arr[i] 并且装满石头的背包数加一。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
vector<int> arr;
for(int i = 0; i < capacity.size(); i++){
arr.push_back(capacity[i] - rocks[i]);
}
sort(arr.begin(), arr.end());
int nums = 0;
for(int i = 0; i < arr.size(); i++){
if(arr[i] == 0) {
nums ++;
continue;
}
if(additionalRocks > 0 && additionalRocks >= arr[i]){
additionalRocks -= arr[i];
nums++;
}
else{
break;
}
}
return nums;
}
};
|
- 时间复杂度：O(n \ logn)，其中 n* 为数组的大小，排序耗时。
- 空间复杂度：O(n)，需要一个额外的数组保存每个背包剩余的空间。
执行用时：144 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：87.4 MB, 在所有 C++ 提交中击败了100.00%的用户
通过测试用例：79 / 79
题目3：表示一个折线图的最少线段数
表示一个折线图的最少线段数
标签
数组、排序、数学
思路
先将所有的点按照横坐标从小到大进行排序，直接使用 sort(stockPrices.begin(), stockPrices.end()); 进行排序即可。然后遍历一遍函数，每次计算当前元素和前一元素组成的线段的斜率是否和前一段斜率相同，若不同，则结果加一。需要使用一个变量记录前一斜率，再不相同时更新该变量。
sort(stockPrices.begin(), stockPrices.end());，默认按照数组的第一列进行升序排序。
sort(stockPrices.rbegin(), stockPrices.rend());，默认按照数组的第一列进行降序排列。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int minimumLines(vector<vector<int>>& stockPrices) {
if(stockPrices.size() == 1) return 0;
else if(stockPrices.size() == 2) return 1;
sort(stockPrices.begin(), stockPrices.end());
int res = 0;
long double pre = 2e9;
for(int i = 1; i < stockPrices.size(); i++){
int x1 = stockPrices[i - 1][0], y1 = stockPrices[i - 1][1];
int x2 = stockPrices[i][0], y2 = stockPrices[i][1];
long double cur = (long double)(y2 - y1) / (long double)(x2 - x1);
if(cur != pre){
res ++;
pre = cur;
}
}
return res;
}
};
|
- 时间复杂度：O(n \ logn)，其中 n* 为数组的大小，排序耗时。
- 空间复杂度：O(1)
执行用时：392 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：98.3 MB, 在所有 C++ 提交中击败了100.00%的用户
通过测试用例：79 / 79
题目4：巫师的总力量和
巫师的总力量和