简介
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
详细描述请看这里
算法案例
1.分割平衡字符串
在一个「平衡字符串」中，'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".
题解：
根据贪心算法，我们只要解决当前的子问题就好，使之达到最优解。 R和L成对出现，抓住R找后边的L就可以了（不管R是几个，R有几个就找几个L），找到一对儿计数器加一。
Java代码如下：public class Question {
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.balancedStringSplit("LLLLRRRR"));
}
}
class Solution {
public int balancedStringSplit(String s) {
int frequency = 0; // 计数器
int tr = 0,tl = 0; // R和L出现次数计数器
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == 'R') { // 出现R tr就加一
tr++;
} else { //s.charAt(i) == 'L'
tl++; // 出现L tl就加一
}
if(tr == tl) { // 如果tr和tl相等，说明两者成对儿出现，计数器加一，并将两者清零
frequency++;
tr = 0;
tl = 0;
}
}
return frequency;
}
}
2.用户分组
有n位用户参加活动，他们的ID从0到n-1，每位用户都恰好属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。
样例1：
输入：groupSizes = [3,3,3,3,3,1,3]
输出：[[5],[0,1,2],[3,4,6]]
解释： 其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
样例2：
输入：groupSizes = [2,1,3,3,3,2]
输出：[[1],[0,5],[2,3,4]]
题解：
根据贪心算法，我们只要解决当前的子问题就好，使之达到最优解。我们抓住一个人找他的同组人然后在放进一个组里，然后在抓住下一个未被分组的人重复动作。
Java代码如下：import java.util.List;
import java.util.Vector;
public class Question {
public static void main(String[] args) {
Solution s = new Solution();
int groupSizes[] = {2,1,3,3,3,2};
List<List<Integer>> res = s.groupThePeople(groupSizes);
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res.get(i).size(); j++) {
System.out.print(res.get(i).get(j)+" ");
}
System.out.println();
}
}
}
class Solution {
public List<List<Integer>> groupThePeople(int[] groupSizes) {
List<List<Integer>> res = new Vector<List<Integer>>();// 这是大组
boolean flag[] = new boolean[groupSizes.length];// 设置标记位数组
for (int i = 0; i < flag.length; i++) {
flag[i] = true;
}
for (int i = 0; i < groupSizes.length; i++) { // 未被取过的数组可以成为新分组的成员
if(flag[i]) {
List<Integer> t = new Vector<Integer>(); // 创建新的小分组
t.add(i); // 添加当前值
flag[i] = false;// 将当前的值标记
for (int j = i+1; j < flag.length && t.size() < groupSizes[i]; j++) { // 顺着当前值找同组值
if(groupSizes[i] == groupSizes[j]) { // 找到啦！
t.add(j); // 把它加入组内
flag[j] = false;// 标记一下
}
}
res.add(t); // 把小组加入大组
}
}
return res;
}
}
3.情侣牵手
N对情侣坐在连续排列的2N个座位上，想要牵到对方的手。计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。一次交换可选择任意两人，让他们站起来交换座位。人和座位用0到2N-1的整数表示，情侣们按顺序编号，第一对是(0,1)，第二对是(2,3)，以此类推，最后一对是(2N-2,2N-1)。
这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。
样例1：
输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。
样例2：
输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。
题解：
根据贪心算法，我们只要解决当前的子问题就好，使之达到最优解。我们从第一个人开始，看TA右侧的人是否是TA的情侣。偶数的情侣是其值加一，奇数的情侣是其值减一。如果当前右侧不是其情侣，向后找，找到后与其右侧的数字交换位置。然后下标加二重复上述动作。
Java代码：public class Question765 {
public static void main(String[] args) {
Solution s = new Solution();
int lover[] = {3, 2, 0, 1};
System.out.println(s.minSwapsCouples(lover));
}
}
class Solution {
public int minSwapsCouples(int[] row) {
int counter = 0;
for (int i = 0; i < row.length; i += 2) {
if(row[i] % 2 == 0) { // 偶数：如果对象不在右（偶数对象是其值加一）
if( !(i+1 < row.length && row[i+1] == row[i] + 1) ) {
for (int j = i+2; j < row.length; j++) {
if(row[j] == row[i] + 1) {
int t = row[j];
row[j] = row[i+1];
row[i+1] = t;
counter++;
break;
}
}
}
} else { // 奇数：如果对象不在右（奇数对象是其值减一）
if( !(i+1 < row.length && row[i+1] == row[i] - 1) ) {
for (int j = i+2; j < row.length; j++) {
if(row[j] == row[i] - 1) {
int t = row[j];
row[j] = row[i+1];
row[i+1] = t;
counter++;
break;
}
}
}
}
}
return counter;
}
}