【第四轮】4.6 - 4.12 Career Cup 2.1

2.1 Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

请参加活动的童鞋跟帖回复自己的解法，回复请参考以下格式：

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎探讨各种follow up questions，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

【解题思路】
  1. 用 HashSet 來檢測 duplicate，遍歷鏈表同時向 HashSet 中添加當前，一旦發現失敗了，那麽就要刪除。比較 tricky 的地方是 head 元素是不可能重複的，所以無需使用dummy node 2. 如何處理 head，讓代碼更清晰
2. 用 nested loop 來檢測 duplicate， 一旦發現重復元素就在內層循環中刪除

【时间复杂度】
1. Time - O(N)
2. Time - O(N^2)

【空间复杂度】
1. Space - O(N)
2. Space - O(1)
【gist link]
https://github.com/noisedispatch/CC150/blob/master/src/main/java/chap2/RemoveDuplicates.java

【test case】(optional，如果觉得比较好，欢迎贴出来分享）
https://github.com/noisedispatch/CC150/blob/master/src/test/java/chap2/TestRemoveDuplicates.java

------------

用 intellJ 創建了 maven 的工程，這樣不需要花時間去添加 library 或者 import 之類和編程沒什麽關係的事情。此外，第二次做 CC150，感覺其實很多 solution 非常好，但是自己比較懶，沒有認真的去測試，去面試的時候面試官讓我自己寫 test case，根本就沒什麽想法。所以用 Junit 來寫test case，感覺效率高一些。

repo 的地址都在上面的鏈接裏面，我自己感覺比較方便（如果大家都這樣寫的話，那麽 review 別人的代碼也會容易一點），寫 Java 的同學不如試一下，也歡迎你一起來寫 test case

【解题思路】
use hashtable to store the existing data, if the hastable  contans the data
    means duplicated
   
【时间复杂度】
O(N)
【空间复杂度】
O(N)

   Follow up  How would you solve this problem if a temporary buffer is not allowed?
【解题思路】   Brote force   
   use  two  iterators   one move from  the  root to the end
    second  move from first iterated   node to compare with   all the rest  and move  the dupiclated one
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/michaelniu/6cc6df41ce07bb8857ea

【解题思路】   1. Use hashtable to store the data element for visited nodes, compare newly visted node
        to see if its data is already in the table. If yes, remove the duplicate, else add its data
        into the table.

   2(No temporary buffer). Use two pointers for two layers iteration.
【时间复杂度】 O(n) for 1, O(n^2) for 2
【空间复杂度】O(n) for 1, O(1) for 2
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_1.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

【解题思路】
With extra buffer: Do bin sort or use hash map to de-duplicate
Without extra buffer: For each element, visit all its decedents in this linked list and remove all duplicate values.
【时间复杂度】O(N) or O(N^2)
【空间复杂度】O(C) or O(1), where C is the number of unique values in that linked list.
【gist link] https://github.com/bxshi/intervi ... ate_linked_list.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享） https://github.com/bxshi/intervi ... c/test/2_1_test.cpp

【解题思路】
With extra buffer: 用一个hashtable存储data的值，若unique存入hash中，若又重复删去。
Without extra buffer: 对于每一个node，去除后面所有与它相同的node。
【时间复杂度】
O(N) or O(N^2)
【空间复杂度】
O(N) or O(1)
【gist link]
https://gist.github.com/chongtianzs/2f8df4b36d9c3889e64d
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

【解题思路】
//write a code to remove duplicates from an unsorted array
//using hashtable, time complexity is O(n), space complexity is O(n)
【时间复杂度】
O（n）
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/34db168892b516034894
【test case】

解题思路：目前只想到一种糟糕的方法，当遍历整个链表时，将剩余链表部分钟与当前元素值相同的节点统统从链表中删除。
时间复杂度：O(n^2)
空间复杂度：O(1)
code snippet & test case: https://gist.github.com/coperd/07ff535221bb887d5a79
补充： 想到另一种思路，先排序，而后遍历一遍删除相同的元素。这样子时间复杂度O(nlgn)+O(n)=O(nlgn), 空间复杂度：采用快排的话O(lgn)

【解题思路】
使用两个指针遍历链表（两层循环），当第二个指针指向的下一个节点值和第一个相同，删除第二个指针指向的下一个节点（因为实现的是双向链表所以其实多添了个指针，一共三个）
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... -2-1-removedup-java

【解题思路】
1.考虑只有大写字母，用一个flag来保存字符是否出现.此时要考虑空白键，当成第27个字符。
2.考虑所有字符，用HashSet()。
3.不用Buffer，用两个指针iterate。
【时间复杂度】
1.O(n)
2.O(n)
3.O(n^2)
【空间复杂度】
1.O(1)
2.O(n)
3.O(1)
[gist link]        Java
https://gist.github.com/LinyinWu/b3a01634d2f7aa3ea8e8
[test case]
"FOLLOW UP"         --->        "FOLW UP"
"FOLLOW  P"         --->        "FOLW P

[解题思路]
1 把list转化成vector方便对每一个元素操作（c++）（暂时没有考虑follow up部分）
2 从最后一个元素开始，和前面的所有元素比较，一旦发现前面有与它相同的，删除它，否则保留
3 再把这个处理好的vector转回原来的list
[时间复杂度]
O（n^2）
[空间复杂度]
O(n)
[gist link] https://gist.github.com/yiyizheliu/32263f3957b43f013fbb
follow up: no temepare buffer available
[解题思路]
直接在list上操作，思路同上
[时间复杂度]
O（n^2）
[空间复杂度]
O(1)
[gist link] https://gist.github.com/yiyizheliu/e672737559ffe5a7bf51