茉莉Python

voidqueens@hotmail.com

0%

5609. 统计一致字符串的数目

链接:https://leetcode-cn.com/problems/count-the-number-of-consistent-strings/

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中,就称这个字符串是 一致 字符串。

请你返回 words 数组中 一致 字符串的数目。


示例 1:

输入:allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
输出:2
解释:字符串 "aaab" 和 "baa" 都是一致字符串,因为它们只包含字符 'a' 和 'b' 。
示例 2:

输入:allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
输出:7
解释:所有字符串都是一致的。
示例 3:

输入:allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
输出:4
解释:字符串 "cc","acd","ac" 和 "d" 是一致字符串。


提示:

1 <= words.length <= 104
1 <= allowed.length <= 26
1 <= words[i].length <= 10
allowed 中的字符 互不相同 。
words[i] 和 allowed 只包含小写英文字母。

题解一:

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        count=len(words)
        m=len(allowed)
        for word in words:
            i=0
            word=list(set(word))
            if len(word)>m:
                count-=1
            else:
                while i<len(word):
                    if word[i] not in allowed:
                        count-=1
                        break
                    i+=1
        return count

题解二:

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        for i in allowed:
            for j in range(len(words)):
                words[j]=words[j].replace(i,'')
        return words.count('')

5625. 比赛中的配对次数

链接:https://leetcode-cn.com/problems/count-of-matches-in-tournament/

给你一个整数 n ,表示比赛中的队伍数。比赛遵循一种独特的赛制:

如果当前队伍数是 偶数 ,那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛,且产生 n / 2 支队伍进入下一轮。
如果当前队伍数为 奇数 ,那么将会随机轮空并晋级一支队伍,其余的队伍配对。总共进行 (n - 1) / 2 场比赛,且产生 (n - 1) / 2 + 1 支队伍进入下一轮。
返回在比赛中进行的配对次数,直到决出获胜队伍为止。

示例 1:

输入:n = 7
输出:6
解释:比赛详情:
- 第 1 轮:队伍数 = 7 ,配对次数 = 3 ,4 支队伍晋级。
- 第 2 轮:队伍数 = 4 ,配对次数 = 2 ,2 支队伍晋级。
- 第 3 轮:队伍数 = 2 ,配对次数 = 1 ,决出 1 支获胜队伍。
总配对次数 = 3 + 2 + 1 = 6
示例 2:

输入:n = 14
输出:13
解释:比赛详情:
- 第 1 轮:队伍数 = 14 ,配对次数 = 7 ,7 支队伍晋级。
- 第 2 轮:队伍数 = 7 ,配对次数 = 3 ,4 支队伍晋级。 
- 第 3 轮:队伍数 = 4 ,配对次数 = 2 ,2 支队伍晋级。
- 第 4 轮:队伍数 = 2 ,配对次数 = 1 ,决出 1 支获胜队伍。
总配对次数 = 7 + 3 + 2 + 1 = 13


提示:

1 <= n <= 200

题解一:

时间复杂度:O(n)
空间复杂度:O(1)

class Solution:
    def numberOfMatches(self, n: int) -> int:
        count=0
        while n>1:
            if n%2==0:
                n=n//2
                count+=n
            else:
                n=(n-1)//2+1
                count+=(n-1)
        return count

题解二:

思路:
共有n个队伍,一个冠军,需要淘汰n-1个 队伍。
每一场比赛淘汰一个队伍,因此进行了n-1场比赛。
所以共有n-1个配对。

class Solution:
    def numberOfMatches(self, n: int) -> int:
        return n-1

5626. 十-二进制数的最少数目

链接:https://leetcode-cn.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/

如果一个十进制数字不含任何前导零,且每一位上的数字不是 0 就是 1 ,那么该数字就是一个 十-二进制数 。例如,101 和 1100 都是 十-二进制数,而 112 和 3001 不是。

给你一个表示十进制整数的字符串 n ,返回和为 n 的 十-二进制数 的最少数目。

示例 1:

输入:n = "32"
输出:3
解释:10 + 11 + 11 = 32
示例 2:

输入:n = "82734"
输出:8
示例 3:

输入:n = "27346209830709182346"
输出:9


提示:

1 <= n.length <= 105
n 仅由数字组成
n 不含任何前导零并总是表示正整数

题解一:

class Solution:
    def minPartitions(self, n: str) -> int:
        count=0
        for i in range(len(n)):
            count=max(count,int(n[i]))
        return count

?5627. 石子游戏 VII

链接:https://leetcode-cn.com/problems/stone-game-vii/

石子游戏中,爱丽丝和鲍勃轮流进行自己的回合,爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中,可以从行中 移除 最左边的石头或最右边的石头,并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时,得分较高者获胜。

鲍勃发现他总是输掉游戏(可怜的鲍勃,他总是输),所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ,其中 stones[i] 表示 从左边开始 的第 i 个石头的值,如果爱丽丝和鲍勃都 发挥出最佳水平 ,请返回他们 得分的差值 。

示例 1:

输入:stones = [5,3,1,4,2]
输出:6
解释:
- 爱丽丝移除 2 ,得分 5 + 3 + 1 + 4 = 13 。游戏情况:爱丽丝 = 13 ,鲍勃 = 0 ,石子 = [5,3,1,4] 。
- 鲍勃移除 5 ,得分 3 + 1 + 4 = 8 。游戏情况:爱丽丝 = 13 ,鲍勃 = 8 ,石子 = [3,1,4] 。
- 爱丽丝移除 3 ,得分 1 + 4 = 5 。游戏情况:爱丽丝 = 18 ,鲍勃 = 8 ,石子 = [1,4] 。
- 鲍勃移除 1 ,得分 4 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [4] 。
- 爱丽丝移除 4 ,得分 0 。游戏情况:爱丽丝 = 18 ,鲍勃 = 12 ,石子 = [] 。
得分的差值 18 - 12 = 6 。
示例 2:

输入:stones = [7,90,5,1,100,10,10,2]
输出:122


提示:

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000

题解一|动态规划:

https://leetcode-cn.com/problems/stone-game-vii/solution/c-qu-jian-dp-si-lu-zheng-li-guo-cheng-by-3h0l/

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n=len(stones)
        dp=[[0]*n for i in range(n)]
        res=[[0]*n for i in range(n)]
        for i in range(n):
            for j in range(i,n):
                if i==j:
                    dp[i][j]=stones[i]
                else:
                    dp[i][j]=stones[j]+dp[i][j-1]
        for i in range(n-1,-1,-1):
            for j in range(i+1,n):
                if j==i+1:
                    res[i][j]=max(stones[i],stones[j])
                else:
                    res[i][j]=max(dp[i+1][j]-res[i+1][j],dp[i][j-1]-res[i][j-1])
        return res[0][n-1]

5245. 堆叠长方体的最大高度

链接:https://leetcode-cn.com/problems/maximum-height-by-stacking-cuboids/

给你 n 个长方体 cuboids ,其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti](下标从 0 开始)。请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。

如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ,你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列,以将它放在另一个长方体上。

