art.averin
BAN USERLinear algo on python with some explanations.
class ListNode:
def __init__(self, idx, prev, next):
self.idx = idx
self.prev = prev
self.next = next
map = {}
links = []
idxToRemove = []
def __remove(idx):
idxToRemove.append(idx)
prevNode = links[idx].prev
nextNode = links[idx].next
links[prevNode].next = nextNode
links[nextNode].prev = prevNode
def removeDuplicatedLetters(s):
for i in range(len(s)):
links.append(ListNode(i, i - 1, i + 1))
for idx, c in enumerate(s):
if not c in map.keys():
map[c] = []
map[c].append(idx)
letterList = filter(lambda x: len(map[x]) > 1, map.keys())
letterList.sort()
letterList.reverse()
for c in letterList:
candidates = []
for idx in reversed(map[c]):
if links[idx].next >= len(s) or s[links[idx].next] <= s[idx]:
#good candidate to remove
candidates.append(idx)
if len(candidates) == 0: # have to remove all except first appearance
for i in range(1, len(map[c])):
__remove(map[c][i])
elif len(candidates) == len(map[c]): # have to remove all entries except last
for i in range(len(map[c]) - 1):
__remove(map[c][i])
else: # have to remove all the candidates + all others except last non-candidate
positionToSkip = max(filter(lambda x: x not in candidates, map[c]))
for i in map[c]:
if i != positionToSkip:
__remove(i)
answer = ""
for i in range(len(s)):
if i not in idxToRemove:
answer += s[i]
return answer
There's one thing that should be mentioned.
Your solution is good and fast, but it requires uniqueness of numbers. btw I think that the original formulation of the task has this requirement. So, with this aproach, it's the best and fastest solution.
Atleast you didn't notice that in my words there's "to the left FREE hole" :) So, obviously my solution puts only 1 mouse in 1 hole.
- art.averin October 29, 2014that's not the exact code, just the main idea. If you need the full code, I will write it.
- art.averin October 08, 2014if you are talking about my solution - that's just the main idea.
BTW, the task is similar to
acm.timus. ru/problem.aspx?space=1&num=1296&locale=en
List<Integer> ml = toList(new int[]{4, 6, 11});
List<Integer> hl = toList(new int[]{0, 5, 10, 16});
answer is right, but time is wrong.
List<Integer> ml = toList(new int[]{4, 6, 11});
List<Integer> hl = toList(new int[]{0, 5, 9, 13});
wrong answer and time
Well, it seems to be a binary search problem.
f(t) - discrete function, which says FALSE if it is impossible to move mice to the holes in t minutes, and TRUE if possible.
Obviously, this function is monotone. So we need to find the border between FALSE and TRUE. So binary search for t seems to work fine.
For an exact amount of minutes t it's easy to check whether it is possible or not: just try to put mice to the left free hole(if this path is less then t), else to the right(if less). mice's paths won't intersect(but can overlap).
So, if this solution is right, its complexity is O(NlogP) P - the longest distance between mouse and the hole.
Seems to look like:
1) Find the most-left 0. sum = 1, left = i, max = 1, ansleft = i, ansright = i
2) Go right bit by bit while sum > 0:
a[i] == 0 -> sum++
renew max, ansleft and ansright if needed
a[i] == 1 -> sum--
if sum == 0
find next 0 and start from it.
final answer = number of 1 outside the [ansleft, ansright] + max.
Simple O(N) algo.
Came up with this O(N) solution that uses O(N) memory, but pretty simple.
- art.averin May 04, 2016