leetcode1066

import sys
class Solution:
    def __init__(self):
        self.sums = sys.maxsize

    def backtrack(self,workers,i,bikes,used,sums):
        if i == len(workers):
            self.sums = min(self.sums,sums)
            return

        if sums > self.sums:
            return

        for j in range(len(bikes)):
            if used[j]:
                continue
            used[j] = True
            self.backtrack(workers,i+1,bikes,used,sums+self.getDist(workers[i],bikes[j]))
            used[j] = False

    def getDist(self,worker,bike):
        return  abs(worker[0]-bike[0]) + abs(worker[1]-bike[1])

    def assignBikes(self, workers: 'List[List[int]]', bikes: 'List[List[int]]') -> int:
        v = [False] * len(bikes)
        self.backtrack(workers,0,bikes,v,0)
        return self.sums

上面的代码使用回溯法，但是TLE。考虑需要使用动态规划提升效率，目前还做不出来。

看到一个同样思路的解决方案，使用java语言，却可以AC，这难道又是leetcode平台的“语言杀”？

这种同样思路，使用java可以AC，但是使用.net或python却TLE的情况，我是遇到过几次的。

但也有可能是我的代码写的有问题，目前还没弄明白具体原因。

java版本的代码如下：

class Solution {
    public int assignBikes(int[][] workers, int[][] bikes) {
        dfs(workers, 0, bikes, new boolean[bikes.length], 0);
        return min;
    }
    
    int min = Integer.MAX_VALUE;
    void dfs(int[][] workers, int i, int[][] bikes, boolean[] used, int sum) {
        if (i == workers.length) {
            min = Math.min(min, sum);
            return;
        }
        
        if (sum > min) return;  // early termination
        
        for (int j = 0; j < bikes.length; ++j) {
            if (used[j]) continue;
            used[j] = true;
            dfs(workers, i+1, bikes, used, sum + getDistance(workers[i], bikes[j]));
            used[j] = false;
        }
    }
    
    int getDistance(int[] worker, int[] bike) {
        return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
    }
}

参考地址：https://leetcode.com/problems/campus-bikes-ii/discuss/303375/Java-straightforward-DFS-solution