返回 堆叠长方体 cuboids 可以得到的 最大高度 。

示例 1:

输入:cuboids = [[50,45,20],[95,37,53],[45,23,12]]
输出:190
解释:
第 1 个长方体放在底部,53x37 的一面朝下,高度为 95 。
第 0 个长方体放在中间,45x20 的一面朝下,高度为 50 。
第 2 个长方体放在上面,23x12 的一面朝下,高度为 45 。
总高度是 95 + 50 + 45 = 190 。
示例 2:

输入:cuboids = [[38,25,45],[76,35,3]]
输出:76
解释:
无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它,使 35x3 的一面朝下,其高度为 76 。
示例 3:

输入:cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
输出:102
解释:
重新排列长方体后,可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下,这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。


提示:

n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100

题解一|动态规划:

https://leetcode-cn.com/problems/maximum-height-by-stacking-cuboids/solution/jian-dan-yi-dong-dong-tai-gui-hua-13xing-7hsn/

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        n=len(cuboids)
        for i in range(n):
            cuboids[i].sort(reverse=True) # 倒序排序
        print(cuboids)
        cuboids.sort(reverse=True)
        print(cuboids)
        dp=[0]*n
        for i in range(n):
            dp[i]=cuboids[i][0]
            for j in range(i):
                if cuboids[j][0]>=cuboids[i][0] and cuboids[j][1]>=cuboids[i][1] and cuboids[j][2]>=cuboids[i][2]:
                    dp[i]=max(dp[i],dp[j]+cuboids[i][0])
        return max(dp)

207. 课程表

链接:https://leetcode-cn.com/problems/course-schedule/

你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?


示例 1:

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

提示:

输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵 。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5

题解一|拓扑排序|bfs:

有向无环图,把一个 有向无环图 转成 线性的排序 就叫 拓扑排序。

有向图有 入度 和 出度 的概念:

如果存在一条有向边 A --> B,则这条边给 A 增加了 1 个出度,给 B 增加了 1 个入度。

思路:

A-->B
每次选择入度为0的课程,因为它不需要依赖其他的课程;
当选择A后,B的依赖课程少了一门,入度由1变为0,接着选B;
一直选择,直到选不到入度为0的课程;
import collections

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        n=len(prerequisites)
        if n==0:
            return True
        in_degrees=[0 for _ in range(numCourses)]
        adjacency=[[] for _ in range(numCourses)]
        queue=collections.deque()

        for second,first in prerequisites:
            in_degrees[second]+=1 # 节点的入度,index代表节点,value代表入度值。
            adjacency[first].append(second) # 邻接矩阵关系

        for i in range(numCourses):
            if in_degrees[i]==0:
                queue.append(i) # 如果入度为0,则把index即节点加入到queue队列中。

        while queue:
            node=queue.popleft()
            for i in adjacency[node]: # 节点指向的节点
                in_degrees[i]-=1
                if in_degrees[i]==0:
                    queue.append(i)
            numCourses-=1
        return numCourses==0

题解二|dfs:

import collections

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        def dfs(i, adjacency, flags):
            if flags[i] == -1: return True
            if flags[i] == 1: return False
            flags[i] = 1
            for j in adjacency[i]:
                if not dfs(j, adjacency, flags): return False
            flags[i] = -1
            return True

        adjacency = [[] for _ in range(numCourses)]
        flags = [0 for _ in range(numCourses)]
        for cur, pre in prerequisites:
            adjacency[pre].append(cur)
        for i in range(numCourses):
            if not dfs(i, adjacency, flags): return False
        return True

997. 找到小镇的法官

链接:https://leetcode-cn.com/problems/find-the-town-judge/

在一个小镇里,按从 1 到 N 标记了 N 个人。传言称,这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在,那么:

小镇的法官不相信任何人。
每个人(除了小镇法官外)都信任小镇的法官。
只有一个人同时满足属性 1 和属性 2 。
给定数组 trust,该数组由信任对 trust[i] = [a, b] 组成,表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -1。

示例 1:

输入:N = 2, trust = [[1,2]]
输出:2
示例 2:

输入:N = 3, trust = [[1,3],[2,3]]
输出:3
示例 3:

输入:N = 3, trust = [[1,3],[2,3],[3,1]]
输出:-1
示例 4:

输入:N = 3, trust = [[1,2],[2,3]]
输出:-1
示例 5:

输入:N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
输出:3


提示:

1 <= N <= 1000
trust.length <= 10000
trust[i] 是完全不同的
trust[i][0] != trust[i][1]
1 <= trust[i][0], trust[i][1] <= N

题解一|出度和入度:

class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        if N<1:
            return -1
        n=len(trust)
        indegree=[0 for _ in range(N+1)]
        outdegree=[0 for _ in range(N+1)]
        for first,second in trust:
            indegree[second]+=1
            outdegree[first]+=1
        for i in range(1,N+1): # 从1开始
            if indegree[i]==N-1 and outdegree[i]==0:
                return i
        return -1
class Solution:
    def findJudge(self, N: int, trust: List[List[int]]) -> int:
        if N<=1:
            return N
        n=len(trust)
        degree=[0 for _ in range(N+1)]
        for first,second in trust:
            degree[first]-=1
            degree[second]+=1
        for i in range(N+1):
            if degree[i]==N-1:
                return i
        return -1

https://labuladong.github.io/ebook/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E5%8C%BA%E9%97%B4%E9%97%AE%E9%A2%98%E5%90%88%E9%9B%86.html

56. 合并区间

链接:https://leetcode-cn.com/problems/merge-intervals/

给出一个区间的集合,请合并所有重叠的区间。

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意:输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示:

intervals[i][0] <= intervals[i][1]

题解一:

时间复杂度:O(nlogn),其中 n为区间的数量。除去排序的开销,我们只需要一次线性扫描,所以主要的时间开销是排序的 O(nlogn)。

空间复杂度:O(logn),其中 n为区间的数量。这里计算的是存储答案之外,使用的额外空间。O(logn) 即为排序所需要的空间复杂度。

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        if not intervals:
            return
        intervals.sort(key=lambda x:(x[0],-x[1]))
        res=[]
        res.append(intervals[0])
        for i in range(1,len(intervals)):
            tmp=intervals[i]
            last=res[-1]
            if last[1] >= tmp[0]:
                last[1]=max(last[1],tmp[1])
            else:
                res.append(tmp)
        return res

57. 插入区间

链接:https://leetcode-cn.com/problems/insert-interval/

给出一个无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]
示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

注意:输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。

题解一|分段考察:

1、不重叠,位于newInterval的左侧
2、重叠
2、不重叠,位于newInterval的右侧

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        res=[]
        i,n=0,len(intervals)
        while i<n and intervals[i][1]<newInterval[0]:
            res.append(intervals[i])
            i+=1
        while i<n and intervals[i][0]<=newInterval[1]:
            newInterval[0]=min(newInterval[0],intervals[i][0])
            newInterval[1]=max(newInterval[1],intervals[i][1])
            i+=1
        res.append(newInterval)
        while i<n:
            res.append(intervals[i])
            i+=1
        return res

