33
loading...
Day 1: My Leetcode Adventure[2]
How many problems have I solved? Uno
Leetcode 1920: Build Array from Permutation
Leetcode 1920: Build Array from Permutation
*Return same-length zero-based permutation nums array[array of distinct integers from 0 to nums.length-1] in which ans[i] = nums[nums[i]] where 0<=i< nums.length. *
My Answer
This is the first problem I had for the Weekly Contest 248. On top of that, it has been a while since I visited this website. I am starting the grind to secure a job after graduation.
This is the first problem I had for the Weekly Contest 248. On top of that, it has been a while since I visited this website. I am starting the grind to secure a job after graduation.
newArr=[]
for i in range(len(nums)):
# Calculate the new val
temp=nums[nums[i]]
newArr.append(temp)
return newArrBetter Solution
return [nums[nums[i]] for i in range(len(nums))]Even BetterSolution
return [nums[i] for i in nums]What I learned?
newArr=[]
for i in range(len(nums)):
# Calculate the new val
temp=nums[nums[i]]
newArr.append(temp)
return newArr
Do...
return [nums[i] for i in nums]Leetcode 1921: Build Array from Permutation
*Given monsters arr and speed arr where monster i travels at speed j. You are allowed to kill any monsters starting from minute 0. Keep in mind that monsters are not allowed to be killed in the middle of a minute and only one monster can be killed at the start of the minute. If monster reaches city == start of the minute, you still lose. Return the max numbers of monsters you can kill before the monster reach your city. *
*Given monsters arr and speed arr where monster i travels at speed j. You are allowed to kill any monsters starting from minute 0. Keep in mind that monsters are not allowed to be killed in the middle of a minute and only one monster can be killed at the start of the minute. If monster reaches city == start of the minute, you still lose. Return the max numbers of monsters you can kill before the monster reach your city. *
Answer
I had trouble with this question because I was not able to solve it completely with 3 attempts. Every attempt got me closer to the answer.
I had trouble with this question because I was not able to solve it completely with 3 attempts. Every attempt got me closer to the answer.
Attempt 1
killed=0
while dist or sum(1 for d in dist if d<0)>0:
killed +=1
#Remove 1st monster
dist.pop(0)
speed.pop(0)
# Subtract dist and speed
for i in range(len(dist)):
dist[i]-=speed[i]
return killedMy first approach was to kill the first monster, but it is flawed because the other monsters could be faster. In addition, the second condition[sum(1 for d in dist if d<0)>0] doesn't make sense. It should stop iterating if monster reached the city.
Attempt 2
Attempt 2
killed=0
# print(sum(1 for d in dist if d<=0))
while dist and sum(1 for d in dist if d<=0)==0:
print(dist)
print(speed)
# print("Killing...")
for i in range(len(dist)):
dist[i]-=speed[i]
print(dist)
# Remove a monster
delMon=[ind for ind,elem in enumerate(dist) if elem <=0]
delMonInd= delMon[0] if delMon else dist.index(min(dist))
print("Killed #", killed,", Index:",delMonInd, ", Value:",dist[delMonInd] )
dist.pop(delMonInd)
speed.pop(delMonInd)
killed +=1
return killed2nd approach was to dist-speed and then find all monster that have entered the city and remove 1st occurence. The problem is for the else condition where some monster can advance to the city faster so I can't just remove the monster with the shortest distance.
Attempt 3
Attempt 3
killed=0
while dist and sum(1 for d in dist if d<=0)==0:
for i in range(len(dist)):
dist[i]-=speed[i]
# Remove a monster
delMon=[ind for ind,elem in enumerate(dist) if elem <=0]
special=[]
for i in range(len(dist)):
special.append(int(dist[i]/speed[i]))
# delMonInd= delMon[0] if delMon else self.turnsLeft(dist,speed)
delMonInd= delMon[0] if delMon else special.index(min(special))
dist.pop(delMonInd)
speed.pop(delMonInd)
killed +=1
# print("Killed #", killed,", Index:",delMonInd )
return killed3rd approach was to take current result and perform division between distance and speed. This helps resolve the closest monster problem and this is the right approach. However, time exceeded for this approach.
Better Solution
Better Solution
arr=[]
#Store the minute time for each monster
for i in range(len(dist)):
minute=math.ceil(dist[i]/speed[i] )
arr.append(minute)
arr.sort()
killed=0
#Count number of monster killed
for m in range(len(arr)):
if(arr[m]<=m):
return killed
killed+=1
return killedThis sorting approach is O(nlogn) which is simple and fast. First, it converts to comparable units. Then it sorts to decide which monster to remove during minute m. Remove monsters until monster has reached the city. *
**What I learned?*
**What I learned?*
33