• 等级
  • 2465132 访问
  • 169 原创
  • 0 转发
  • 282 排名
  • 1329 评论
  • 91 获赞

LeetCode总结 -- 树的构造篇

这篇总结主要介绍树中比较常见的一类题型--树的构造。其实本质还是用递归的手法来实现,但是这类题目有一个特点,就是它是构建一棵树,而不是给定一棵树,然后进行遍历,所以实现起来思路上有点逆向,还是要练习一下。LeetCode中关于树的构造的题目有以下几道:ConvertSortedArraytoBinarySearchTreeConvertSortedListtoBinarySe

2014-11-12 10:40:31

Min Stack -- LeetCode

原题链接: https://oj.leetcode.com/problems/min-stack/这道题是关于栈的题目,实现一个栈的基本功能,外加一个获得最小元素的操作。正常情况下top,pop和push操作都是常量时间的,而主要问题就在于这个getMin上面,如果遍历一遍去找最小值,那么getMin操作就是O(n)的,既然出出来了这道题就肯定不是这么简单的哈。比较容易想到就是要追溯这个最小值,在

2014-11-11 11:11:32

Find Minimum in Rotated Sorted Array II -- LeetCode

这道题是SearchinRotatedSortedArray的扩展,思路在FindMinimuminRotatedSortedArray中已经介绍过了,和FindMinimuminRotatedSortedArray唯一的区别是这道题目中元素会有重复的情况出现。不过正是因为这个条件的出现,影响到了算法的时间复杂度。原来我们是依靠中间和边缘元素的大小关系,来判断哪一半是不

2014-10-25 07:12:45

Find Minimum in Rotated Sorted Array -- LeetCode

这道题是SearchinRotatedSortedArray的扩展,区别就是现在不是找一个目标值了,而是在bst中找最小的元素。主要思路还是跟SearchinRotatedSortedArray差不多,还是通过左边界和中间的大小关系来得到左边或者右边有序的信息,如果左半边有序,那么左半边最小就是左边第一个元素,可以和当前最小相比取小的,然后走向右半边。否则,那么就是右半半边第一个元

2014-10-25 07:11:17

LeetCode总结 -- 二叉查找树篇

这篇总结主要介绍一个比较常见的数据结构--二叉查找树。二叉查找树既是一颗树,又带有特别的有序性质,所以考察的方式比较多而且灵活,属于面试题目中的常客。LeetCode中关于二叉查找树的题目有以下几道:ValidateBinarySearchTreeRecoverBinarySearchTreeUniqueBinarySearchTreesUniqueBinarySearch

2014-09-25 09:37:45

Maximum Product Subarray -- LeetCode

原题链接: https://oj.leetcode.com/problems/maximum-product-subarray/ 这道题跟MaximumSubarray模型上和思路上都比较类似,还是用一维动态规划中的“局部最优和全局最优法”。这里的区别是维护一个局部最优不足以求得后面的全局最优,这是由于乘法的性质不像加法那样,累加结果只要是正的一定是递增,乘法中有可能现在看起来小的一个负数,后面

2014-09-25 01:39:13

LeetCode总结 -- 图篇

图的算法跟树一样是准备面试中必不可少的一块,不过图的方法很容易概括,面试中考核的无非就是两种搜索算法:深度优先搜索和广度优先搜索。LeetCode中关于图的问题有以下几个:CloneGraphWordLadderWordLadderIILongestConsecutiveSequenceWordSearchSurroundedRegions先来看看最基础的CloneGraph,很

2014-09-18 06:55:18

LeetCode总结 -- 矩阵篇

矩阵(一般是二维数组)操作的题目在面试中考察基础coding的时候比较常见,一般来说不带有太多算法思想,纯粹就是二维数组下标的操作。虽然比较简单,不过还是比较能体现基本的实现能力。LeetCode中关于矩阵操作的题目有以下几个:SpiralMatrixSpiralMatrixIIRotateImageValidSudokuSetMatrixZeroes前面三个题SpiralMatr

2014-09-13 07:46:42

LeetCode总结 -- 位运算篇

位运算一直编程和面试中的一个必须准备的主题。不过现在面试中关于位运算的出现得不多,主要原因还是位运算太考察技巧了,很多时候很难在短时间内想出来,所以作为面试的题目显得有点太花时间了。LeetCode中关于位运算的题目有以下几道:SingleNumberSingleNumberIIDivideTwoIntegersPow(x,n)先来说说SingleNumber,这应该LeetCo

2014-09-10 10:53:36

LeetCode总结 -- 高精度篇

我们常见的一些基本的数据结构比如整型int或者浮点型float由于位数过多无法用内置类型存储,这时候我们就需要自己实现高精度的数据类型来进行存储和运算。这种问题在实际产品中还是比较实用的,所以相对来说也是面试中的常客。LeetCode中关于高精度的题目有以下几道:AddBinaryAddTwoNumbersPlusOneMultiplyStringsAddBinary和AddTwo