题解二|模拟:

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        left,right=newInterval
        flag=False
        ans=[]
        for low,high in intervals:
            if low>right: # 在插入区间右侧且无交集
                if not flag:
                    ans.append([left,right]) # 此处插入交集部分
                    flag=True
                ans.append([low,high])
            elif high<left: # 在插入区间左侧且无交集
                ans.append([low,high])
            else: # 与插入区间有交集,计算它们的并集
                left=min(left,low)
                right=max(right,high)
        if not flag: # 如果intervals为空时,此处插入newInterval
            ans.append([left,right])
        return ans

228. 汇总区间

给定一个无重复元素的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出:

"a->b" ,如果 a != b
"a" ,如果 a == b

示例 1:

输入:nums = [0,1,2,4,5,7]
输出:["0->2","4->5","7"]
解释:区间范围是:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2:

输入:nums = [0,2,3,4,6,8,9]
输出:["0","2->4","6","8->9"]
解释:区间范围是:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
示例 3:

输入:nums = []
输出:[]
示例 4:

输入:nums = [-1]
输出:["-1"]
示例 5:

输入:nums = [0]
输出:["0"]

提示:

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同

题解一|双指针:

时间复杂度:O(N)
空间复杂度:O(1)

class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        left,right=0,0
        nums.append(float('inf')) # 解决溢出问题
        res=[]
        for i in range(len(nums)-1):
            right=i
            if nums[i]+1 != nums[i+1]:
                if left==right:
                    res.append(str(nums[right])+'')
                else:
                    res.append(str(nums[left])+'->'+str(nums[right]))

                left=i+1
                right=i+1
        return res
class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        if len(nums) == 0: 
            return []
        elif len(nums) == 1:
            return [str(nums[0])]
        result = []
        j = 0 
        for i in range(len(nums)):
            if i:
                if nums[i] - nums[i-1] != 1:
                    if j == i-1:
                        result.append(str(nums[j]))
                    else:
                        result.append(str(nums[j]) + '->' + str(nums[i-1]))
                    if i == len(nums)-1:
                        result.append(str(nums[i]))
                    j = i
            if i == len(nums)-1 and j < len(nums)-1:
                result.append(str(nums[j]) + '->' + str(nums[i]))
        return result

986. 区间列表的交集

链接:https://leetcode-cn.com/problems/interval-list-intersections/

给定两个由一些 闭区间 组成的列表,每个区间列表都是成对不相交的,并且已经排序。

返回这两个区间列表的交集。

(形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b。两个闭区间的交集是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。)

示例:

输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]


提示:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

题解一|归并计算:

时间复杂度:O(M+N),其中 M, N 分别是数组 A 和 B 的长度。

空间复杂度:O(M+N),答案中区间数量的上限。

class Solution(object):
    def intervalIntersection(self, A, B):
        """
        :type A: List[List[int]]
        :type B: List[List[int]]
        :rtype: List[List[int]]
        """
        i,j=0,0
        res=[]
        while i<len(A) and j<len(B):
            a1,a2=A[i][0],A[i][1]
            b1,b2=B[j][0],B[j][1]

            if b2>=a1 and a2>=b1:
                res.append([max(a1,b1),min(a2,b2)]) # 交集计算
            if b2<a2:
                j+=1
            else:
                i+=1
        return res

1288. 删除被覆盖区间

链接:https://leetcode-cn.com/problems/remove-covered-intervals/

给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时,我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后,请你返回列表中剩余区间的数目。

示例:

输入:intervals = [[1,4],[3,6],[2,8]]
输出:2
解释:区间 [3,6] 被区间 [2,8] 覆盖,所以它被删除了。

提示:​​​​​​

1 <= intervals.length <= 1000
0 <= intervals[i][0] < intervals[i][1] <= 10^5
对于所有的 i != j:intervals[i] != intervals[j]

题解一:

1、区间被完全覆盖
2、两个区间相交,合并成一个大区间
3、两个区间完全不相交

注意:对于这两个起点相同的区间,我们需要保证长的那个区间在上面(按照终点降序),这样才会被判定为覆盖,否则会被错误地判定为相交,少算一个覆盖区间。

class Solution(object):
    def removeCoveredIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        intervals.sort(key=lambda x: (x[0],-x[1])) # 起点升序排序,起点相同时降序排序
        left,right=intervals[0][0],intervals[0][1] # 合并区间的起点和终点
        count=0
        for i in range(1,len(intervals)):
            tmp=intervals[i]
            if left<=tmp[0] and right>=tmp[1]: # 覆盖区间
                count+=1
            if right>=tmp[0] and right<=tmp[1]: # 相交区间,合并
                right=tmp[1]
            if right<tmp[0]: # 完全不相交区间,更新起点和终点
                left=tmp[0]
                right=tmp[1]
        return len(intervals)-count

题解二|贪心|扫描线:

class Solution(object):
    def removeCoveredIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        intervals.sort(key=lambda x: (x[0],-x[1]))
        right=intervals[0][1]
        count=0
        for i in range(1,len(intervals)):
            if right>=intervals[i][1]:
                count+=1
            else:
                right=intervals[i][1]
        return len(intervals)-count

496. 下一个更大元素 I

链接:https://leetcode-cn.com/problems/next-greater-element-i/

给定两个 没有重复元素 的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4,你无法在第二个数组中找到下一个更大的数字,因此输出 -1。
    对于num1中的数字1,第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2,第二个数组中没有下一个更大的数字,因此输出 -1。
示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 num1 中的数字 2 ,第二个数组中的下一个较大数字是 3 。
    对于 num1 中的数字 4 ,第二个数组中没有下一个更大的数字,因此输出 -1 。


提示:

nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。

题解一|暴力:

时间复杂度:O(n^2)

从前向后遍历:

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        m=len(nums1)
        n=len(nums2)
        res=[-1]*m
        for i in range(m):
            flag=0
            for j in range(n):
                if nums1[i]==nums2[j]:
                    flag=1
                if flag==1 and nums1[i]<nums2[j]:
                    res[i]=nums2[j]
                    break
        return res

从后向前遍历:

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        m=len(nums1)
        n=len(nums2)
        res=[-1]*m
        for i in range(m):
            for j in range(n-1,-1,-1):
                if nums1[i]==nums2[j]:
                    break
                if nums1[i]<nums2[j]:
                    res[i]=nums2[j]
        return res

题解二|单调递减栈:

思路:

遍历nums2,维护一个递减栈
当得到一个更大的数的时候,将栈里小于它的数都放到哈希表当中

时间复杂度:O(M+N)
空间复杂度:O(M)

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        m=len(nums1)
        n=len(nums2)
        hash={}
        stack=[]
        res=[]
        for i in range(n):
            while stack and stack[-1]<nums2[i]:
                hash[stack.pop()]=nums2[i] # hash中存储第一个比它大的数字
            stack.append(nums2[i])
        for i in nums1:
            res.append(hash.get(i,-1))
        return res 

