欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode第6双周赛

程序员文章站 2022-07-12 12:01:51
...

总结,终于在最后时间做完了四题,第三题最晚,压哨做完,很爽
第一题
https://leetcode-cn.com/contest/biweekly-contest-6/problems/check-if-a-number-is-majority-element-in-a-sorted-array/

public boolean isMajorityElement(int[] nums, int target) {
	int num = 0;
	for (int i = 0; i < nums.length; i++) {
		if (nums[i] == target) {
			num++;
		}
	}
	return num > (nums.length / 2);
}

第二题
https://leetcode-cn.com/contest/biweekly-contest-6/problems/minimum-swaps-to-group-all-1s-together/

public int minSwaps(int[] data) {
	int allN = 0;
	for (int i = 0; i < data.length; i++) {
		allN += data[i];
	}
	if (allN == 0 || allN == 1 || allN == data.length) {
		return 0;
	}
	int max = 0;
	for (int i = 0; i < allN; i++) {
		max += data[i];
	}
	int n = max;
	for (int i = allN; i < data.length; i++) {
		n += data[i] - data[i - allN];
		max = Math.max(n, max);
	}
	return allN - max;
}

第三题
https://leetcode-cn.com/contest/biweekly-contest-6/problems/analyze-user-website-visit-pattern/
这道题其实一上来就有个思路,就是先按照名字进行分类
然后就是一个一个试
新建UTW类,就是通过name进行区分,顺便通过timestamp进行排序

public List<String> mostVisitedPattern(String[] username, int[] timestamp,
		String[] website) {
	Map<String, UTW> maps = new HashMap<String, UTW>();
	for (int i = 0; i < username.length; i++) {
		UTW utw = maps.get(username[i]);
		if (utw == null) {
			utw = new UTW(username.length);
			maps.put(username[i], utw);
		}
		utw.add(timestamp[i], website[i]);
	}
	List<UTW> list = new ArrayList<UTW>();
	for (UTW temp : maps.values()) {
		if (temp.len >= 3) {
			list.add(temp);
		}
	}
	int maxT = 0;
	//哪些是出现过的,防止重复
	Set<String> his = new HashSet<String>();
	//次数等于最大次数的答案
	Set<String> ans = new HashSet<String>();
	for (int i = 0; i < list.size(); i++) {
		UTW utw = list.get(i);
		String[] webs = utw.webs;
		int len = utw.len;
		int x = 0;
		int y = 1;
		int z = 2;
		while (true) {
			String[] strs = { webs[x], webs[y], webs[z] };
			if (contans(his, strs)) {
			} else {
				his.add(toStr(strs));
				int k = 0;
				for (int j = i + 1; j < list.size(); j++) {
					if (list.get(j).contans(strs)) {
						k++;
					}
				}
				if (k > maxT) {
					maxT = k;
					ans = new HashSet<String>();
					ans.add(toStr(strs));
				} else {
					if (k == maxT) {
						ans.add(toStr(strs));
					}
				}
			}
			z++;
			if (z == len) {
				y++;
				z = y + 1;
				if (z == len) {
					x++;
					y = x + 1;
					z = y + 1;
					if (z == len) {
						break;
					}
				}
			}
		}
	}
	List<String> nns = new ArrayList<String>(ans);
	nns.sort(new Comparator<String>() {

		@Override
		public int compare(String o1, String o2) {
			return o1.compareTo(o2);
		}
	});
	String[] ss = nns.get(0).split(",");
	List<String> res = new ArrayList<String>();
	for (int j = 0; j < 3; j++) {
		res.add(ss[j]);
	}
	return res;
}

private boolean contans(Set<String> ans, String[] strs) {
	return ans.contains(toStr(strs));
}

private String toStr(String[] strs) {
	return strs[0] + "," + strs[1] + "," + strs[2];
}

class UTW {
	String name;
	int[] tims;
	String[] webs;
	int len = 0;

	public UTW(int len) {
		tims = new int[len];
		for (int i = 0; i < tims.length; i++) {
			tims[i] = -1;
		}
		webs = new String[len];
	}

	public boolean contans(String[] strs) {
		for (int i = 0; i < len - 2; i++) {
			if (webs[i].equals(strs[0])) {
				for (int j = i + 1; j < len - 1; j++) {
					if (webs[j].equals(strs[1])) {
						for (int k = j + 1; k < len; k++) {
							if (webs[k].equals(strs[2])) {
								return true;
							}
						}
					}
				}
			}
		}
		return false;
	}

	public void add(int tim, String web) {
		len++;
		boolean k = true;
		for (int j = len - 1; j >= 1; j--) {
			if (tim > tims[j - 1]) {
				tims[j] = tim;
				webs[j] = web;
				return;
			} else {
				tims[j] = tims[j - 1];
				webs[j] = webs[j - 1];
			}
		}
		if (k) {
			tims[0] = tim;
			webs[0] = web;
		}
	}
}

第四题
https://leetcode-cn.com/contest/biweekly-contest-6/problems/string-transforms-into-another-string/
这道题先开始的想法:a变b,b变a的话,不就false,其他true,不行了?于是就判断是否有循环
错了一次之后,反应过来,可以借用第三个字母啊,然后把这个循环判断去掉了
发现又错了,然后再加上,想到如果有第三方字母存在的话,可以把循环加上

public boolean canConvert(String str1, String str2) {
	int[] ans = new int[26];
	int[] ends = new int[26];
	for (int i = 0; i < ans.length; i++) {
		ans[i] = -1;
	}
	char[] chars1 = str1.toCharArray();
	char[] chars2 = str2.toCharArray();
	int len = str1.length();
	for (int i = 0; i < len; i++) {
		if (ans[chars1[i] - 'a'] != -1
				&& ans[chars1[i] - 'a'] != chars2[i] - 'a') {
			//如果一个key有两个value的话,是不行的
			return false;
		}
		ans[chars1[i] - 'a'] = chars2[i] - 'a';
		ends[chars2[i] - 'a']++;
	}
	//如果有个value是不存在的,那就可以借用,就是true,不用判断是否有循环
	for (int i = 0; i < 26; i++) {
		if (ends[i] == 0) {
			return true;
		}
	}
	Set<Integer> thisList;
	for (int i = 0; i < 26; i++) {
		thisList = new HashSet<Integer>();
		thisList.add(i);
		int key = i;
		if(ans[key]==key){
			//自己和自己循环不算
			continue;
		}
		while (ans[key] != -1) {
			if (thisList.contains(ans[key])) {
				//出现循环了,那就不行
				return false;
			}
			key = ans[key];
			thisList.add(key);
		}
	}
	return true;
}