1、
1.png
输入：
10
0
5 3 0
8 4 0
9 0
9 0
3 0
0
7 9 0
0
9 7 0
输出：
2
这题使用并查集可能会超时，应当使用DFS或BFS解决。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class test1 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
Queue<Integer>[] queue = (LinkedList<Integer>[]) new LinkedList[num+1];
for (int i = 1; i <= num; i++){
queue[i] = new LinkedList<>();
}
for (int i = 1; i <= num; i++){
int k = scan.nextInt();
while (k != 0){
queue[i].add(k);
queue[k].add(i);
k = scan.nextInt();
}
}
boolean[] marked = new boolean[num+1]; //维护一个标记数组
int count = 0;
for (int i = 1; i <= num; i++){
if (!marked[i]) {
dfs(queue, marked, i);
count++;
}
}
System.out.println(count);
}
public static void dfs(Queue<Integer>[] queue, boolean[] marked, int v){
marked[v] = true;
for (int w : queue[v]){
if (!marked[w]) {
dfs(queue, marked, w);
}
}
}
}
2、
2.png
输入：
1
输出：
10
思路是用动态规划来做，dp[i]=dp[i-1]中全为数字的数量+dp[i-1]中加减号的数量（添加一个数字）+dp[i-1]中连续数字的对数（添加一个加号或减号）+dp[i-2]中加减号的数量（添加左右括号）；但觉得会出现很多重复的情况，暂未想出结果。
3、
3.png
输入：
3
2
helloworld
hdlrowolle
2
helloworld
worldhello
2
abcde
acbde
输出：
Yeah
Yeah
Sad
一道很常见的字符串匹配题
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class test3 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int num = Integer.parseInt(scan.nextLine());
String[] result = new String[num];
for(int i = 0; i < num; i++){
int n = Integer.parseInt(scan.nextLine());
String[] str = new String[n];
for(int j = 0; j < n; j++){
str[j] = scan.nextLine();
}
if(resolve(str)) result[i]="Yeah";
else result[i]="Sad";
}
for(int i = 0; i < num; i++){
System.out.println(result[i]);
}
}
public static boolean resolve(String[] str){
for(int i = 0; i < str.length-1; i++)
for(int j = i + 1; j < str.length; j++)
if(str[i].length() == str[j].length())
if(find(str[i],str[j])) return true;
return false;
}
public static boolean find(String str1, String str2){
String s1 = str1 + str1;
Pattern p = Pattern.compile(str2);
Matcher m = p.matcher(s1);
if(m.find()) return true;
String s2 =new StringBuilder(str2).reverse().toString();
p = Pattern.compile(s2);
m = p.matcher(s1);
if(m.find()) return true;
return false;
}
}
4、
4.png
输入：
4 3
10 3 7 5
输出：
4
求最长上升序列（LIS），常见的方法是对每个数遍历其前面有多少个小于它的数，但这样的时间复杂度为O（n^2）。另一种方法是维护一个栈，如果当前数字大于栈顶数字，则直接存入栈顶；如果小于栈顶数字，则存入栈中最接近且大于等于该数字的位置（二分法查找），时间复杂度是O（nlogn）。
import java.util.*;
public class test4 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
int count = scan.nextInt();
int[] arr = new int[num];
for (int i = 0; i < num; i++){
arr[i] = scan.nextInt();
}
Map<Integer, Integer> map = new HashMap<>();
map.put(0, arr[0]);
for (int i = 0; i < count; i++){
for (int j = 0; j < num; j++){
if (arr[j] >= map.get(map.size()-1))
map.put(map.size(), arr[j]);
else {
map.put(find(map, arr[j]), arr[j]);
}
}
}
System.out.println(map.size());
}
//二分法查找
public static int find(Map<Integer, Integer> map, int i){
int lo = 0, hi = map.size()-1;
while (lo <= hi){
int mid = lo+(hi-lo)/2;
if (map.get(mid) < i) lo = mid + 1;
else if (map.get(mid) > i) hi = mid - 1;
else return mid;
}
return lo;
}
}
5、
5.png
输入：
3 2
a = 0 - b
b = 2 - c
c = 4 - d
b - d
b - c
输出：
-2
cannot_answer
其本质是一道无向图的寻找路径题，每添加一个y=k-x等式，相当于向一副加权无向图中分别添加了y、x、yy、xx四个顶点，以及y点到xx点权重为k的无向边和x点到yy点权重为-k的无向边。而想要求y-x的值就看是否存在一条从y点到x点的路径，并求出该路径的值。
import java.util.*;
public class test5 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String[] str = scan.nextLine().split(" ");
int num1 = Integer.parseInt(str[0]);
int num2 = Integer.parseInt(str[1]);
Graph G = new Graph();
for (int i = 0; i < num1; i++){
str = scan.nextLine().split(" ");
G.addEdge(new Edge(str[0], str[4]+"2", Integer.parseInt(str[2])));
G.addEdge(new Edge(str[0]+"2", str[4], -(Integer.parseInt(str[2]))));
}
String[] result = new String[num2];
for (int i = 0; i < num2; i++){
str = scan.nextLine().split(" ");
String v = str[0];
String w = str[2];
List<String> marked = new ArrayList<>(); //维护一个标记列表，用于DFS解决路径问题
result[i] = path(G, v, w, marked);
}
for (int i = 0; i < num2; i++){
System.out.println(result[i]);
}
}
// 加权无向边
public static class Edge{
public String v;
public String w;
public int weight;
public Edge(String v, String w, int weight){
this.v = v;
this.w = w;
this.weight = weight;
}
public int weight() {
return weight;
}
public String either(){
return v;
}
public String other(String vertex){
if (vertex.equals(v)) return w;
else return v;
}
}
// 加权无向图
public static class Graph {
public Map<String, List<Edge>> adj = new HashMap<>();
public void addEdge(Edge e){
String v = e.either(), w = e.other(v);
if (adj.get(v) == null) adj.put(v, new ArrayList<>());
adj.get(v).add(e);
if (adj.get(w) == null) adj.put(w, new ArrayList<>());
adj.get(w).add(e);
}
public List<Edge> adj(String v){
return adj.get(v);
}
}
// 加权无向图的路径问题使用DFS
public static String path(Graph G, String v, String target, List<String> marked){
marked.add(v);
for (Edge e : G.adj(v)){
String w = e.other(v);
if (w.equals(target)) return Integer.toString(e.weight);
else if (marked.contains(w)) continue;
else {
String result = path(G, w, target, marked);
if (result == "cannot_answer") continue;
else return Integer.toString(e.weight + Integer.parseInt(result));
}
}
return "cannot_answer";
}
}
网友评论