503. 下一个更大元素 II

链接:https://leetcode-cn.com/problems/next-greater-element-ii/

给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数; 
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。
注意: 输入数组的长度不会超过 10000。

题解一|暴力:

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        new=nums+nums
        res=[-1]*len(new)
        for i in range(len(new)):
            tmp=new[i]
            if i>len(nums):
                break
            for j in range(i+1,len(new)):
                if new[i]<new[j]:
                    res[i]=new[j]
                    break
        return res[:len(nums)]

题解二|单调递减栈:

不同点:和上一题不相同的是,这个是循环数组,关于循环数组的一个技巧就是*2取余了

栈内存储的是什么,是下标还是值,都是可以的。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n=len(nums)
        stack=[]
        res=[-1]*n
        for i in range(2*n):
            while stack and nums[stack[-1]] < nums[i%n]:
                index=stack.pop()
                res[index%n]=nums[i%n]
            stack.append(i%n)
        return res

739. 每日温度

链接:https://leetcode-cn.com/problems/daily-temperatures/

请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。

例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

题解一|暴力|超时:

关键:找出右边第 1 个严格大于自己的元素的索引。

问题:就像选择排序一样,上一轮的操作并没有为下一轮的操作留下什么有用的信息。

时间复杂度:O(n^2)
空间复杂度:O(n)

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        n=len(T)
        res=[0]*n
        for i in range(n-1):
            tmp=T[i]
            for j in range(i+1,n):
                if tmp<T[j]:
                    res[i]=j-i
                    break                
        return res    

题解二|单调递减栈:

单调栈介绍视频:https://leetcode-cn.com/problems/daily-temperatures/solution/leetcode-tu-jie-739mei-ri-wen-du-by-misterbooo/

时间复杂度:O(n)
空间复杂度:O(n)

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        n=len(T)
        stack=[]
        res=[0]*n
        for i in range(n):
            while stack and T[stack[-1]]<T[i]:
                index=stack.pop()
                res[index]=i-index
            stack.append(i)
        return res    

190. 颠倒二进制位

链接:https://leetcode-cn.com/problems/reverse-bits/

颠倒给定的 32 位无符号整数的二进制位。

示例 1:

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
     因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。
示例 2:

输入:11111111111111111111111111111101
输出:10111111111111111111111111111111
解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。


提示:

请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 2 中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825。


进阶:
如果多次调用这个函数,你将如何优化你的算法?

题解一:

zfill():32位右对齐,不够的话,左边补0

class Solution:
    def reverseBits(self, n: int) -> int:
        return int(bin(n)[2:].zfill(32)[::-1],2)

题解二|移位:

class Solution:
    def reverseBits(self, n: int) -> int:
        res=0
        count=32
        while count:
            res<<=1
            res+=n&1
            n>>=1
            count-=1
        return int(bin(res),2)

191. 位1的个数

链接:https://leetcode-cn.com/problems/number-of-1-bits/

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。
示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。
示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。


提示:

请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3。


进阶:
如果多次调用这个函数,你将如何优化你的算法?

题解一|循环:

class Solution:
    def hammingWeight(self, n: int) -> int:
        tmp=bin(n)[2:]
        res=0
        for i in tmp:
            if int(i)==1:
                res+=1
        return res    

题解二|循环和位移动:

class Solution:
    def hammingWeight(self, n: int) -> int:
        bits=0
        mask=1
        for i in range(32):
            if (n & mask) != 0:
                bits+=1
            mask<<=1
        return bits

题解三|位操作:

时间复杂度:O(1) 。运行时间与 n 中位为 1 的有关。在最坏情况下, n 中所有位都是 11 。对于 32 位整数,运行时间是 O(1) 的。

空间复杂度:O(1) ,没有使用额外空间。

class Solution:
    def hammingWeight(self, n: int) -> int:
        res=0
        while n != 0:
            res+=1
            n &= (n-1)
        return res

268. 丢失的数字

链接:https://leetcode-cn.com/problems/missing-number/

给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

进阶:

你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?


示例 1:

输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。
示例 2:

输入:nums = [0,1]
输出:2
解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。
示例 3:

输入:nums = [9,6,4,2,3,5,7,0,1]
输出:8
解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。
示例 4:

输入:nums = [0]
输出:1
解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。

提示:

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

题解一|数学:

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n=len(nums)
        ans=((n+1)*n)//2
        for i in range(len(nums)):
            ans-=nums[i]
        return ans

371. 两整数之和

链接:https://leetcode-cn.com/problems/sum-of-two-integers/

不使用运算符 + 和 - ​​​​​​​,计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

示例 1:

输入: a = 1, b = 2
输出: 3
示例 2:

输入: a = -2, b = 3
输出: 1

题解一|位运算:

参考:https://leetcode-cn.com/problems/sum-of-two-integers/solution/wei-yun-suan-xiang-jie-yi-ji-zai-python-zhong-xu-y/

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 2^32
        MASK = 0x100000000
        # 整型最大值
        MAX_INT = 0x7FFFFFFF
        MIN_INT = MAX_INT + 1
        while b != 0:
            # 计算进位
            carry = (a & b) << 1 
            # 取余范围限制在 [0, 2^32-1] 范围内
            a = (a ^ b) % MASK
            b = carry % MASK
        return a if a <= MAX_INT else ~((a % MIN_INT) ^ MAX_INT) 

461. 汉明距离

链接:https://leetcode-cn.com/problems/hamming-distance/

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y,计算它们之间的汉明距离。

注意:
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

题解一|内置函数:

时间复杂度:O(1)
空间复杂度:O(1)

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x^y).count('1')

题解二|移位:

时间复杂度:O(1)
空间复杂度:O(1)

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor=x^y
        count=0
        while xor:
            if xor & 1:
                count+=1
            xor=xor>>1
        return count

33. 搜索旋转排序数组

链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

给你一个整数数组 nums ,和一个整数 target 。

该整数数组原本是按升序排列,但输入时在预先未知的某个点上进行了旋转。(例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。


示例 1:

输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:

输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:

输入:nums = [1], target = 0
输出:-1

提示:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
nums 肯定会在某个点上旋转
-10^4 <= target <= 10^4

题解一|二分查找:

时间复杂度:O(logn),其中 n 为 nums数组的大小。整个算法时间复杂度即为二分搜索的时间复杂度 O(logn)。

空间复杂度:O(1) 我们只需要常数级别的空间存放变量。

注意:if中很多等号的判断

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        left,right=0,len(nums)-1
        while left<=right:
            mid=left+(right-left)//2
            if nums[mid]==target:
                return mid
            elif nums[0]<=nums[mid] : # 此处加=号,解决case[3,1]和1
                if nums[0]<=target<nums[mid]: # 此处加=号,解决case[1,3,5]和1
                    right=mid-1
                else:
                    left=mid+1
            else:
                if nums[mid]<target<=nums[len(nums)-1]: # 此处加=号,解决case[1,3]和3
                    left=mid+1
                else:
                    right=mid-1
        return -1

34. 在排序数组中查找元素的第一个和最后一个位置

链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

题解一:

时间复杂度: O(n)
空间复杂度: O(1)

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res=[-1,-1]
        for i in range(len(nums)):
            if nums[i]==target:
                res[0]=i
                break
        if res[0]==-1:
            return res
        for i in range(len(nums)-1,-1,-1):
            if nums[i]==target:
                res[1]=i
                break
        return res

题解二|二分查找:

时间复杂度: O(logn)
空间复杂度: O(1)

    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1,-1]
        left,right=0,len(nums)-1
        while left=target:
                right=mid
            else:
                left=mid+1
        if nums[left]!=target:
            return [-1,-1]
        start=left

        left,right=0,len(nums)-1
        while left

