Leetcode LC-Contest

Weekly Contest 265

Leetcode 2057, 2058, 2059, 2060

Sailorlqh
2021-10-30
5 min

# 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 0num10000 \leq num \leq 1000

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