Code_Ganker-CSDN博客

原创 LeetCode总结 -- 树的构造篇

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

2014-11-12 10:40:31 20162 5

原创 Min Stack -- LeetCode

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

2014-11-11 11:11:32 16298 20

原创 Find Minimum in Rotated Sorted Array II -- LeetCode

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

2014-10-25 07:12:45 15726 9

原创 Find Minimum in Rotated Sorted Array -- LeetCode

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

2014-10-25 07:11:17 17636 7

原创 LeetCode总结 -- 二叉查找树篇

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

2014-09-25 09:37:45 18042 2

原创 Maximum Product Subarray -- LeetCode

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

2014-09-25 01:39:13 23038 11

原创 LeetCode总结 -- 图篇

图的算法跟树一样是准备面试中必不可少的一块，不过图的方法很容易概括，面试中考核的无非就是两种搜索算法：深度优先搜索和广度优先搜索。LeetCode中关于图的问题有以下几个：Clone GraphWord LadderWord Ladder IILongest Consecutive SequenceWord SearchSurrounded Regions先来看看最基础的Clone Graph，很

2014-09-18 06:55:18 20307 3

原创 LeetCode总结 -- 矩阵篇

矩阵（一般是二维数组）操作的题目在面试中考察基础coding的时候比较常见，一般来说不带有太多算法思想，纯粹就是二维数组下标的操作。虽然比较简单，不过还是比较能体现基本的实现能力。LeetCode中关于矩阵操作的题目有以下几个：Spiral MatrixSpiral Matrix IIRotate ImageValid SudokuSet Matrix Zeroes前面三个题Spiral Matr

2014-09-13 07:46:42 12532 1

原创 LeetCode总结 -- 位运算篇

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

2014-09-10 10:53:36 9893 3

原创 LeetCode总结 -- 高精度篇

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

2014-09-04 05:38:50 9242 3

原创 LeetCode总结 -- 树的性质篇

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

2014-09-03 10:47:58 10724 1

原创 LeetCode总结 -- 树的求和篇

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

2014-09-01 10:32:49 12736

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

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

2014-08-27 12:23:12 6914

原创 LeetCode总结 -- 数值计算篇

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

2014-08-23 02:25:35 10473 1

原创 LeetCode总结 -- kSum篇

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

2014-08-14 11:14:12 18508 7

原创 LeetCode总结 -- 树的遍历篇

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

2014-08-12 09:10:07 16715 9

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

这篇文章的主题是动态规划，主要介绍LeetCode中一维动态规划的题目，列表如下： Climbing StairsDecode WaysUnique Binary Search TreesMaximum SubarrayBest Time to Buy and Sell Stock在介绍上述具体题目之前, 我们先说说动态规划的通常思路。动态规划是一种算法思路（注意这里不要和递归混淆，事实上

2014-08-10 11:16:12 33648 4

原创 LeetCode总结--二分查找篇

二分查找算法虽然简单，但面试中也比较常见，经常用来在有序的数列查找某个特定的位置。在LeetCode用到此算法的主要题目有：Search Insert PositionSearch for a RangeSqrt(x)Search a 2D MatrixSearch in Rotated Sorted ArraySearch in Rotated Sor

2014-06-16 10:50:14 24813 8

原创 4Sum -- LeetCode

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

2014-05-01 04:13:26 23582 6

原创 Unique Binary Search Trees -- LeetCode

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

2014-04-30 06:16:29 23773 1

原创 Unique Binary Search Trees II -- LeetCode

原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees-ii/ 这道题是求解所有可行的二叉查找树，从Unique Binary Search Trees中我们已经知道，可行的二叉查找树的数量是相应的卡特兰数，不是一个多项式时间的数量级，所以我们要求解所有的树，自然是不能多项式时间内完成的了。算法上还是用求解NP问题的

2014-04-30 06:15:46 18961 17

原创 Restore IP Addresses -- LeetCode

原题链接: http://oj.leetcode.com/problems/restore-ip-addresses/ 这道题的解法非常接近于NP问题，也是采用递归的解法。基本思路就是取出一个合法的数字，作为IP地址的一项，然后递归处理剩下的项。可以想象出一颗树，每个结点有三个可能的分支（因为范围是0-255，所以可以由一位两位或者三位组成）。并且这里树的层数不会超过四层，因为IP地址由四段组

