刚做完滴滴,编程题比较简单,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; } }
全部评论
(6) 回帖