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

最近东京有点热，撸道二叉树遍历解解暑气。思路：二叉树遍历没啥难度，按照常规操作递归遍历即可。先序：根左右中序：左根右后序：左右根 代码： class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None # # @param root TreeNode类 the root of binary tree # @return int整型二维数组 # class Solution: def threeOrders(self , root ): pre_order, in_order, post...

首先吐槽一下，有些老铁采用了这种投机取巧的方法：直接遍历列表，取出每个链表里面的值然后进行数组排序，最后再依次插入到一个新链表中。 喂，你要这么写，那面试官只能面带微笑的告诉你：“写的不错，今天的面试就先到这里吧。”很明显这种解法走偏了，自己刷题可以试，面试可别这么整。这种题其实就是两个有序链表合并的升级版。下面讲下思路： 思路：这道题目最容易想到的做法是，使用【合并两个有序链表】中的方法，融合前两个链表，将下一个链表与当前结果融合，遍历列表中的每个链表，不断循环下去。但是这种方法时间复杂度很高，我们考虑用二分法把列表进行中间拆分，将列表都拆成长度相等的两个列表，然后融合每个小列表中的链表即可...

这题文字有点多呀，实际上是让你设计数据结构：⾸先要接收⼀个 capacity 参数作为 缓存的最⼤容量，然后实现两个 API，⼀个是 put(key, val) ⽅法存⼊键值 对，另⼀个是 get(key) ⽅法获取 key 对应的 val，如果 key 不存在则返回 -1。要让 put 和 get ⽅法的时间复杂度为 O(1)，我们可以 总结出 cache 这个数据结构必要的条件：查找快，插⼊快，删除快，有顺序 之分。 因为显然 cache 必须有顺序之分，以区分最近使⽤的和久未使⽤的数据；⽽ 且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后⼀个数 据；每次访问还要把数据插...

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

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

归并排序的套路，按照下面套路来就完事了。思路:  双指针从A和B的m、n尾部遍历 比较A和B的m、n尾部的值，将较大值赋给A整体数组的尾部，指针左移 注意特殊情况处理：A的尾指针已遍历结束，B尾指针还未结束。  代码： # @param A int整型一维数组 # @param B int整型一维数组 # class Solution: def merge(self , A, m, B, n): if not A and not B: return [] elif not A: return B elif not B: return A while m > 0 and n > 0:...

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