共 6 篇文章
传送门 这是我做过最简单的 。 先考虑非法的情况。显然，如果n个缺失的骰子全置为6都不能使骰子值之和满足题设条件，这组数据就找不到合法答案。同理可得，n个缺失骰子全为1都不满足题设也是一种镜像情况。这样我们就得到了这道题的边界条件。 接着考虑合法解法。我们可以根据rolls数组之和与mean值计算出n个缺失数据的平均值，将这个值向下取整，就是每个缺失骰子的“最低值”。再依次给n个骰子分配点数，直到分完为止。这样就能依次得出合法的答案序列。 class Solution { public: vector<int> missingRolls(vector<int>& rolls, int mean, int n) { int m = rolls.size(); int tot = 0; for (auto roll : rolls) tot += roll; int idealSum = (n + m) * mean; if (idealSum - tot > n …
传送门 水题，一眼栈 class Solution { public: int calPoints(vector<string>& ops) { stack<int> stk; for (auto el : ops) { if (el[0] == 'C') { if (!stk.empty()) { stk.pop(); } } else if (el[0] == 'D') { int score = stk.top(); stk.push(score * 2); } else if (el[0] == …
传送门 思路 这题其实挺基础的，开这篇博文也只是为了记录一下该类“异型遍历”题型的套路，主要就是突出一个代码清晰逻辑明确。 代码 ```cpp class Solution { public: vector spiralOrder(vector>& matrix) { vector ans; int left = 0; int right = matrix[0].size() - 1; int top = 0; int bottom = matrix.size() - 1; int area = matrix.size() * matrix[0].size(); // 一圈一圈向内收 while (area …
传送门 T1替换隐藏数字得到的最晚时间 思路 签到题，注意一些细节就行。 代码 ```cpp class Solution { public: string maximumTime(string time) { if (time[0] == '?' && time[1] >= '4' && time[1] != '?') time[0] = '1'; else if (time[0] == '?') time[0] = '2'; if (time[1] == '?' && time[0] == '2') …
传送门 题目大意 一个序列s，题目定义两种编码方式： 第一种方式是p，其中pi表示第i个右括号之前的左括号数；第二种是w，其中wi表示第i个右括号(包括它本身)之前完成匹配的括号对数。 现给出序列s在p方式下的编码，求出它在w方式下的编码序列。 思路 已知条件是p序列，那就从p序列入手。 对于pi，设j<i，那么pi-pj的含义显然是第j个右括号与第i个右括号之间的左括号数。而且不难得知，wi能达到的最大值就是i-j，因为括号能匹配成功的前提是有富余的右括号。那么按照这个逻辑去枚举每一对(i,j)就行了。 代码 ```cpp #include #include using namespace std; int t, n; int str[110]; int main() { cin >> t; while(t--) { cin >> n; for(int i = 0; i < n; i++) { scanf("%d", &str;[i]); int j = i - …
传送门 题目大意 一个游戏包含n个阶段，每个阶段有四种类型： 类型0：没有鱼也没有蛤。类型1：只有一只蛤。类型2：只有一条鱼。类型3：有一条鱼和一只蛤。 在每个阶段都可以执行四种操作之一： 用一只蛤换一包鱼饵。如果有一条鱼，可以无需鱼饵抓到这条鱼。无论在此阶段有没有鱼，都可以使用一包鱼饵捕获一条鱼。跳过阶段。 要求求出每局游戏中能抓到鱼的最大条数。 思路 采用贪心的思想。首先，对于类型2、3，显然直接抓鱼是最优的，即有鱼抓鱼。但是类型0时只能用鱼饵抓鱼，类型1时只能做鱼饵或者用鱼饵抓鱼。 根据上面的分析，前导0是可以忽略的，因为我们什么都做不了。忽略后如果遇到类型2、3就直接答案++。其余情况下，优先用鱼饵抓鱼，其次用蛤来换鱼饵。在执行完整个过程后如果还有鱼饵，那么消耗两次类型1来换一条鱼。 值得注意的是，第一次遇见类型0时是没有鱼饵去捕鱼的，所以需要用一个bool来判断当前遇到类型0时是否有鱼饵。 ```cpp #include using namespace std; string s; int t, n, bait, ans; int main() { scanf( "%d", &t; ); while ( t-- ) { int i = 0; scanf( "%d", &n; ); …