| For the median question, I did not allow myself to combine the array. My idea was to increment in each array based on which value would come next in a sequence (as if they were on array), stop when I've incremented n times where n = length of both arrays / 2 (the median position) and then return. Here's the code: class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
""" length = len(nums1) + len(nums2)
medianIndex = length // 2
ptr1 = 0
ptr2 = 0
curr = 0
flag = 0
if nums1[ptr1] < nums2[ptr2]:
val = nums1[ptr1]
else:
val = nums2[ptr2]
while curr < medianIndex:
if nums1[ptr1] == val:
if nums2[ptr2] < val:
curr += 1
ptr1 +=1
val = nums1[ptr1]
flag = 0
else:
if ptr1+1 < len(nums1) and abs(nums1[ptr1+1]) - abs(val) < abs(nums2[ptr2]) - abs(val):
curr+=1
ptr1+=1
val = nums1[ptr1]
flag = 0
else:
curr+=1
val = nums2[ptr2]
flag = 1
else:
if nums1[ptr1] < val:
curr += 1
ptr2 +=1
val = nums2[ptr2]
flag = 1
else:
if ptr2+1 < len(nums2) and abs(nums2[ptr2+1]) - abs(val) < abs(nums1[ptr1]) - abs(val):
curr+=1
ptr2+=1
val = nums2[ptr2]
flag = 1
else:
curr+=1
val = nums1[ptr1]
flag = 0
if flag == 1:
med = nums2[ptr2]
else:
med = nums1[ptr2]
if length % 2 == 0:
if med - nums1[ptr1 + 1] < med - nums2[ptr2 +1]:
return (med + nums1[ptr1+1])/2
else:
return (med + nums2[ptr2+1])/2
else:
return med
Here's what I wrote for your sum the cubes. Took me 1 minute. I hope I didn't misunderstand the question.def sumCubes(n):
sumC = 0
for i in range(n+1):
sumC += i 3
return sumC I'll give you 2 more leetcode examples. Neither passed all test cases. The first is 2-3 hours. The latter 3. I didn't post the last submission for the latter one because I believe the one I posted is more telling of my thought process and coding ability imo so that solution is between 1 and 2 hours of work, but I wasn't able to get it in the end. I honestly don't recall my idea here. I think it was to see if the start and end of the array had the same letter and if it didn't cut off the first and last letter and continue analyzing the array until the center is reached. https://leetcode.com/problems/longest-palindromic-substring/... class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
curr = ""
big = "" for c in s:
curr += c
if curr != curr[::-1]:
if len(curr[:len(curr)-1]) >= len(big):
big = curr[:len(curr)-1]
print(big)
while curr != curr[::-1]:
curr = curr[1:]
if len(curr) > len(big):
return curr
else:
return big
I thought there were 3 cases in this problem. You hit a character, you hit a ? or you hit . The first one meant an exact match had to be made. The second that there only had to be some character in the string to take a position (the string couldn't end if there was a ?). The last could mean 0 to n matches so there had to be a lot of checks in my mind. I also thought about what happens if there's "?" which I wrote as a case inside the "" if case. When test cases didn't work I would try and code for that test case and it kept going wrong so I eventually gave up and looked at the solution. My main flaw is that it didn't occur to me that backtracking was the way to go or a way to check all the potential combinations. I thought you just had to keep moving forward.https://leetcode.com/problems/wildcard-matching/description/ class Solution:
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if len(p) == 0 and len(s) == 0:
return True
if len(p) == 0:
return False i = 0
j = 0
while i < len(s):
if j >= len(p) and p[len(p) - 1] != '*':
return False
if p[j] == '*':
while j < len(p) and p[j] == '*':
j+=1
if j == len(p):
break
elif p[j] == '?':
x = len(p)- j
while len(s) - i > x:
i+=1
while j < len(p) and p[j] == '?':
i+=1
j+=1
if i > len(s) or j >= len(p) and i < len(s):
print(i)
return False
if i == len(s) and j == len(p):
break
else:
while i < len(s) and p[j] != s[i]:
i+=1
if i == len(s):
return False
elif p[j] == '?':
i+=1
j+=1
else:
if p[j] != s[i]:
print(i, s[i])
print(j, p[j])
return False
i+=1
j+=1
if j < len(p):
while j < len(p) and p[j] =='*':
j+=1
if j == len(p) and p[j-1] == '*':
return True
else:
return False
return True
|
This kind of problems are designed to test you can define a grammar and apply recursion. Another problem with the same flavor could be to evaluate string expressions like "3+25" using a grammar. My one-hour solution (not checked). But I think I have done similar problems.