6 李旭东

学生身份

我要认证

研究方向:深度学习,迁移学习,AutoDL,工业设备健康管理 让深度玄学再auto一点

等级
TA的排名 4w+

数据结构与算法——一个模板手撕滑动窗

一、滑动窗模板参考自leetcodedef solution(s, t): # hash_记录t中字符出现的次数,window记录窗口中相应字符出现的次数 hash_, window = {}, {} # 根据t构建hash_字典 for c in t: hash_[c] = hash_.get(c, 0) + 1 # 初始化窗口左右边界,左闭右开区间 [left, right) left, right = 0, 0 # valid表示窗口中满足要求的字符的个数 valid =

2020-07-13 15:36:06

数据结构与算法——使用优先队列的题目

一、数组中第k大元素此题为leetcode第215题一、数据流中的第k大元素此题为leetcode第703题思路:建立小根堆,维护长度为k。添加元素时,列表元素小于k时直接添加,否则新元素大于堆顶元素时,替换堆顶元素。import heapqclass KthLargest: def __init__(self, k: int, nums: List[int]): self.nums = nums self.k = k heapq.heap

2020-06-29 10:16:16

数据结构预算法——使用栈和队列的题目

一、柱状图中最大的矩形此题为leetcode第84题思路:枚举每一根柱子i的高度hight[i],随后我们需要进行向左右两边扩展,使得扩展到的柱子的高度均不小于h。换句话说,我们需要找到左右两侧最近的高度小于h的柱子,这样这两根柱子之间(不包括其本身)的所有柱子高度均不小于h,并且就是i能够扩展到的最远范围。使用单调栈可以实现这样的功能,即栈中元素都是单调递增或递减的。这里我们使用单调递增的栈。(1)当前位第i个柱子,栈中存放j值,j为i左边的柱子。从栈底到栈顶,j的值严格单调递增,同时对应的高度值

2020-06-29 17:08:36

数据结构与算法——DFS/BFS题目

一、电话号码的字母组合此题为leetcode第17题思路:使用深度优先搜索。在每次递归时有个变量combination,表示当前递归深度下的字母组合,如果它的长度等于digits的长度,那么说明递归到了最深,将它放入答案中。否则遍历下一个digits里的字母,将其与combination结合传入下层递归。class Solution: def letterCombinations(self, digits: str) -> List[str]: self.phone =

2020-07-01 17:33:21

数据结构与算法——二叉树的题目

一、二叉搜索树的最近公共祖先此题为leetcode第235题思路:因为此题的前提是二叉搜索树,有个很好的性质即根节点的左子树的值都小于根节点,右子树的值都大于根节点。因此给定两个值p和q,如果p和q都小于根节点的话说明他们一定在左子树,继续在左子树寻找,对于右子树也是如此;如果p和q有一个小于等于根节点而另一个大于等于根节点,说明当前根节点便是最近公共祖先。class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: '

2020-06-28 21:27:18

数据结构与算法——动态规划系列题目

一、最长回文子串此题为leetcode第5题思路:此题的“中心扩展法”在前面已经讲过,这里解释动态规划解法。设状态dp[i][j]的含义是在区间[i, j]的字符串是否为回文串。如果[i+1, j-1]区间内已经是回文串了,那么只要s[i] == s[j]那么[i, j]区间的字符串便是回文串。另外要主要内外循环的次序。一般是先循环i再循环j,但在这里会导致参考的状态还没有被计算出来。比如当下计算dp[i][j],会用到dp[i+1][j-1],由于先循环的i所以这个状态还没有被计算出来。因此要先循环j

2020-06-27 11:07:58

数据结构与算法——高智商犯罪之打家劫舍

