Li Kou daily question 1 (2)

Persimmons should always be picked up and pinched soft , The daily question must also be written from the simplest . Probably just because it started , Just don't want to give up . Simple though , Stick to it, too , Is it just an effort to show yourself ？ Perhaps my so-called insistence is also quite ridiculous .

It's just , How happy how to come .

One 、5.28 Remove the outermost bracket

The main idea of the topic ： A set of strings , It consists of several characters , It contains several sets of parentheses , The requirement of this question is to delete the outermost parentheses of each group in the string , Output the remaining string .

analysis ： It matches the parentheses almost , You need to use a stack to save parentheses , You also need another string to hold the output .

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        stack = []
        res = ''
        for i in s:
            #  First judge whether there is a right bracket , If you have any , Then output its left bracket 
            if i == ')':
                stack.pop()
            #  If the stack is not empty , It means that it is not the outermost character , Is added to the result string 
            if stack:
                res += i
            #  If left parenthesis , Add to the stack 
            if i == '(':
                stack.append(i)
        return res

Two 、5.25 The unique substring in the surround string

The main idea of the topic ： Given a set of strings p, Judgment string p in a-z-a-z The number of non empty substrings in the circular string , namely p The substring of is in the circular string . Involving dynamic programming , Nor is it simply seeking the longest substring , Because we just find the number of non empty substrings .

I still don't understand dynamic planning , We can't draw inferences from one instance , Just remember that this problem is solved like this , My understanding ability is not good , Have a chance , Have a chance to have a good look , It is important to understand the process of Dynamic Planning . And sliding windows .

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        dp = defaultdict(int)
        # k Used to record the number of consecutive characters 
        k = 0
        for i, ch in enumerate(p):
            #  The difference between characters is  1  or  -25
            if i > 0 and (ord(ch) - ord(p[i - 1])) % 26 == 1:  
                k += 1
            else:
                k = 1
            # dp Is used to record the longest substring ending with the current character 
            dp[ch] = max(dp[ch], k)
        #  That's going to be dp All values in add up , It's just a string p Number of all substrings in 
        return sum(dp.values())

3、 ... and 、5.24 Single valued binary trees

The main idea of the topic ： Determine whether all values of the binary tree are the same , If the same , return True, otherwise False.

analysis ： Breadth first search BFS, Depth-first search DFS Fine , Just traverse the binary tree once .

Breadth first search ： You need to complete the search with the help of queues .

There is no need to determine which layer to traverse ：

# 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:
    def isUnivalTree(self, root: TreeNode) -> bool:
        q = deque()
        q.append(root)
        val = root.val
        while q:
            cur = q.popleft()
            if not cur:
                continue
            if val != cur.val:
                return False;
            #  Traverse the nodes of the current layer 
            q.append(cur.left)
            q.append(cur.right)
        return True

Depth-first search ： There are three kinds of , The first sequence traversal 、 In the sequence traversal 、 After the sequence traversal , Let's take preorder traversal as an example

class Solution:
    def isUnivalTree(self, root: TreeNode) -> bool:
        return self.dfs(root, root.val)

    def dfs(self, root, val):
        if not root:
            return True
        if val != root.val:
            return False
        return self.dfs(root.left, val) and self.dfs(root.right, val)

Four 、 In the length of 2N To find out the repetition N Secondary elements

The main idea of the topic ： Given an array , The length is 2N, Among them is N+1 Elements , And just one element repeats N Time , Ask for repetition N The next element .

analysis ： There's a repetition of an element N Time , And there are N+1 Elements , The length is 2N, Then other elements only appear once . Traverse one side of the array to count and find . Or use hash table （ It is a set of key value structures ）, Count .

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        # # Traversal count 
        # n = len(nums)/2
        # flag = [0 for i in range(0, max(nums)+1)]
        # for j in nums:
        #     flag[j] += 1
        #     if flag[j] == n:
        #         return j
        
        #  Hash 
        found = set()
        for i in nums:
            if i in found:
                return i
            found.add(i)