最详解析：https://blog.csdn.net/qq_17550379/article/details/82871892 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例:输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。方法一：动态规划 记录每个元素前面出现的比它小的元素个数。lst = [10,9,2,5,3,7,101,18] l = len(lst) if l <= 1:print(l) else:data = [1]*lfor i in range(1, l):for j in range(i):if lst[i]...
原题 https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/ 解法 BFS. 由于题意要求先按照x顺序排列, 再按照y倒序排列, 最后按照节点的值顺序排列, 我们构建字典d, 格式为d[x] = [(y, node.val)], 用q储存每层的(node, x, y), 将每层的信息放入字典d. 然后对d的键进行升序排列, 得到每层的列表, 然后对列表先按照y倒序排列, 再按照node.val顺序排列, 最后将每层的node.val放入ans即可. Time: O(n) Space: O(...
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。 示例 1：输...
所有Leetcode题目不定期汇总在 Github, 欢迎大家批评指正，讨论交流。'''Remove all elements from a linked list of integers that have value val.Example:Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5'''# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def removeElements(self, head: ListNode, val...
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。 示例：输入： {“KaTeX parse error: Expected }, got EOF at end of input: …":"1","next":{"id”:“2”,“next”:null,“random”:{“KaTeX parse error: Expected EOF, got } at position 9: ref":"2"}?,"val":2},"rand…ref”:“2”},“val”:1} 解释： 节点 1 的值是 1，它的下一个指针和随机指针都...
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。 例如，从根到叶子节点路径 1->2->3 代表数字 123。 计算从根到叶子节点生成的所有数字之和。 说明: 叶子节点是指没有子节点的节点。 示例 1: 输入: [1,2,3]1/ 2 3输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25. 示例 2: 输入: [4,9,0,5,1]4/ 9 ...
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。 例如, 给定二叉搜索树:4/ 2 7/ 1 3和 插入的值: 5你可以返回这个二叉搜索树: 4/ 2 7/ \ /1 3 5或者这个树也是有效的: 5/ 2 7/ \ 1 ...
递归和非递归方法中序遍历二叉树 Leetcode题 递归方法：# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution(object):def inorderTraversal(self, root):""":type root: TreeNode:rtype: List[int]"""ans = []if root==None:return ansself.inTraverse(root, ans)return ansdef inTrave...
解答： class Solution(object):def countPrimes(self, n):""":type n: int:rtype: int"""if n < 3:return 0prime = [1] * nprime[0] = prime[1] = 0for i in range(2, int(n**0.5)+1):if prime[i] == 1:prime[i*i:n:i] = [0]*len(prime[i*i:n:i])return sum(prime)总结： 厄拉多塞筛法：西元前250年，希腊数学家厄拉多塞(Eeatosthese)想到了一个非常美妙的质数筛法，减少了逐一检查每个数的的步骤，可以比较简单的从一大堆数字之中...
题目：24. Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the lists nodes, only nodes itself may be changed. Example:Given 1->2->3->4, you should return the list as 2->1->4->3. 题意： 给一个单链表，返回相邻节点相互交换后的新链表。 分析： 如果不注意上面大大的note ，直接依次遍历交换相邻节点的值，即可得到结果。如Code1. 但既...
反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""p=headres=Nonewhile p:res,res.next,p=p,res,p.nextreturn res
题意： 给定一个二叉树，返回它的后序遍历。 示例： 输入: [1,null,2,3] 12/3 输出: [3,2,1]中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则： （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点 方法一： 递归 class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:if root == None:return []res = []res += self.postorderTraversal(root.left)res += s...
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。示例 1:输入: ["flower","flow","flight"] 输出: "fl" 示例 2:输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明:所有输入只包含小写字母 a-z 。这题比较好理解，给定一个列表，查询列表中的公共前缀 自己的想法是直接暴力法解决，将列表的第一个值作为对比值，通过一层for循环不断遍历对比值与其他元素是否相等，如果...
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。 示例 1: 输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true 示例 2: 输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false 进阶: 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。 这会影响到...
题目： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 解答： 方法一：原地反转。# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:def reverseList(self, head: ListNode) -> ListNode:# cur当前节点# pre为当前节点的上...