- 博客(30)
- 收藏
- 关注
RSS订阅原创 leetcode python3 通配符匹配
代码思路：基于动态规划的思想，首先进行状态方程的初始化，其中dp[0][0]表示s和p为空，其值为 true；第一行 dp[0][j]，换句话说，s 为空，与 p 匹配，所以只要 p 开始为 * 才为 true。接下来设计状态转移方程， 当 s[i] == p[j]，或者 p[j] == ? 那么 dp[i][j] = dp[i - 1][j - 1];当 p[j] == * 那么 dp[i][j...
2020-03-30 08:41:51
167
原创 leetcode python3 加油站
代码思路：采用双指针遍历方法，首先判断总油量是否大于总耗油量，是则必能完成行驶人物，反之无法完成，若可以，开始遍历，初始化车的起点指针i，若该点的油量不足，则起点指针右移，若油量可以行驶至下一站点，则初始行驶指针j，开始判断行驶下一站点后油量是否可以继续行驶，若不可以则令起点指针i等于行驶指针j，直至完成循环class Solution: def canCompleteCircuit(s...
2020-03-29 09:12:26
153
原创 leetcode python3 跳跃游戏
代码思路：关注数组中的0值，从后往前推，遇0检测是否可以跳过即可class Solution: def canJump(self, nums: List[int]) -> bool: if len(nums)==0: return False elif len(nums)==1: return True...
2020-03-28 09:38:32
120
原创 leetcode python3 分发饼干
代码思路：基于双指针遍历的思想，首先对给出数组进行排序，然后开始扫描两数组，检测当前饼干是否可以满足小朋友，记录满足该条件的结果res，直至两数组全部扫描完class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: res,i,j=0,0,0 g....
2020-03-27 07:56:13
126
原创 leetcode python3 判断子序列
代码思路：利用双指针思想，逐一比较两字符串中各个字符是否相等，若s是t的子序列，则指向s的指针必会到达s末尾。class Solution: def isSubsequence(self, s: str, t: str) -> bool: i,j=0,0 res=False while i<len(s) and j<len...
2020-03-26 08:49:18
132
原创 leetcode python3 买卖股票的最佳时机 II
代码思路：采用贪心算法思想，遍历股票价格，若当天价格比前一天的高，则保留差值视为买入，直至全部遍历完成，返回总利润class Solution: def maxProfit(self, prices: List[int]) -> int: res=0 for i in range(len(prices)-1): if pric...
2020-03-25 08:01:45
164
原创 leetcode python3 恢复二叉搜索树
代码思路：中序遍历，结果中如果有一个降序对，说明该两个node需交换；若有两个降序对，说明第一对的前一个node和第二对的后一个node需要交换。class Solution: def __init__(self): self.res = [] def inorderTraversalSon(self,root): if root is not N...
2020-03-24 09:25:19
70
原创 leetcode python3 二叉树的中序遍历
代码思路：利用递归思想，一次输出当前的左子树、根节点和右子树，直到所有树的根节点全部搜索完毕class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res=[] def inorderTraversalSon(root): if root...
2020-03-23 07:58:41
134
原创 leetcode python3 不同的二叉搜索树
代码思路：利用递归思想，遍历1到n的数字i作为根节点，i左侧的点为该树的左节点，右侧的点为右节点，递归得到所有左子树和右子树后将结果输出# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = No...
2020-03-22 09:16:32
66
原创 leetcode python3 二叉树的最大深度
代码思路：利用递归思想，进行二叉树深度判断class Solution: def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 else: left_height = self.maxDepth(root.left...
2020-03-21 08:15:17
107
原创 leetcode python3 对称二叉树
代码思路：利用递归思想，检测每一根结点是否两两相等，且每个树右子树与另一个树的左子树相等class Solution: def isSymmetric(self, root: TreeNode) -> bool: def isMirror(p,q): if p == None and q == None: re...
2020-03-20 08:01:09
101
原创 leetcode python3 相同的树
代码思路：采用递归思想，逐级判断树节点是否相等或为空，搜索完毕即可得到最终答案class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: def cheak(p, q): if p == None and q == None: ...
2020-03-19 08:58:13
593
原创 leetcode python3 正则表达式匹配
代码思路：利用动态规划思想，设定dp[i][j]为s的前i个字符串与p的前j个字符串是否匹配，初始化第一行后进入动态规划循环，一般有下述几种情况：s[i-1]==p[j-1]两字符相等，只需继承前一状态dp[i-1][j-1]即可s[i-1]！=p[j-1] and p[j-1]==’.’两字符不等，且p当前字符为点，只需继承前一状态dp[i-1][j-1]即可s[i-1]！=p[j-...
2020-03-18 11:01:47
84
原创 leetcode python3 最长回文子串
代码思路：利用动态规划算法思路，若“aba”为回文，则去头去尾，“a”亦必为回文，将字符串每个点作为一回文，搜索符合条件的二回文、三回文。。。存储最长回文并返回class Solution: def longestPalindrome(self, s: str) -> str: res="" n=len(s) if n==1: ...
2020-03-17 09:41:45
77
原创 leetcode python3 无重复字符的最长子串
代码思路：j 表示子串终止位置，i表示字串起始位置 当未出现重复时，字符串的长度即为字符串的结束位置减去起始位置。发生重复时，重新利用字符串的结束位置j减去新的起始位置i，并与之前的未重复字串的长度作比较取较大者class Solution: def lengthOfLongestSubstring(self, s: str) -> int: s1 = {} ...
2020-03-16 08:10:48
90
原创 leetcode python3 有效的括号
代码思路：若存在满足条件的括号，必定有一个或一个以上的成对顺序括号，重复删除知道没有满足条件的括号对出现，返回结果class Solution: def isValid(self, s): while '{}' in s or '()' in s or '[]' in s: s = s.replace('{}', '') s...
2020-03-15 09:42:37
95
原创 leetcode python3 最长公共前缀
代码思路：利用分治思想，两两比较找到公共前缀，直至全部比较完class Solution: def twoCommonPrefix(self, s1: str, s2: str) -> str: for i,x in enumerate(s1): if i==len(s2) or x!= s2[i]: retu...
2020-03-14 10:39:43
103
原创 leetcode python3 罗马数转整数
代码思路：建立一个HashMap来映射符号和值，然后对字符串从左到右来，如果当前字符代表的值不小于其右边，就加上该值；否则就减去该值。以此类推到最左边的数，最终得到的结果即是答案class Solution: def romanToInt(self, s: str) -> int: a = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100...
2020-03-13 08:03:46
78
原创 leetcode python3 合并K个排序链表
代码思路：分治思想，K个链表两两配对，合并排序，重复此过程直到合并所有链表class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: res=ListNode(None) node=res while l1 and l2: ...
2020-03-12 16:32:19
99
原创 leetcode python3 删除链表的倒数第N个节点
代码思路：采用双指针，快指针先走n次，接下来快慢指针同时走，直到快指针走完时，慢指针所在位置即为需要删除的节点class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: slow=head fast=head while n>0:...
2020-03-11 09:41:02
100
原创 leetcode python3两数相加
代码思路：从l1与l2分别取数求和，以和与10的余数作为结果链表的新一位数，重复至l1与l2取完，查验和数是否还有剩余数，完成输出class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: res=ListNode(None) node=res ...
2020-03-10 09:51:54
72
原创 leetcode python3 环形链表
代码思路：利用快慢指针遍历链表，若存在环形链表，两指针必相遇，否则快指针会先遍历完成class Solution: def hasCycle(self, head: ListNode) -> bool: show=fast=head while fast and fast.next: show=show.next ...
2020-03-09 09:17:08
105
原创 leetcode python3 删除排序链表中的重复元素
代码思路：首先判断链表是否不存在节点或只有一个节点，答案为真则返回原链表，若答案为假，则比较当前节点与下一节点的值，若两值相等则排除后者，不相等则节点指针后移，直至链表比较完成class Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: node=head if nod...
2020-03-08 10:01:04
94
原创 leetcode python3 合并两个有序链表
代码核心思路：比较两链表的值，将小值赋给结果链表，并后移小值所在链表的指针。class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: res=ListNode(None) node=res while l1 and l2: ...
2020-03-07 15:42:49
130
原创 leetcode python3 买卖股票的最佳时机 III
代码思路：设定每一天结束后的状态，未持股0卖出为状态0，已持股0卖出为状态1，未持股1卖出为状态2，已持股1卖出为状态3，未持股2卖出为状态4，初始化第一天的各种状态后，根据当前状态的改变原因以及前一天的状态设定每一天状态的值，完成所有每一天的遍历后，最大股票利益必定为0、状态3和状态5三者的最大值class Solution: def maxProfit(self, prices: L...
2020-03-06 11:41:05
263
原创 leetcode python3 最接近的三数之和
代码思路：先排序，后遍历，利用双指针进行比较，重点是通过三数之和缩小最相似数值所在位置class Solution: def threeSumClosest(self, nums: List[int], tar: int) -> int: nums.sort() n=len(nums) res=float("inf") ...
2020-03-05 12:45:41
234
原创 leetcode python3 三数之和
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() n=len(nums) ans=[] for i in range(0,n-2): if nums[i]>0: break...
2020-03-04 13:32:46
109
原创 leetcode python3 移除元素
class Solution: def removeElement(self, nums: List[int], val: int) -> int: lens=len(nums) i=0 while i<lens: if (nums[i]==val): del nums[i]...
2020-03-03 10:18:19
78
原创 leetcode python3 删除排序数组中的重复项
class Solution: def removeDuplicates(self, nums: List[int]) -> int: lens=len(nums) i=0 while i<lens-1: if (nums[i]==nums[i+1]): del nums[i...
2020-03-02 10:55:02
91
原创 leetcode python3 两数之和
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: #初始化 lens=len(nums) for i in range(0,lens-1): for j in range(i+1,lens): ...
2020-03-01 10:11:41
63
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人