0ms C++ Solution


  • 7

    To read n characters, we first call read4 for n / 4 times. For example, if we want to read 10 characters, we will read them in the 8 (4 * 2) + 2 manner by first calling read4 for 2 (n / 4) times to read the 8 characters.

    Then we see if there are any remaining characters to read (in this case, remain = 2).

    If remain > 0, we read them again using read4. However, we may not be able to read all of them. For example, buf has 9 characters and we need to read 10. After reading the 8 characters we can only read the remaining 1 character. In this case, we simply add the minimum of remain and the actual number of characters read by read4 to the couter (total) and return it. Otherwise, we are done and just return n .

    The code is as follows.

    // Forward declaration of the read4 API.
    int read4(char *buf);
    
    class Solution {
    public:
        /** 
         * @param buf Destination buffer
         * @param n   Maximum number of characters to read
         * @return    The number of characters read
         */
        int read(char *buf, int n) {
            int total = 0;
            for (int i = 0; i < n / 4; i++)
                total += read4(buf + total);
            int remain = n - total;
            if (remain) {
                int read = read4(buf + total);
                return total + min(read, remain);
            }
            return n;
        }
    };

  • 0
    C

    You solution is correct!


  • 0

    Hi, caikehe. Thanks! Well, I have the access now and I just forget to update this post :-)


  • 0
    C

    Yeap, you are a student from CAS?


  • 0

    Hi, caikehe. Yeah, I am a master student there :-)


  • 0
    C

    Wow, I saw ur linkedIn profile!


  • 0

    Haha, yeah. I have seen your last visit. Well, we have built connections now :-)


  • 0
    C

    yes, Nice to meet u!


  • 0

    Nice to meet you too :-)


  • 2
    H

    This answer is not 100% correct in the sense that it may cause overwrite in buf. Consider the situation that the file has 8 chars but the read is called with n=3. In this case, we should never call read4() on buf directly because that will overwrite 1 byte after the allocated space of buf, which has only 3 . The correct way to handle this is to read into a temporary buffer when there is risk for buf overwrite.


  • 0
    R

    @jianchao-li-fighter

    I am wondering why are you passing total into read4(buf + total)?
    why do you include total inside the read4 function call?


  • 0
    P

    @randy_wales buf is a pointer that supports pointer arithmetic, by adding the number of characters already read to the original pointer, it accesses the appropriate pointer in the buffer. You can think of a buffer as an array on the heap (that is contiguous memory in the free store). buf points to the first element in that array, and total is the index, in fact buf[total] would have also worked since most C and C++ compilers can convert between the two with ease.

    As others have pointed out with every top C++ solution, this answer is wrong. It passes the tests, but has undefined behavior because it can overwrite past the end of the buffer.

    Here is correct code that has no buffer overruns:

    int read(char *buf, int n) {
        char local[4];
        int read = 0, cur = 0, i = 0;
        while((read = read4((char*)&local))) {
            read = cur + read <= n ? cur + read : n;
            for(i = 0; cur < read; ++cur, ++i)
                buf[cur] = local[i];
        }
        return cur;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.