字节青训-多米诺骨牌均衡状态、红包运气排行榜

目录

一、多米诺骨牌均衡状态

问题描述

测试样例

解释

解题思路：

问题理解

数据结构选择

算法步骤

最终代码：

运行结果：

二 、红包运气排行榜

问题描述

测试样例

解题思路： 

问题理解

数据结构选择

算法步骤

最终代码：

 

运行结果： 

---

一、多米诺骨牌均衡状态

问题描述

小S玩起了多米诺骨牌，他排列了一行骨牌，并可能将某些骨牌向左或向右推倒。随着骨牌连锁反应的进行，一些骨牌可能因为左右两侧受力平衡而保持竖立。现在小S想要知道在所有动作完成后，哪些骨牌保持竖立。

给定一个表示骨牌初始状态的字符串，其中：

• "L" 表示该位置的骨牌将向左倒。
• "R" 表示该位置的骨牌将向右倒。
• "." 表示该位置的骨牌初始时保持竖立。

模拟整个骨牌倒下的过程，求出最终仍然保持竖立的骨牌的数目和位置。

测试样例

样例1：

输入：num = 14, data = ".L.R...LR..L.." 输出：'4:3,6,13,14'

样例2：

输入：num = 5, data = "R...." 输出：'0'

样例3：

输入：num = 1, data = "." 输出：'1:1'

解释

• 样例1：

  • 输入字符串 ".L.R...LR..L.." 表示有 14 个骨牌，初始状态为竖立、向左倒、竖立、向右倒，等等。
  • 最终结果是 '4:3,6,13,14'，表示有 4 个骨牌保持竖立，位置分别是 3, 6, 13, 14。

• 样例2：

  • 输入字符串 "R...." 表示有 5 个骨牌，第一个骨牌向右倒，其余保持竖立。
  • 最终结果是 '0'，表示没有骨牌保持竖立。

• 样例3：

  • 输入字符串 "." 表示有 1 个骨牌，初始状态为竖立。
  • 最终结果是 '1:1'，表示有 1 个骨牌保持竖立，位置是 1。

解题思路：

 

问题理解

你有一个字符串表示骨牌的初始状态，其中：

• "L" 表示该位置的骨牌将向左倒。
• "R" 表示该位置的骨牌将向右倒。
• "." 表示该位置的骨牌初始时保持竖立。

你需要模拟整个骨牌倒下的过程，并找出最终仍然保持竖立的骨牌的数目和位置。

数据结构选择

1. 字符串：用于存储骨牌的初始状态和最终状态。
2. 栈：用于处理骨牌的倒下过程。我们可以使用栈来模拟骨牌的连锁反应。

算法步骤

1. 初始化：创建一个与输入字符串长度相同的数组，用于记录每个位置的骨牌最终状态。
2. 遍历字符串：
   • 如果遇到 "L"，则从当前位置向左遍历，直到遇到 "R" 或字符串边界。
   • 如果遇到 "R"，则从当前位置向右遍历，直到遇到 "L" 或字符串边界。
   • 如果遇到 "."，则继续遍历。
3. 处理连锁反应：
   • 当 "L" 和 "R" 相遇时，根据它们之间的距离和方向，决定哪些骨牌会倒下，哪些会保持竖立。
4. 统计结果：遍历最终状态数组，统计仍然保持竖立的骨牌的数目和位置。

最终代码：

 

