萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

贪心算法

发表于 2020-01-29 | 分类于 算法学习日记 | 4 | 阅读次数 619

简介

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

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

详细描述请看这里

算法案例

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题解代码由博主编写


# 算法 # 贪心算法
动态优先权调度算法模拟
Android基础知识
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持