我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 1795|回复: 5
收起左侧

[算法题] 一道LeetCode算法题求助

[复制链接] |试试Instant~ |关注本帖
我的人缘0
zhcxyz 发表于 2014-3-3 05:56:14 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

x
LeetCode上名为 Copy List with Random Pointer的题目。
题目要求是:
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

我的想法是借助哈希表来实现,每次在新的List中添加一个Node之后就按照<OldNode, NewNode>的pair存进哈希表里面,后面再为新的LinkedList创建Node的时候,看看next,random两个Point所指向的Node是不是已经在先前创建过了,如果是就直接用创建好的,不然就新建一个。以下是我的实现代码:
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
*     int label;
*     RandomListNode next, random;
*     RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution
{
    public RandomListNode copyRandomList(RandomListNode head)
    {
                if (head == null)
                        return null;

        RandomListNode newhead = new RandomListNode(head.label);
                if (head.next == null)
                {
                        newhead.next = head.next;
                        newhead.random = head.random;
                        return newhead;
                }

                HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
                map.put(head, newhead);
                map.put(null,null);

                RandomListNode pOld = head, pNew;

                while(pOld!=null)
                {
                        if (map.containsKey(pOld))
                                pNew = map.get(pOld);
                        else
                        {
                                pNew = new RandomListNode(pOld.label);
                                map.put(pOld, pNew);
                        }

                        if (map.containsKey(pOld.next))
                                pNew.next = map.get(pOld.next);
                        else
                        {
                                pNew.next = new RandomListNode(pOld.next.label);
                                map.put(pOld.next, pNew.next);
                        }

                        if (map.containsKey(pOld.random))
                                pNew.random = map.get(pOld.random);
                        else
                        {
                                pNew.random = new RandomListNode(pOld.random.label);
                                map.put(pOld.random, pNew.random);
                        }
                        pOld = pOld.next;
                }

                return newhead;
    }
}

没有Accept,报错如下:
/*
Submission Result: Wrong Answer

Input:        {-1,-1}
Output:        Random pointer of node with label -1 points to a node from the original list.
Expected:        {-1,-1}
*/

求哪位大神给我解答一下,问题出在哪里啊? 纠结了一下午了><

上一篇:一道Amazon intern面试题有感
下一篇:求教一个bit的算法题?
我的人缘0
一剑终情 发表于 2014-3-3 06:47:29 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 一剑终情 于 2014-3-2 16:55 编辑

怎么你复制粘贴下来所有指针的星号都不见了
原来是Java、、不懂了但是从OJ给的信息来看,指针应当指向新list的,但是你的指针指向原来的list了
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
一剑终情 发表于 2014-3-3 07:46:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
  1. if (head.next == null)
  2.                 {
  3.                         newhead.next = head.next;
  4.                         newhead.random = head.random;
  5.                         return newhead;
  6.                 }
复制代码
问题出在这几行。newhead.random = head.random ,在head.random不等于null的时候,是原list中的node。

而且这几行毫无意义,这几步都在后面的while循环里处理掉了,没必要加这几行处理list中只有两个node的特殊情况。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| zhcxyz 发表于 2014-3-3 08:25:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

试了一下,果然是这里的问题! 太感谢了,纠结了好久。 自己吃了不少special case不处理的亏,所以会特地多想一下是不是要处理special case,这里反倒是想多了。 感谢!!
回复 支持 反对

使用道具 举报

我的人缘0
dhtim135 发表于 2014-3-5 11:55:05 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
我遇到过一样的问题
主要还是reference没搞清楚
设置新的random pointer时一定是新创建的node
回复 支持 反对

使用道具 举报

我的人缘0
landuostorm 发表于 2014-3-5 21:44:37 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
今天做到这个题了。分享一个思路
假设原链表为[1,2,3,4]
遍历并为这个链表做一个“影子”, 操作后链表为[1,1,2,2,3,3,4,4]
设置影子的random pointer (若node->random不为null,node->next->random = node->random->next)
最后拆分
这样做的好处是不需要额外空间,但是需要遍历两次链表

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 04:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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