2014-09-04 05:38:50

LeetCode总结 -- 树的性质篇

树的性质判断是树的数据结构比较基本的操作,一般考到都属于非常简单的题目,也就是第一道入门题,面试中最好不能有问题,力求一遍写对,不要给面试官任何挑刺机会。LeetCode中关于树的性质有以下题目:MaximumDepthofBinaryTreeMinimumDepthofBinaryTreeBalancedBinaryTreeSameTreeSymmetricTree首先说

2014-09-03 10:47:58

LeetCode总结 -- 树的求和篇

树的求和属于树的题目中比较常见的,因为可以有几种变体,灵活度比较高,也可以考察到对于树的数据结构和递归的理解。一般来说这些题目就不用考虑非递归的解法了(虽然其实道理是跟LeetCode总结--树的遍历篇一样的,只要掌握了应该没问题哈)。 LeetCode中关于树的求和有以下题目:PathSumPathSumIISumRoottoLeafNumbersBinaryTreeMax

2014-09-01 10:32:49

LeetCode总结 -- 一维数据合并篇

合并是一维数据结构中很常见的操作,通常是排序,分布式算法中的子操作。这篇总结主要介绍LeetCode中关于合并的几个题目: MergeTwoSortedListsMergeSortedArraySortListMergekSortedLists我们先来看看两个有序一维数据的合并,这里主要是要介绍链表的合并操作,不过因为一维数组的合并也比较简单,而且与链表有比较性,就

2014-08-27 12:23:12

LeetCode总结 -- 数值计算篇

数值计算在工业界是非常实用而且常见的具体问题,所以在面试中出现频率非常高,几乎可以说是必考题目。LeetCode中关于数值运算的有以下题目: PalindromeNumberReverseIntegerSqrt(x)Pow(x,n)DivideTwoIntegersMaxPointsonaLine在LeetCode中,关于数值运算的题目分为三种类型,下面将进行一一讲解。

2014-08-23 02:25:35

LeetCode总结 -- kSum篇

这篇总结主要介绍LeetCode中几道关于求kSum的题目,主要要求是在数组中寻找k个数的和能否达到目标值。LeetCode关于kSum的主要题目有: TwoSum3Sum3SumClosest4Sum首先从TwoSum开始,这道题目提供了后面k>2的题目的基本思路,也是最常考到的题目(亚马逊的面试对这道题算是情有独钟了)。主要有两种思路,一种是利用哈希表对元素的出现进行记录,然

2014-08-14 11:14:12

LeetCode总结 -- 树的遍历篇

遍历树的数据结构中最常见的操作,可以说大部分关于树的题目都是围绕遍历进行变体来解决的。一般来说面试中遇到树的题目是用递归来解决的,不过如果直接考察遍历,那么一般递归的解法就过于简单了,面试官一般还会问更多问题,比如非递归实现,或者空间复杂度分析以及能否优化等等。树的遍历题目在LeetCode中有以下几个: BinaryTreeInorderTraversalBinaryTr

2014-08-12 09:10:07

LeetCode总结 -- 一维动态规划篇

这篇文章的主题是动态规划,主要介绍LeetCode中一维动态规划的题目,列表如下: ClimbingStairsDecodeWaysUniqueBinarySearchTreesMaximumSubarrayBestTimetoBuyandSellStock在介绍上述具体题目之前,我们先说说动态规划的通常思路。动态规划是一种算法思路(注意这里不要和递归混淆,事实上

2014-08-10 11:16:12

LeetCode总结--二分查找篇

二分查找算法虽然简单,但面试中也比较常见,经常用来在有序的数列查找某个特定的位置。在LeetCode用到此算法的主要题目有:SearchInsertPositionSearchforaRangeSqrt(x)Searcha2DMatrixSearchinRotatedSortedArraySearchinRotatedSor

2014-06-16 10:50:14

4Sum -- LeetCode

原题链接: http://oj.leetcode.com/problems/4sum/ 这道题要求跟3Sum差不多,只是需求扩展到四个的数字的和了。我们还是可以按照3Sum中的解法,只是在外面套一层循环,相当于求n次3Sum。我们知道3Sum的时间复杂度是O(n^2),所以如果这样解的总时间复杂度是O(n^3)。代码如下:publicArrayList>fourSum(int[]num,

2014-05-01 04:13:26

Unique Binary Search Trees -- LeetCode

原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees/ 这道题要求可行的二叉查找树的数量,其实二叉查找树可以任意取根,只要满足中序遍历有序的要求就可以。从处理子问题的角度来看,选取一个结点为根,就把结点切成左右子树,以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积,所以总的数量是将以所有结点为根的可行结果

2014-04-30 06:16:29

Code_Ganker

留美博士生一枚,四大爱好:创业,编程,dota,德扑。
关注
  • 计算机软件
  • 中国