75. 颜色分类

链接:https://leetcode-cn.com/problems/sort-colors/

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?

题解一|重写数组:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        c0,c1,c2=0,0,0
        for i in nums:
            if i==0:
                c0+=1
            elif i==1:
                c1+=1
            elif i==2:
                c2+=1
        for i in range(len(nums)):
            if c0:
                nums[i]=0
                c0-=1
            elif c1:
                nums[i]=1
                c1-=1
            elif c2:
                nums[i]=2
                c2-=1

题解二|单指针:

时间复杂度:O(n),其中 n 是数组 nums 的长度。
空间复杂度:O(1)。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        ptr=0
        for i in range(n):
            if nums[i]==0:
                nums[i],nums[ptr]=nums[ptr],nums[i]
                ptr+=1
        for i in range(ptr,n):
            if nums[i]==1:
                nums[i],nums[ptr]=nums[ptr],nums[i]
                ptr+=1

题解三|双指针:

时间复杂度:O(n),其中 n 是数组 nums 的长度。
空间复杂度:O(1)。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        p0=p1=0
        for i in range(n):
            if nums[i]==1:
                nums[i],nums[p1]=nums[p1],nums[i]
                p1+=1
            elif nums[i]==0:
                nums[i],nums[p0]=nums[p0],nums[i]
                if p0 < p1:
                    nums[i],nums[p1]=nums[p1],nums[i]
                p0+=1
                p1+=1
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n=len(nums)
        p0,p2=0,n-1
        i=0
        while i<=p2:
            while i<=p2 and nums[i]==2:
                nums[i],nums[p2]=nums[p2],nums[i]
                p2-=1
            if nums[i]==0:
                nums[i],nums[p0]=nums[p0],nums[i]
                p0+=1
            i+=1

162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素,你的函数应该返回其索引 2。
示例 2:

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1,其峰值元素为 2;
     或者返回索引 5, 其峰值元素为 6。
说明:

你的解法应该是 O(logN) 时间复杂度的。

题解一|线性扫描:

1、一直上坡
2、一直下坡
3、上坡和下坡

时间复杂度 : O(n)。 我们对长度为 n 的数组 nums 只进行一次遍历。
空间复杂度 : O(1)。 只使用了常数空间。

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)-1):
            if nums[i]>nums[i+1]:
                return i
        return len(nums)-1

题解二|递归|二分查找:
时间复杂度 : O(logn)。每一步都将搜索空间减半。因此,总的搜索空间只需要 log(n) 步。其中 n 为 nums 数组的长度。
空间复杂度: O(logn)。每一步都将搜索空间减半。因此,总的搜索空间只需要 log(n) 步。于是,递归树的深度为 log(n)。

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.binarySearch(nums,0,len(nums)-1)
    def binarySearch(self,nums,left,right):
        if left==right:
            return left
        mid=left+(right-left)//2
        if nums[mid]>nums[mid+1]:
            return self.binarySearch(nums,left,mid)
        return self.binarySearch(nums,mid+1,right)

题解三|迭代|二分查找:

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left,right=0,len(nums)-1
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]>nums[mid+1]:
                right=mid
            else:
                left=mid+1
        return left

179. 最大数

链接:https://leetcode-cn.com/problems/largest-number/

