原文地址：
贪心的使用方法
先考虑暴力解法： 使用动态规划，枚举所有字符串，得到字典序最小的那个即可
贪心解法：使用排序，排序策略是
如果 （字符串1 + 字符串2）的字典序小于（字符串2 + 字符串1）的字典序，则将 (字符串1 + 字符串2)放在前面。
完整代码如下（使用暴力作为对数器验证贪心解法）
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
//[编程题]拼接所有的字符串产生字典序最小的字符串
//https://www.nowcoder.com/questionTerminal/f1f6a1a1b6f6409b944f869dc8fd3381
public class NowCoder_LowestString {
public static String minString(String[] strs) {
Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
StringBuilder sb = new StringBuilder();
for (String s : strs) {
sb.append(s);
}
return sb.toString();
}
// 暴力解
public static String minString2(String[] strs) {
HashSet used = new HashSet<>();
ArrayList all = new ArrayList<>();
String path = "";
process(strs, used, path, all);
String min = all.get(0);
for (String s : all) {
if (min.compareTo(s) > 0) {
min = s;
}
}
return min;
}
// 已经用过的字符串在used中登记了
// 已经用过的字符串拼接的结果是path
// 所有拼接的方式存在all里面
public static void process(String[] strs, HashSet used, String path, ArrayList all) {
if (used.size() == strs.length) {
all.add(path);
} else {
for (int i = 0; i < strs.length; i++) {
if (!used.contains(i)) {
used.add(i);
process(strs, used, path + strs[i], all);
used.remove(i);
}
}
}
}
public static void main(String[] args) {
int arrLen = 6;
int strLen = 5;
int times = 100000;
for (int i = 0; i < times; i++) {
String[] arr = generateRandomStringArray(arrLen, strLen);
String[] arr1 = copyStringArray(arr);
String[] arr2 = copyStringArray(arr);
String ans1 = minString(arr1);
String ans2 = minString2(arr2);
if (!ans1.equals(ans2)) {
printArray(arr);
System.out.println(ans1);
System.out.println(ans2);
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
private static void printArray(String[] arr) {
for (String s : arr) {
System.out.print(s + ",");
}
System.out.println();
}
private static String[] copyStringArray(String[] arr1) {
if (null == arr1) {
return null;
}
String[] arr2 = new String[arr1.length];
for (int i = 0; i < arr1.length; i++) {
arr2[i] = String.valueOf(arr1[i]);
}
return arr2;
}
private static String[] generateRandomStringArray(int arrLen, int strLen) {
int len = (int) (Math.random() * (arrLen + 1));
String[] arr = new String[len];
for (int i = 0; i < len; i++) {
arr[i] = generateString(strLen);
}
return arr;
}
private static String generateString(int strLen) {
int len = (int) (Math.random() * (strLen)) + 1;
char[] arr = new char[len];
for (int i = 0; i < arr.length; i++) {
int v = 97 + (int) (Math.random() * 26);
arr[i] = (char) v;
}
return String.valueOf(arr);
}
}
会议室安排问题
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回最多的宣讲场次。
完整代码如下（使用暴力作为对数器验证贪心解法）：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class Code_BestArrange {
public static class Program {
public int start;
public int end;
public Program(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "start:" + start + " end:" + end;
}
}
public static int bestArrange0(Program[] programs) {
if (null == programs || programs.length < 1) {
return 0;
}
List ans = new ArrayList<>();
return p(programs, 0, ans);
}
public static int p(Program[] programs, int start, List ans) {
if (programs.length == 0 || !enough(programs, start)) {
return ans.size();
} else {
int max = Integer.MIN_VALUE;
for (int i = 0; i < programs.length; i++) {
if (start = timeLine) {
Program[] next = copyButExcept(programs, i);
max = Math.max(max, process(next, done + 1, programs[i].end));
}
}
return max;
}
public static Program[] copyButExcept(Program[] programs, int i) {
Program[] ans = new Program[programs.length - 1];
int index = 0;
for (int k = 0; k < programs.length; k++) {
if (k != i) {
ans[index++] = programs[k];
}
}
return ans;
}
public static int bestArrange2(Program[] programs) {
Arrays.sort(programs, Comparator.comparingInt(o -> o.end));
int timeLine = 0;
int result = 0;
for (Program program : programs) {
if (timeLine
霍夫曼算法，贪心的策略为：
准备一个小根堆，把所有金条的价值加入小根堆，每次弹出堆顶两个（当下排名最小的两个值）相加存入cost变量，然后把相加后的和继续放入小根堆，反复上述操作，一直到大根堆只有一个数据。返回 cost 就是最小代价。
完整代码如下（使用暴力作为对数器验证贪心解法）：
import java.util.PriorityQueue;
/**
* 一块金条切成两半，是需要花费和长度数值一样的铜板的。 比如长度为20的金条， 不管怎么切，都要花费20个铜板。 一群人想整分整块金条，怎么分最省铜板?
* 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为60，金条要分成10，20，30三个部分。
* 如果先把长度60的金条分成10和50，花费60; 再把长度50的金条分成20和30，花费50; 一共花费110铜板。
* 但如果先把长度60的金条分成30和30，花费60;再把长度30金条分成10和20， 花费30; 一共花费90铜板。 输入一个数组，返回分割的最小代价。
*
*
* 注：堆和排序是解决贪心问题的最常用的两种方案
*/
// https://www.nowcoder.com/questionTerminal/418d2fcdf7f24d6f8f4202e23951c0da
// https://www.lintcode.com/problem/minimum-cost-to-connect-sticks/description
public class NowCoder_SplitGolden {
public static long lessMoney(long[] arr) {
if (arr == null || arr.length queue = new PriorityQueue<>();
for (long i : arr) {
queue.add(i);
}
long cost = 0;
while (queue.size() > 1) {
long i = queue.poll();
long j = queue.poll();
cost += (i + j);
queue.offer(i + j);
}
return cost;
}
// 暴力递归版本
public static long lessMoney0(long[] arr) {
if (arr == null || arr.length
贪心策略：
设置两个堆（一个大根堆，一个小根堆）来实现获取收益的最大值，由于本金为 W ，我们先把所有项目加入到小根堆中，将成本比 W 小或等于的项目加入到大根堆中，那么大根堆的堆顶元素就是但当前能获取收益最大的项目，然后将获取的收益和本金相加，重复这个过程直到做了 k 个项目为止。最终整体的最大收益即为每次的局部最大收益。
完整代码如下（使用暴力作为对数器验证贪心解法）：
class Solution {
public static class Project {
public int profit;
public int capital;
public Project(int profit, int capital) {
this.profit = profit;
this.capital = capital;
}
}
// k项目个数
// W初始资金
// Profits收益
// Capital花费
// 所有花费可以cover的项目中，取最大收益的项目
public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
if (k == 0) {
return W;
}
if (Profits.length == 0) {
return W;
}
k = Math.min(Profits.length, k); // 因为项目无法重复做，所以k最大只能是项目个数
Project[] projects = initProjects(Profits, Capital);
PriorityQueue min = new PriorityQueue<>(Comparator.comparingInt((Project o) -> o.capital));
PriorityQueue max = new PriorityQueue<>((o1, o2) -> o2.profit - o1.profit);
for (Project project : projects) {
min.offer(project);
}
int maxProfit = W;
while (k > 0) {
while (!min.isEmpty() && min.peek().capital
贪心策略：如果 i 位置有点，且 i+1 位置也是点，那么 i 位置一定不需要放灯，等到 i+1 号位置来放灯即可。
完整代码如下（使用暴力作为对数器验证贪心解法）：
import java.util.HashSet;
import java.util.Set;
/**
* 给定一个字符串str，只由'X'和'.'两种字符构成。 'X'表示墙，不能放灯，也不需要点亮 '.'表示居民点，可以放灯，需要点亮
* 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯
*
* 暴力方法 可以放灯的点，有放灯不放灯两种情况，在这两种情况下，摘出照亮所有点的情况， 然后再在这些情况中选出灯最少的方案
*/
// https://www.nowcoder.com/questionTerminal/45d20d0e59d94e7d8879f19a5755c177
// 贪心解法
public class NowCoder_Light {
public static int minLight1(String str) {
if (str == null || str.length() < 1) {
return 0;
}
return p(str.toCharArray(), 0, new HashSet<>());
}
// i及其往后最少的放灯数
// i之前的放灯情况存在set里面
public static int p(char[] str, int i, Set set) {
if (i == str.length) {
for (int s = 0; s < str.length; s++) {
if (str[s] == '.' && (!set.contains(s - 1) && !set.contains(s) && !set.contains(s + 1))) {
return Integer.MAX_VALUE;
}
}
return set.size();
}
int no = p(str, i + 1, set);
if (str[i] == '.') {
set.add(i);
int yes = p(str, i + 1, set);
set.remove(i);
return Math.min(yes, no);
}
return no;
}
// 贪心解法
// i位置有点，且i+1位置也是点，那么i位置一定不需要放灯，等到i+1号位置来放灯
public static int minLight2(String s) {
if (s == null || s.length() < 1) {
return 0;
}
char[] str = s.toCharArray();
int ans = 0;
int i = 0;
while (i < str.length) {
if (str[i] == 'X') {
i++;
} else {
// 无论如何都要
ans++;
if (i + 1 < str.length) {
if (str[i + 1] == '.') {
i += 3;
} else {
// str[i+1] == 'X'
i += 2;
}
} else {
// i+1==str.length
i++;
}
}
}
return ans;
}
// for test
public static String randomString(int len) {
char[] res = new char[(int) (Math.random() * len) + 1];
for (int i = 0; i < res.length; i++) {
res[i] = Math.random() < 0.5 ? 'X' : '.';
}
return String.valueOf(res);
}
public static void main(String[] args) {
int len = 20;
int testTime = 100000;
for (int i = 0; i < testTime; i++) {
String test = randomString(len);
int ans1 = minLight1(test);
int ans2 = minLight2(test);
if (ans1 != ans2) {
System.out.println("oops!");
}
}
System.out.println("finish!");
}
}
参考资料
Original: https://www.cnblogs.com/greyzeng/p/16704842.html
Author: Grey Zeng
Title: 使用贪心来解决的一些问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/802441/
转载文章受原作者版权保护。转载请注明原作者出处！