akak18183
BAN USER- 0of 0 votes
AnswersGiven integer m and n where n is odd, for all mxn matrixes that consist of 0 and 1, find the one that has max count of 1s and meets following conditions:
- akak18183 in United States
1. All 0s are connected;
2. All 1s are adjacent to at least one 0 (Adjacent includes diagonal line adjacent, 8 directions);
3. maxtrix[m-1][n/2] = 0.
Example :
Input: m=2, n=3
Output: [[1,1,1],[1,0,1]]
Follow up:
Given another list of 'blocked' points. Matrix will set those points to -1 and you cannot change that. Solve the problem again.| Report Duplicate | Flag | PURGE
unknown Software Engineer Algorithm
T:O(s+k), S:O(s)
class Interval:
def __init__(self, start, end):
self.start, self.end = start, end
class Solution(object):
def sol(self, shards, keys):
if not shards or not keys:
return []
i, j, ret = 0, 0, [None] * len(shards)
while i < len(shards) and j < len(keys):
sh = shards[i]
while j < len(keys):
k = keys[j]
if self.intersect(sh, k):
if not ret[i]:
ret[i] = Interval(max(sh.start, k.start), min(sh.end, k.end))
else:
ret[i].start = max(min(ret[i].start, k.start), sh.start)
ret[i].end = min(max(ret[i].end, k.end), sh.end)
if k.end > sh.end:
i += 1
break
else:
j += 1
else:
if k.end <= sh.start:
j += 1
else:
i += 1
break
return [x for x in ret if x]
def intersect(self, sh, k):
return (k.end <= sh.end and k.end > sh.start) or \
(k.end >= sh.end and k.start < sh.end)
if __name__ == "__main__":
sh1 = Interval(1, 9)
sh2 = Interval(12, 59)
sh3 = Interval(100, 999)
k1 = Interval(2,3)
k2 = Interval(6,8)
k3 = Interval(11,20)
k4 = Interval(200,220)
for i in Solution().sol([sh1,sh2,sh3],[k1,k2,k3,k4]):
print([i.start, i.end])
for i in Solution().sol([sh1,sh2,sh3],[Interval(1,1000)]):
print([i.start, i.end])
for i in Solution().sol([sh1,sh2,sh3],[Interval(4,16), Interval(59,100)]):
print([i.start, i.end])
Similar with catsnow9's idea.
def removeDuplicatedLetters(s):
# First scan
dict, ret = {}, []
for i in xrange(len(s)):
if s[i] not in ret:
ret.append(s[i])
dict[s[i]] = i
else:
ret.remove(s[i])
ret.append(s[i])
dict[s[i]] = i
ind = dict.values()
# Second scan
for i in xrange(len(s)):
if s.index(s[i]) in ind:
continue
temp = dict[s[i]]
dict[s[i]] = i
lst = sorted(dict.keys(),key = lambda d:dict[d])
if ''.join(lst) < ''.join(ret):
ret = lst
else:
dict[s[i]] = temp
return ''.join(ret)
if __name__ == "__main__":
l1 = 'cbacdcbc'
l2 = 'bcabc'
print removeDuplicatedLetters(l1) # acdb
print removeDuplicatedLetters(l2) # abc
# -*- coding: utf-8 -*-
__author__ = 'YUAN'
def solution(lst):
if len(lst) < 4: return 'not crossed'
for i in xrange(3, len(lst)):
if i == 3:
if lst[2] <= lst[0] and lst[3] >= lst[1]:
return 'corssed'
elif i == 4:
if (lst[3] == lst[1] and lst[4] + lst[0] >= lst[2]) or (lst[3] < lst[1] and lst[4] >= lst[2]):
return 'corssed'
elif i > 4:
# outer spiral
if lst[i-2]>=lst[i-4] and lst[i-3]>=lst[i-5]:
if lst[i-3] - lst[i-5] <= lst[i-1] <= lst[i-3] and lst[i]>=lst[i-2]-lst[i-4]:
return 'crossed'
elif lst[i-1]<lst[i-3]-lst[i-5] and lst[i]>=lst[i-2]:
return 'crossed'
# inner spiral
elif lst[i-1]<=lst[i-3] and lst[i-2]<=lst[i-4] and lst[i]>=lst[i-2]:
return 'corssed'
return 'not corssed'
if __name__ == "__main__":
print solution([ 1, 2, 2, 5, 3, 3, 2]) # crossed
print solution([1,1,2,2,3,3,4,4,10,4,4,3,3,2,2,1,1]) # not crossed
print solution([1, 1, 2, 5, 3, 3, 2]) # not crossed
- akak18183 September 23, 2016