贪心
使所有字符相等的最小成本
2712. 使所有字符相等的最小成本 - 力扣（LeetCode）
该题目贪心加脑筋急转弯
从前往后遍历，我们只关心相邻两个字符是否相同，如果不相同则需要反转其中一侧，这里需要使用贪心思想，我们每次反转时，比较一下反转左侧需要的成本小，还是反转右侧需要的成本小，每次反转成本小的那一侧，这样遍历时，每次我们都会将相邻的字符变成相同的，需要注意的是反转操作只会改变 s[i−1] 与 s[i] 是否相等，不会改变其他相邻字符是否相等（相等的都反转还是相等，不相等的都反转还是不相等），所以每对相邻字符其实是互相独立的，我们只需要分别计算这些不相等的相邻字符的最小成本，即 min(i,n−i)，累加即为答案。
class Solution {
public long minimumCost(String s) {
char[] ch = s.toCharArray();
long res = 0;
int len = s.length();
for(int i = 1;i < len;i++){
if(ch[i-1] != ch[i]){
res += Integer.min(i,len - i);
}
}
return res;
}
}我们并不需要做实质性的反转，即不需要操作s字符串，因为我们操作是会影响 [0,i -1] 或者 [ i - n - 1]区间的所有字符串的，反转之后，相等的还是相等，不相等的还是不相等，当我们遍历到时还是需要操作，所有我们只需要记录答案即可，而不要真正的反转。举例：当在判断下标为 0 和 1 时，它们不相等我们会将其反转成相等的，而在判断下标为1 和 2 时，我们会将其反转成相等的，这样0，1，2都是相等的了，以此类推最后全部变成相等的
最大子数组和
贪心点：如果遍历到当前点时，前面所有累加和小于0，那么先直接将累加和重置成0，因为负数只会将当前点的值变得更小，所有我们先将累加和重置成0
每次累加完当前值时我们需要将其与当前最大值相比较，防止当前结果是最大值时将其错过
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
int res = Integer.MIN_VALUE;
for(int num : nums){
sum+=num;
res = Integer.max(res,sum);
if(sum < 0){
sum = 0;
}
}
return res;
}
}跳跃游戏
我们设置一个cover值，表示遍历到当前位置时，我们所能向前跳跃的最远距离，因为本题没有次数限制，只需要判断是否能到达终点即可，所以当我们每遍历一个位置时，我们更新现在cover的最大值，如果其覆盖到了终点则直接返回true，否则遍历结束返回false
class Solution {
public boolean canJump(int[] nums) {
if(nums.length == 1){
return true;
}
int cover = nums[0];
for(int i = 0; i <= cover; i++ ){
cover = Integer.max(cover,i + nums[i]);
if(cover >= nums.length - 1){
return true;
}
}
return false;
}
}跳跃游戏II
这题相比于上一题，要难好多啊。
我们定义一个int curr 表示当前我们所能到达的范围（范围右边界），定义 int next 表示在该范围内我们找到的下一个能跳得范围最广的右边界，注意：curr和next表示的是数组当中的索引值，而不是范围的大小，我们在当前范围寻找下个范围最大值时，如果发现已经找到一个范围，它涵盖了数组右边界即n - 1，那我们直接在该范围的基础上，跳跃到终点。如果我们遍历到当前右边界还未发现能数组右边界的范围，则我们需要更新现在的范围为下一个范围的最大值（就是在遍历上一个范围计算出来的范围），这个更新现在的范围的操作就相当于是在跳跃，跳跃的点就是拥有下一个范围的最大值的点
class Solution {
public int jump(int[] nums) {
if(nums.length == 1){
return 0;
}
int res = 0;
int curr = 0;
int next = 0;
for(int i = 0; i < nums.length; i++){
next = Integer.max(next,i + nums[i]);
if(next >= nums.length-1){
return res+1;
}
if(i == curr){
curr = next;
res++;
}
}
return res;
}
}加油站
好难啊😡😣
在遍历的时候，我们保存累计油量的开始位置，并且累加计算从前面到现在为止，我们总共消耗多少油，以及还剩多少油，如果剩下的油已经变成负数了，那我们从下一位置开始重新计算剩余油量（总共消耗多少油一直累加），当循环遍历结束后，如果总共消耗油量小于0，说明整体来看，耗油量大于加油量，直接返回-1，否则就是一定有解，由前面所示，如果剩下的油已经变成负数了，那我们从下一位置开始重新计算剩余油量，所以我们保存累计油量的开始位置的值就一定是答案，返回保存累计油量的开始位置即可
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int[] arr = new int[gas.length];
for(int i = 0;i < gas.length; i++){
arr[i] = gas[i] - cost[i];
}
int sum = 0;
int len = arr.length;
int t = 0;
int res = 0;
for(int i = 0; i<len ;i++){
sum += arr[i];
t+=arr[i];
if(sum < 0){
sum = 0;
res = i + 1;
}
}
return t >= 0?res:-1;
}
}