nil12285
BAN USERI think there is much easy solution
find the frequency of the element
and then based on the frequency you can find the longest possible palindrome with given string
def get_longest_palindrom_length(s):
if not s:
return 0
sd = {}
for i in s:
if i not in sd:
sd[i] = 1
else:
sd[i] += 1
pl = 1
for i, c in sd.items():
if c > 1:
pl += (c // 2)
return pl
space : o(n)
time : sort => O(n)
Observation:
As there are only 3 elements of series it's hard to assume anything. But if the assumption of deducting even factorial from the previous odd factorial.
here is the solution with O(1) space and O(n) time
def fancyFactorial(n):
n1fact = 1
result = 1
if n <= 1:
return n1fact
i = 2
while i <= n:
n1fact = n1fact * i
if i % 2 == 0:
result = result - n1fact
else:
result = result + n1fact
i += 1
return result
lol, I like 2 answers from above, array.sort() and LMFAO
array.sort() can have O(n log n) time
But if we just find min and max of the list it can be found in O (n)
remove them from the list and insert them at first and the last position respectively
def doWhatever(arglist):
min = (0, arglist[0])
max = (0, arglist[0])
for i in range(1,len(arglist)):
if arglist[i] < min[1]:
min = (i, arglist[i])
if arglist[i] > max[1]:
max = (i, arglist[i])
del arglist[min[0]]
del arglist[max[0]]
arglist.insert(0, min[1])
arglist.append(max[1])
return arglist
Node class
class Node(object):
def __init__(self, x):
self.val = x
self.next = None
#self.prev = None
def __str__(self, *args, **kwargs):
return str(self.val)
LinkedList class
class LinkedList(object):
def __init__(self, argList):
self.size = 1
self.head = Node(argList[0])
if argList[1:]:
self.setTail(argList[1:])
def setHead(self, headNode):
self.head = headNode
def setTail(self, argList):
currentNode = self.head
for i in argList:
currentNode.next = Node(i)
currentNode = currentNode.next
self.size += 1
def getNthNode(self, n):
c = self.head
for i in range(n-1):
if c:
c = c.next
else:
c = None
return c
def size(self):
return self.size
Solution
# this will return linklist for given list
ll = LinkedList([1,2,3,4,5,6])
i = 1
cnode = ll.head
while i <= ll.size//2 and cnode.next:
t2 = ll.getNthNode(ll.size - i)
t3 = ll.getNthNode(ll.size - i + 1)
t2.next = t3.next
t3.next = cnode.next
cnode.next = t3
cnode = cnode.next.next
i += 1
- nil12285 September 21, 2016