目录
一、小C的类二进制拼图
问题描述
小C发现了一种特殊的数字,称为类二进制数字,即仅由数字0和1组成的十进制数。例如,101
和1100
都是类二进制数字,而112
和3001
则不是。现在,小C手上有一个正整数n
,他想知道最少需要多少个类二进制数字相加才能得到n
。
测试样例
样例1:
输入:
n = "10101"
输出:1
样例2:
输入:
n = "212"
输出:2
样例3:
输入:
n = "1000000"
输出:1
样例4:
输入:
n = "123456789"
输出:9
样例5:
输入:
n = "9876543210"
输出:9
解题思路:
问题理解
我们需要找到最少的类二进制数字(即仅由0和1组成的数字)相加,使得它们的和等于给定的正整数 n
。
数据结构选择
由于 n
是一个字符串表示的数字,我们可以将其转换为整数进行处理,或者直接在字符串上进行操作。
算法步骤
- 逐位处理:从
n
的最高位开始,逐位处理。 - 构建类二进制数字:对于每一位,如果当前位是
1
,则可以直接使用该位作为类二进制数字的一部分;如果当前位是0
,则不需要处理。 - 进位处理:如果当前位是
2
或更高,则需要将其减去1
,并将进位加到下一位。 - 计数:每处理一个非零位,计数器加一。
第一版代码:
#include <iostream>
using namespace std;
int solution(string n) {
int count = 0; // 用于记录最少需要的类二进制数字的个数
int carry = 0; // 用于处理进位
// 从最高位开始逐位处理
for (int i = 0; i < n.size(); ++i) {
int digit = n[i] - '0' + carry; // 当前位的数字,加上进位
if (digit > 0) {
// 如果当前位大于0,则需要一个类二进制数字
count++;
// 处理进位
carry = digit - 1;
} else {
// 如果当前位为0,则不需要处理
carry = 0;
}
}
return count;
}
int main() {
cout << (solution("10101") == 1) << endl;
cout << (solution("212") == 2) << endl;
cout << (solution("1000000") == 1) << endl;
cout << (solution("123456789") == 9) << endl;
cout << (solution("9876543210") == 9) << endl;
return 0;
}
但实际上并没过,不过反应过来了有一个更简单的思路,只要找到这串数字的每个位上的数字最大值就是答案
最终代码:
#include <iostream>
#include <algorithm>
using namespace std;
int solution(string n) {
int max_digit = 0; // 用于记录最大位数
// 遍历字符串 n,找到最大位数
for (char c : n) {
int digit = c - '0'; // 将字符转换为数字
max_digit = max(max_digit, digit); // 更新最大位数
}
return max_digit;
}
int main() {
cout << (solution("10101") == 1) << endl;
cout << (solution("212") == 2) << endl;
cout << (solution("1000000") == 1) << endl;
cout << (solution("123456789") == 9) << endl;
cout << (solution("9876543210") == 9) << endl;
return 0;
}
二、小M的奶酪问题
问题描述
小M在集市上买了一公斤奶酪回家。然而,在小M不在的时候,小F偷偷地偷走了 ABBA 公斤的奶酪。现在,小M想知道他还剩下多少奶酪。要求答案以分数的形式表示,并且分数的分母必须为 BB。
测试样例
样例1:
输入:
A = 2,B = 7
输出:'5/7'
样例2:
输入:
A = 1,B = 3
输出:'2/3'
样例3:
输入:
A = 3,B = 5
输出:'2/5'
解题思路:
问题理解
小M原本有一公斤奶酪,小F偷走了 BA 公斤的奶酪。我们需要计算小M还剩下多少奶酪,并且结果需要以分数的形式表示,分母必须是 B。
数据结构选择
由于我们需要表示一个分数,并且分母是固定的 B,我们可以直接使用整数来表示分子。
算法步骤
- 初始化:小M原本有1公斤奶酪,即 BB 公斤。
- 计算剩余奶酪:小F偷走了 BA 公斤奶酪,所以小M剩下的奶酪是 BB−BA。
- 简化分数:由于分母已经是 B,我们只需要计算分子即可。分子可以通过 B−A 得到。
- 返回结果:将分子和分母组合成字符串形式的分数。
最终代码:
#include <iostream>
#include <string>
std::string solution(int A, int B) {
// 计算分子
int numerator = B - A;
// 构建分数字符串
std::string result = std::to_string(numerator) + "/" + std::to_string(B);
// 返回结果
return result;
}
int main() {
std::cout << (solution(2, 7) == "5/7") << std::endl;
std::cout << (solution(1, 3) == "2/3") << std::endl;
std::cout << (solution(3, 5) == "2/5") << std::endl;
}
运行结果:
三、小T的密码变换规则
问题描述
小T设计了一套密码变换规则,将输入的字符串转换成一串数字密码。变换规则如下:
- 小写字母按以下映射关系进行转换:
a, b, c
->2
d, e, f
->3
g, h, i
->4
j, k, l
->5
m, n, o
->6
p, q, r, s
->7
t, u, v
->8
w, x, y, z
->9
-
大写字母先转为小写字母,再跳到字母表中的前一个字母,并按上述规则转换为对应的数字。例如,
B
转换为a
,再转换为2
;A
特殊处理,先变为Z
,再转换为9
。 -
非字母字符保持不变。
例如:对于输入字符串 "LIming0701"
,转换后的数字密码为 5464640701
。
测试样例
样例1:
输入:
s = "LIming0701"
输出:'5464640701'
样例2:
输入:
s = "PassW0rd"
输出:'62778073'
样例3:
输入:
s = "helloWORLD123"
输出:'4355686752123'
解题思路:
问题理解
我们需要将输入的字符串按照特定的规则转换成一串数字密码。规则包括对小写字母、大写字母和非字母字符的处理。
数据结构选择
我们可以使用一个字符串来存储最终的转换结果。对于字母的转换,我们可以使用一个映射表(例如 std::unordered_map
或 std::array
)来存储字母到数字的映射关系。
算法步骤
- 初始化映射表:创建一个映射表,存储小写字母到对应数字的映射关系。
- 遍历输入字符串:
- 对于每个字符,判断其是否为字母。
- 如果是大写字母,先转换为小写字母,然后跳到字母表中的前一个字母。
- 如果是小写字母,直接查找映射表。
- 如果是非字母字符,保持不变。
- 构建结果字符串:将每个字符的转换结果依次添加到结果字符串中。
具体步骤
- 初始化映射表:
- 例如,
a, b, c
映射到2
,d, e, f
映射到3
,依此类推。
- 例如,
- 遍历输入字符串:
- 对于每个字符,使用
isalpha()
判断是否为字母。 - 如果是大写字母,使用
tolower()
转换为小写字母,然后根据规则跳到前一个字母。 - 如果是小写字母,直接查找映射表。
- 如果是非字母字符,直接添加到结果字符串中。
- 对于每个字符,使用
- 返回结果字符串。
最终代码:
#include <iostream>
#include <string>
#include <unordered_map>
std::string solution(const std::string& s) {
// 初始化映射表
std::unordered_map<char, char> charToDigit = {
{'a', '2'}, {'b', '2'}, {'c', '2'},
{'d', '3'}, {'e', '3'}, {'f', '3'},
{'g', '4'}, {'h', '4'}, {'i', '4'},
{'j', '5'}, {'k', '5'}, {'l', '5'},
{'m', '6'}, {'n', '6'}, {'o', '6'},
{'p', '7'}, {'q', '7'}, {'r', '7'}, {'s', '7'},
{'t', '8'}, {'u', '8'}, {'v', '8'},
{'w', '9'}, {'x', '9'}, {'y', '9'}, {'z', '9'}
};
std::string result;
// 遍历输入字符串
for (char c : s) {
if (std::isalpha(c)) {
// 如果是大写字母,先转换为小写字母,然后跳到前一个字母
if (std::isupper(c)) {
c = std::tolower(c);
// 特殊处理 'a' 和 'A'
if (c == 'a') {
c = 'z';
} else {
c -= 1;
}
}
// 查找映射表并添加到结果字符串
result += charToDigit[c];
} else {
// 非字母字符保持不变
result += c;
}
}
return result;
}
int main() {
std::cout << (solution("LIming0701") == "5464640701") << std::endl;
std::cout << (solution("PassW0rd") == "62778073") << std::endl;
std::cout << (solution("helloWORLD123") == "4355686752123") << std::endl;
return 0;
}
运行结果:
四、数值操作的期望计算问题
问题描述
小R有两个正整数aa和bb,她将随机选择其中一个数并将其乘以22。这个操作会进行两次,操作后的两个数之和会有所变化。小R想知道,操作结束后,两个数之和的期望值是多少?
例如:如果 a=3a=3 和 b=3b=3,那么有 1/21/2 的概率两数之和为 1212,1/21/2 的概率两数之和为 1515。因此,期望值为 13.513.5。
测试样例
样例1:
输入:
a = 3 ,b = 3
输出:'13.50'
样例2:
输入:
a = 5 ,b = 7
输出:'27.00'
样例3:
输入:
a = 1 ,b = 1
输出:'4.50'
解题思路:
问题理解
小R有两个正整数 a 和 b,她会随机选择其中一个数并将其乘以 2。这个操作会进行两次。我们需要计算操作结束后,两个数之和的期望值。
关键点
- 随机选择:每次操作有 1/2 的概率选择 a,1/2 的概率选择 b。
- 操作两次:每次操作后,数会乘以 2。
期望值计算
我们需要考虑所有可能的操作组合,并计算每种组合的概率和结果。
可能的操作组合
- 第一次选择 a,第二次选择 a:结果是 2a+2a=4a
- 第一次选择 a,第二次选择 b:结果是 2a+2b
- 第一次选择 b,第二次选择 a:结果是 2b+2a
- 第一次选择 b,第二次选择 b:结果是 2b+2b=4b
概率计算
每种组合的概率是 1/4,因为每次选择是独立的,且每次选择 a 或 b 的概率都是 1/2。
期望值公式
期望值 E 可以表示为:
[ E = \frac{1}{4} \times (4a) + \frac{1}{4} \times (2a + 2b) + \frac{1}{4} \times (2b + 2a) + \frac{1}{4} \times (4b) ]
简化后:
[ E = \frac{1}{4} \times (4a + 2a + 2b + 2b + 2a + 4b) ]
[ E = \frac{1}{4} \times (8a + 8b) ]
[ E = 2a + 2b ]
最终代码:
#include <iostream>
#include <string>
#include <iomanip> // 用于格式化输出
using namespace std;
string solution(int a, int b) {
// 计算期望值
// 1. 计算所有可能的操作结果
// 2. 计算每种结果的概率
// 3. 使用加权平均的方法计算期望值
// 计算每种组合的概率和结果
double expected_value = (1.0/4) * (4*a + b) + (1.0/2) * (2*a + 2*b) + (1.0/4) * (a + 4*b);
// 格式化输出为两位小数的字符串
ostringstream oss;
oss << fixed << setprecision(2) << expected_value;
return oss.str();
}
int main() {
// 打印实际输出以便调试
cout << solution(3, 3) << endl;
cout << solution(5, 7) << endl;
cout << solution(1, 1) << endl;
// 测试样例
cout << (solution(3, 3) == "13.50") << endl;
cout << (solution(5, 7) == "27.00") << endl;
cout << (solution(1, 1) == "4.50") << endl;
return 0;
}
运行结果:
五、数组重排最小化差值
问题描述
小C 和小U 有两个数组,分别是 a
和 b
,它们的长度相同。小U 想通过重新排列数组 a
的元素,来最小化 a
和 b
之间的差异。具体来说,他们要最小化所有元素差值绝对值之和,即 sum(abs(a[i] - b[i]))
。
你能帮助小C 和小U 找到这个最小化的值吗?
测试样例
样例1:
输入:
a = [2, 1, 3, 2], b = [5, 2, 4, 2]
输出:5
样例2:
输入:
a = [1, 4, 6], b = [2, 5, 7]
输出:3
样例3:
输入:
a = [1, 9, 6], b = [2, 5, 7]
输出:4
解题思路:
-
理解问题:
- 我们需要重新排列数组
a
的元素,使得a
和b
中对应元素的差值绝对值之和最小。 - 这意味着我们需要找到一种排列方式,使得
a
中的元素尽可能接近b
中的对应元素。
- 我们需要重新排列数组
-
数据结构的选择:
- 由于我们需要对数组
a
进行排列,因此可以考虑对a
进行排序。 - 排序后,我们可以尝试将
a
中的元素与b
中的元素进行匹配,使得差值绝对值之和最小。
- 由于我们需要对数组
-
算法步骤:
- 首先,对数组
a
进行排序。 - 然后,对数组
b
进行排序。 - 计算排序后的
a
和b
中对应元素的差值绝对值之和。
- 首先,对数组
关键点
- 通过排序,我们可以确保
a
中的元素与b
中的元素尽可能接近,从而最小化差值绝对值之和。 - 排序的时间复杂度为
O(n log n)
,计算差值绝对值之和的时间复杂度为O(n)
,因此整体时间复杂度为O(n log n)
。
最终代码:
#include <iostream>
#include <vector>
#include <algorithm> // 用于排序
using namespace std;
long long solution(vector<int> a, vector<int> b) {
// 对数组 a 和 b 进行排序
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// 初始化差值绝对值之和
long long sum = 0;
// 遍历数组 a 和 b,计算差值绝对值之和
for (int i = 0; i < a.size(); ++i) {
sum += abs(a[i] - b[i]);
}
return sum;
}
int main() {
vector<int> a1 = {2, 1, 3, 2}, b1 = {5, 2, 4, 2};
vector<int> a2 = {1, 4, 6}, b2 = {2, 5, 7};
vector<int> a3 = {1, 9, 6}, b3 = {2, 5, 7};
cout << (solution(a1, b1) == 5) << endl;
cout << (solution(a2, b2) == 3) << endl;
cout << (solution(a3, b3) == 4) << endl;
return 0;
}
运行结果:
六、选择题反选效果分析
问题描述
小U正在检查某同学的选择题答案。试卷共有 n
道题目,每道题目只有两个选项 A
和 B
。当前小U手上有两组答案:
s
:该同学的原始答案。t
:标准答案。
小U想知道,如果将该同学的所有答案都反选(即:如果某题的答案是 A
则改成 B
,如果是 B
则改成 A
),那么在反选之后,正确的答案数量是否会增加?具体结果有三种可能:
- 如果反选后的正确答案数 增加,输出 "yes"。
- 如果反选后的正确答案数 不变,输出 "draw"。
- 如果反选后的正确答案数 减少,输出 "no"。
测试样例
样例1:
输入:
n = 2,s = "AB",t = "AA"
输出:'draw'
样例2:
输入:
n = 3,s = "BAA",t = "ABB"
输出:'yes'
样例3:
输入:
n = 4,s = "ABAB",t = "BABA"
输出:'yes'
解题思路:
问题理解
-
输入:
n
:题目数量。s
:该同学的原始答案,长度为n
,每个字符为A
或B
。t
:标准答案,长度为n
,每个字符为A
或B
。
-
输出:
- 如果反选后的正确答案数 增加,输出 "yes"。
- 如果反选后的正确答案数 不变,输出 "draw"。
- 如果反选后的正确答案数 减少,输出 "no"。
解题思路
-
计算原始正确答案数:
- 遍历
s
和t
,统计原始答案s
中与标准答案t
相同的字符数量,记为original_correct
。
- 遍历
-
计算反选后的正确答案数:
- 反选后的正确答案数可以通过
n - original_correct
计算得到,因为反选后,原来正确的答案会变成错误的,原来错误的答案会变成正确的。
- 反选后的正确答案数可以通过
-
比较原始正确答案数和反选后的正确答案数:
- 如果
n - original_correct
大于original_correct
,输出 "yes"。 - 如果
n - original_correct
等于original_correct
,输出 "draw"。 - 如果
n - original_correct
小于original_correct
,输出 "no"。
- 如果
数据结构选择
- 使用简单的字符串遍历和计数即可,不需要复杂的数据结构。
算法步骤
- 初始化
original_correct
为 0。 - 遍历
s
和t
,统计s
中与t
相同的字符数量,累加到original_correct
。 - 计算反选后的正确答案数
flipped_correct
为n - original_correct
。 - 比较
original_correct
和flipped_correct
,根据比较结果输出相应的字符串。
最终代码:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
std::string solution(int n, std::string s, std::string t) {
// 初始化原始正确答案数
int original_correct = 0;
// 遍历 s 和 t,统计原始正确答案数
for (int i = 0; i < n; ++i) {
if (s[i] == t[i]) {
original_correct++;
}
}
// 计算反选后的正确答案数
int flipped_correct = n - original_correct;
// 比较原始正确答案数和反选后的正确答案数
if (flipped_correct > original_correct) {
return "yes";
} else if (flipped_correct == original_correct) {
return "draw";
} else {
return "no";
}
}
int main() {
std::cout << (solution(2, "AB", "AA") == "draw") << std::endl;
std::cout << (solution(3, "BAA", "ABB") == "yes") << std::endl;
std::cout << (solution(4, "ABAB", "BABA") == "yes") << std::endl;
return 0;
}
运行结果:
七、二进制反码转换问题
问题描述
小C在学习二进制运算,他了解到每个非负整数都有其二进制表示。例如,整数 5
可以被表示为二进制 "101"
,整数 11
可以被表示为二进制 "1011"
,并且除了 N = 0
外,任何二进制表示中都不含前导零。
二进制的反码表示是将每个 1
变为 0
,每个 0
变为 1
。例如,二进制数 "101"
的二进制反码为 "010"
。现在小C想知道,给定一个十进制数 N
,它的二进制反码对应的十进制数是多少。
测试样例
样例1:
输入:
N = 5
输出:2
样例2:
输入:
N = 10
输出:5
样例3:
输入:
N = 0
输出:1
解题思路:
问题理解
我们需要将一个十进制数 N
转换为其二进制表示,然后对这个二进制表示进行反码操作(即 1
变为 0
,0
变为 1
),最后将反码后的二进制数转换回十进制数。
数据结构选择
- 二进制表示可以使用字符串来存储。
- 反码操作可以直接在字符串上进行。
算法步骤
- 转换为二进制:将十进制数
N
转换为二进制字符串。 - 反码操作:遍历二进制字符串,将每个
1
变为0
,每个0
变为1
。 - 转换回十进制:将反码后的二进制字符串转换回十进制数。
特殊情况
- 当
N = 0
时,其二进制表示为"0"
,反码后为"1"
,对应的十进制数为1
。
最终代码:
#include <iostream>
#include <string>
#include <bitset>
int solution(int N) {
std::string binary_representation = std::bitset<32>(N).to_string();
size_t first_one = binary_representation.find('1');
if (first_one != std::string::npos) {
binary_representation = binary_representation.substr(first_one);
} else {
binary_representation = "0";
}
for (char &bit : binary_representation) {
bit = (bit == '0') ? '1' : '0';
}
int result = std::stoi(binary_representation, nullptr, 2);
return result;
}
int main() {
std::cout << (solution(5) == 2) << std::endl;
std::cout << (solution(10) == 5) << std::endl;
std::cout << (solution(0) == 1) << std::endl;
return 0;
}
运行结果:
八、充电总时间计算
问题描述
小R有nn部电脑,每部电脑的电池容量分别为aiai。她可以使用两种不同的充电方式来给电脑充电:
- 普通充电:每单位时间为电脑充电xx单位的电量。
- 闪充:每单位时间为电脑充电4x4x单位的电量。
现在,所有电脑的电量都为零。小R希望使用闪充给所有电脑充满电,计算她需要的总充电时间。请保留结果的小数点后两位。
测试样例
样例1:
输入:
n = 4 ,x = 1 ,a = [2, 3, 4, 5]
输出:'3.50'
样例2:
输入:
n = 3 ,x = 2 ,a = [4, 6, 8]
输出:'2.25'
样例3:
输入:
n = 2 ,x = 1 ,a = [10, 5]
输出:'3.75'
解题思路:
问题理解
小R有n
部电脑,每部电脑的电池容量分别为a_i
。她可以使用两种不同的充电方式来给电脑充电:
- 普通充电:每单位时间为电脑充电
x
单位的电量。 - 闪充:每单位时间为电脑充电
4x
单位的电量。
目标是计算使用闪充给所有电脑充满电所需的总充电时间,并保留结果的小数点后两位。
数据结构选择
- 输入:整数
n
(电脑数量),整数x
(普通充电速率),整数数组a
(每部电脑的电池容量)。 - 输出:一个字符串,表示总充电时间,保留两位小数。
算法步骤
- 计算每部电脑的充电时间:
- 对于每部电脑,其充电时间为
a_i / (4 * x)
,因为闪充的速率是4x
。
- 对于每部电脑,其充电时间为
- 累加所有电脑的充电时间:
- 将所有电脑的充电时间累加起来,得到总充电时间。
- 格式化输出:
- 将总充电时间格式化为字符串,保留两位小数。
最终代码:
#include <iostream>
#include <vector>
#include <string>
#include <iomanip> // 用于格式化输出
using namespace std;
string solution(int n, int x, vector<int> a) {
// 初始化总充电时间为0
double totalTime = 0.0;
// 遍历每部电脑,计算并累加充电时间
for (int i = 0; i < n; ++i) {
// 计算当前电脑的充电时间
double time = a[i] / (4.0 * x); // 注意使用4.0来确保浮点数除法
// 累加到总充电时间
totalTime += time;
}
// 格式化输出总充电时间,保留两位小数
ostringstream oss;
oss << fixed << setprecision(2) << totalTime;
return oss.str();
}
int main() {
cout << (solution(4, 1, {2, 3, 4, 5}) == "3.50") << endl;
cout << (solution(3, 2, {4, 6, 8}) == "2.25") << endl;
cout << (solution(2, 1, {10, 5}) == "3.75") << endl;
return 0;
}
运行结果:
标签:std,输出,反码,二进制,样例,反选,int,include From: https://blog.csdn.net/m0_73302939/article/details/143893662