给定一组非负整数 nums,重新排列它们每个数字的顺序(每个数字不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1:

输入:nums = [10,2]
输出:"210"
示例 2:

输入:nums = [3,30,34,5,9]
输出:"9534330"
示例 3:

输入:nums = [1]
输出:"1"
示例 4:

输入:nums = [10]
输出:"10"


提示:

1 <= nums.length <= 100
0 <= nums[i] <= 109

题解一|重载运算符:

class StrLt(str):
    def __lt__(x,y):
        # 1、比较 ab 与 ba的大小,按降序排列;
        # 2、将数组转化为字符串。
        return x+y>y+x

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        tostr=[str(i) for i in nums]
        tostr.sort(key=StrLt)
        return ''.join(tostr) if tostr[0] != '0' else '0'

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

题解一|小顶堆:

class Solution(object):
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        self.buildHeap(nums[:k])
        # print(self.heapList)
        for i in range(k,len(nums)):
            if nums[i]>self.heapList[1]:
                self.heapList[1]=nums[i]
                self.percDown(1)
        return self.heapList[1]
    def percDown(self,i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
                # self.heapList[i],self.heapList[mc]=self.heapList[mc],self.heapList[i]
            i = mc

    def minChild(self,i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i*2] < self.heapList[i*2+1]:
                return i * 2
            else:
                return i * 2 + 1

    def delMin(self):
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval

    def buildHeap(self,alist):
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
            self.percDown(i)
            i = i - 1

240. 搜索二维矩阵 II

链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出:true
示例 2:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出:false

提示:

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

题解一|暴力:

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        for row in matrix:
            if target in row:
                return True
        return False

题解二|二分查找:

时间复杂度:O(mlogn)
空间复杂度:O(1)

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        for i in range(len(matrix)):
            if self.binarySearch(matrix,i,target):
                return True
        return False

    def binarySearch(self,matrix,i,target):
        left,right=0,len(matrix[0])-1
        while left<=right:
            mid=left+(right-left)//2
            if target > matrix[i][mid]:
                left=mid+1
            elif target < matrix[i][mid]:
                right=mid-1
            elif target == matrix[i][mid]:
                return True
        return False

题解三|规律:

时间复杂度:O(m+n)
空间复杂度:O(1)

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        left,right=0,len(matrix[0])-1
        while left<len(matrix) and right>=0:
            if matrix[left][right]>target:
                right-=1
            elif matrix[left][right]<target:
                left+=1
            elif matrix[left][right]==target:
                return True
        return False

278. 第一个错误的版本

链接:https://leetcode-cn.com/problems/first-bad-version/

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5,并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。 

题解一|二分查找:

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left,right=1,n
        while left<=right: # 注意是小于等于
            mid=left+(right-left)//2
            if isBadVersion(mid):
                right=mid-1
            else:
                left=mid+1
        return left

347. 前 K 个高频元素

链接:https://leetcode-cn.com/problems/top-k-frequent-elements/

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]


提示:

你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

题解一|小根堆:

import collections 
class Solution(object):
    def __init__(self):
        self.size=0
        self.heap=[(0,0)]

    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        hash={}
        for i in nums:
            hash[i]=hash.get(i,0)+1
        hashlist=[[key,value] for key,value in hash.items()]
        self.buildHeap(hashlist[:k]) # 建立基于次数的小根堆
        for i in range(k,len(hashlist)):
            if self.heap[1][1]<=hashlist[i][1]:
                self.heap[1]=hashlist[i]
                self.percDown(1)
        return [self.heap[i][0] for i in range(1,k+1)]

    def percDown(self,i):
        while (i * 2) <= self.size:
            mc = self.minChild(i)
            if self.heap[i][1] > self.heap[mc][1]: # 注意,基于次数
                self.heap[i],self.heap[mc]=self.heap[mc],self.heap[i]
            i = mc

    def minChild(self,i):
        if i * 2 + 1 > self.size:
            return i * 2
        else:
            if self.heap[i*2][1] < self.heap[i*2+1][1]: # 注意此处比较的是次数,而不是self.heap[i*2] < self.heap[i*2+1]
                return i * 2
            else:
                return i * 2 + 1
    def buildHeap(self,arr):
        i=len(arr)//2
        self.size=len(arr)
        self.heap=[(0,0)]+arr[:]
        while i>0:
            self.percDown(i)
            i-=1

451. 根据字符出现频率排序

链接:https://leetcode-cn.com/problems/sort-characters-by-frequency/

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。
示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

题解一|小根堆:

class Solution(object):
    def __init__(self):
        self.size=0
        self.heap=[['0',0]]
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        hash={}
        for i in s:
            if i not in hash:
                hash[i]=1
            else:
                hash[i]+=1
        hashlist=[[key,value] for key,value in hash.items()]
        self.buildHeap(hashlist)

        for i in range(len(hashlist),0,-1): 不要写成self.size,和下面self.size-=1不好区分。
        # for i in range(self.size,0,-1):
            self.heap[1],self.heap[i]=self.heap[i],self.heap[1]
            self.size-=1 # 关键点,减1后避免和最后一个元素再交换回去。
            self.percDown(1)
        result=''
        for i in range(1,len(self.heap)):
            result+=str(self.heap[i][0]*self.heap[i][1])
        return result
    def percDown(self,i):
        while (i*2)<=self.size:
            mc=self.minChild(i)
            if self.heap[i][1]>self.heap[mc][1]:
                self.heap[i],self.heap[mc]=self.heap[mc],self.heap[i]
            i=mc
    def minChild(self,i):
        if i*2+1>self.size:
            return i*2
        else:
            if self.heap[i*2][1]<self.heap[i*2+1][1]:
                return i*2
            else:
                return i*2+1
    def buildHeap(self,arr):
        i=len(arr)//2
        self.size=len(arr)
        self.heap=[['0',0]]+arr
        while i>0:
            self.percDown(i)
            i-=1

973. 最接近原点的 K 个点

链接:https://leetcode-cn.com/problems/k-closest-points-to-origin/

我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

(这里,平面上两点之间的距离是欧几里德距离。)

你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。

示例 1:

输入:points = [[1,3],[-2,2]], K = 1
输出:[[-2,2]]
解释: 
(1, 3) 和原点之间的距离为 sqrt(10),
(-2, 2) 和原点之间的距离为 sqrt(8),
由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。
示例 2:

输入:points = [[3,3],[5,-1],[-2,4]], K = 2
输出:[[3,3],[-2,4]]
(答案 [[-2,4],[3,3]] 也会被接受。)


提示:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

题解一|大根堆:

import math
class Solution(object):
    def __init__(self):
        self.size=0
        self.heap=[[0,0]]
    def kClosest(self, points, K):
        """
        :type points: List[List[int]]
        :type K: int
        :rtype: List[List[int]]
        """
        self.buildHeap(points[:K])
        for i in range(K,len(points)):
            if self.cal(self.heap[1]) > self.cal(points[i]):
                self.heap[1]=points[i]
                self.percDown(1)
        return [self.heap[i] for i in range(1,K+1)]

    def percDown(self,i):
        while i*2<=self.size:
            mc=self.maxChild(i)
            if self.cal(self.heap[i])<self.cal(self.heap[mc]):
                self.heap[i],self.heap[mc]=self.heap[mc],self.heap[i]
            i=mc
    def maxChild(self,i):
        if (i*2+1)>self.size:
            return i*2
        else:
            if self.cal(self.heap[i*2])>self.cal(self.heap[i*2+1]):
                return i*2
            else:
                return i*2+1
    def buildHeap(self,arr):
        i=len(arr)//2
        self.heap=[[0,0]]+arr
        self.size=len(arr)
        while i>0:
            self.percDown(i)
            i-=1

    def cal(self,point):
        return math.sqrt(point[0]**2+point[1]**2)

155. 最小栈

链接:https://leetcode-cn.com/problems/min-stack/solution/

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

pop、top 和 getMin 操作总是在 非空栈 上调用。

题解一|双栈:

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=[]
        self.minstack=[]

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.minstack or self.minstack[-1]>=x:
            self.minstack.append(x)

    def pop(self) -> None:
        if self.stack:
            if self.stack[-1] == self.minstack[-1]:
                self.minstack.pop()
            return self.stack.pop()

    def top(self) -> int:
        if self.stack:
            return self.stack[-1]
        else:
            return 

    def getMin(self) -> int:
        if self.minstack:
            return self.minstack[-1]
        else:
            return

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

146. LRU 缓存机制

链接:https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。


进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?


示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4


提示:

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put

题解一|OrderedDict:

import collections

class LRUCache(collections.OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity=capacity

    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key)
        return self[key]


    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key) # 表达把key移动到最后,即更新key
        self[key]=value
        if len(self)>self.capacity:
            self.popitem(last=False) # last=False表示先进先出,last=True表示后进先出


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

题解二|hash|双向链表:

时间复杂度:对于 put 和 get 都是 O(1)O(1)。

空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity+1 个元素。

class DLinkedNode:
    def __init__(self,key=0,value=0):
        self.key=key
        self.value=value
        self.prev=None
        self.next=None

