滴滴笔试后端2道AC代码
刚做完滴滴，编程题比较简单，1+1，先占个坑，赛后放代码，许愿给个面试机会
--------------------------------更新-------------------------------
第一题：反转子字符串 easy
import java.util.Scanner;
public class T1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
in.nextLine();
String str = in.nextLine();
int len = str.length();
StringBuilder sb = new StringBuilder();
if (n <= len) {
int yushu = len % n;
int up = len / n * n;
for (int i = 0; i < up; i += n) {
sb.append(reverseStr(str.substring(i, i + n)));
}
if (yushu > 0) {
sb.append(reverseStr(str.substring(len - yushu)));
}
System.out.println(sb.toString());
} else {
System.out.println(reverseStr(str));
}
}
static String reverseStr(String str) {
return new StringBuilder(str).reverse().toString();
}
}
第二题：判断n个点能否联通，mid
思路：最小生成树，注意相同边要取最小。
import java.util.Scanner;
public class T2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
int n, m, k;
int[][] cost;
boolean[] vis;
int[] mincost;
while (T-- > 0) {
n = in.nextInt();
m = in.nextInt();
k = in.nextInt();
cost = new int[n + 1][n + 1];
vis = new boolean[n + 1];
mincost = new int[n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cost[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0, a, b, c; i < m; i++) {
a = in.nextInt();
b = in.nextInt();
c = in.nextInt();
if (c <= k)
cost[a][b] = cost[b][a] = Math.min(cost[a][b], c);
}
int ans = Prim(mincost, n, vis, cost);
System.out.println(ans > 0 ? "Yes" : "No");
}
}
static int Prim(int[] mincost, int n, boolean[] vis, int[][] cost) {
for (int i = 1; i <= n; ++i)
mincost[i] = cost[1][i];
mincost[1] = 0;
vis[1] = true;
int res = 0;
for (int i = 1; i < n; ++i) {
int k = -1;
for (int j = 1; j <= n; ++j)
if (!vis[j] && (k == -1 || mincost[k] > mincost[j]))
k = j;
if (k == -1)
break;
vis[k] = true;
if (mincost[k] == Integer.MAX_VALUE)
return -1;
res += mincost[k];
for (int j = 1; j <= n; ++j)
if (!vis[j])
mincost[j] = Math.min(mincost[j], cost[k][j]);
}
return res;
}
}