2014-04-29 05:01:34 14360 3

原创 Interleaving String -- LeetCode

原题链接: http://oj.leetcode.com/problems/interleaving-string/ 这是一道关于字符串操作的题目，要求是判断一个字符串能不能由两个字符串按照他们自己的顺序，每次挑取两个串中的一个字符来构造出来。像这种判断能否按照某种规则来完成求是否或者某个量的题目，很容易会想到用动态规划来实现。先说说维护量，res[i][j]表示用s1的前i个字符和s

2014-04-29 04:28:30 10596 12

原创 Reverse Linked List II -- LeetCode

原题链接: http://oj.leetcode.com/problems/reverse-linked-list-ii/ 这道题是比较常见的链表反转操作，不过不是反转整个链表，而是从m到n的一部分。分为两个步骤，第一步是找到m结点所在位置，第二步就是进行反转直到n结点。反转的方法就是每读到一个结点，把它插入到m结点前面位置，然后m结点接到读到结点的下一个。总共只需要一次扫描，所以时间是O(n

2014-04-28 04:58:33 14747 3

原创 Subsets II -- LeetCode

原题链接: http://oj.leetcode.com/problems/subsets-ii/这道题跟Subsets一样是经典的NP问题--求子集。比Subsets稍微复杂一些的是这里的集合中可能出现重复元素，因此我们在求子集的时候要避免出现重复的子集。在Subsets中我们每次加进一个元素就会把原来的子集都加上这个元素，然后再加入到结果集中，但是这样重复的元素就会产生重复的子集。为了避免

2014-04-28 04:23:53 12819 6

原创 Decode Ways -- LeetCode

原题链接: http://oj.leetcode.com/problems/decode-ways/ 这道题要求解一个数字串按照字符串编码方式可解析方式的数量。看到这种求数量的，我们很容易想到动态规划来存储前面信息，然后迭代得到最后结果。我们维护的量res[i]是表示前i个数字有多少种解析的方式，接下来来想想递归式，有两种方式：第一种新加进来的数字不然就是自己比较表示一个字符，那么解析的方

2014-04-27 06:18:13 15664 6

原创 Recover Binary Search Tree -- LeetCode

原题链接: http://oj.leetcode.com/problems/recover-binary-search-tree/ 这道题是要求恢复一颗有两个元素调换错了的二叉查找树。一开始拿到可能会觉得比较复杂，其实观察出规律了就比较简单。主要还是利用二叉查找树的主要性质，就是中序遍历是有序的性质。那么如果其中有元素被调换了，意味着中序遍历中必然出现违背有序的情况。那么会出现几次呢？有两种情

2014-04-27 03:09:51 16784 5

原创 Gray Code -- LeetCode

原题链接: http://oj.leetcode.com/problems/gray-code/ 这道题要求求出n位的格雷码对应的二进制数，主要在于找到一种格雷码的递增方法（格雷码并不是唯一的，可以有多种）。我们来看看有了n-1位的格雷码如何得到n位的格雷码呢？其实方法比较简单，首先在n-1位的格雷码前面都添加0作为前2^(n-1)个格雷码，它们一定是合法的因为除了第一位（都是0）其余位都

2014-04-26 06:22:42 10668 2

原创 Binary Tree Zigzag Level Order Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ 这道题其实还是树的层序遍历Binary Tree Level Order Traversal，如果不熟悉的朋友可以先看看哈。不过这里稍微做了一点变体，就是在遍历的时候偶数层自左向右，而奇数层自右向左。在Binary Tree L

2014-04-26 04:31:29 14732 8

原创 Scramble String -- LeetCode

原题链接: http://oj.leetcode.com/problems/scramble-string/ 这道题看起来是比较复杂的，如果用brute force，每次做切割，然后递归求解，是一个非多项式的复杂度，一般来说这不是面试官想要的答案。这其实是一道三维动态规划的题目，我们提出维护量res[i][j][n]，其中i是s1的起始字符，j是s2的起始字符，而n是当前的字符串长度，re

2014-04-26 02:50:20 15649 5

原创 Partition List -- LeetCode

