一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 770|回复: 2
收起左侧

[Leetcode] read4 II 我的感想

[复制链接] |试试Instant~ |关注本帖
nano 发表于 2014-11-26 22:18:20 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
这里我觉得难的地方在于对题目的理解,尤其是对于我这种没做过底层,embedded 之类的,首先说read4这个function
官方给出的是 int read4(char *buf); 注意做为输入参数的buf是指读入数据所存放的内存指针。可以想象read4从网络端口读入数据,存入buf中,并返回buf中读入数据的大小。

int read(char *buf, int n)函数要实现的功能,是利用read4函数,把数据存入buf中,返回实际数据长度,要求这个数据长度不超过n

这个题目考查的地方其实虽然有点tricky但是并不复杂,read4 c++ 解法如下,参考了leetcode的官方答案

// 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) {
        bool eof=false;
        int num_read=0;

        while(!eof && num_read<=n)
        {
            int sz=read4(buf);
            if(sz<4) eof=true;

            int byte=min(sz, n-num_read);
            num_read+=byte;
            buf+=byte;
        }

        return num_read;
    }
};


然后是read4 II的解法,要考虑多次调用,用同样的code ,于是可能出现你本次要读的一部分数据可能已经被读入上次开的数组里面了。
有一个test case "ab", read(1), read(2), 如果用read4 I的程度调用,read(buf1,1), 有buf1={a,b},再用read(buf2, 2),实际上此时buf2里面已经什么都读不到了。所以需要多开一个local_buf和read4相连,存储每次调用read4读入的数据,此外需要两个变量,一个offset,表示下次读的时候从local_buf哪一位开始,一个endpoint,表示下次读从offset读到endpoint. 我最后用了remaining_bytes_in_buf表示offset到endpoint的距离,这三个量可以用static分配存储空间,也可以在类里面加变量

我的c++ code如下,参考了官方的java版本
// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
    char *local_buff=new char[4];
    int offset=0, remaining_bytes_in_buf=0;
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) {
        bool eof=false;
        int num_read=0;

        while(!eof && num_read<n){
            int sz=remaining_bytes_in_buf>0?remaining_bytes_in_buf:read4(local_buff);
            if(remaining_bytes_in_buf==0 && sz<4) eof=true;
            int bytes=min(n-num_read,sz);
            memcpy(buf+num_read,local_buff+offset,bytes);
            offset=(offset+bytes)%4;
            num_read+=bytes;
            remaining_bytes_in_buf=sz-bytes;
        }

        return num_read;
    }
};


blactangeri 发表于 2014-11-27 05:35:43 | 显示全部楼层
都通过了吗??
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 02:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表