Блог

Я решал проблему во время проводимого раз в две недели конкурса на Leetcode.

Ссылка: https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests /

Сначала я попробовал грубую силу, но я скептически относился к тому, сработает ли это. И, как оказалось, я получил TLE. Позже, после решения вопроса с использованием TreeSet и PQs, я нашел одно представление, которое было почти точной копией моей собственной попытки перебора. И этот был принят. Я не смог найти никаких различий. Может кто-нибудь указать мне на них?

МОЙ КОД:

 public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        int[] time = new int[k];
        int[] count = new int[k];
        for (int i = 0; i < arrival.length; i  ) {
            int x = i%k;
            for (int j = 0; j < k; j  , x  ) {
                if (x == k) x = 0;
                if (time[x] <= arrival[i]) {
                    count[x]  ;
                    time[x] = arrival[i]   load[i]; 
                    break;
                }
            }
        }
        List<Integer> ans = new ArrayList<Integer>();
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < count.length; i  ) {
            if (count[i] == max)
                ans.add(i);
            else if (count[i] > max) {
                ans = new ArrayList<Integer>();
                ans.add(i);
                max = count[i];
            }
        }
        return ans;
    }
  

КОД, КОТОРЫЙ БЫЛ ПРИНЯТ:

 public List<Integer> busiestServers(int k, int[] as, int[] ls) {
        int exp[] = new int[k], cnt[] = new int[k], max = 0;
        for (int i = 0; i < as.length; i  ) {
            int t = as[i], l = ls[i], s = i % k;
            for (int j = 0; j < k; j  , s  ) {
                if (s == k) s = 0;
                if (exp[s] <= t) {  // check if free by last job expiration time;
                    cnt[s]  ;
                    exp[s] = t   l;  // load the job and set the job exp time;
                    break;
                }
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i  ) {
            if (cnt[i] == max) res.add(i);
            else if (cnt[i] > max) {
                max = cnt[i];
                res = new ArrayList<>();
                res.add(i);
            }
        }
        return res;
    }
  

Единственное (едва) значимое различие, которое я вижу, заключается в том, что вы arrival[i] load[i] каждый раз обращаетесь к and внутри вашего j цикла, тогда как принятое решение помещает их в переменные вне цикла и каждый раз ссылается на эти переменные, что означает, что их внутренний цикл (по-видимому) немного быстрее. Невероятно, но для этой конкретной проблемы с Leetcode это, похоже, делает разницу между принятым и превышенным лимитом времени.

В частности, я переписал этот цикл в вашем коде:

 for (int j = 0; j < k; j  , x  ) {
    if (x == k) x = 0;
    if (time[x] <= arrival[i]) {
        count[x]  ;
        time[x] = arrival[i]   load[i];
        break;
    }
}
  

следующим образом, чтобы соответствовать второму опубликованному вами решению, которое было принято:

 int currentArrival = arrival[i];
int currentLoad = load[i];
for (int j = 0; j < k; j  , x  ) {
    if (x == k) x = 0;
    if (time[x] <= currentArrival) {
        count[x]  ;
        time[x] = currentArrival   currentLoad;
        break;
    }
}