目录
1.多机调度问题
1.1 题目描述
某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，
任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：
算出n个作业由m台机器加工处理的最短时间
输入
第一行T（1<T<100)表示有T组测试数据。每组测试数据的第一行分别是整数n，m
（1<=n<=10000，1<=m<=100），接下来的一行是n个整数ti（1<=t<=100)。
输出
所需的最短时间1.2 解题思路
多机调度问题用贪心策略来解决的时候, 就可以分两种情况来讨论:
1. 机器数 > 作业数
- 那么每个机器只需要完成一个作业即可, 那么机器处理的最短时间, 就是装有最大作业的完成时间, 就只需要将作业排好序, 返回最大的那一个作业即可.
2. 机器数 < 作业数
- 每次寻找装有最小作业的机器, 然后将任务从大到小取出来挂在装有最小作业的机器上, 当作业全部挂在机器上的时候, 只需返回机器中装有的作业的最大值即可.
1.3 代码实现
public static int getMatTime(int[] taskTime, int[] machines) {
Arrays.sort(taskTime);
int n = taskTime.length;
int m = machines.length;
// 作业数 < 机器数
if(n <= m) {
return taskTime[n - 1];
} else {
for(int i = n - 1; i >= 0; i--) {
int minMachinesTime = machines[0];
int finish = 0;
// 寻找一个装最小作业的机器
for(int j = 1; j < m; j++) {
if(machines[j] < minMachinesTime) {
// 记录该机器下标
finish = j;
minMachinesTime = machines[j];
}
}
// 将最大作业挂在装有最小作业的机器上
machines[finish] += taskTime[i];
}
}
// 返回装有最大作业的机器中的作业数
return findMax(machines);
}
public static int findMax(int[] machines) {
int max = machines[0];
for(int j = 1; j < machines.length; j++) {
if(machines[j] > max) {
max = machines[j];
}
}
return max;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int taskNum = scan.nextInt();
int machineNum = scan.nextInt();
int[] taskTime = new int[taskNum];
int[] machines = new int[machineNum];
for(int i = 0; i < taskNum; i++) {
taskTime[i] = scan.nextInt();
}
System.out.println(getMatTime(taskTime, machines));
}2. 钱币找零
2.1 题目描述
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。
现在要用这些钱来支付K元，至少要用多少张纸币？2.2 解题思路
要支付 k 元, 我们只需要不断选择面值大的纸币来支付就行了, 如果所有纸币都支付完了, k 还大于 0 , 那么就说明支付不起, 如果 k == 0, 就返回使用的纸币张数, 且这种使用方法,使用的纸币张数是最少的. (将一个表示纸币面值和张数的二维数组基于纸币面值排序)
2.3 代码实现
public static int solve(int money, int[][] moneyCount) {
Arrays.sort(moneyCount, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o2[0] - o1[0];
}
});
int count = 0;
int maxMoneyNumber = 0;
for(int i = moneyCount.length - 1; i >= 0; i--) {
// 需要的当前面值与面值数量取最小
maxMoneyNumber = Math.min(money / moneyCount[i][0], moneyCount[i][1]);
money = money - maxMoneyNumber * moneyCount[i][0];
count += maxMoneyNumber;
}
// 如果待支付的钱还大于 0, 则支付不起
if(money > 0) {
return -1;
} else {
return count;
}
}
public static void main(String[] args) {
int[][] moneyCount = { { 100, 10 }, { 2, 1 }, { 10, 3 }, { 5, 4 }, { 20, 0 } ,{50, 1}, { 1, 3 }};
Scanner scan = new Scanner(System.in);
System.out.println("请输入要支付的钱: ");
int money = scan.nextInt();
int res = solve(money, moneyCount);
if(res == -1) {
System.out.println("余额不足!");
} else {
System.out.println(res);
}
}3. 跳跃游戏
3.1 题目描述
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。示例 1
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ，
所以永远不可能到达最后一个下标。3.2 解题思路
设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述, 只要存在一个位置 x, 它本身可以到达最后一个下标，并且它跳跃的最大长度为 x + nums[x], 这个值大于等于 y, 即 x+nums[x] ≥ y, 那么位置 y 也可以到达最后一个下标. 也就是说, 对于任意一个可以到达最后下标的位置 x, 它可以使得 x + 1, x + 2 .... x + nums[x] 这些连续的位置都可以到达.
- 不断遍历数组中每一个位置, 并实时维护最远可以到达的.在跳跃的过程中可以通过 x + num[x] 不断更新跳跃距离的最大值.
3.3 代码实现
public boolean canJump(int[] nums) {
if(nums.length == 0 || nums == null) {
return true;
}
int max = 0;
for(int i = 0; i < nums.length; i++) {
// 是否可以到达当前位置
if(max >= i) {
max = Math.max(max, i + nums[i]);
// 到达的最远的位置是否包含最后一个位置
if(max >= nums.length - 1) {
return true;
}
} else {
// 达到不了,直接返回 false
return false;
}
}
return true;
}
本文含有隐藏内容，请 开通VIP 后查看