# Biweekly Contest 63
# Leetcode 2057
2037. Minimum Number of Moves to Seat Every
class Solution {
public int smallestEqual(int[] nums) {
for(int i = 0; i < nums.length; i++) {
if(nums[i] == i % 10){
return i;
}
}
return -1;
}
}
# Leetcode 2058
2058. Find the Minimum and Maximum Number of Nodes Between Critical Points
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
if head == None:
return [-1, -1]
first = head
second = head.next
nodes = []
index = 1
minRes = 1000000
maxRes = 0
if second == None:
return [-1, -1]
third = second.next
if third == None:
return [-1, -1]
while third != None:
if second.val < first.val and second.val < third.val:
if(len(nodes) >= 1):
minRes = min(minRes, index - nodes[-1])
maxRes = index - nodes[0]
nodes.append(index)
elif second.val > first.val and second.val > third.val:
if(len(nodes) >= 1):
minRes = min(minRes, index - nodes[-1])
maxRes = index - nodes[0]
nodes.append(index)
index += 1
first = first.next
second = second.next
third = third.next
if(len(nodes) < 2):
return [-1, -1]
else:
return [minRes, maxRes]
# Leetcode 2059
2059. Minimum Operations to Convert Number
BFS, break when
class Solution:
def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
visited = set()
queue = []
queue.append((start, 0))
while queue:
num, level = queue.pop(0)
visited.add(num)
for element in nums:
temp1 = num + element
if temp1 == goal:
return level + 1
if temp1 not in visited and temp1 <= 1000 and temp1 >= 0:
visited.add(temp1)
queue.append((temp1, level + 1))
temp2 = num - element
if temp2 == goal:
return level + 1
if temp2 not in visited and temp2 <= 1000 and temp2 >= 0:
visited.add(temp2)
queue.append((temp2, level + 1))
temp3 = num ^ element
if temp3 == goal:
return level + 1
if temp3 not in visited and temp3 <= 1000 and temp3 >= 0:
visited.add(temp3)
queue.append((temp3, level + 1))
return -1
# Leetcode 2060
2060. Check if an Original String Exists Given Two Encoded Strings
Current solution leads to TLE, working on improvement.
class Solution:
def possiblyEquals(self, s1: str, s2: str) -> bool:
def helper1(s):
length = []
i = 0
temp = ''
if ord(s[i]) >= ord('a') and ord(s[i]) <= ord('z'):
flag = True
else:
flag = False
while i < len(s):
if ord(s[i]) >= ord('a') and ord(s[i]) <= ord('z'):
if not flag:
length.append(temp)
temp = ''
flag = True
temp += s[i]
else:
if flag:
length.append(temp)
temp = ''
flag = False
temp += s[i]
i += 1
length.append(temp)
return length
def calLength(s):
res = []
if len(s) == 1:
res.append(int(s))
if len(s) == 2:
res.append(int(s[0]) + int(s[1]))
res.append(int(s))
if len(s) == 3:
res.append(int(s[0]) + int(s[1]) + int(s[2]))
res.append(int(s[:2]) + int(s[2]))
res.append(int(s[0]) + int(s[1:]))
return res
length1 = helper1(s1)
length2 = helper1(s2)
# print(length1)
# print(length2)
s1Candidate = ['']
for element in length1:
if ord(element[0]) >= ord('a') and ord(element[0]) <= ord('z'):
s1Candidate = [temp + element for temp in s1Candidate]
else:
pos = calLength(element)
temp = s1Candidate
s1Candidate = []
for num in pos:
for element in temp:
s1Candidate.append(element + '_' * num)
# print(s1Candidate)
s2Candidate = ['']
for element in length2:
if ord(element[0]) >= ord('a') and ord(element[0]) <= ord('z'):
s2Candidate = [temp + element for temp in s2Candidate]
else:
pos = calLength(element)
temp = s2Candidate
s2Candidate = []
for num in pos:
for element in temp:
s2Candidate.append(element + '_' * num)
# print(s2Candidate)
dic1 = {}
dic2 = {}
for element in s1Candidate:
if len(element) not in dic1.keys():
dic1[len(element)] = [element]
else:
dic1[len(element)].append(element)
for element in s2Candidate:
if len(element) not in dic1.keys():
continue
possiable = dic1[len(element)]
for temp in possiable:
# print(element, temp)
flag = True
for i in range(len(temp)):
if temp[i] == '_' or element[i] == '_':
continue
if temp[i] != element[i]:
flag = False
if flag:
return True
return False