原题链接: http://oj.leetcode.com/problems/partition-list/ 这是一道链表操作的题目，要求把小于x的元素按顺序放到链表前面。我们仍然是使用链表最常用的双指针大法，一个指向当前小于x的最后一个元素，一个进行往前扫描。如果元素大于x，那么继续前进，否则，要把元素移到前面，并更新第一个指针。这里有一个小细节，就是如果不需要移动（也就是已经是接在小于x的最

2014-04-25 04:51:26 9845

原创 Maximal Rectangle -- LeetCode

原题链接: http://oj.leetcode.com/problems/maximal-rectangle/ 这是一道非常综合的题目，要求在0-1矩阵中找出面积最大的全1矩阵。刚看到这道题会比较无从下手，brute force就是对于每个矩阵都看一下，总共有m(m+1)/2*n(n+1)/2个子矩阵（原理跟字符串子串类似，字符串的子串数有n(n+1)/2，只是这里是二维情形，所以是两个相乘

2014-04-25 02:30:11 16085 7

原创 Construct Binary Tree from Inorder and Postorder Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/ 这道题和Construct Binary Tree from Preorder and Inorder Traversal思路完全一样，如果有朋友不了解，请先看看Construct Binar

2014-04-24 09:02:17 13802 1

原创 Construct Binary Tree from Preorder and Inorder Traversal -- LeetCode

原题链接: http://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ 这道题是树中比较有难度的题目，需要根据先序遍历和中序遍历来构造出树来。这道题看似毫无头绪，其实梳理一下还是有章可循的。下面我们就用一个例子来解释如何构造出树。假设树的先序遍历是12453687，中序

2014-04-24 08:43:09 19535 11

原创 Remove Duplicates from Sorted List II -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ 这道题跟Remove Duplicates from Sorted List比较类似，只是这里要把出现重复的元素全部删除。其实道理还是一样，只是现在要把前驱指针指向上一个不重复的元素中，如果找到不重复元素，则把前驱指针知道该元素，否则删除

2014-04-24 08:33:10 11854 1

原创 Remove Duplicates from Sorted List -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/ 这是一道比较简单的链表操作的题目，要求是删去有序链表中重复的元素。方法比较清晰，维护两个指针，一个指向当前不重复的最后一个元素，一个进行依次扫描，遇到不重复的则更新第一个指针，继续扫描，否则就把前面指针指向当前元素的下一个（即把当前元素从链表中删除

2014-04-23 11:25:06 10128 1

原创 Remove Duplicates from Sorted Array II -- LeetCode

原题链接: http://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ 这道题跟Remove Duplicates from Sorted Array比较类似，区别只是这里元素可以重复出现至多两次，而不是一次。其实也比较简单，只需要维护一个counter，当counter是2时，就直接跳过即可，否则说明元素

2014-04-23 08:39:29 12754 2

原创 Word Search -- LeetCode

原题链接: http://oj.leetcode.com/problems/word-search/ 这道题很容易感觉出来是图的题目，其实本质上还是做深度优先搜索。基本思路就是从某一个元素出发，往上下左右深度搜索是否有相等于word的字符串。这里注意每次从一个元素出发时要重置访问标记（也就是说虽然单次搜索字符不能重复使用，但是每次从一个新的元素出发，字符还是重新可以用的）。深度优先搜索的算法就

2014-04-23 01:21:12 20011 12

原创 Subsets -- LeetCode

原题链接: http://oj.leetcode.com/problems/subsets/ 求子集问题是经典的NP问题，复杂度上我们就无法强求了哈，肯定是非多项式量级的。一般来说这个问题有两种解法：递归和非递归。我们先来说说递归解法，主要递推关系就是假设函数返回递归集合，现在加入一个新的数字，我们如何得到包含新数字的所有子集。其实就是在原有的集合中对每集合中的每个元素都加入新元素得到子集

2014-04-22 08:08:48 14168 2

原创 Sort Colors -- LeetCode

原题链接: http://oj.leetcode.com/problems/sort-colors/ 这道题也是数组操作的题目，其实就是要将数组排序，只是知道数组中只有三个元素0,1,2。熟悉计数排序的朋友可能很快就发现这其实就是使用计数排序，元素空间只需要三个元素即可。代码如下： public void sortColors(int[] A) { if(A==null || A.le

2014-04-22 08:06:02 12147

空空如也

空空如也