解题思路:自己:先把points里的点拿来求出坐标系的离原点最远的点,然后根据最远距离新建一个数组,然后把points的点都在新建的数组上标记出来。然后再便利从边长为0的正方形开始,里面是否有重复的标签。但是代码写不出来。
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {// int[] arr = new int[s.length()];// int length = points.length;// int center =// for(int i =0 ;i<points.length;i++){int max =0;for(int i=0;i<points.length;i++){int max_index = Math.abs(points[i][0]) > Math.abs(points[i][1]) ? Math.abs(points[i][0]) : Math.abs(points[i][1]);int max = max_index>max?max_index:max;}int[] arr = new int[max*2+1][max*2+1];for(int i =0 ;i<points.length;i++){arr[points[i][0]+max][points[i][1]+max]=i+1;//通过赋值来表示第几个点}for(int i=0;i<max;i++){}}
看过官方提示之后:
但是运行不通过。
import java.lang.Math;
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {// int[] arr = new int[s.length()];// int length = points.length;// int center =// for(int i =0 ;i<points.length;i++){char[] s_arr = s.toCharArray();for(int i =0;i<points.length-1;i++){for(int j=i;j<points.length-1;j++){if(Math.max(Math.abs(points[j][0]),Math.abs(points[j][1]))>Math.max(Math.abs(points[j+1][0]),Math.abs(points[j+1][1]))){int[][] index = new int[1][2];index[0] = points[j];points[j]=points[j+1];points[j+1]=index[0];char index_s =s_arr[j];s_arr[j]=s_arr[j+1];s_arr[j+1]=index_s;}}}int re=0;for(int i=0 ;i<Math.max(Math.abs(points[points.length-1][0]),Math.abs(points[points.length-1][1]));i++){ArrayList<Character> list = new ArrayList<>();for(int j=0;j<points.length;j++){if(i<Math.max(Math.abs(points[points.length-1][0]),Math.abs(points[points.length-1][1]))){if((list.indexOf(s_arr[j]))!=-1){return i;}else{list.add(s_arr[j]);}}else{break;}}}return Math.max(Math.abs(points[points.length-1][0]),Math.abs(points[points.length-1][1]));}
}
他人思路:
对于一个点 (x,y),我们可以将其映射到以原点为中心的第一象限,即 (max(∣x∣,∣y∣),max(∣x∣,∣y∣))。这样,我们就可以将所有的点映射到第一象限,然后按照点到原点的距离进行排序。我们可以使用哈希表 g 来存储所有点到原点的距离,然后按照距离进行排序。对于每个距离 d,我们将所有距离为 d 的点放在一起,然后遍历这些点,如果有两个点的标签相同,那么这个正方形是不合法的,直接返回答案。否则,我们将这些点加入到答案中。
链接:https://leetcode.cn/problems/maximum-points-inside-the-square/solutions/1/python3javacgotypescript-yi-ti-yi-jie-ha-vsvi/
class Solution {public int maxPointsInsideSquare(int[][] points, String s) {TreeMap<Integer, List<Integer>> g = new TreeMap<>();for (int i = 0; i < points.length; ++i) {int x = points[i][0], y = points[i][1];int key = Math.max(Math.abs(x), Math.abs(y));g.computeIfAbsent(key, k -> new ArrayList<>()).add(i);//这段代码的作用是,如果g这个Map中不存在某个key,//则使用k -> new ArrayList<>()这个函数创建一个新的ArrayList并将其赋值给这个key;//如果key已经存在,则直接在对应的ArrayList中添加元素i。}boolean[] vis = new boolean[26];int ans = 0;for (var idx : g.values()) {//通过g.values()提取出来每个key对应的多个标签的在s中的位置。for (int i : idx) {//针对idx这个key有很多标签,便利每个标签int j = s.charAt(i) - 'a';if (vis[j]) {return ans;}vis[j] = true;}ans += idx.size();}return ans;}
}