力扣每日一题（二）

柿子总要捡软的捏，每日一题肯定也要从最简单的写起。大概只是因为开始了，就不想放弃罢了。虽然简单，也在坚持吧，是只给自己看的努力吗？或许自己所谓的坚持也蛮可笑的吧。

罢了罢了，怎么开心怎么来吧。

一、5.28删除最外层的括号

题目大意：一组字符串，由若干字符组成，其中包含若干组括号，而本题的要求就是将字符串中每组的最外围括号删除，输出剩下的字符串。

解析：跟括号匹配差不多，需要采用栈来保存括号，也需要另一个字符串来保存要输出的结果。

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        stack = []
        res = ''
        for i in s:
            # 先判断是否有右括号，若有，则将其左括号输出
            if i == ')':
                stack.pop()
            # 若栈不为空，则说明不是最外层字符，则添加到结果字符串中
            if stack:
                res += i
            # 若为左括号，则添加到栈中
            if i == '(':
                stack.append(i)
        return res

二、5.25环绕字符串中唯一的子字符串

题目大意：给定一组字符串p，判断字符串p中a-z-a-z循环字符串中非空子串的数量，即p的子串是在循环字符串中的。涉及到动态规划的，也不是单一的求最长子串，因为只是求非空子串的数量。

对于动态规划还是不那么理解的，不能举一反三，只是记着这个题是这样的解法，我的理解能力不行，有机会吧，有机会好好看看吧，理解动态规划的过程还是很重要的。还有滑动窗口。

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        dp = defaultdict(int)
        # k用于记录连续字符的数量
        k = 0
        for i, ch in enumerate(p):
            # 字符之差为 1 或 -25
            if i > 0 and (ord(ch) - ord(p[i - 1])) % 26 == 1:  
                k += 1
            else:
                k = 1
            # dp是用于记录以当前字符的结尾的最长子串
            dp[ch] = max(dp[ch], k)
        # 那就是将dp中的所有值加起来，就是字符串p中的所有子串数量
        return sum(dp.values())

三、5.24单值二叉树

题目大意：判断二叉树是否所有值都相同，若相同，返回True，否则False。

解析：广度优先搜索BFS，深度优先搜索DFS都可以，只是遍历一遍二叉树。

广度优先搜索：需要借助于队列来完成搜索。

不需要确定遍历到哪一层：

# 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;
            # 遍历当前层的节点
            q.append(cur.left)
            q.append(cur.right)
        return True

深度优先搜索：有三种，先序遍历、中序遍历、后序遍历，下面以先序遍历为例

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)

四、在长度为2N的数组种找出重复N次的元素

题目大意：给定一个数组，长度为2N，其中有N+1个元素，且恰有一个元素重复了N次，要求找出重复N次的那个元素。

解析：有一个元素重复了N次，而且有N+1个元素，长度又为2N，那么其他元素都只出现了一次。遍历一边数组进行计数就找到了。或则采用哈希表（就是一组键值结构），进行计数。

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        # #遍历计数
        # 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
        
        # 哈希
        found = set()
        for i in nums:
            if i in found:
                return i
            found.add(i)