23.05.22 Today’s Leetcode

347. Top K Frequent Elements (medium)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = Counter(nums)
        d = defaultdict(set)
        for p in counter.keys():
            d[counter[p]].add(p)

        res = []
        order = sorted(list(d.keys()), reverse=True)
        # print(order)
        for key in order:
            res += list(d[key])
        
        return res[:k]

334. Increasing Triplet Subsequence

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first = second = float('inf') 
        for n in nums: 
            if n <= first: 
                first = n
            elif n <= second:
                second = n
            else:
                return True
        return False

335. Self Crossing (hard)

class Boundary:
    def __init__(self, fixed, bound, type_):
        self.type_ = type_
        self.fixed = fixed
        self.bound = sorted(bound)

    def isInside(self, pos):
        if type_:
            return pos[1] == self.fixed and pos[0] >= self.bound[0] and pos[0] <= self.bound[1]
        else:
            return pos[0] == self.fixed and pos[1] >= self.bound[0] and pos[1] <= self.bound[1]

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        p = []
        cur = [0, 0]
        dirs = [1, 0, -1, 0, 1]
        for i, v in enumerate(distance):
            prev = cur[:]
            cur[0] += dirs[i % 4] * v
            cur[1] += dirs[(i + 1) % 4] * v
            b = None
            if dirs[i % 4] == 0:
                b = Boundary(cur[0], [prev[1], cur[1]), False)
            else:
                b = Boundary(cur[1], [prev[0], cur[0]), True)
            p.append(b)

케이스를 나눠서 생각해보자.

class Solution:
  def isSelfCrossing(self, x: List[int]) -> bool:
    # If there are less than 4 values in the array, the path can't cross itself
    if len(x) <= 3:
      return False

    # Loop through the array starting from the 3rd index
    for i in range(3, len(x)):
      # Case 1: current line crosses the line 3 steps before it
      #           _______
      #         |      |
      #         |      |
      # ________|______| <-- current line
      #         |          |
      #         |          |
      #         |__________| <-- line 3 steps before
      if x[i - 2] <= x[i] and x[i - 1] <= x[i - 3]:
        return True
      
      # Case 2: current line crosses the line 4 steps before it
      #         _____
      #        |      |
      #        |      |
      #        |      |________
      #        |               |
      #        |               |
      #        |_______________| <-- current line
      #              line 4 steps before
      if i >= 4 and x[i - 1] == x[i - 3] and x[i - 2] <= x[i] + x[i - 4]:
        return True
      
      # Case 3: current line crosses the line 5 steps before it
      #         ______
      #        |      |
      #        |      |
      #        |______| <-- line 5 steps before
      #               |
      #               |
      #         ______|_______
      #        |              |
      #        |              |
      #        |______________| <-- current line
      if i >= 5 and x[i - 4] <= x[i - 2] and x[i - 2] <= x[i] + x[i - 4] and x[i - 1] <= x[i - 3] and x[i - 3] <= x[i - 1] + x[i - 5]:
        return True

    # If no crossing has been found, the path does not cross itself
    return False

##

class Solution:

    def isPalindrome(self, s):
        return s == s[::-1]

    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        res = []
        n = len(words)
        for i in range(n):
            for j in range(n):
                if i == j: continue
                if self.isPalindrome(words[i] + words[j]):
                    res.append([i, j])

        return res 

with Pruning: TLE at 134/136

class Solution:

    def isPalindrome(self, s):
        return s == s[::-1]

    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        res = []
        n = len(words)
        for i in range(n):
            for j in range(n):
                if i == j: continue
                if words[i] and words[j] and words[i][0] != words[j][-1]: continue
                if self.isPalindrome(words[i] + words[j]):
                    res.append([i, j])

        return res 

class Solution:

    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        backward, res = {}, []
        for i, word in enumerate(words):
           backward[word[::-1]] = i
                
        for i, word in enumerate(words):
        
            if word in backward and backward[word] != i:
                res.append([i, backward[word]])
                
            if word != "" and "" in backward and word == word[::-1]:
                res.append([i, backward[""]])
                res.append([backward[""], i])
                
            for j in range(len(word)):
                if word[j:] in backward and word[:j] == word[j-1::-1]:
                    res.append([backward[word[j:]], i])
                if word[:j] in backward and word[j:] == word[:j-1:-1]:
                    res.append([i, backward[word[:j]]])

        return res