穿过所有点的所需最少直线数量

Submission

运行时间: 64 ms

内存: 16.9 MB

class Solution:
    def minimumLines(self, points: List[List[int]]) -> int:
        n = len(points)
        
        tmp = 1
        i = 0
        pos = {}
        while i < n:
            pos[tmp] = i
            tmp <<= 1
            i += 1
        
        def checkIfSameK(x1,y1,x2,y2,a,b):
            if (y1 == y2 and y1 == b) or (x1 == x2 and x1 == a):
                return True
            return (x2 - x1) * (b - y1) == (y2 - y1) * (a - x1)
        
        
        def getNstate(s,x1,y1,x2,y2):
            ns = s
            while s:
                tmp = s&-s
                a,b = points[pos[tmp]]
                s &= s-1
                if checkIfSameK(x1,y1,x2,y2,a,b):
                    ns ^= tmp
            return ns
        
        @cache
        def dfs(state):
            # 所有点都提取了
            if not state:
                return 0
            
            s = state
            # 先取一个点 
            x,y = points[pos[s&-s]]
            s &= s - 1
            
            # 取不了第二个点了，那当前点随意直线即可
            if not s:
                return dfs(s) + 1
            
            res = inf
            # 枚举第二个点
            while s:
                p,q = points[pos[s&-s]]
                s &= s-1
                
                # 获取state下，去掉共线的点
                nstate = getNstate(state,x,y,p,q)
                res = min(res,dfs(nstate)+1)
            
            return res
        
        return dfs((1<<n)-1)

Explain

这段代码通过动态规划和位掩码的方式来解决问题。首先，它把每个点映射到一个2的幂上的位位置上，以便可以用一个整数的位状态来表示点的集合。接着，定义了两个辅助函数，`checkIfSameK`用来检查三个点是否共线，`getNstate`用于获取从当前状态移除所有与已选两点共线的点后的新状态。最后，使用`dfs`函数来递归地求解最少直线数，其中通过缓存来优化重复计算的问题。`dfs`函数尝试选择每一对点作为直线上的点，并递归计算剩余点组成的新状态所需的最小直线数。

时间复杂度: O(n^2 * 2^n)

空间复杂度: O(n + 2^n)

class Solution:
    def minimumLines(self, points: List[List[int]]) -> int:
        n = len(points)
        
        tmp = 1
        i = 0
        pos = {}
        while i < n:
            pos[tmp] = i
            tmp <<= 1
            i += 1
        
        def checkIfSameK(x1,y1,x2,y2,a,b):
            return (y1 == y2 and y1 == b) or (x1 == x2 and x1 == a) or ((x2 - x1) * (b - y1) == (y2 - y1) * (a - x1))
        
        def getNstate(s,x1,y1,x2,y2):
            ns = s
            while s:
                tmp = s&-s
                a,b = points[pos[tmp]]
                s &= s-1
                if checkIfSameK(x1,y1,x2,y2,a,b):
                    ns ^= tmp
            return ns
        
        @cache
        def dfs(state):
            if not state:
                return 0
            s = state
            x,y = points[pos[s&-s]]
            s &= s - 1
            if not s:
                return dfs(s) + 1
            res = inf
            while s:
                p,q = points[pos[s&-s]]
                s &= s-1
                nstate = getNstate(state,x,y,p,q)
                res = min(res,dfs(nstate)+1)
            return res
        
        return dfs((1<<n)-1)

Explore

在此解法中，我们使用一个整数的位来表示点集，每个点映射到一个2的幂上的位位置。这种方法在点的数量小于或等于整数位数的情况下是有效的。在Python中，整数类型是动态大小的，可以根据需要自动扩展以存储更多的位，因此在实际应用中点的数量受到的限制较少。然而，在其他一些编程语言中，整数类型的位数是固定的（如32位或64位），如果点的数量超过这个位数，就需要采用更复杂的数据结构（如位向量）来处理超过基本整数类型位数的情况。

在`checkIfSameK`函数中，我们避免了浮点运算，而是使用整数运算来检查共线性。这是通过验证 `(x2 - x1) * (b - y1) == (y2 - y1) * (a - x1)` 来实现的，这个条件确保了两个斜率相等，从而避免了由于浮点数精度限制可能引入的误差。通过这种方法，我们可以精确地验证点是否共线，不受浮点数不精确的影响。

在`dfs`函数中使用缓存是为了避免重复计算相同状态下的最少直线数量，从而显著减少计算时间和提高效率。由于问题具有重叠子问题的特性（即不同的递归路径可能会遇到相同的状态），使用缓存可以让我们只计算一次每个状态的结果并存储下来，之后再遇到相同的状态时可以直接使用已缓存的结果。这种方法的主要优点是减少了计算量和执行时间。然而，缓存的缺点是增加了空间复杂度，因为需要额外的空间来存储中间结果，这在状态数量非常多时可能会导致较高的内存使用。

在`getNstate`函数中，我们移除所有与已选择的两点共线的点。这是通过迭代当前状态的所有点，并使用`checkIfSameK`函数检查每个点是否与选定的两点共线来完成的。如果点共线，则从状态中移除该点。这种方法理论上是准确的，因为它基于共线性的严格定义来移除点。然而，如果`checkIfSameK`函数的实现不够精确或存在逻辑错误，则可能错误地排除或保留某些点。在正确实现的情况下，此方法不应错误排除任何点。