麻豆出品

题解

/ 注册

全部文章 / 题解（共8篇）

最长回文子串（python，动规/马拉车）

思路1（动态规划，O(n^2)）从第一个字符往后遍历，把每个字符都当作中心去向两边扩散，依次比较对称位置是否相等，当碰到左右边界停下。注意要分奇偶子串两种情况。代码1 class Palindrome: def getLongestPalindrome(self, A, n): ...

2020-09-13

12 1997

二叉树先序、中序、后序遍历（python版）

最近东京有点热，撸道二叉树遍历解解暑气。思路：二叉树遍历没啥难度，按照常规操作递归遍历即可。先序：根左右中序：左根右后序：左右根代码： class TreeNode: def __init__(self, x): self.val = x self.le...

2020-09-08

84 4712

合并K个有序链表(分治+递归)(python版）

首先吐槽一下，有些老铁采用了这种投机取巧的方法：直接遍历列表，取出每个链表里面的值然后进行数组排序，最后再依次插入到一个新链表中。喂，你要这么写，那面试官只能面带微笑的告诉你：“写的不错，今天的面试就先到这里吧。”很明显这种解法走偏了，自己刷题可以试，面试可别这么整。这种题其实就是两个有序链表合并...

2020-09-06

10 2401

设计LRU缓存结构（python版）

这题文字有点多呀，实际上是让你设计数据结构：⾸先要接收⼀个 capacity 参数作为缓存的最⼤容量，然后实现两个 API，⼀个是 put(key, val) ⽅法存⼊键值对，另⼀个是 get(key) ⽅法获取 key 对应的 val，如果 key 不存在则返回 -1。要让 put 和 get...

2020-09-06

18 3396

反转链表（python版）

反转链表是个老生常谈的问题了，可谓是链表的入门级问答。思路：给定一个单链表，将其反转。其实很容易想到，只需要修改每个结点的指针指向：即令后一个结点指向前一个结点，并且将表头指针指向最后一个结点即可。这个过程可以用循环实现，也可以用递归来实现。代码1（非递归版） class ListNode: ...

2020-09-06

23 3830

合并有序链表（python版）

跟合并有序数组差不多套路，就是数据结构麻烦些。思路：先选出第一个节点，然后遍历两个链表，把小的作为当前节点的下一个节点，一直到其中一个链表遍历完，这时候把另一个链表直接接上。当然实现起来有递归和非递归版本，看你喜欢哪个啦，都没毛病，不过递归可能代码更短小精湛些。代码1（非递归版）： class L...

2020-09-06

19 1097

合并两个有序数组（python版）

归并排序的套路，按照下面套路来就完事了。思路: 双指针从A和B的m、n尾部遍历比较A和B的m、n尾部的值，将较大值赋给A整体数组的尾部，指针左移注意特殊情况处理：A的尾指针已遍历结束，B尾指针还未结束。代码： # @param A int整型一维数组 # @param B int整型一维...

2020-09-06

55 3522

寻找第K大O(n)解法（快排+二分）

最近面试东京株式会社遇到这个题，特地来刷一下。思路：快排+二分，与快排不同的是，利用二分法每次都减少了一半的不必要排序。当high=low小于k的时候，在后半部分搜索，当high=low大于k的时候，在前半部分搜索。代码： # -*- coding:utf-8 -*- import sys def...

2020-09-05

30 4460