python3 解法, 执行用时: 288 ms, 内存消耗: 47.6 MB, 提交时间: 2024-05-13 14:49:34

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        ans = 0
        def check(size: int) -> bool:
            vis = set()
            for (x, y), c in zip(points, s):
                if abs(x) <= size and abs(y) <= size:
                    if c in vis:
                        return True
                    vis.add(c)
            nonlocal ans
            ans = len(vis)
            return False
        bisect_left(range(1_000_000_001), True, key=check)
        return ans

java 解法, 执行用时: 10 ms, 内存消耗: 98.4 MB, 提交时间: 2024-05-13 14:48:55

class Solution {
    private int ans;

    public int maxPointsInsideSquare(int[][] points, String S) {
        char[] s = S.toCharArray();
        int left = -1, right = 1_000_000_001;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(mid, points, s)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return ans;
    }

    boolean check(int size, int[][] points, char[] s) {
        int vis = 0;
        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];
            int c = s[i] - 'a';
            if (Math.abs(x) <= size && Math.abs(y) <= size) {
                if ((vis >> c & 1) > 0) {
                    return false;
                }
                vis |= 1 << c;
            }
        }
        ans = Integer.bitCount(vis);
        return true;
    }
}

cpp 解法, 执行用时: 213 ms, 内存消耗: 95.6 MB, 提交时间: 2024-05-13 14:48:39

class Solution {
public:
    // 两次遍历，时间复杂度O(n)
    int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
        vector<pair<int,int>> mark(26, {INT_MAX,INT_MAX});
        const size_t n = points.size();
        int td = INT_MAX;
        for( size_t i = 0; i < n; ++i ) {
            size_t j = s[i]-'a';
            int d = max(abs(points[i][0]), abs(points[i][1]));
            // 维护每个标记的第二大边长
            if( d < mark[j].first ) {
                mark[j] = {d, mark[j].first};
            }
            else {
                mark[j].second = min(d, mark[j].second);
            }
            td = min(td, mark[j].second);
        }
        if( td == INT_MAX ) return n;
        size_t cnt = 0;
        for( size_t i = 0; i < n; ++i ) {
            int d = max(abs(points[i][0]), abs(points[i][1]));
            cnt += d < td;
        }
        return cnt;
    }
    
    // 二分边长，时间复杂度O(nlogU)
    int maxPointsInsideSquare2(vector<vector<int>>& points, string s) {
        int ans = 0;
        auto check = [&](int size) -> bool {
            int vis = 0;
            for (int i = 0; i < points.size(); i++) {
                int x = points[i][0];
                int y = points[i][1];
                char c = s[i] - 'a';
                if (abs(x) <= size && abs(y) <= size) {
                    if (vis >> c & 1) {
                        return false;
                    }
                    vis |= 1 << c;
                }
            }
            ans = __builtin_popcount(vis);
            return true;
        };
        int left = -1, right = 1'000'000'001;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            (check(mid) ? left : right) = mid;
        }
        return ans;
    }
};

golang 解法, 执行用时: 139 ms, 内存消耗: 18.4 MB, 提交时间: 2024-05-13 14:47:10

/**
 * 由于正方形边长越大，越不合法，有单调性，所以可以二分边长。
 * 在二分中统计点数，如果正方形合法，则更新答案的最大值。
 */
func maxPointsInsideSquare(points [][]int, s string) (ans int) {
	sort.Search(1_000_000_001, func(size int) bool {
		vis := 0
		for i, p := range points {
			if abs(p[0]) <= size && abs(p[1]) <= size {
				c := s[i] - 'a'
				if vis>>c&1 > 0 {
					return true
				}
				vis |= 1 << c
			}
		}
		ans = bits.OnesCount(uint(vis))
		return false
	})
	return
}

func abs(x int) int { if x < 0 { return -x }; return x }