#include <iostream>
#include <string>
#include <vector>using namespace std;std::string solution(int num, std::string data) {// 初始化最终状态数组vector<char> finalState(num, '.');// 遍历字符串for (int i = 0; i < num; ++i) {if (data[i] == 'L') {finalState[i] = '-';// 处理向左倒的情况for (int j = i - 1; j >= 0; --j) {if (data[j] == 'R') {// 计算 "L" 和 "R" 之间的距离int distance = i - j;if (distance % 2 == 0) {// 距离为偶数，中间的骨牌保持竖立finalState[(i+j)/2] = '.';} else {// 距离为奇数，中间的两个骨牌都倒finalState[(i+j)/2] = finalState[(i+j)/2+1] = '-';}break;} else if (data[j] == 'L') {break; // 遇到另一个 "L"，停止} else if (data[j] == '.') {finalState[j] = '-'; // 更新状态}}} else if (data[i] == 'R') {finalState[i] = '-';// 处理向右倒的情况for (int j = i + 1; j < num; ++j) {if (data[j] == 'L') {// 计算 "R" 和 "L" 之间的距离int distance = j - i;if (distance % 2 == 0) {// 距离为偶数，中间的骨牌保持竖立finalState[(i+j)/2] = '.';} else {// 距离为奇数，中间的两个骨牌都倒finalState[(i+j)/2] = finalState[(i+j)/2+1] = '-';}break;} else if (data[j] == 'R') {break; // 遇到另一个 "R"，停止} else if (data[j] == '.') {finalState[j] = '-'; // 更新状态}}}}// 统计结果string result;int count = 0;string positions;for (int i = 0; i < num; ++i) {if (finalState[i] == '.') {// 记录保持竖立的骨牌位置if (count > 0) positions += ",";positions += std::to_string(i + 1);count++;}}// 构建结果字符串result = std::to_string(count);if (count > 0) result += ":" + positions;return result;
}int main() {//  You can add more test cases herestd::cout << (solution(14, ".L.R...LR..L..") == "4:3,6,13,14") << std::endl;std::cout << (solution(5, "R....") == "0") << std::endl;std::cout << (solution(1, ".") == "1:1") << std::endl;return 0;
}

运行结果：

二 、红包运气排行榜

问题描述

小C参与了一场抢红包的游戏，现在他想要对所有参与抢红包的人进行一次运气排名。排名规则如下：抢到的金额越多，排名越靠前；如果两个人抢到的金额相同，则按照他们抢红包的顺序进行排名。比如，如果小C和小U抢到的金额相同，但小C比小U先抢，则小C排在小U前面。

测试样例

样例1：

输入：n = 4 ,s = ["a", "b", "c", "d"] ,x = [1, 2, 2, 1] 输出：['b', 'c', 'a', 'd']

样例2：

输入：n = 3 ,s = ["x", "y", "z"] ,x = [100, 200, 200] 输出：['y', 'z', 'x']

样例3：

输入：n = 5 ,s = ["m", "n", "o", "p", "q"] ,x = [50, 50, 30, 30, 20] 输出：['m', 'n', 'o', 'p', 'q']

解题思路： 

 

问题理解

你需要对抢红包的人进行排名，排名规则如下：

1. 抢到的金额越多，排名越靠前。
2. 如果两个人抢到的金额相同，则按照他们抢红包的顺序进行排名。

数据结构选择

1. **使用 vector<pair<string, int>>**：这个数据结构可以存储每个人的名字和抢到的金额。
2. **使用 map<string, int>**：虽然你不想使用 map，但 map 可以自动处理键的唯一性，并且在插入时可以累加值。

算法步骤

1. 初始化数据结构：使用 vector<pair<string, int>> 来存储每个人的名字和抢到的金额。
2. 插入数据并累加：遍历输入的 s 和 x，检查 vector 中是否已经存在相同的字符串。如果存在，则累加其对应的值；如果不存在，则将新的字符串和值插入到 vector 中。
3. 排序：使用自定义的比较函数对 vector 进行排序。比较函数首先比较金额，如果金额相同，则保持插入顺序。
4. 提取结果：将排序后的 vector 中的名字提取到结果向量 result 中。

最终代码：

 

#include <bits/stdc++.h>
using namespace std;// 自定义比较函数
bool cmp(const pair<string, int>& a, const pair<string, int>& b) {if (a.second != b.second) {return a.second > b.second; // 按照值从大到小排序}return false; // 如果值相同，保持插入顺序
}vector<string> solution(int n, vector<string> s, vector<int> x) {// 使用 vector 来存储数据，并在插入时进行累加vector<pair<string, int>> vec;for (int i = 0; i < n; ++i) {bool found = false;for (auto& p : vec) {if (p.first == s[i]) {p.second += x[i];found = true;break;}}if (!found) {vec.push_back({s[i], x[i]});}}sort(vec.begin(), vec.end(), cmp);// 提取排序后的名字vector<string> result;for (const auto& p : vec) {result.push_back(p.first);}return result;
}int main() {cout << (solution(4, {"a", "b", "c", "d"}, {1, 2, 2, 1}) == vector<string>{"b", "c", "a", "d"}) << endl;cout << (solution(3, {"x", "y", "z"}, {100, 200, 200}) == vector<string>{"y", "z", "x"}) << endl;cout << (solution(5, {"m", "n", "o", "p", "q"}, {50, 50, 30, 30, 20}) == vector<string>{"m", "n", "o", "p", "q"}) << endl;return 0;
}

运行结果：