leetcode第7双周赛

很烦，状态不在，第四题是抄别人的
第一题
我们定制了一款特殊的力扣键盘，所有的键都排列在一行上。
我们可以按从左到右的顺序，用一个长度为 26 的字符串 keyboard （索引从 0 开始，到 25 结束）来表示该键盘的键位布局。
现在需要测试这个键盘是否能够有效工作，那么我们就需要个机械手来测试这个键盘。
最初的时候，机械手位于左边起第一个键（也就是索引为 0 的键）的上方。当机械手移动到某一字符所在的键位时，就会在终端上输出该字符。
机械手从索引 i 移动到索引 j 所需要的时间是 |i - j|。
当前测试需要你使用机械手输出指定的单词 word，请你编写一个函数来计算机械手输出该单词所需的时间。

例:
输入：keyboard = “abcdefghijklmnopqrstuvwxyz”, word = “cba”
输出：4
解释：
机械手从 0 号键移动到 2 号键来输出 ‘c’，又移动到 1 号键来输出 ‘b’，接着移动到 0 号键来输出 ‘a’。
总用时 = 2 + 1 + 1 = 4.

public int calculateTime(String keyboard, String word) {
	int start = 0;
	int ans = 0;
	for (int i = 0; i < word.length(); i++) {
		int v = keyboard.indexOf(word.charAt(i));
		ans += Math.abs(start - v);
		start = v;
	}
	return ans;
}

第二题
你需要设计一个能提供下面两个函数的文件系统：
create(path, value): 创建一个新的路径，并尽可能将值 value 与路径 path 关联，然后返回 True。如果路径已经存在或者路径的父路径不存在，则返回 False。
get(path): 返回与路径关联的值。如果路径不存在，则返回 -1。
“路径” 是由一个或多个符合下述格式的字符串连接起来形成的：在 / 后跟着一个或多个小写英文字母。
例如 /leetcode 和 /leetcode/problems 都是有效的路径，但空字符串和 / 不是有效的路径。
好了，接下来就请你来实现这两个函数吧！（请参考示例以获得更多信息）

例:
输入：
[“FileSystem”,“create”,“create”,“get”,“create”,“get”]
[[],["/leet",1],["/leet/code",2],["/leet/code"],["/c/d",1],["/c"]]
输出：
[null,true,true,2,false,-1]
解释：
FileSystem fileSystem = new FileSystem();

fileSystem.create("/leet", 1); // 返回 true
fileSystem.create("/leet/code", 2); // 返回 true
fileSystem.get("/leet/code"); // 返回 2
fileSystem.create("/c/d", 1); // 返回 false 因为父路径 “/c” 不存在。
fileSystem.get("/c"); // 返回 -1 因为该路径不存在。

有点理解错误了开始

class FileSystem {

	Node node;

	public FileSystem() {
		node = new Node();
		node.map = new HashMap<String, Node>();
	}

	public boolean create(String path, int value) {
		int indx = path.indexOf('/');
		int old = indx + 1;
		Node nNode = node;
		while (indx >= 0) {
			indx = path.indexOf('/', indx + 1);
			if (indx > 0) {
				String s = path.substring(old, indx);
				if (!nNode.map.containsKey(s)) {
					return false;
				}
				nNode = nNode.map.get(s);
			} else {
				String s = path.substring(old);
				if (nNode.map.containsKey(s)) {
					return false;
				}
				Node newNode = new Node();
				newNode.value = value;
				newNode.name = s;
				newNode.map = new HashMap<String, Node>();
				nNode.map.put(s, newNode);
				return true;
			}
		}
		return false;
	}

	public int get(String path) {
		int indx = path.indexOf('/');
		int old = indx + 1;
		Node nNode = node;
		while (indx >= 0) {
			indx = path.indexOf('/', indx + 1);
			if (indx > 0) {
				String s = path.substring(old, indx);
				if (!nNode.map.containsKey(s)) {
					return -1;
				}
				nNode = nNode.map.get(s);
			} else {
				String s = path.substring(old);
				if (!nNode.map.containsKey(s)) {
					return -1;
				}
				nNode = nNode.map.get(s);
				return nNode.value;
			}
		}
		return -1;
	}

}

class Node {
	int value;
	String name;
	Map<String, Node> map;
}

第三题
为了装修新房，你需要加工一些长度为正整数的棒材 sticks。
如果要将长度分别为 X 和 Y 的两根棒材连接在一起，你需要支付 X + Y 的费用。 由于施工需要，你必须将所有棒材连接成一根。
返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。

例：
输入：sticks = [2,4,3]
输出：14
解释：先将 2 和 3 连接成 5，花费 5；再将 5 和 4 连接成 9；总花费为 14。

public int connectSticks(int[] sticks) {
	Arrays.sort(sticks);
	int ans = 0;
	for (int i = 0; i < sticks.length - 1; i++) {
		ans += sticks[i] + sticks[i + 1];
		sticks[i + 1] += sticks[i];
		for (int j = i + 1; j < sticks.length - 1; j++) {
			if (sticks[j + 1] < sticks[j]) {
				int k = sticks[j + 1];
				sticks[j + 1] = sticks[j];
				sticks[j] = k;
			} else {
				break;
			}
		}
	}
	return ans;
}

第四题
村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
对于每个房子 i，我们有两种可选的供水方案：
一种是直接在房子内建造水井，成本为 wells[i]；
另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes[i] = [house1, house2, cost] 代表用管道将 house1 和 house2 连接在一起的成本。当然，连接是双向的。
请你帮忙计算为所有房子都供水的最低总成本。

例：
输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
输出：3
解释：
上图展示了铺设管道连接房屋的成本。
最好的策略是在第一个房子里建造水井（成本为 1），然后将其他房子铺设管道连起来（成本为 2），所以总成本为 3。

这道题有个想法就是，有一个点是编号0，每个点到0的距离就是挖井的成本，成本排序，依次计算，直到所有的井连成一串

int[] father;

int find(int x) {
	if (father[x] == x)
		return x;
	return father[x] = find(father[x]);
}

public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
	father = new int[n + 1];
	for (int i = 0; i <= n; i++)
		father[i] = i;
	PriorityQueue<int[]> queue = new PriorityQueue<int[]>(
			new Comparator<int[]>() {
				@Override
				public int compare(int[] a, int[] b) {
					return a[0] - b[0];
				}
			});
	for (int i = 0; i < n; i++) {
		queue.add(new int[] { wells[i], 0, i + 1 });
	}
	for (int i = 0; i < pipes.length; i++) {
		queue.add(new int[] { pipes[i][2], pipes[i][0], pipes[i][1] });
	}
	int res = 0;
	while (!queue.isEmpty()) {
		int[] cur = queue.poll();
		int fa = find(cur[1]);
		int fb = find(cur[2]);
		if (fa == fb)
			continue;
		father[fa] = fb;
		res += cur[0];
	}
	return res;
}

leetcode的一些已经写的觉得有意思的其他题目
https://blog.csdn.net/qq_33321609/article/category/9012437
如果有我没有写博客的其他题目需要讨论，欢迎评论，一起探讨