贪心算法小介绍~

什么是贪心算法？

从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，得到整个问题的最优解。简而言之，就是每一步都选择当前最优解，不考虑整体。下面来练两道题试试水~

【题目<简单>】

        分割平衡字符串，当L和R的总数相同时，为一个平衡字符串的子串，求出最大子串。

力扣链接https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/

示例：

输入：s = "RLRRLLRLRL"输出：4

思路：

对于一个平衡字符串，其左右两边必然相等。故可以直接遍历。当左右两边相等时，也就得到了一个平衡字符串子串了。

class Solution {    public int balancedStringSplit(String s) { int L = 0 ; int R = 0; int count =  0 ; for (char c: s.toCharArray()) {        //toCharArray（）作用：返回一个字符数组，该数组中存放了当前字符串的所有字符。     if (c=='L'){  L++;     }else {  R++;     }     if (L == R){  count++;     } } return count;    } }

【题目】 （类似0-1背包问题）

    救生艇问题：船的数量不限，每艘可以承载的最大量为limit，求承载所有人所需的最小船数。

力扣链接：https://leetcode-cn.com/problems/boats-to-save-people/

示例

输入：people = [1,2], limit = 3输出：1输入：people = [3,2,2,1], limit = 3输出：3

思路

    因为使用了贪心算法，肯定需要的是双人船更多，也就是使用的船的总数需要最少。因此肯定需要遍历，选择最大的和最小的为一组，将二者的体重相加，和limit去 进行比对。

class Solution {    public int numRescueBoats(int[] people, int limit) {    //   排序      Arrays.sort(people);      int count = 0 ;      int left = 0 ;       int right = people.length -1;      while (left <= right){      //如果大+小成立。 则大+小一个船  否则体重大的单独一个船   if(people[left]+people[right] <= limit){left++;          }     right--;     count++;      }      return count;    }}