if you think of
res = -1 * res
then yes it is using multiply,
but you can also think of it as
res = 0 - res
then it is just subtraction :-)
Good question though, I didn't really think much of that inconspicuous line until I saw your post.
if you think of
res = -1 * res
then yes it is using multiply,
but you can also think of it as
res = 0 - res
then it is just subtraction :-)
Good question though, I didn't really think much of that inconspicuous line until I saw your post.
Hope all my comments make sense, please let me know if there's anything unclear.
class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
# takes care of edge case when t is longer than s
if len(t) > len(s):
return ""
# initialize dictionary to store letters needed and counted as [#needed, #counted]
needcount = {}
# initialize the variable to keep track of number of letters still needed
needNum = 0
for letter in t:
# sets default to [0,0] if letter not already in dictionary
needcount[letter] = needcount.get(letter,[0,0])
# needed letter goes in slot 0 from 't', count will go in slot 1 later when looping through 's'
needcount[letter][0] += 1
needNum += 1
# initialize indices and counters
left, right = 0, 0
length = len(s)
minlen = length+1
# stop condition is when right exceeds the length and when needNum is 0
while right < length or not needNum:
# while there is needNum indicating missing letters, increase right
if needNum:
letter = s[right]
right += 1
if letter in t:
# calculate how many of this particular letter are missing by need-count
if needcount[letter][0]-needcount[letter][1] > 0:
# if any missing, subtract 1 from needNum because we just adding 1 of this letter
needNum -= 1
# increment the letter count by 1 since we just added this letter
needcount[letter][1] += 1
# while there is no needNum when all letters are fulfilled and left < right, increase left
elif not needNum and left < right:
letter = s[left]
left += 1
if letter in t:
# calculate how many of this particular letter are missing by need-count
if needcount[letter][0]-needcount[letter][1] >= 0:
# if there any are missing or need is same as count, then add 1 to needNum
# because 1 was just gotten rid of when left moved up by one
needNum += 1
# update count accordingly
needcount[letter][1] -= 1
# after each move of left or right, check if the new window is smaller than minlen
if not needNum:
if right-left < minlen:
# if right-left is smaller then update minlen and the start, end indices
minlen = right-left
start, end = left, right
# return the string starting and ending at the specified indices if minlen has been modified
return s[start:end] if minlen < len(s)+1 else ""
# O(n) 145 ms
When k >= len(prices)//2 this problem reduces to the problem type II, so using that solution for that special case.
The thinking behind this code is to generalize the k = 2 case from the problem type III to k > 2.
The sequence of events, can be thought of in chronological order, the stock is traded as the following:
buy1, sell1, buy2, sell2, buy3, sell3...
when buying, we spend money, when selling, we earn the profit, so profits are defined as
profit1 = -buy1 + sell1 (usually we write profit = sell_price - buy_price, but to illustrate the sequence I write buy first)
profit2 = -buy2 + sell2
profit3 = -buy3 + sell3
...
total money after buy1 = -buy1
total money after sell1 = -buy1 + sell1 = profit1
total money after buy2 = -buy2 + profit1
total money after sell2 = -buy2 + sell2 + profit1 = profit2 + profit1
total money after buy3 = -buy3 + profit2 + profit1
total money after sell3 = -buy3 + sell3 + profit2 + profit1 = profit3 + profit2 + profit1
...
The lowest price as we traverse through prices list will be assigned transaction 1 so the first one is unique:
if i == 0:
buy[0] = min(buy[0], p)
sell[i] = max(sell[i], p - buy[i])
But the rest of the transactions all follow the same pattern for k > 0, after the buy or sell, to maximize the total money currently with:
else:
buy[i] = max(buy[i], sell[i - 1] - p)
sell[i] = max(sell[i], p + buy[i])
So, in the end, the loop with elements with k > 0 will all behave similarly, and we just need to return the money after the last sell. Here buy and sell indicate the total money after the buy or sell i-th transaction, and p is the buy or sell price. Hope this all makes perfect sense to everyone.
Another leetcoder found a more elegant solution without using the special case of the first transaction reversing k:
https://discuss.leetcode.com/topic/23888/concise-python-solution-with-detailed-explanation-o-kn-time-o-k-space
but just thought I share my solution since it made more sense in my head.
Complete code:
class Solution(object):
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
if not prices or not k:
return 0
if k >= len(prices) // 2:
profit = 0
for i in range(len(prices) - 1):
nextP, currP = prices[i + 1], prices[i]
if nextP > currP:
profit += max(nextP - currP, 0)
return profit
buy = [-float('inf')] * k
buy[0] = prices[0]
sell = [0] * k
for p in prices:
for i in range(k):
if i == 0:
buy[0] = min(buy[0], p)
sell[i] = max(sell[i], p - buy[i])
else:
buy[i] = max(buy[i], sell[i - 1] - p)
sell[i] = max(sell[i], p + buy[i])
return sell[k - 1]
@tejas7 said in Easy Python Solution 68 ms beats 100%:
try: float(s)
except ValueError: return False
else: return True
This works too :-)
I think this problem is one of the hardest on leetcode if not done in python, but simple in python.
try: float(s)
except ValueError: return False
return True
@o_sharp said in 2 Python implementations using dictionary and list (Syned and Asyned), with explanation:
if val in self.d: return False self.d[val] = len(self.l) self.l.append(val) return True
Why does the time shoot way up if I do:
"if val in self.l" instead of "if val in self.d",
Basically, why is checking if something is in a dictionary way faster than if something is in a list for python?
class Solution(object):
def moveZeroes(self, nums):
for i in range(len(nums))[::-1]:
if nums[i] == 0:
nums.append(nums.pop(i))
If we iterate from the front and pop, the rest of the array will shift place and you will skip an element.
If pop from the back then that is avoided by using [::-1] of range.
popping from the middle of the list is more expensive because it has to shift all the elements behind, but from the test cases this is pretty fast (probably because the tests are really short). This is not as efficient as the two pointer solution (https://github.com/kamyu104/LeetCode/blob/master/Python/move-zeroes.py), but very very easy to understand.
something must be wrong with the server.
Before, the leetcode.com page would not load, once the page came back it was incredibly slow, and some features like looking at submitted details are now not working.