当前位置：首页 > news >正文

4.27算法题

news 来源：原创 2025/6/16 3:10:12

力扣649.Dota2 参议院

649. Dota2 参议院

Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。

给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。

示例 1：

输入：senate = “RD”
输出：“Radiant”
解释：
第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。

示例 2：

输入：senate = “RDD”
输出：“Dire”
解释：
第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。
这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

提示：

n == senate.length
1 <= n <= 104
senate[i] 为 'R' 或 'D'

题目分析

每个人都尽量禁止自己后面的对手，用flag记录判断当前位置是否被禁止，同时改变R和D的值。

解题思路

这个题拿到手会比较绕，文字信息太多太杂了，感觉读完题和没读过一样。其实我们只要能看明白两个阵营的禁止策略逻辑就行了。

假如给一个例子：RDDRD。第一轮：senate[0]的R禁止senate[1]的D，那么senate[2]的D，是禁止senate[0]的R还是禁止senate[3]的R呢？当然是禁止senate[3]的R，因为当轮到这个R的时候，它依然有权利禁止senate[4]的D的禁止权利。所以禁止的策略是，尽量禁止自己后面的对手，因为前面的对手已经使用过权利了，而后续的对手依然可以使用权利禁止自己的同伴。

弄清楚禁止的逻辑以后，我们开始实现代码。先进行初始化，将R和D定义为两个阵营的人是否存活（true or false），读取字符串的长度，方便后面进行循环。在这里我们还需要定义一个flag，目的是保存两个阵营的人是否被禁止，并且方便后续进行判断。flag++就代表遍历到了R阵营，flag- -就代表遍历到了D阵营。因此只要我们把flag初始化为0，我们就可以很容易的判断，flag>0时，就代表此时遍历到的位置，D阵营已被R阵营禁止完了，反之亦然。

每一轮的操作具体为，把R和D再进行初始化变为false，进入for循环，如果当前位置为R，就先判断此处的R是否存活，被禁止就把senate[i]改成0，存活就把R改成true，并且flag++，记录保存R的人数。当前位置为D就把以上操作反过来。外层用while循环判断控制，是否有哪一阵营已经全部被禁止。循环到直到R和D有其中之一为false，就退出while循环。最后留下的R如果为true，就输出R阵营，反之输出D阵营。

代码实现

char* predictPartyVictory(char* senate) {bool R=true,D=true;int flag=0;int n=strlen(senate);while(R&&D){R=false;D=false;for(int i=0;i<n;i++){if(senate[i]=='R'){if(flag<0) senate[i]=0;else R=true;flag++;}if(senate[i]=='D'){if(flag>0) senate[i]=0;else D=true;flag--;}}}if(R==true) return "Radiant";else return "Dire";
}

力扣53.最大子数组和

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

题目分析

计算连续子数组和，当和为负数时放弃当前连续和，连续和归0，从下一节点开始重新计算。

解题思路

这道题代码随想录里面归到了贪心里，但是又有很多地方把它归到了动态规划的Kadane算法里。。我理解贪心的思路，所以我拿贪心写一下这道题的思路。

我们的贪心思想就是从局部最优推出全局最优，这道题也不例外。遇到负数就要有相应的取舍，有些大负数可以留下，有些小负数就要扔掉。我们如何判断负数的留存呢？我们可以先把负数加进我们的连续子数组和中，并且先记录没有加入它之前的连续和。如果加入它没有让连续和小于0，我们就可以继续遍历，或许后面还会有正数；如果加上它连续和已经小于0了，那我们就没必要留它了，这证明加上它一定会影响总和。

理论捋清楚了，我们开始实现代码。先初始化result（全局总和）=-10000（题目给出的最小值），count（局部总和）=0。接着我们进入for循环，遍历数组，count计算目前连续和，并且拿result保存count最大值。如果count加了某个元素导致它小于0了，那就重置连续和，重新开始一段子数组。最后输出之前保存的最大值即可。

代码实现

int maxSubArray(int* nums, int numsSize) {int result=-10000,count=0;for (int i=0;i<numsSize;i++) {count+=nums[i];if (count>result) { result=count;}if(count<=0) count=0;}return result;
}

力扣649.Dota2 参议院

题目分析

解题思路

代码实现

力扣53.最大子数组和

题目分析

解题思路

代码实现

相关文章：