共 11 篇文章
传送门 T1 可以形成最大正方形的矩形数目 思路 签到题，半分钟直接来。 代码 ```cpp class Solution { public: int countGoodRectangles(vector>& rectangles) { int ans = 0; int maxLen = -1; for(auto el : rectangles) { maxLen = max(maxLen, min(el[0], el[1])); } for(auto el : rectangles) { if(min(el[0], el[1]) == maxLen) { …
传送门 题目意思很好理解，就是维护一个单调栈。 ```cpp class Solution { public: vector mostCompetitive(vector& nums, int k) { int n = nums.size(); if(k == n) return nums; stack st; for(int i = 0; i < n; i++) { while(!st.empty() && st.top() > nums[i] && k - st.size() < n - …
传送门 好久没写博客了啊...考试周真是烦人。216周赛可以说是最简单的一次周赛了吧，贪就vans了。 T1 检查两个字符串数组是否相等 签到打卡。 ```cpp class Solution { public: bool arrayStringsAreEqual(vector& word1, vector& word2) { string str1 = "", str2 = ""; for(auto el : word1) { str1 += el; } for(auto el : word2) { str2 += el; } return str1 == …
传送门 冷知识：Y2K就是常说的千年虫。（这题的题意是真的搞，建议语文太差的人不要参与出题） 题目大意 微软公司每个月都可能盈余s元或者亏损d元，但具体是盈余还是亏损不知道。知道的是每连续的五个月统计一次总收入，都是亏损的(不难知道这样的统计一共有八次)。现问在这种条件下一年到头能盈利吗？如果能，找出最大盈利，如果不能就输出"Deficit"。 思路 这题抛开晦涩难懂的题干，其实挺简单的，两位数的数据范围，怎么都能过。有一种做法是统计出所有可能出现的盈亏情况，然后直接对sd判断就行了。 但我本着练算法的原则刷oj，肯定还是采用贪心的思路。 先假设每个月都是盈利的，然后对每个连着的五个月进行判断。如果满足题设的“亏损”条件，就挪到下一个连续的五个月继续判断；如果不满足，就将当前五个月中最后一个不亏损的月份置为亏损，继续上述操作。 代码 ```cpp #include #include #include using namespace std; int s, d; int arr[20]; int calcSum(int pos) { int res = 0; for(int i = pos; i < pos + 5; i++) res += arr[i]; …
传送门 题目大意 假设海岸是一条无限长的直线。陆地在海岸的一边，海洋在另一边。每个小岛都是位于海边的一个点。而任何位于海岸线上的雷达装置，只能覆盖d距离。所以如果小岛与一个雷达之间的距离最多为d，那么它可以被这个雷达覆盖。 我们使用笛卡尔坐标系，定义海岸是x轴，海边在x轴上方，陆地在下方。给定海洋中每个岛屿的位置，给定雷达装置覆盖的距离，你的任务是编写一个程序，找到覆盖所有岛屿的最小数量的雷达装置。请注意，岛屿的位置由其(x,y)坐标表示。如果无法完成覆盖，则输出“-1”。 思路 给定覆盖半径与一系列散点，问最少用多少雷达可以覆盖到所有小岛。 很明显是一个贪心问题。在思考贪心策略之前我们需要考虑一下输出“-1”的情况。首先，因为雷达只能装在岸边，所以如果至少存在一个点，它距岸边的距离大于雷达半径，显然就无法完成覆盖了。其次，数据中存在d<0的情况，这种情况也是输出-1. 接下来思考贪心。要让雷达尽可能少，那就要让每个雷达尽可能的多覆盖小岛。如何去判断多个小岛能否被同一个雷达覆盖就成了这道题的核心问题。 以每个岛屿为圆心，d为半径做一个新圆，圆与x轴相交的两点会构成一个区间。不难想到，如果任意两个岛屿的区间存在重合，那么它们就能被同一个雷达覆盖。 所以对每个岛屿计算出它的区间值，以左边界为关键字排序，然后去判断就行了。 代码 ```cpp #include #include #include #include #include #include #define PAIR pair using namespace std; const int N = 1010; int n, d, cnt; class Node { public: int …
传送门 t1 圆形赛道上经过次数最多的扇区 有一个圆形区域，被分成n块扇区，给出一系列起点与终点，问跑到最后经过次数最多的扇区是哪些。 赛时居然没过这题... 当时写了一个模拟，因为没处理好边界问题，死活过不去。赛后下来看了发现确实想复杂了。 我们要发现一个事实，因为赛道是圆形的，所以除了结尾的那一圈“不完整”的赛程，之前若干圈赛程都是没有意义的，因为每个扇区都同时累加了经过次数，“同时”在本题中是没有讨论意义的。所以我们的答案只用关注最后那不完整的赛程经过了哪些扇区。 值得注意的是，起点不一定是第一块扇区，所以要处理越界问题。同时，观察样例不难发现答案是有序的，所以还要对最终答案数组做一个排序。 ```cpp class Solution { public: vector mostVisited(int n, vector& rounds) { vectorans; int l = rounds[0]; int r = rounds[rounds.size()-1]; while(l != r) { if(l == n+1) { l %= n; continue; } ans.push_back(l++); } ans.push_back(r); …
传送门 t1 存在连续三个奇数的数组 签到题，直接O(n²)遍历就能过。 ```cpp class Solution { public: bool threeConsecutiveOdds(vector& arr) { const int n = arr.size(); if(n < 3) return false; for(int i = 2; i < n; i++) { int cnt = 0; for(int j = i-2; j <= i; j++) …
传送门 题目大意 现在有四种随从： 圣盾亡语圣盾亡语白板 如果对方随从没有免疫，以上随从都能做到一击必杀。 词缀的效果如下： 圣盾：免疫一次伤害，免疫后圣盾消失。亡语：死亡时召唤一只1/1的藤蔓。 每回合只能发动一次攻击，游戏结束时你还有随从存活就算你获胜。你很会玩，所以你一定能找到制胜策略，哪怕只有一点可能。 给你双方随从信息，请告诉我你能否获胜。 思路 贪心处理。 藤蔓没法拿来解场，只能破圣盾，因为每个随从的血量都是1e9。没有藤蔓时只能硬解，为了亏得少一些，优先用有亡语的随从解。上述条件都满足不了了，用圣盾亡语的随从。 ```cpp #include using namespace std; int t; int a[5], b[5]; void battle() { if(b[3]) { b[3]--; b[5]++; } else if(b[4]) b[4]--; else if(b[1]) { b[1]--; b[3]++; } else { b[2]--; b[4]++; } …
传送门 题目大意 一个游戏包含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; ); …
传送门 这题还是一道贪心。（最近LC很喜欢出贪心啊）因为nums[i]表示在第i个位置时每一步能向前走0~nums[i]的长度，所以若每一步都走的尽量远，最后到达终点时消耗的步数一定最短。（如果这题改成在i位置时只能走nums[i]长度那就变成一道dp了）所以对于每一步，我们都去选择能够到的最远位置。 在具体实现的时候选择一个循环从左向右遍历。维护一个maxpos值表示当前这个位置能走到的最远位置，并把它更新为边界。当走到边界的时候step++表示走了一步，然后继续更新边界。 值得一提的是，遍历过程仅访问0~n-1个元素，因为在跳到最后一个位置前，border值肯定是大于等于n的，不然就不符合题中“ 总是可以到达数组的最后一个位置”的设定了。如果border==n，step会多加一次。 ```cpp class Solution { public: int jump(vector& nums) { int maxpos = 0, border = 0, step = 0; int n = nums.size(); for (int i = 0; i < n - 1; i++) { if (maxpos >= i)//还没走到边界 { …
传送门→ 这双周赛改成贪心赛算了，fo了。 A拥有糖果最多的孩子 贪心+暴力。两重循环外层枚举每一个小朋友，内层去找当前的最大糖果数量。如果当前小朋友的糖加上额外给的能大于等于这个最大值就push一个1进去，否则push一个0。 ```cpp class Solution { public: vector kidsWithCandies(vector& candies, int extraCandies) { vector ans; int n = candies.size(); for(int i = 0; i < n; i++) { int maxn = 0; for(int j = 0; j < n; j++) if(i == j) …