2016 9月 Algorithm，Part1 week2 作业帖

课程汇总 && 介绍：http://www.1point3acres.com/bbs/thread-200970-1-1.html

第二次作业，Randomized Queues and Deques  作业入口

1.Deque可以用双向链表实现
2.RandomizedQueue用教授上课说的resizing array实现，remove的时候把随机得到的数对应的坑用array最后一个数填上
3.因为用的eclipse，添加命令行参数以后也无法运行，所以研究了好久好久的命令行编译，总结来说，-classpath中添加jar必须要用详细文件位置，需要多个class时用:分割，冒号前后不能有空格，感觉好麻烦啊，求助老司机怎样在eclipse中运行丫
顺便求学分～转码真的好辛苦啊呜呜呜

youngyang 发表于 2016-9-10 20:06
Deque是用双向链表加了一个sentinel，这样在遍历的时候只要从sentinel的next一直往后遍历直到又走回sentine ...

双向链表的sentinel的值怎么表示啊？
我是这样写的：

1.         private DLinkNode<Item> head;
   
2.         private int size;
   
3.        
   
4.        
   
5.         // create a sentinel
   
6.         @SuppressWarnings("unchecked")
   
7.         public DLinkedListDeque()
   
8.         {
   
9.                 head = new DLinkNode<Item>((Item) "", null, null);
   
10.                 head.next = head;
    
11.                 head.prev = head;
    
12.                 size = 0;
    
13.         }

复制代码

Deque是用双向链表加了一个sentinel，这样在遍历的时候只要从sentinel的next一直往后遍历直到又走回sentinel就表示遍历完成了。看有些双向链表的介绍说双向链表用两个sentinel，但是这个作业里一个就够了啊。。

youngyang 发表于 2016-9-10 20:06
Deque是用双向链表加了一个sentinel，这样在遍历的时候只要从sentinel的next一直往后遍历直到又走回sentine ...

你好，subset使用 randomizedqueue 吧，请问怎么满足题目要求的maximum size 是N呢？

nhqgoal 发表于 2016-9-12 10:01
你好，subset使用 randomizedqueue 吧，请问怎么满足题目要求的maximum size 是N呢？

是用RandomizedQueue，但是你说的max-size是什么意思，不是输入几个就是几个吗

farewell 发表于 2016-9-8 00:21
1.Deque可以用双向链表实现
2.RandomizedQueue用教授上课说的resizing array实现，remove的时候把随机得到 ...

选中project ->project(上方的工具栏) -> properties -> java build path -> add jars or add external jars, 把algs4.jar 和 Std.jar 加进去就可以，但eclipse command line 不适用于这个StdIn,其他亲测可用

第二个random挺有意思的，想合适的next()方法用了很久，要测试nested 和 synchronic 的情况

youngyang 发表于 2016-9-12 23:01
是用RandomizedQueue，但是你说的max-size是什么意思，不是输入几个就是几个吗

用resize的话， 如果N 不恰好是2的幂， 那么数组的大小不是就超过N 了吗？

nhqgoal 发表于 2016-9-13 15:13
用resize的话， 如果N 不恰好是2的幂， 那么数组的大小不是就超过N 了吗？

好像是这样。。没想到这个

这节课不是还没开吗？请问大家是怎么做作业的，能发一个你们交作业的连接吗？就是那个auto grader或者课的链接