class LRUCache:

    def __init__(self, capacity: int):
        self.cache=dict()
        self.head=DLinkedNode()
        self.tail=DLinkedNode()
        self.head.next=self.tail
        self.tail.prev=self.head
        self.capacity=capacity
        self.size=0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node=self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node=DLinkedNode(key,value)
            self.cache[key]=node
            self.addToHead(node)
            self.size+=1
            if self.size>self.capacity:
                removed=self.removeTail()
                self.cache.pop(removed.key)
                self.size-=1
        else:
            node=self.cache[key]
            node.value=value
            self.moveToHead(node)

    def addToHead(self,node):
        node.prev=self.head
        node.next=self.head.next
        self.head.next.prev=node
        self.head.next=node

    def removeNode(self,node):
        node.prev.next=node.next
        node.next.prev=node.prev

    def moveToHead(self,node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node=self.tail.prev
        self.removeNode(node)
        return node

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

380. 常数时间插入、删除和获取随机元素

链接:https://leetcode-cn.com/problems/insert-delete-getrandom-o1/

设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。

insert(val):当元素 val 不存在时,向集合中插入该项。
remove(val):元素 val 存在时,从集合中移除该项。
getRandom:随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :

// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ,表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ,返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中,所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字,getRandom 总是返回 2 。
randomSet.getRandom();

题解一|hash|动态数组:

1、insert:

平均插入时间为O(1) 的选择:
    哈希表:Java 中为 HashMap,Python 中为 dictionary。
    动态数组:Java 中为 ArrayList,Python 中为 list。

2、getRandom:

哈希表提供常数时间的插入和删除,但是实现 getRandom 时会出现问题。
getRandom 的思想是选择一个随机索引,然后使用该索引返回一个元素。而哈希表中没有索引,因此要获得真正的随机值,则要将哈希表中的键转换为列表,这需要线性时间。解决的方法是用一个列表存储值,并在该列表中实现常数时间的 getRandom。

3、remove:

列表有索引可以实现常数时间的 insert 和 getRandom,则接下来的问题是如何实现常数时间的 remove。

删除任意索引元素需要线性时间,这里的解决方案是总是删除最后一个元素。
    将要删除元素和最后一个元素交换。
    将最后一个元素删除。

综上:

动态数组存储元素值。
哈希表存储存储值到索引的映射。
import random
class RandomizedSet(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.list=[]
        self.dict={}


    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.dict:
            return False
        self.dict[val]=len(self.list)
        self.list.append(val)
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.dict:
            last,index=self.list[-1],self.dict[val]
            self.list[index],self.dict[last]=last,index
            self.list.pop()
            del self.dict[val]
            return True
        return False


    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.list)

# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

384. 打乱数组

链接:https://leetcode-cn.com/problems/shuffle-an-array/

打乱一个没有重复元素的数组。

示例:

// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

拷贝知识:

直接赋值:其实就是对象的引用(别名)。

浅拷贝(copy):拷贝父对象,不会拷贝对象的内部的子对象。

深拷贝(deepcopy): copy 模块的 deepcopy 方法,完全拷贝了父对象及其子对象。

题解一|暴力:

时间复杂度: O(n^2),乘方时间复杂度来自于 list.remove(list.pop)。每次操作都是线性时间的,总共发生 n 次。

空间复杂度: O(n),因为需要实现 重置 方法,需要额外的空间把原始数组另存一份,在重置的时候用来恢复原始状态。

class Solution:
    from copy import copy
    from random import random
    def __init__(self, nums: List[int]):
        self.ori=copy.deepcopy(nums)
        self.nums=nums

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.ori

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        self.aux=copy.deepcopy(self.nums)
        for i in range(len(self.nums)):
            index=random.randrange(len(self.aux))
            self.nums[i]=self.aux.pop(index)
        return self.nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

题解二| Fisher-Yates 洗牌算法:

时间复杂度 : O(n),Fisher-Yates 洗牌算法时间复杂度是线性的,因为算法中生成随机序列,交换两个元素这两种操作都是常数时间复杂度的。

空间复杂度: O(n),因为要实现 重置 功能,原始数组必须得保存一份,因此空间复杂度并没有优化。

class Solution:
    from copy import copy
    from random import random
    def __init__(self, nums: List[int]):
        self.ori=copy.deepcopy(nums)
        self.nums=nums

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.ori

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        for i in range(len(self.nums)):
            index=random.randint(i,len(self.nums)-1)
            self.nums[i],self.nums[index]=self.nums[index],self.nums[i]
        return self.nums

# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

1678. 设计 Goal 解析器

链接:https://leetcode-cn.com/problems/goal-parser-interpretation/

请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成。Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ,"(al)" 解释为字符串 "al" 。然后,按原顺序将经解释得到的字符串连接成一个字符串。

给你字符串 command ,返回 Goal 解析器 对 command 的解释结果。



示例 1:

输入:command = "G()(al)"
输出:"Goal"
解释:Goal 解析器解释命令的步骤如下所示:
G -> G
() -> o
(al) -> al
最后连接得到的结果是 "Goal"
示例 2:

输入:command = "G()()()()(al)"
输出:"Gooooal"
示例 3:

输入:command = "(al)G(al)()()G"
输出:"alGalooG"


提示:

1 <= command.length <= 100
command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成

题解一:

class Solution:
    def interpret(self, command: str) -> str:
        ans=''
        i=0
        while i<len(command):
            if command[i]=='G':
                ans+='G'
                i+=1
            elif command[i:i+2]=='()':
                ans+='o'
                i+=2
            elif command[i:i+4]=='(al)':
                ans+='al'
                i+=4
        return ans

扩展:链表有环,如何判断相交?

分析:如果有环且两个链表相交,则两个链表都有共同一个环,即环上的任意一个节点都存在于两个链表上。因此,就可以判断一链表上俩指针相遇的那个节点,在不在另一条链表上。

无环链表和有环链表是不可能相交的;

两个有环链表若相交,其“整个环上”的所有node一定都重合;

有环链表的相交,情况只有2种:相交于”环上”或相交于”不是环的部分”,即下图所示;

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/link.png

https://cloud.tencent.com/developer/article/1045468

一.问题:QuerySet object has no attribute _meta

    filter() returns a QuerySet also if only one object if found. If you want to return just a model instance, use get()

    edit_content = models.Wikistore.objects.filter(id=edit_id)
    form = EditorTestForm(instance=edit_content)

    # 将filter改为get即可。

二.问题:django.db.utils.InternalError: (1050, “Table ‘wiki’ already exists”)

    $ python manage.py migrate wiki --fake 
    # wiki是自己的应用名
    $ python manage.py migrate

三.问题:执行python manage.py migrate无反应

已有model,修改后重新建模,于是将migrations文件夹中除__init__.py之外其他文件都删掉,再次执行以下步骤python manage.py makemigrations确认成功,执行python manage.py migrate,提示No migrations to apply. 
再次修改,指定表名,再次尝试,问题依旧。

1.排查

python manage.py dbshell 进到数据库里面,查看是否表已存在 
结果:表不存在
检查migrations文件 
结果:文件没问题

2.解决方案

$ python manage.py dbshell # 进入数据库
$ delete from django_migrations where app='your_appname';
$ python manage.py makemigrations(若migrations文件未删除,可不执行这一步)
$ python manage.py migrate # 成功

3.原因分析

(1)查看django_migrations表结构 
建表语句: 
CREATE TABLE "django_migrations" ("id" integer NOT NULL PRIMARY KEY AUTOINCREMENT, "app" varchar(255) NOT NULL, "name" varchar(255) NOT NULL, "applied" datetime NOT NULL); 

(2)原因 
造成多次应用migrations失败的原因是,当前model是修改过的,原来的migrations已经被我删除,但是,重新生成的migrations使用递增整数记名,所以,在django_migrations表中0001,0002等前面几个数字的文件都已被记录,在Django看来,被记录了就相当于已应用,所以,会出现刚开始的No migrations to apply.

4.避免方案

删除migrations文件,请同时到数据库中删除相应记录
可以继续生成新的migrations,旧的就不必理会了

5.其他

执行python manage.py migrate之后,可以使用python manage.py sqlmigrate appname migrations_num(例如python manage.py sqlmigrate user 0002)查看当前migrations文件对应的sql语句。 
另外,在使用上述命令查看0002文件的sql语句时发现,django会新建一个表user_new,然后插入user表中的数据,再把user表删掉,再把user_new重命名为user。所以,修改model的时候,不必担心原有数据会丢失。

四.问题:使用distinct的时候出现了以下问题,DISTINCT ON fields is not supported by this database backend

    文档中的用法:
    Author.objects.distinct()
    Entry.objects.order_by('pub_date').distinct('pub_date')
    Entry.objects.order_by('blog').distinct('blog')
    Entry.objects.order_by('author', 'pub_date').distinct('author', 'pub_date')
    Entry.objects.order_by('blog__name', 'mod_date').distinct('blog__name', 'mod_date')
    Entry.objects.order_by('author', 'pub_date').distinct('author')

    但是根据文档中的用法却出了上述问题

    后来找到原因,如果是使用mysql的话,distinct()中不能使用任何参数,参数应该在value()中使用
    正确使用方法:
    obj= Category.objects.values('parentcode','email').distinct()
    obj= Category.objects.values('parentcode').distinct()

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/ge-chong-pai-xu-suan-fa-tu-xie-zong-jie-by-ke-ai-x/

一、冒泡排序

https://www.cnblogs.com/heyuquan/p/bubble-quick-sort.html

一、思想

每次比较两个相邻的元素,如果他们之前的顺序不符就交换位置。
比如5个数从小到大排序,23,64,1,43,21
第一趟:
第一次比较:23,64,1,43,21
第二次比较:23,1,64,43,21
第三次比较:23,1,43,64,21
第四次比较:23,1,43,21,64
经过第一趟的比较后,最大的数字已经到最后面了,接下来只需要比较前四个数字,以此类推。
第二趟:1,23,21,43,64
第三趟:1,21,23,43,64
第四趟:1,21,23,43,64

冒泡排序每一趟只能对一个数进行归位,如果是n个数进行排序,则需要将n-1个数归位,即n-1趟操作
冒泡排序解决了桶排序浪费空间的问题,但是它效率很低。
时间复杂度:O(n^2)

二、用Python实现

`
#!/usr/bin/env python
# coding:utf-8

def bubbleSort(nums):
    for i in range(len(nums) - 1):
        for j in range(len(nums) - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

nums = [5, 6, 3, 1, 6, 2, 5, 33, 3]
print(bubbleSort(nums))
`

二、选择排序

一、思想

第1趟,在待排序记录r1 ~ r[n]中选出最小的记录,将它与r1交换;
第2趟,在待排序记录r2 ~ r[n]中选出最小的记录,将它与r2交换;
以此类推,第i趟在待排序记录r[i] ~ r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
原始数据:[3,1,0,8,4,2]
第一趟:[0,1,3,8,4,2]
第二趟:[0,1,3,8,4,2]
第三趟:[0,1,2,8,4,3]
第四趟:[0,1,2,3,4,8]
第五趟:[0,1,2,3,4,8]

二、用Python实现选择排序

`
def selectSort(nums):
    for i in range(len(nums)-1):
        print(i)
        min = i
        for j in range(i + 1, len(nums)):
            if nums[min] > nums[j]:
                min = j
        nums[i], nums[min] = nums[min], nums[i]
    return nums`

三、插入排序

一、思想

插入排序原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
其基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,是稳定的排
序方法。
时间复杂度为O(n^2)。

二、步骤

1. 从第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

二、用Python实现插入排序

`
#!/usr/bin/env python
# coding:utf-8

def insertSort(lists):
    for i in range(1, len(lists)):
        key = lists[i]
        j = i - 1
        while j >= 0:
            if lists[j] > key:
                lists[j + 1] = lists[j]
                lists[j] = key
            j -= 1
    return lists

lists = [4, 6, 2, 4, 7, 3, 9, 2, 1]
print(insertSort(lists))

`

四、快速排序

一、思想

快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序记录分割成独立的两部分,一种一部分记录的关键字均比另一部分记录的关键字小,最后再分别对这两部分记录继续进行排序,以达到整个序列有序。

一趟快读排序的具体做法是:附设两个指针low和high,初值分别为low和high,设枢轴记录关键字为pivotkey,则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录相互交换,然后从low所指位置起向后搜索,找到第一个关键字大于pivotkey的记录和枢轴记录相互交换,重复这两步直到low=high为止,过程如图:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/quickSort.jpg

二、用Python实现快速排序

`
#!/usr/bin/env python
# coding:utf-8

def quickSort(lists, left, right):
    if left >= right:
        return lists
    key = lists[left]
    low = left
    high = right
    print("111")
    while left < right:
        while (left < right and lists[right] >= key):
            right -= 1
        lists[left] = lists[right]
        while (left < right and lists[left] <= key):
            left += 1
        lists[right] = lists[left]
    lists[left] = key
    print("key")
    quickSort(lists, low, left - 1)
    quickSort(lists, left + 1, high)
    return lists


lists = [59, 3, 6, 3, 46]
print(quickSort(x, 0, 4))

`

def partition(arr, low, high):
    i = low-1
    pivot = arr[high]
    for j in range(low,high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1


def quickSort(arr, low, high):
    if low<high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    return arr


arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
print(quickSort(arr,0,len(arr)-1))

五、归并排序

时间复杂度:O(nlogn)
空间复杂度:O(n)

https://www.cnblogs.com/JMWan233/p/11175006.html

大文件排序:https://www.cnblogs.com/dream-of-cambridge/articles/8042311.html

5.1 递归

def mergeSort(arr):
    if len(arr) < 2:
        return arr
    mid = len(arr)//2
    left, right = arr[0:mid], arr[mid:]
    return merge(mergeSort(left), mergeSort(right))


def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

print(mergeSort([1, 7, 5, 6, 9, 0, 10, 20, ]))

http://10.160.59.114/web/searchList.jsp?v=5&from=index&pid=sogou-waps-7880d7226e872b77&w=1274&t=1607593533262&s_t=1607593620931&s_from=index&pg=webSearchList&inter_index=&keyword=baidu&suguuid=ec4c985f-a61f-4638-bf33-c45a765ae712&sugsuv=&sugtime=1607593620931&dump=1

http://10.160.67.72/web?query=baidu&_asf=www.sogou.com&_ast=&w=01019900&p=40040100&ie=utf8&from=index-nologin&s_from=index&sut=13051&sst0=1607593834109&lkt=2%2C1607593832605%2C1607593832773&sugsuv=&sugtime=1607593834109&dump=1

5.3 多路归并

https://www.cnblogs.com/dream-of-cambridge/articles/8046031.html

六、桶排序

http://www.chenxm.cc/article/981.html