练习2707

阳光穿透心脏的1/2处 2022-09-01 08:12 93阅读 0赞

# class Solution:
    #     def countPrimes(self, n: int) -> int:
    #         res = 0
    #         for i in range(2, n):
    #             for j in range(2, i):
    #                 if i % j == 0:
    #                     break
    #             else:
    #                 #print(i)
    #                 res += 1
    #         return res
    #
    #
    #
    # s=Solution()
    # print(s.countPrimes(10))
    #
    #
    #
    #
    # # 作者：powcai
    # # 链接：https://leetcode-cn.com/problems/count-primes/solution/qiu-zhi-shu-chao-guo-90-by-powcai/
    # # 来源：力扣（LeetCode）
    # # 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    
    """
    本题难点在于如何去除重复解
    算法流程：
    1.特判,对于数组长度n,如果数组为Null或者数组长度小于3，返回[]
    2.对数组进行排序
    3.遍历排序后数组；
        《1若Nums[i]>0:因为已经排序好，所以后面不可能有三个数加和等于0，直接返回结果；
        《2对于重复元素：跳过  避免出现重复解
        《3令左指针L=i+1,右指针R=n-1，当L<R时，执行循环，
                ·~1.当nums[i]+nums[L]+nums[R]==0,判断左界和右届是否和下一位置重复，去除重复解。并同时将L,R移到下一位置，寻找新的解；
                ·~2.若和大于0，说明nums[R]太大，R左移
                ·~3.若和小于0，说明nums[L]太小，L右移
    复杂度分析
    时间复杂度：O\left(n^{2}\right)O(n
    2
     )，数组排序 O(N \log N)O(NlogN)，遍历数组 O\left(n\right)O(n)，双指针遍历 O\left(n\right)O(n)，总体 O(N \log N)+O\left(n\right)*O\left(n\right)O(NlogN)+O(n)∗O(n)，O\left(n^{2}\right)O(n
    2
     )
    空间复杂度：O(1)O(1)
    Python3
    
    
    作者：wu_yan_zu
    链接：https://leetcode-cn.com/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    """
    
    
    # class Solution:
    #     def threeSum(self, nums) :
    #         n = len(nums)
    #         if (not nums or n < 3):
    #             return []
    #         nums.sort()
    #         print(nums)
    #         res = []
    #         for i in range(n):
    #             if (nums[i] > 0):
    #                 return res
    #             if (i > 0 and nums[i] == nums[i - 1]):
    #                 continue
    #             L = i + 1
    #             R = n - 1
    #             while (L < R):
    #                 if (nums[i] + nums[L] + nums[R] == 0):
    #                     res.append([nums[i], nums[L], nums[R]])
    #                     while (L < R and nums[L] == nums[L + 1]):
    #                         L = L + 1
    #                     while (L < R and nums[R] == nums[R - 1]):
    #                         R = R - 1
    #                     L = L + 1
    #                     R = R - 1
    #                 elif (nums[i] + nums[L] + nums[R] > 0):
    #                     R = R - 1
    #                 else:
    #                     L = L + 1
    #         return res
    #
    #
    # s=Solution()
    # nums=[-1,0,1,2,-1,-4]
    # n=s.threeSum(nums)
    # print(n)
    
    
    # class Solution:
    #     def reverseString(self, s: List[str]) -> None:
    #         """
    #         Do not return anything, modify s in-place instead.
    #         """
    #         self.recursion(self,0,len(s)-1)
    #     def recursion(s,left,right):
    #         if left>=right:
    #             return
    #         s[left],s[right]=s[right],s[left]
    #         s.recursion(s,left+1,right-1)
    
    # class Solution:
    #     def findTheDifference(self,s,t):
    #         a="".join([s,t])
    #         # a=a="".join(s,t)
    #         print(a)
    #         for ch in a:
    #             print(a.count(ch))
    #             if a.count(ch) %2 == 1:
    #                 return  ch
    #
    # s=Solution()
    # res=s.findTheDifference( "abcd","abcde")
    # print(s)
    # print(res)
    
    
    # class Solution:
    #     def findTheDifference(self,s,t):
    #         print(map(ord,t))
    #         print(map(ord,s))
    #         print(sum(map(ord,t)))
    #         print(sum(map(ord,s)))
    #         return chr(sum(map(ord,t))-sum(map(ord,s)))
    #
    #
    # s=Solution()
    # res=s.findTheDifference( "abcd","abcde")
    # print(s)
    # print(res)
    
    
    # class Solution:
    #     def findTheDifference(self,s,t):
    #         ans=0
    #         print(ans)
    #         for i in s:
    #             ans^=ord(i)
    #             print(type(ans))
    #             print("ans与s的异或结果是:%d"%ans)
    #         for i in t:
    #             ans^=ord(i)
    #         return chr(ans)
    #
    #
    # s=Solution()
    # res=s.findTheDifference( "abcd","abcde")
    # # print(s)
    # print(res)
    
    # class Solution:
    #     def findTheDifference(self,s,t):
    #         #长度为26的数组，用以统计字符出现次数
    #         str_count = [0]*26
    #         #先遍历s,统计s中字符出现的次数
    #         for ch in s:
    #             # print(ord(ch)-ord('a'))
    #             print(str_count[ord(ch)-ord('a')])
    #             str_count[ord(ch)-ord('a')] += 1
    #         for ch in t:
    #             """
    #             再遍历t,将出现字符对应次数减1
    #             当出现负值，表视对应的字符就是添加的字母
    #             """
    #         for ch in t:
    #             str_count[ord(ch)-ord('a')] -= 1
    #             if str_count[ord(ch)-ord('a')]<0:
    #                 return ch
    #         # return ''
    #         return
    #
    # s=Solution()
    # res=s.findTheDifference( "abcd","abcde")
    # # print(s)
    # print(res)
    import collections
    
    import collection as collection
    
    
    class Solution:
        def getIntersectionNode(self, headA, headB):
            node1, node2 = headA, headB
    
            while node1 != node2:
                node1 = node1.next if node1 else headB
                node2 = node2.next if node2 else headA
    
            return node1
    
    s=Solution()
    
    """简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。
    
    为了方便举例，假设节点元素数值相等，则节点指针相等。
    
    看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
    
    作者：carlsun-2
    链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/dai-ma-sui-xiang-lu-dai-ni-gao-ding-lian-4pgs/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    class Solution:
        def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
            node1, node2 = headA, headB
            
            while node1 != node2:
                node1 = node1.next if node1 else headB
                node2 = node2.next if node2 else headA
    
            return node1
    
    作者：z1m
    链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/shuang-zhi-zhen-fa-lang-man-xiang-yu-by-ml-zimingm/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"""
    
    """
    存在一个由 n 个不同元素组成的整数数组 nums ，但你已经记不清具体内容。好在你还记得 nums 中的每一对相邻元素。
    
    给你一个二维整数数组 adjacentPairs ，大小为 n - 1 ，其中每个 adjacentPairs[i] = [ui, vi] 表示元素 ui 和 vi 在 nums 中相邻。
    
    题目数据保证所有由元素 nums[i] 和 nums[i+1] 组成的相邻元素对都存在于 adjacentPairs 中，存在形式可能是 [nums[i], nums[i+1]] ，也可能是 [nums[i+1], nums[i]] 。这些相邻元素对可以 按任意顺序 出现。
    
    返回 原始数组 nums 。如果存在多种解答，返回 其中任意一个 即可。
    
     
    
    示例 1：
    
    输入：adjacentPairs = [[2,1],[3,4],[3,2]]
    输出：[1,2,3,4]
    解释：数组的所有相邻元素对都在 adjacentPairs 中。
    特别要注意的是，adjacentPairs[i] 只表示两个元素相邻，并不保证其 左-右 顺序。
    示例 2：
    
    输入：adjacentPairs = [[4,-2],[1,4],[-3,1]]
    输出：[-2,4,1,-3]
    解释：数组中可能存在负数。
    另一种解答是 [-3,1,4,-2] ，也会被视作正确答案。
    示例 3：
    
    输入：adjacentPairs = [[100000,-100000]]
    输出：[100000,-100000]
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs
    
    对于一维数组Nums中的元素nums[i],若其为数组的第一个或最后一个元素，
    则该元素有且仅有一个元素与其相邻;若其为数组的中间元素，则该元素有且仅有两个元素与其相邻。
    我们可以对每个元素记录与它相邻的元素有哪些，然后依次检查每个元素的相邻元素数量，即可找到原数组的第一个元素和最后一个元素。
    由于我们可以返回任意一个满足条件的数组，故指定这两个元素中的一个为原数组的第一个元素，然后根据相邻元素信息确定数组的第二个、第三个元素………………直到
    确定最后一个元素为止。
    具体地，我们使用哈希表记录每一个元素的相邻元素有哪些，然后我们遍历哈希表，找到有且仅有一个相邻元素的元素e1作为原数组的第一个元素，那么与e1唯一相邻的元素
    即为原数组的第二个元素。此时排除掉与e2相邻的e1后，可以确认与e2相邻的e3即为原数组的第三个元素………………y以此类推，我们可以将原数组完整推断出来；
    
    """
    # from collections import defaultdict
    #
    # class Solution:
    #     def restoreArray(self,adjacentPairs):
    #         n = len(adjacentPairs)+1
    #
    #         adjvex = defaultdict(list)
    #         for x,y in adjacentPairs:
    #             adjvex[x].append(y)
    #             adjvex[y].append(x)
    #
    #
    #         start =-1
    #         for x ,ys in adjvex.items():
    #             # 起点和终点，必然只有一个后继
    #              if len(ys) ==1:
    #                  start =x
    #                  break
    #
    #         res=[start,adjvex[start][0]]
    #         for _ in range(2,n):
    #             x=res[-1]
    #             for y in adjvex[x]:
    #                 if y!=res[-2]:
    #                     res.append(y)
    #                     break
    #         return res
    #
    # s=Solution()
    # t=s.restoreArray([[2,1],[3,4],[3,2]])
    # print(t)
    
    """
    思路和心得：
    
    1.题目给的条件比较友好
    
    是n个不同元素组成的数组
    
    2.起点和终点，必然都只有一个邻居
    
    中间的点，有左和右两个邻居
    
    3.邻接表
    
    4.先找起点（起点和终点都行。都可作为起点。无正反）
    
    作者：Hanxin_Hanxin
    链接：https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/solution/cpython3java-lin-jie-biao-by-hanxin_hanx-8959/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    """
    
    
    class Solution:
        def restoreArray(self,adjacentPairs):
            #构建地图哈希表
            graph=dict()
            for item in adjacentPairs:
                for  i in range(2):
                    if item[i] in graph:
                        graph[item[i]].append(item[i-1])
                    else:
                        graph[item[i]]=[item[1-i]]
    
            #spec=[head,tail]
            #查找头和尾元素
            spec=[0,0]
            index=0
            for key,value in graph.items():
                if len(value) == 1:
                    spec[index] = key
                    index += 1
    
            #原序列长度为adjacentPairs的长度+1
            res=[0 for _ in range(len(adjacentPairs)+1)]
            res[0] = spec[0]
            left = res[0]
            res[-1] = spec[-1]
            # 根据头节点开始查找下一个元素，这里要记录查找结点的左节点，否则会出现无限循环的问题
            for i in range(1, len(adjacentPairs)):
                if len(graph[res[i - 1]]) == 2:
                    if left == graph[res[i - 1]][1]:
                        res[i] = graph[res[i - 1]][0]
                    else:
                        res[i] = graph[res[i - 1]][1]
                else:
                    res[i] = graph[res[i - 1]][0]
    
                left = res[i - 1]
            return res
    
    
    
    s=Solution()
    t=s.restoreArray([[2,1],[3,4],[3,2]])
    print(t)