@Vivek said in There is no maximum of INT in python, so.....:
This problem demands us
No, it does not. There is nothing in the problem specification that says that.
@Vivek said in There is no maximum of INT in python, so.....:
This problem demands us
No, it does not. There is nothing in the problem specification that says that.
Input:
head: [1]
k = 2
This should never happen based on this line in the problem description:
k is a positive integer and is less than or equal to the length of the linked list.
class Solution(object):
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
best = num
n = len(str(num))
j, second = 0, num%10
for i in range(1, n):
first = (num%10**(i+1))/10**i
new = num-first*10**i-second*10**j+first*10**j+second*10**i
best = max(best, new)
if first > second:
j, second = i, first
return best
class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
if maxChoosableInteger**2+maxChoosableInteger < desiredTotal*2:
return False
return self.helper(maxChoosableInteger, desiredTotal, 0, {})
def helper(self, max, total, used, cached):
if used not in cached:
cached[used] = False
for num in range(1, max+1):
if used & 1 << num:
continue
if num >= total or not self.helper(max, total-num, used | 1 << num, cached):
cached[used] = True
break
return cached[used]
The dictionary key is the stone and the value is a set that contains the units for each jump that can land on that particular stone.
class Solution(object):
def canCross(self, stones):
"""
:type stones: List[int]
:rtype: bool
"""
landings = collections.defaultdict(set)
landings[1].add(1)
for i in range(1, len(stones)-1):
stone = stones[i]
if stone not in landings:
continue
for k in landings[stone]:
for new_k in k-1, k, k+1:
if not new_k:
continue
landings[stone+new_k].add(new_k)
return stones[-1] in landings
@kq2 this is an elegant, awesome, and truly underrated solution!
Python:
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
pal = [[False for _ in range(len(s))] for _ in range(len(s))]
cuts = [len(s)-i-1 for i in range(len(s))]
for start in range(len(s)-1,-1,-1):
for end in range(start, len(s)):
if s[start] == s[end] and (end-start < 2 or pal[start+1][end-1]):
pal[start][end] = True
if end == len(s)-1:
cuts[start] = 0
else:
cuts[start] = min(cuts[start], 1+cuts[end+1])
return cuts[0]
@awice Thanks! I rattled my brain a little bit before I noticed those issues, but your explanation helped a lot!
@awice said in Python, Straightforward with Explanation:
This partial schedule would have length L = (M-1) * (N-1) + Mct.
Shouldn't this be L = (M - 1) * (N
+1) + Mct
?
After we have inserted all tasks of frequency Mct - 1 (which clearly will not collide), other tasks of frequency lower than Mct - 1 will never have any task written collide with it's left-neighbor (because of the writing order)
Don't you mean M - 1
, not Mct - 1
?
@FutureVolador that would return False during the loop for pos = 3