第一题：幸运员工抽奖
从团队中选出整个工号中含有数字7或者工号是7的倍数的员工。
输入：一组空格分隔的员工工号列表。
输出：幸运员工总人数，未找到时输出0。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class q1 {
public static void main(String[] args) throws IOException {
//
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
if (str == null || str.length() == 0) {
System.out.println(0);
return;
}
String[] strs = str.split(" ");
int len = strs.length;
int[] arr = new int[len];
int sum = 0;
for (int i = 0; i < len; i++) {
if (strs[i].contains("7")) {
sum++;
continue;
}
arr[i] = Integer.parseInt(strs[i]);
if (arr[i] % 7 == 0) {
sum++;
}
}
System.out.println(sum);
}
}
第二题：货运装箱问题
货轮最大重量C，有N个集装箱，每个集装箱重量W(i)，对应货物价值V(i)。求货轮不超过最大载重的前提下装载货物总价值最大。
输入：第一行最大重量C，第二行每个集装箱重量W(i)，第三行每个集装箱价值V(i)。
输出：货物总价值。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class q2 {
public static void main(String[] args) throws IOException {
//
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int C = Integer.parseInt(str);
String[] weights = br.readLine().split(",");
String[] values = br.readLine().split(",");
int n = weights.length; // 货物的数量
int[] w = new int[n];
int[] v = new int[n];
for (int i = 0; i < n; i++) {
w[i] = Integer.parseInt(weights[i]);
v[i] = Integer.parseInt(values[i]);
}
zeroOnePackage(n, C, w, v);
}
private static void zeroOnePackage(int n, int C, int[] w, int[] v) {
int[][] f = new int[n + 1][C + 1];
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < C + 1; j++) {
if (w[i - 1] > j) {
f[i][j] = f[i - 1][j];
} else {
f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
System.out.println(f[n][C]);
}
}
第三题：最短路径
图像从传感器到输出JPEG格式图片经过很多node处理，这些node构成一个图像处理的pipeline，其中的有些节点依赖于其他节点输出。A->B表示B的执行依赖于A。
假设每个node执行时间为A(t)，即node A需要执行t秒，没有依赖的node可以并行执行。编写一个方法输入一个有向无环图pipeline，输出执行完需要的最短时间。
输入：第一行输入node的执行时间，第二行输入node的依赖关系。
输出：最短时间。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class q3 {
public static void main(String[] args) throws IOException {
//
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strs = br.readLine().split(",");
int len = strs.length;
int[] times = new int[len];
for (int i = 0; i < len; i++) {
times[i] = Integer.parseInt(strs[i]);
}
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
strs = br.readLine().split(";");
for (int i = 0; i < len; i++) {
String[] ss = strs[i].split(",");
ArrayList<Integer> tmp = new ArrayList<>();
for (String s : ss) {
tmp.add(Integer.parseInt(s));
}
map.put(i + 1, tmp);
}
int res = solution(times, map);
System.out.println(res);
}
private static int solution(int[] times, HashMap<Integer, ArrayList<Integer>> map) {
int start = lookForStart(times, map);
ArrayList<Integer> lengths = new ArrayList<>(); // 存储DFS每次遍历到末节点时的长度
Stack<Integer> stackElement = new Stack<>(); // 存储节点
Stack<Integer> stackLength = new Stack<>(); // 存储到这个节点时的值
stackElement.push(start);
stackLength.push(times[start - 1]);
while (!stackElement.isEmpty()) {
int tmp = stackElement.pop();
int tmpLength = stackLength.pop();
ArrayList<Integer> tmpAdjacency = map.get(tmp);
for (int i = tmpAdjacency.size() - 1; i >= 0; i--) {
int nodeToPush = tmpAdjacency.get(i);
if (nodeToPush == 0) {
lengths.add(tmpLength);
break;
}
stackElement.push(nodeToPush);
stackLength.push(tmpLength + times[nodeToPush - 1]);
}
}
Collections.sort(lengths);
return lengths.get(lengths.size() - 1); // 找最小值，其实是返回最大值
}
private static int lookForStart(int[] times, HashMap<Integer, ArrayList<Integer>> map) {
boolean[] b = new boolean[times.length + 1];
Iterator<Map.Entry<Integer, ArrayList<Integer>>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, ArrayList<Integer>> e = iterator.next();
ArrayList<Integer> list = e.getValue();
for (int i : list) {
b[i] = true;
}
}
int res = 0;
for (int i = 1; i < b.length; i++) {
if (!b[i]) {
res = i;
}
}
return res;
}
}
全部评论
(2) 回帖