题目以偷东西为背景,但偷东西肯定是违法的,我们千万不能用动态规划去偷东西,用什么算法都不可以,程序员虽然苦逼但这是正当行业,哪怕去摆地摊啊,让我们一起抵制偷窃,共建社会主义和谐社会一、打家劫舍此题为leetcode第198题思路:设状态dp[i]的含义是到第i家时所偷窃到的最高金额。如果偷窃第i家,那么第i – 1家肯定没有被偷窃,偷窃的金额只能是第i-2家加上第i家的。如果不偷窃第i家,那么第i-1家肯定被偷窃了,当前偷窃的金额就是第i-1家。状态转移方程为:dp[i]=max(dp[i−2]+n

2020-06-26 16:15:33

数据结构与算法——经典背包问题

一、0-1背包问题https://www.acwing.com/problem/content/description/2/思路:设状态dp[i][j]的含义是装入前i件物品装入容量为j的背包里时的最大总价值,那么状态转移方程为:因为dp[i][j]只和dp[i-1][j]有关,所以状态可以转为一维的。在遍历j的时候,要逆序遍历,因为要保证较小的j是上一轮的状态:比如i = 3, j = 8, v[3] = 5, w[3] = 1,一维的转移方程为dp[8] = max(dp[8],dp[3]

2020-06-25 16:45:23

数据结构与算法——令人烦恼的括号

一、有效的括号此题在《数据结构与算法——栈与队列》中出现二、括号生成此题在《数据结构与算法——广度优先与深度优先搜索》中出现三、最长有效括号此题为leetcode第32题思路:考虑使用动态规划,定义状态dp[i]为以第i个元素结尾的最长有效括号的长度。有效的括号一定是以“)”结尾的,因此我们只需考察以“)”的字符,状态转移方程如下图所示。注意dp的边界条件,图中并没有体现出来。class Solution: def longestValidParentheses(self, s: s

2020-06-21 01:32:34

数据结构与算法——数学相关

一、整数反转此题为leetcode第7题思路:基本思路就是,初始化y = 0,进入while循环,令y = y * 10 + x % 10,并且x = // 10,当x != 0的时候继续循环,最后返回y。这里需要注意几点:(1)x是有符号整数,取余的时候要对x的绝对值取余,否则负数取余会有问题;(2)此题有范围限制,循环的时候需要判断一下y的范围;(3)当x是负数的时候,返回的y注意也加上负号class Solution: def reverse(self, x: int) -> in

2020-06-19 19:20:07

数据结构与算法——其他关于字符串的题目

一、二、三、二进制求和此题为leetcode第67题思路:由于a、b字符串长度不一定相等,因此可以右对齐然后前面填0使两者对其,使用字符串的zfill()方法。然后从后面依次遍历,设置一个初始为0的carry标志位,如果字符为’1’,那么carry+1。如果carry为2或0,那么当前位变为0;如果carry为1或3,那么当前位边为1。当然还有进位需要考虑,carry为2或3时需要进1位,carry为0或1时不需要进位,那么carry变为carry // 2即可。class Solution:

2020-06-17 00:24:49

数据结构与算法——字符串的中心扩展

一、最长回文子串此题为leetcode第5题思路:根据回文字符串的特点,如果以字符a为中心,各向两边扩散一个字符,这两个字符一样的话这个子串一定是回文子串,并且可以继续扩散;若扩散的两个字符不一样,那么这个子串一定不是回文子串,并且无法继续扩散。中心扩散的另一种形式是以一个空字符为中心向两边扩散,扩散的条件和上面的一样。所以我们需要定义一个check函数,传入开始扩散的左右起始点,一步一步向两边扩散,直到组不成回文子串位置,返回这个子串的长度。class Solution: # 扩展中心

2020-06-15 19:29:23

数据结构与算法——日取其半之二分查找

一、搜索选择排序数组此题为leetcode第33题思路:和常规的二分法套路差不多,定义左右指针left和right,求得中间值mid,此时有一半数组肯定是有序的,如下图所示。如果nums[left] < nums[mid],那就是[left, mid]有序,如果nums[left] <= target < nums[mid],那么就在左半边找,否则在右半边找。如果有nums[mid] < nums[right],那就是[mid, right]有序,如果nums[mid] <

2020-06-14 18:34:28

数据结构与算法——小小数组也不简单

一、下个排列此题为leetcode第31题思路:如果希望下个数比现在的大,那么可以将后面的某个大数与前面的某个小数交换,就可以得到一个比现在大的数。并且由于是字典序中的下个数,那么这两个数的增幅还要最小。比如123564,我们将5和6交换得到123654,但它不是字典序中的下个更大的排列,5和4交换后的123645才是。因此我们可以从数组的最后开始遍历,如果是升序的话就一直往前走。如果遇到非升序的数nums[i],那么从这个升序序列的开头开始遍历,找到第一个比nums[i]小的数nums[j],交换这两

2020-06-13 17:17:58

数据结构与算法——小小链表不简单

一、两数相加此题为leetcode第2题思路:链表的头结点是个位,依次往后是十位、百位等,在每位的数相加时可能有进位,我们要预先有个进位flag=0,后续可能为0也可能为1,每次相加时都要加上这个进位。加完后的数可能大于10,如果大于10则flag=1,否则flag=0。然后这个数取余便是这位相加后的结果。同时以此遍历两个链表,一个到结尾时另一个继续遍历。class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -&

2020-06-11 17:59:08

leetcode高频题——双指针

一、盛最多水的容器此题为leetcode第11题思路:用两个指针指向数组的头尾,以上面的1、7为例,此时水的容量为min(1, 7) * 8=8。然后考虑移动指针,因为水的容量是由最小的那个数决定的,所以应该移动数小的那个指针,这样后面才有机会得到一个大数,使得水的容量变大。class Solution: def maxArea(self, height: List[int]) -> int: if len(height) < 2: retu

2020-06-09 23:32:08

数据结构与算法——万万想不到的位运算

一、出现一次的数字这一系列的题用哈希很容易做出来,但这些题最想考察的是位运算。1、出现一次的数字I此题为leetcode第136题思路:利用异或操作一个数字a和0进行异或操作,得到的是自己:a⨁0=a一个数字和自己进行异或,得到的是0:a⨁a=0异或满足交换律和结合律:a⨁b⨁a=(a⨁a)⨁b=0⨁b=b对所有数字进行异或操作即可得到只出现一次的数。class Solut...

2020-04-24 22:16:21

数据结构与算法——优先队列

一、优先队列优先队列按照队列的方式正常入队,但按照优先级出队。有两种实现方式:堆(二插堆、多项式堆等等)和二叉搜索树数据流中的第k大元素leetcode第703题...

2020-04-09 22:12:29

数据结构与算法——并查集

一、并查集并查集(Union & find) 是一种树形的数据结构,用于处理一些不交集(Disjoint sets)的合并与查询的问题。初始化时把每个点所在集合初始化为其自身。Find: 确定元素属于哪一个子集,它可以被用来确定两个元素是否属于同一子集。Union: 将两个子集合并成同一个子集。如下图所示,一开始有7个字母,每个都指向自己:根据某种规则,将相关的字母合并起来,即...

2020-04-18 00:46:22

数据结构与算法——LRU缓存

一、LRU缓存LRU(least recently used)最近最少使用缓存机制,在计算机的缓存满时,会最先淘汰近期最少使用的数据。示意图如下图所示:设缓存的大小为5,在缓存未满之前,ABCDEF依次进入缓存。当要缓存F时,A近期没有被使用,因此淘汰掉,F放到头的位置,剩下的往后挪。当再次进来C的时候,因为缓存里已经有C了,因此把C提到缓存的头来。再进来G的时候,G放到头,剩下的往后挪。二...

2020-04-15 18:06:19

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 脉脉勋章
    脉脉勋章
    绑定脉脉第三方账户获得
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 分享达人
    分享达人
    成功上传6个资源即可获取