406. 根据身高重建队列

406. 根据身高重建队列

排序+插入

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))
        ans = []
        for i in range(len(people)):
            ans.insert(people[i][1], people[i])
        return ans

797. 所有可能的路径

797. 所有可能的路径

深度优先遍历

class Solution:
    def __init__(self):
        self.ans = None

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.ans = []
        self.dfs(0, graph, [0])
        return self.ans

    def dfs(self, item, graph, path):
        if item == len(graph) - 1:
            self.ans.append(list(path))
            return
        for i in range(len(graph[item])):
            path.append(graph[item][i])
            self.dfs(graph[item][i], graph, path)
            path.pop()

2580. 统计将重叠区间合并成组的方案数

2580. 统计将重叠区间合并成组的方案数

求出有多少组

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        ranges.sort(key=lambda x: x[0])
        cnt = 1
        for i in range(1, len(ranges)):
            if ranges[i][0] > ranges[i - 1][1]:
                cnt += 1
            else:
                ranges[i][1] = max(ranges[i - 1][1], ranges[i][1])
        return (2 ** cnt) % (10 ** 9 + 7)

139. 单词拆分

139. 单词拆分

动态规划

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDict = set(wordDict)
        dp = [False for i in range(len(s) + 1)]
        dp[0] = True
        for i in range(1, len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[-1]