快手笔试A卷 4题100
前三题都是练手
第四题笔试结束上代码~
抱歉更新得晚了一点，写完吃饭去了……
第一题 比较版本号
package 快手.c0825.a;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
for (int i = 0; i < m; i++) {
String versionA = scanner.next();
String versionB = scanner.next();
System.out.println(helper(versionA, versionB));
}
}
private static boolean helper(String versionA, String versionB) {
int[] va = parseVersion(versionA);
int[] vb = parseVersion(versionB);
for (int i = 0; i < 4; i++) {
if (va[i] < vb[i]) {
return true;
} else if (va[i] > vb[i]) {
return false;
}
}
return false;
}
private static int[] parseVersion(String v) {
String[] strings = v.split("\\.");
int[] version = new int[4];
for (int i = 0; i < Math.min(strings.length, 4); i++) {
version[i] = Integer.parseInt(strings[i]);
}
return version;
}
}
第二题 完美平方数变种
package 快手.c0825.b;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
for (int i = 0; i < m; i++) {
int num = scanner.nextInt();
Set<Integer> set = new HashSet<>();
boolean res = helper(num, set);
System.out.println(res);
}
}
private static boolean helper(int num, Set<Integer> set) {
if (num == 1) {
return true;
}
if (set.contains(num)) {
return false;
}
set.add(num);
int cur = 0;
while (num != 0) {
cur += (num % 10) * (num % 10);
num /= 10;
}
return helper(cur, set);
}
}
package 快手.c0825.c;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] a = scanner.nextLine().split(" ");
String[] b = scanner.nextLine().split(" ");
int count = Math.min(a.length / 4, b.length);
int ia = 0, ib = 0;
for (int i = 0; i < count; i++) {
for (int j = 0; j < 4; j++) {
System.out.print(a[ia++]);
System.out.print(" ");
}
System.out.print(b[ib++]);
System.out.print(" ");
}
while (ia < a.length) {
System.out.print(a[ia++]);
System.out.print(" ");
}
while (ib < b.length) {
System.out.print(b[ib++]);
System.out.print(" ");
}
}
}
第四题 树的好序列
这道题区分度大一点，大概就是总数减去纯红色连通域的个数，再就是记得取模
package 快手.c0825.d;
import java.util.*;
class Node {
int label;
List<Node> neighbors;
List<Boolean> edgeColors;
public static final Boolean RED = false;
public static final Boolean BLACK = true;
public Node(int label) {
this.label = label;
neighbors = new ArrayList<>();
edgeColors = new ArrayList<>();
}
public static Boolean parseColor(int color) {
return color == 1 ? BLACK : RED;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
Node[] graph = new Node[n + 1];
for (int i = 0; i < (n - 1); i++) {
int e1 = scanner.nextInt();
int e2 = scanner.nextInt();
int color = scanner.nextInt();
if (graph[e1] == null) {
graph[e1] = new Node(e1);
}
if (graph[e2] == null) {
graph[e2] = new Node(e2);
}
graph[e1].neighbors.add(graph[e2]);
graph[e1].edgeColors.add(Node.parseColor(color));
graph[e2].neighbors.add(graph[e1]);
graph[e2].edgeColors.add(Node.parseColor(color));
}
System.out.println(helper(graph, k));
}
private static final int MOD = 1000000007;
private static int helper(Node[] graph, int k) {
int n = graph.length - 1;
long total = pow(n, k);
List<Integer> setList = new ArrayList<>();
Set<Node> visited = new HashSet<>();
Queue<Node> q = new LinkedList<>();
for (int i = 1; i < graph.length; i++) {
if (visited.contains(graph[i])) {
continue;
}
Set<Node> redSet = new HashSet<>();
redSet.add(graph[i]);
visited.add(graph[i]);
q.offer(graph[i]);
while (!q.isEmpty()) {
Node node = q.poll();
for (int j = 0; j < node.neighbors.size(); j++) {
if (node.edgeColors.get(j) == Node.RED && !visited.contains(node.neighbors.get(j))) {
Node next = node.neighbors.get(j);
q.offer(next);
redSet.add(next);
visited.add(next);
}
}
}
setList.add(redSet.size());
}
for (Integer size : setList) {
total = (total + MOD - pow(size, k)) % MOD;
}
return (int) total;
}
private static long pow(int n, int k) {
long total = 1;
for (int i = 0; i < k; i++) {
total = (total * n) % MOD;
}
return total;
}
}
