[leetcode 추석맞이 3문제] minimum-absolute-, differencerepeated-dna-sequences, pseudo-palindromic-paths-in-a-binary-tree

 

Minimum Absolute Difference (Dictionary 이용)

 

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

• a, b are from arr
• a < b
• b - a equals to the minimum absolute difference of any two elements in arr

---

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        #정렬을 해놓고
        #두 수의 간격이 가장 작은거 = minimum absolute difference
        arr = sorted(arr)
        minNum = 10000000 #arr[i]가 10^6까지랬으니까
        dic = {} #작은 값들 저장할 dic
        
        for idx in range(len(arr)-1):
            tmp = abs(arr[idx]-arr[idx+1])
            if tmp <= minNum:
                minNum = tmp
                if tmp not in dic:
                    print(tmp)
                    dic[tmp] =[]
                dic[tmp].append([arr[idx],arr[idx+1]])

                               
        return dic[minNum]

 

---

Repeated DNA Sequences (슬라이딩 윈도우 이용)

 

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

---

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        start, end = 0, 10
        candidate = {}
        while end <= len(s):
            seq = s[start:end]
            if seq in candidate:
                candidate[seq] +=1
            else:
                candidate[seq] = 1
            start +=1
            end +=1
        
        return [k for k,v in candidate.items() if v >=2]
            

---

Pseudo-Palindromic Paths in a Binary Tree(set이용)

 

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

---

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    cnt = 0
    def find(self, root:TreeNode, route:List) -> bool:
        #마지막 노드일때 지금까지 담은 경로를 확인한다. 이때 모든 요소가 짝수가 아니면 빈 배열을 return
        route = route^{root.val} #★☆○☆★ 가운데 하나빼고 다 짝수여야함 또는 그냥 다 짝수
        
        if root.left:
            self.find(root.left, route)
        if root.right:
            self.find(root.right, route)
        if not root.left and not root.right and len(route) <2 : #마지막이니 count
            self.cnt+=1
            
    def pseudoPalindromicPaths (self, root: TreeNode) -> int:
        #find 함수돌려서 배열이 비어있지 않으면 counting
        self.find(root, set())
        return self.cnt