mardi 26 septembre 2023

Leetcode 11: Why is my answer so slow compared to this one?

Here is the Question Link. Both my solution and the quickest solution are based on the same algorithm.

Here is my solution, moderate, but no mistakes:

class Solution {
public:
  int maxArea(const std::vector<int> &height) {
    uint32_t cur_v = 0;
    uint32_t tmp;

    std::remove_reference_t<decltype(height)>::const_iterator
        iter1 = height.begin(),
        iter2 = height.begin() + height.size() - 1;
    while (iter1 < iter2) {
      tmp = std::distance(iter1, iter2) * std::min(*iter1, *iter2);
      cur_v = tmp > cur_v ? tmp : cur_v;    // update the greatest storage 
      *iter1 > *iter2 ? --iter2 : ++iter1;  // move the smaller pointer
    }

    return cur_v;
  }
};

Here's the quickest solution:

int init = [] {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ofstream out("user.out");
    for (string s; getline(cin, s); out << '\n') {
        int n = count(s.begin(), s.end(), ',') + 1;
        int ans = 0, l = 0, r = n - 1, i = 0, j = s.length() - 1, x, y;
        bool read_l = true, read_r = true;
        while (l < r) {
            if (read_l) {
                read_l = false;
                ++i;
                // translate char into decimal number
                x = s[i++] & 15;
                while ((s[i] & 15) < 10) x = x * 10 + (s[i++] & 15);
            }
            if (read_r) {
                read_r = false;
                for (j -= 2; (s[j] & 15) < 10; --j);
                int k = j + 1;
                y = s[k++] & 15;
                while ((s[k] & 15) < 10) y = y * 10 + (s[k++] & 15);
            }
            ans = max(ans, min(x, y) * (r - l));
            if (x < y) ++l, read_l = true;
            else --r, read_r = true;
        }
        out << ans;
    }
    out.flush();
    exit(0);
    return 0;
}();

class Solution {
public:
    int maxArea(vector<int>) { return 0; }
};

My understanding of this solution is:

  1. This solution utilized LeetCode's adjudication mechanism, which uses an output file to check if the user's solution is correct
  2. It uses ASCII and bit operation to accelerate the operating rate and comparing rate.

I mean, these tricks are interesting, but I don't understand how it can be that quick. My solution takes about 100 ms and 57.9 MB while it takes 12 ms and 7.9 MB, it is unacceptable.

What's worse, my solution is also slower 32 ms than the "Beginner Friendly" solution which provided above while takes the same memory.

Aucun commentaire:

Enregistrer un commentaire