【第三轮】6.23-6.29 CareerCup 2.1

【解题思路】Traverse the linked list from the beginning. Create a runner to remove duplicated list nodes after current node.
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/a63189296107e55d52ec

【解题思路】
1. Use a set. Then go through the list, if the node exists in the set, remove it; otherwise, keep it and put it into the set
2. (no tmp buffer) Compare each node with the others, when encounters a dup one, remove that dup node
【时间复杂度】
1. O(N)
2.O(N^2)
【空间复杂度】
1. O(N)
2.O(1)
【gist link】
https://github.com/FinalF/CarrerUp/blob/master/listDupRemove.java

【解题思路】
参考书上思路，第一种用set，add(item)只添加不重复的
第二种两次遍历linked list
【时间复杂度】
1. O(N)
2.O(N^2)
【空间复杂度】
1. O(N)
2.O(1)
【gist link】解题思路】
1. Use a set. Then go through the list, if the node exists in the set, remove it; otherwise, keep it and put it into the set
2. (no tmp buffer) Compare each node with the others, when encounters a dup one, remove that dup node
【时间复杂度】
1. O(N)
2.O(N^2)
【空间复杂度】
1. O(N)
2.O(1)
【gist link】https://gist.github.com/yokiy/078e7b4865929a15fa2d

【解题思路】
check duplication for each node in the list to avoid buffer
【时间复杂度】
O(N^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/51c7aee25b898ddcf699

1.
【解题思路】hashtable
【时间复杂度】O(N)
【空间复杂度】O(N)
2
【解题思路】two pointer
【时间复杂度】O(N^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/pchong90/ca41bc80780c2d1329ce

【解题思路】
use a hashset to check duplication
follow up: brute force search
【时间复杂度】
O(N)
follow up : O(N^2)
【空间复杂度】
O(N)
follow up : O(1)
【gist link】https://gist.github.com/jyhjuzi/83a9f2ab30415da23c72

【解题思路】
iterate through the linked list and use a bool array to mark whether a character has appeared before. (ASK about the character set!)
FOLLOW UP: brute force, o(N^2)
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/08d9198fb0f9b4bda559
【test case】
null list

============================================================================
Solution        : iterate through the whole, add char to a set
                      if char already existed in set, skip this node
Time Complexity : Average Case: O(1), Worst Case: O(N)
Space Complexity: O(N)
Gist Link       : https://gist.github.com/habina/3896531754d629b2032f
============================================================================

【解题思路】hash set to check duplicate; for follow-up, use two pointers to track
【时间复杂度】hash set O(n), two ptrs O(n^2)
【空间复杂度】hash set O(n), two ptrs O(1)
【gist link】https://gist.github.com/chrislukkk/fc2ce325c06ab6e47c1e

【解题思路】for each node, examine all its previous nodes and check if it's a duplicate.
【复杂度】   // 1. Time: O(n), Space: O(n)
                  // Use unordered_set to record node
【复杂度】   // 2. Time: O(n^2), Space: O(1)
                  // The "Runner" Technique
【gist link】 https://gist.github.com/xun-gong/bebcd35a3874032268e7