089贪心经典题目专题1

狭义的贪心
每一步做出在当前状态下的最好或者最优的选择，从而希望最终的结果是最好或者最优的算法

题目一

// 最大数
// 给定一组非负整数nums
// 重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数
// 测试链接 : https://leetcode.cn/problems/largest-number/
public static String largestNumber(int[] nums) {
		int n = nums.length;
		String[] strs = new String[n];
		for (int i = 0; i < n; i++) {
			strs[i] = String.valueOf(nums[i]);
		}
		Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
		if (strs[0].equals("0")) {
			return "0";
		}
		StringBuilder path = new StringBuilder();
		for (String s : strs) {
			path.append(s);
		}
		return path.toString();
	}

题目二

class Solution {
// 两地调度
// 公司计划面试2n个人，给定一个数组 costs
// 其中costs[i]=[aCosti, bCosti]
// 表示第i人飞往a市的费用为aCosti，飞往b市的费用为bCosti
// 返回将每个人都飞到a、b中某座城市的最低费用
// 要求每个城市都有n人抵达
// 测试链接 : https://leetcode.cn/problems/two-city-scheduling/
	public static int twoCitySchedCost(int[][] costs) {
		int n = costs.length;
		int[] arr = new int[n];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			arr[i] = costs[i][1] - costs[i][0];
			sum += costs[i][0];
		}
		Arrays.sort(arr);
		int m = n / 2;
		for (int i = 0; i < m; i++) {
			sum += arr[i];
		}
		return sum;
	}
}