简介

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

详细描述请看这里

算法案例

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;
	}
}
该题来自力扣1221题解代码由博主编写


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;
	}
}
该题来自力扣1282题解代码由博主编写


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;
	}
}
该题来自力扣765题解代码由博主编写



萤火小屋分享世界