力扣刷题篇——贪心

目录❣❣

1221题目描述🌌:

解题思路🌌：

代码附上🌌： 

1217 题目描述🌌：

解题思路:🌌 :

代码附上🌌:

1029题目描述🌌： 

解题思路🌌：

代码附上🌌： 

 10.11 题目描述：🌌

解题思路🌌：

代码附上🌌：

1221题目描述🌌:

在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。 给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。 注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。 返回可以通过分割得到的平衡字符串的 最大数量 。 示例 1： 输入：s = "RLRRLLRLRL" 输出：4 解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。 示例 2： 输入：s = "RLLLLRRRLR" 输出：3 解释：s 可以分割为 "RL"、"LLLRRR"、"LR" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。 示例 3： 输入：s = "LLLLRRRR" 输出：1 解释：s 只能保持原样 "LLLLRRRR". 示例 4： 输入：s = "RLRRRLLRLL" 输出：2 解释：s 可以分割为 "RL"、"RRRLLRLL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

解题思路🌌：

• 将字符串一次性分割成尽可能多的平衡段，则最多段数等于从前往后遍历时达到平衡的次数，一次遍历即可。 
• 遇到'L'就加+1 反正就-1
• 每次达到平衡 就是次数为0时就记录count 表示找到了一个平衡字符串
• 输出即可

代码附上🌌： 

        int count=0;
        int res=0;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
           res+=(ch=='L')?+1:-1; 
           if(res==0){
               count++;
           }
        }
        return count;


    }
}

1217 题目描述🌌：

有 n 个筹码。第 i 个芯片的位置是 position[i] 。 我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个芯片的位置从 position[i] 改变为: position[i] + 2 或 position[i] - 2 ，此时 cost = 0 position[i] + 1 或 position[i] - 1 ，此时 cost = 1 返回将所有筹码移动到同一位置上所需要的 最小代价 。 示例 1： 输入：position = [1,2,3] 输出：1 解释：第一步:将位置3的芯片移动到位置1，成本为0。 第二步:将位置2的芯片移动到位置1，成本= 1。 总成本是1。 示例 2： 输入：position = [2,2,2,3,3] 输出：2 解释：我们可以把位置3的两个芯片移到位置2。每一步的成本为1。总成本= 2。 示例 3: 输入：position = [1,1000000000] 输出：1

解题思路:🌌 :

• 根据题意可知，移动偶数步不消耗步数，移动奇数倍消耗步数1步
• 为了最小化步数 先将偶数步数设置为0
• 分别把偶数位跟奇数位各自挪到一起
• 只需要计算一个数组中 奇数跟偶数的数量即可
• 返回最小的那一个

代码附上🌌:

class Solution {
    public int minCostToMoveChips(int[] position) {



    int oddnumber=0; //奇数的个数
    int evennumber=0;//偶数的个数
    for(int i=0;i<position.length;i++){
        if(position[i]%2==0){
            evennumber++; //偶数++

        }
        else {
            oddnumber++;//奇数++

        }
      
    }
  return Math.min(evennumber,oddnumber);

    }
}

1029题目描述🌌： 

公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。 返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。 示例 1： 输入：costs = [[10,20],[30,200],[400,50],[30,20]] 输出：110 解释： 第一个人去 a 市，费用为 10。 第二个人去 a 市，费用为 30。 第三个人去 b 市，费用为 50。 第四个人去 b 市，费用为 20。 最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。 示例 2： 输入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] 输出：1859 示例 3： 输入：costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]] 输出：3086

解题思路🌌：

• 按照价格A 和价格B分别进行排序
• 将前n个人飞往a 然后用总的人数减去前n个人即为b的人数

代码附上🌌： 

class Solution {
    public int twoCitySchedCost(int[][] costs) {
     
      Arrays.sort(costs, new Comparator<int[]>() {
          @Override
          public int compare(int[] o1, int[] o2) {
              return o1[0] - o1[1] - (o2[0] - o2[1]);
          }
      });

      int res = 0;
      int n = costs.length / 2;
    
      for (int i = 0; i < n; ++i) res += costs[i][0] + costs[i + n][1];
      return res;
    }
}

 10.11 题目描述：🌌

在一个整数数组中，“峰”是大于或等于相邻整数的元素，相应地，“谷”是小于或等于相邻整数的元素。例如，在数组{5, 8, 4, 2, 3, 4, 6}中，{8, 6}是峰， {5, 2}是谷。现在给定一个整数数组，将该数组按峰与谷的交替顺序排序。 示例: 输入: [5, 3, 1, 2, 3] 输出: [5, 1, 3, 2, 3]

解题思路🌌：

先排序，再依次遍历数组，每两个数交换位置。 也可以不排序，直接判断奇数位和偶数位的数字是否符合要求。

• 如果当前i位置为峰判断当前位置跟是否小于前一个位置若小于则交换 大于则不动
• 如果当前位置为谷则判断当前位置是否小于前一个位置若大于则交换小于则不动

代码附上🌌：

class Solution {
    public void wiggleSort(int[] nums) {
      
        for(int i=1;i<nums.length;i++){
            if(i%2==0){
                if(nums[i]>nums[i-1])
                {
                    swap(nums,i,i-1);
                }
            }else{
                if(nums[i]<nums[i-1]){
                    swap(nums,i,i-1);
                }
            }
        }
        

    
    }
private  void  swap(int arr[],int i,int j){
     int temp=arr[i];
       temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;


        

    }
  
}

以上就是小王同学带给大家的几道经典的贪心算法