首页 > 滴滴笔试后端2道AC代码
头像
字节内推滴滴me
编辑于 2020-09-14 11:58
+ 关注

滴滴笔试后端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;
	}
}



全部评论

(6) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