class Solution:
    def canFinish(self, numCourses, prerequisites):
        indegrees = [0] * numCourses  # 度列表
        adjacency = [[0 for i in range(numCourses)] for i in range(numCourses)]  # 邻接矩阵　表示节点之间关系
        print('==init adjacency:', adjacency)
        for cur, pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre][cur] = 1
        print('==init adjacency complete:', adjacency)
        print('==init indegrees complete:', indegrees)

        quene = []
        for i in range(len(indegrees)):
            if indegrees[i] == 0:
                quene.append(i)
        print('==quene:', quene)
        num_nodes = 0
        learn_nodes = []
        while quene:
            node = quene.pop()
            learn_nodes.append(node)
            num_nodes += 1
            for j in range(numCourses):
                if adjacency[node][j] == 1:
                    next_node = j
                    adjacency[node][j] -= 1
                    indegrees[next_node] -= 1
                    if indegrees[next_node] == 0:
                        quene.append(next_node)
        print('==num_nodes:', num_nodes)
        print('=learn_nodes:', learn_nodes)
        return learn_nodes if num_nodes == numCourses else []

# numCourses = 2
# prerequisites = [[0, 1]]
numCourses = 4
prerequisites = [[1, 0], [2, 0], [3,1],[3,2]]
sol = Solution()
sol.canFinish(numCourses, prerequisites)

57.实现 Trie (前缀树)

思路:利用字典存储每个单词，同时用特殊字符结尾。

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.word_end = -1

    def insert(self, word):
        """
        Inserts a word into the trie.
        """
        curNode = self.root
        for c in word:
            if c not in curNode:
                curNode[c] = {}
            curNode = curNode[c]
        curNode[self.word_end] = True
        # print('==curNode:', curNode)


    def search(self, word):
        """
        Retu
        rns if the word is in the trie.
        """
        curNode = self.root
        for c in word:
            if c not in curNode:
                return False
            curNode = curNode[c]
        if self.word_end not in curNode:
            return False
        return True


    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        curNode = self.root
        for c in prefix:
            if c not in curNode:
                return False
            curNode = curNode[c]
        return True

word = 'apple'
prefix = 'ad'
obj = Trie()
obj.insert(word='apple')
obj.insert(word='add')
# obj.insert(word='app')
print('tree:', obj.root)
param_2 = obj.search(word)
print('search res:', param_2)
param_3 = obj.startsWith(prefix)
print('==param_3:', param_3)

class Solution:
    def quicksort(self, arr):
        if len(arr) <= 1:
            return arr
        privot = arr[len(arr) // 2]
        left = [i for i in arr if i < privot]
        middle = [i for i in arr if i == privot]
        right = [i for i in arr if i > privot]

        # left = [arr[i] for i in range(len(arr)) if arr[i] < privot]
        # middle = [arr[i] for i in range(len(arr)) if arr[i] == privot]
        # right = [arr[i] for i in range(len(arr)) if arr[i] > privot]

        return self.quicksort(left) + middle + self.quicksort(right)

    def findKthLargest(self, nums, k):

        return self.quicksort(nums)[::-1][k-1]

# nums = [3, 2, 1, 5, 6, 4]
# k = 2
nums = [3,2,3,1,2,4,5,5,6]
k = 4
sol = Solution()
res = sol.findKthLargest(nums, k)
print('res:', res)

class Solution:
    def findKthLargest(self, nums, k):
        arr = []
        heapq.heapify(arr)
        for i in range(k):
            heapq.heappush(arr, nums[i])
        for i in range(k, len(nums)):
            heapq.heappush(arr, nums[i])
            heapq.heappop(arr)
        print('==arr:', arr)
        return arr[0]

arr = [3,2,1,5,6,4]
k = 2
sol = Solution()
sol.findKthLargest(arr, k)

class Solution:
    def maximalSquare(self, matrix):
        max_side = 0
        h,w = len(matrix),len(matrix[0])
        dp = [[0 for i in range(w)] for i in range(h)]
        print('初始化dp',np.array(dp))
        for i in range(h):
            dp[i][0] = int(matrix[i][0])
            max_side = max(max_side, dp[i][0])
        for i in range(w):
            dp[0][i] = int(matrix[0][i])
            max_side = max(max_side, dp[0][i])
        print('初始化边界dp',np.array(dp))

        for i in range(1,h):
            for j in range(1,w):
                if matrix[i][j]=='1':
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
                max_side = max(max_side, dp[i][j])
        print('转移好dp',np.array(dp))
        return max_side**2


matrix = [["1","0","1","0","0"],
          ["1","0","1","1","1"],
          ["1","1","1","1","1"],
          ["1","0","0","1","0"]]
# matrix = [["0","1"],["1","0"]]
sol = Solution()
res=  sol.maximalSquare(matrix)
print(res)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return None
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right
        root.right = left
        return root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr){
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        stack= []
        while head:
            stack.append(head.val)
            head = head.next
        return stack==stack[::-1]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> res;
        while(head){
            res.push_back(head->val);
            head = head->next;
        }
        int left=0;
        int right=res.size()-1;
        while(left<right){
            if(res[left]==res[right]){
                left+=1;
                right-=1;
            }
            else{
                return false;
            }
        }
        return true;

    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root==p or root==q:#递归终止条件　节点为空　或者节点等于p,q其中之一
            return root
        left = self.lowestCommonAncestor(root.left, p, q)#遍历左子树
        right = self.lowestCommonAncestor(root.right, p, q)#遍历右子树
        if left is None:#左子树为空　就去右子树　
            return right
        if right is None:#右子树为空　就去左子树　
            return left
        return root#左右子树都不为空　说明找到了节点　

#超时时间复杂度O(N)
class Solution:
    def productExceptSelf(self, nums):
        output = len(nums)*[0]
        for i in range(len(nums)):
            temp = 1
            for j in nums[:i]:
                temp*=j
            for j in nums[i+1:]:
                temp*=j
            output[i] = temp

        # print('==output:', output)
        return output

nums = [1, 2, 3, 4]
sol = Solution()
sol.productExceptSelf(nums)

class Solution:
    def productExceptSelf(self, nums):
        length = len(nums)
        L,R,output = [0]*length,[0]*length,[0]*length
        L[0] = 1
        for i in range(1, length):
            L[i] = L[i-1]*nums[i-1]
        print('==L:', L)

        R[length-1] = 1
        for i in range(length-2, -1, -1):
            print('==i:', i)
            R[i] = R[i + 1] * nums[i + 1]
        print('==R:', R)
        for i in range(length):
            output[i] = L[i]*R[i]
        return output

nums = [1, 2, 3, 4]
sol = Solution()
sol.productExceptSelf(nums)

class Solution:
    def maxSlidingWindow(self, nums, k):
        #时间复杂度O(Nk)超时了
        res = []
        for i in range(len(nums)-k+1):
            res.append(max(nums[i:i+k]))
        return res