LeetCode——3143. 正方形中的最多点数
通过万岁！！！
- 题目：给你一个n*2的数组，然后第i行表示第i个点的坐标，然后还给你了一个字符串s，s[i]则表示第i个点的名称。然后让你找一个中心是（0,0）的正方形，正方形中尽可能包含多的点，但是里面的点的名称不能重复。即所有的点不存在s[i]=s[j]的情况。
- 思路：下面的点我们先都以第一象限来考虑，然后写代码的时候加个绝对值就好了。首先是构建一个map，然后key是名称，value是点的list。如果list的长度大于1，就对list进行排序，排序的规则就是坐标轴（x或者y）最大的那个点在后面，即切比雪夫距离，也就是max(|x|,|y|)。然后我们找正方形边长的一半（这里叫他minWidth）就好了，因为这个list的长度大于1，我们要让正方形尽可能的大，list是排序过的，所以不包含第二点（暂记为（a,b））就好了，也就是minWidth=max(a,b)-1，但是minWidth还要与之前的minWidth取最小值，所以最终公式为minWidth=max(minWidth,max(a,b)-1)。拿到宽度以后我们再遍历map，然后记录有多少个点再minWidth的范围之内就好了。
- 进阶思路：我的代码时间复杂度有点高，因为涉及到了排序。然后我看了下网上大佬们的思路，其实不用排序的，我们只需要遍历字符串，找到s[i]的这些点中，第二小的切比雪夫距离。
- 技巧：排序
java代码
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {Map<Character, List<int[]>> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {List<int[]> list = map.getOrDefault(s.charAt(i), new ArrayList<>());list.add(points[i]);map.put(s.charAt(i), list);}// 对list进行排序int minWidth = Integer.MAX_VALUE;for (Map.Entry<Character, List<int[]>> entry : map.entrySet()) {List<int[]> value = entry.getValue();if (value.size() >= 2) {// 坐标最大的那个放在后面value.sort(Comparator.comparingInt(o -> Math.max(Math.abs(o[0]), Math.abs(o[1]))));// 获取第二个点int[] point = value.get(1);// 不能包含第二个点minWidth = Math.min(minWidth, Math.max(Math.abs(point[0]), Math.abs(point[1])) - 1);}}int ret = 0;for (Map.Entry<Character, List<int[]>> entry : map.entrySet()) {List<int[]> value = entry.getValue();int[] point = value.getFirst();if (Math.abs(point[0]) <= minWidth && Math.abs(point[1]) <= minWidth) {ret++;}}return ret;}
}
java代码——进阶
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {Map<Character, Integer> map = new HashMap<>();// 正方形的宽度的一半int minWidth = Integer.MAX_VALUE;for (int i = 0; i < s.length(); i++) {int temp = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));// s[i]的宽度Integer siWidth = map.getOrDefault(s.charAt(i), Integer.MAX_VALUE);if (temp < siWidth) {// 因为已经有比siWidth小的点了，siWidth可能是第二小的点minWidth = Math.min(minWidth, siWidth);// 当前这个点的坐标会更小，我们要保留这个点map.put(s.charAt(i), temp);} else if (temp < minWidth) {// temp这个可能是不是s[i]中更小的，但是他比minWidth小minWidth = temp;}}int ret = 0;for (Map.Entry<Character, Integer> entry : map.entrySet()) {if (entry.getValue() < minWidth) {ret++;}}return ret;}
}
- 总结：题目还是有点难度的，主要是这里的切比雪夫距离。