刷题记录（2）
1. HWOD机试 - 模拟消息队列(100)
package com.yue.test;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/**
* @Author: 夜雨
* @Date: 2021-12-08-10:31
* @Description:
* @Version 1.0
*/
public class tsest01 {
@Test
public void demo01() {
String one = "2 22 1 11 4 44 5 55 3 33";
String two = "1 7 2 3";
LinkedList<String> baseOne = new LinkedList<>(Arrays.asList(one.split(" ")));
LinkedList<String> baseTwo = new LinkedList<>(Arrays.asList(two.split(" ")));
int resultSize = baseTwo.size() / 2;
List<List<Integer>> result = new ArrayList<>();
for (int j = baseTwo.size() - 1; j >= 0; j -= 2) {
List<Integer> tmp = new ArrayList<>();
for (int k = 0; k < baseOne.size() - 1; ) {
int time = Integer.parseInt(baseOne.get(k));
if (Integer.parseInt(baseTwo.get(j)) > time && Integer.parseInt(baseTwo.get(j - 1)) <= time) {
tmp.add(Integer.valueOf(baseOne.get(k + 1)));
baseOne.remove(k);
baseOne.remove(k);
continue;
}
k += 2;
}
if (tmp.isEmpty()){
tmp.add(-1);
}
result.add(tmp);
}
}
}
改进
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] aStr = scanner.nextLine().split(" ");
int[] a = new int[aStr.length];
for (int i = 0; i < aStr.length; i++) {
a[i] = Integer.parseInt(aStr[i]);
}
List<Pair> t = new ArrayList<>();
for (int i = 0; i < a.length; i += 2) { // 第一行输入两个一对，为发布者的发布时刻和发布内容
t.add(new Pair(a[i], a[i + 1]));
}
t.sort(null); // 按发布时间排序
String[] bStr = scanner.nextLine().split(" ");
int[] b = new int[bStr.length];
for (int i = 0; i < bStr.length; i++) {
b[i] = Integer.parseInt(bStr[i]);
}
List<List<Integer>> msg = new ArrayList<>();
for (int i = 0; i < b.length - 1; i += 2) {
msg.add(new ArrayList<>());
}
for (Pair pair : t) {
int x = pair.x;
int y = pair.y;
int ans = -1;
for (int i = b.length - 2; i >= 0; i -= 2) { // 从优先级高的订阅者开始遍历，优先匹配优先级高的订阅者
if (b[i] <= x && x < b[i + 1]) { // 如果发布时刻在订阅时间中，订阅者收到发布内容
ans = i / 2;
break; // 只有优先级最高的收到
}
}
if (ans != -1) {
msg.get(ans).add(y); // 收到内容
}
}
for (List<Integer> list : msg) {
if (list.isEmpty()) {
System.out.println(-1);
} else {
for (int i : list) {
System.out.print(i + " ");
}
System.out.println();
}
}
}
static class Pair implements Comparable<Pair> {
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Pair other) {
return Integer.compare(this.x, other.x);
}
}
}
2. 分割数组的最大差值(100)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n];
long sum = 0;
for (int i = 0; i < n; i++) {
int num = scanner.nextInt();
sum += num;
nums[i] = num;
}
long maxAbs = 0, leftSum = 0;
for (int i = 0; i < n - 1; i++) {
leftSum += nums[i];
// rightSum = sum - leftSum, 差值 = rightSum - leftSum = Math.abs(sum - leftSum)
maxAbs = Math.max(maxAbs, Math.abs(sum - 2 * leftSum));
}
System.out.println(maxAbs);
}
}
3. 数值同化(200)-BFS
存在一个m*n的二维数组，其成员取值范围为0,1,2。其中值为1的元素具备同化特性，每经过1s,将上下左右值为0的元素同化为1。而值为2的元素，免疫同化。将数组所有成员随机初始化为0或2，再将矩阵的[0,0]元素修改成1，在经过足够长的时间后，求矩阵中有多少个元素是0或2（即0和2数量之和）
输入：输入的前两个数字是矩阵大小。后面的数字是矩阵内容。
如：4 4
[[0, 0, 0, 0], [0, 2, 2, 2], [0, 2, 0, 0], [0, 2, 0, 0]]
输出：返回矩阵中非1的元素个数
import java.util.*;
public class MatrixAssimilation {
static class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static int countNonOnes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
// 使用队列来进行BFS
Queue<Point> queue = new LinkedList<>();
// 初始化，将所有初始值为1的点加入队列
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) {
queue.offer(new Point(i, j));
}
}
}
// 定义四个方向的偏移量
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 广度优先搜索
while (!queue.isEmpty()) {
Point current = queue.poll();
for (int[] dir : directions) {
int newX = current.x + dir[0];
int newY = current.y + dir[1];
// 检查新坐标是否有效且值为0
if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {
// 同化该点，并将其加入队列以便进一步同化其相邻的0
matrix[newX][newY] = 1;
queue.offer(new Point(newX, newY));
}
}
}
// 计算非1的元素个数
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] != 1) {
count++;
}
}
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
// 确保起始点为1
if (matrix[0][0] != 1) {
matrix[0][0] = 1;
}
System.out.println(countNonOnes(matrix));
}
}
4. 数组组成的最小数字(100)
public class Test {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] str = scanner.nextLine().split(",");
Arrays.sort(str, (a, b) -> {
int lengthA = a.length();
int lengthB = b.length();
if (lengthA != lengthB) {
return lengthA - lengthB;
} else {
return a.compareTo(b);
}
});
StringBuilder stringBuilder = new StringBuilder();
if (str.length == 1) {
stringBuilder.append(str[0]);
System.out.println(stringBuilder);
} else if (str.length == 2) {
String s1 = str[0] + str[1];
String s2 = str[1] + str[0];
stringBuilder.append(s1.compareTo(s2) < 0 ? s1 : s2);
System.out.println(stringBuilder);
} else {
String[] res = Arrays.copyOf(str, 3);
Arrays.sort(res);
for (String r : res) {
System.out.print(r);
}
}
}
}
5. 垃圾信息拦截(200)
问题描述：按照如下规则进行垃圾信息识别，发送者A符合以下条件之一，则认为A为垃圾信息发送者：
A发送短信的接收者中，没有发过短信给A的人数L＞5
A发送的短信数-A接收的短信数M＞10
如果存在X，A发送给X的短信数-A接收到X的短信数N＞5
输入描述第一行为条目数目，接下来几行是具体的条目，每个条目是一对ID，第一个数字是发送者ID，后面的数字是接收者ID，中间空格隔开，所有的ID都是为无符号整型，ID最大值为100；
同一个条目中，两个ID不会相同（不会自己给自己发信息）
最后一行为指定ID
输出描述：输出该ID是否为垃圾短信发送者，并且按序列输出L M的值（由于N值不唯一，不需要输出）
例：输入：
15
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
14 1
1 15
1
输出：
true 13 13
输入：
15
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
14 1
1 15
2
输出：
false 0 -1
public class Test {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<Msg> msgList = new ArrayList<>();
int count = Integer.parseInt(scanner.nextLine());
for (int i=0;i<count;i++){
String[] str = scanner.nextLine().split(" ");
msgList.add(new Msg(Integer.parseInt(str[0]),Integer.parseInt(str[1])));
}
Boolean flag = false;
int A = Integer.parseInt(scanner.nextLine());
List<Msg> aSendList = msgList.stream().filter(msg -> msg.sendUser==A).collect(Collectors.toList());
List<Integer> receiveFromA = aSendList.stream().map(msg -> {return msg.receiveUser;}).distinct().collect(Collectors.toList());
List<Msg> otherSendList = msgList.stream().filter(msg -> msg.sendUser!=A).collect(Collectors.toList());
List<Integer> aReceiveList = msgList.stream().filter(msg -> msg.receiveUser==A).map(msg -> {return msg.sendUser;}).collect(Collectors.toList());
int M = aSendList.size()-aReceiveList.size();
int L = aSendList.size();
for (int i=0;i<otherSendList.size();i++){
if (receiveFromA.contains(otherSendList.get(i).sendUser)){
L-=1;
}
}
if (M>10 || L>5){
flag = true;
System.out.print(flag + " " + L + " " + M);
}else {
List<Msg> msgList1 = new ArrayList<>();
for (int i = 0;i<receiveFromA.size();i++) {
int Y = 0;
int X = 0;
int id = receiveFromA.get(i);
Y = aReceiveList.stream().filter(m -> id ==m).collect(Collectors.toList()).size();
X = aSendList.stream().filter(msg -> msg.receiveUser == id).collect(Collectors.toList()).size();
if (Math.abs(X-Y)>5){
flag = true;
break;
}
}
System.out.print(flag + " " + L + " " + M);
}
}
static class Msg{
int sendUser;
int receiveUser;
Msg( int sendUser, int receiveUser){
this.sendUser = sendUser;
this.receiveUser = receiveUser;
}
}
}