2015 年文章归档
共 45 篇文章
Sliding Window Maximum
Sliding Window Maximum Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. For example, Given nums = , and k = 3. Window po…
2015-12-25 05:15 · Leetcode
Gray Code
首先简单介绍一下什么是格雷码。在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同,则称这种编码为格雷码(Gray Code),另外由于最大数与最小数之间也仅一位数不同,即“首尾相连”,因此又称循环码或反射码。有关格雷码的详细讲解请大家查阅网上其它资料,这里主要讲解格雷码是如何编码的。 我们不妨从简单例子开始进一步看一下什么是格雷码,假设n代表格雷码的位数,当n=1时,我们只有两种选择( 0, 1 ); 当 n =2 时,格雷码为( 00, 01 , 11, 10); 当n = 3时,格雷码为( 000, 001, 011,010, 110, 111, 101, 100);我们发现了一…
2015-12-24 02:11 · Leetcode
Wildcard Matching
Wildcard Matching 给定两个字符串p和q,判断两个字符串是否匹配。规则是:‘ ’可以代表任意长度的字符串,也可以代表空串;‘?’代表任意单个的字符串。 例如: isMatch("aa", "a") → false isMatch("aa", "aa") → true isMatch("aaa", "aa") → false isMatch("aa", " ") → true isMatch("aa", "a*") → true isMatch("ab", "? ") → true isMatch("aab", "c a*b") → false 这是leetcode中一道偏难的…
2015-12-24 01:36 · Leetcode
Kth Largest Element in an Array
Kth Largest Element in an Array 给定一个无序的数组,找出第K大的元素,假定k一直有效,1 ≤ k ≤ array's length。 例如给定:nuts = , k = 2 返回 5 如果我们用Arrays的sort方法将数组排序,然后输出nums就是第k大的元素。代码如下: public class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length-k]; } } 如果我们在面试中遇到这个问题,这显然不是面试…
2015-12-23 10:33 · Leetcode
Majority Element II
Majority Element II 给定一个长度为n的数组,找出所有出现次数大于的元素。 这道题是Majority Element的变形,如果次数大于时,只可能有一个元素,这里要求出现次数多于次,也就是说有可能有两个元素,同样我们可以用哈希表来做,这样时间复杂度为O(n),空间复杂度为O(n)。代码如下: public class Solution { public List<Integer> majorityElement(int[] nums) { HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); List…
2015-12-23 10:05 · Leetcode
Majority Element
Majority Element 给定一个长度为n的数组,从中找出出现次数最多的元素,这个元素出现的次数多余次。假设数组不为空并且始终存在一个majority元素。 解决这道题有很多种方法,但是时间复杂度和空间复杂度各不相同,在这里我们用三种不同的方法解这道题。 1,最简单的方法就是先将数组排好序,根据题意我们知道,出现最多的元素肯定是中间的元素。 我们直接调用Arrays的sort方法,这样时间复杂度是O(nlogn),空间复杂度为O(1)。代码如下: public class Solution { public int majorityElement(int[] nums) { Arra…
2015-12-23 08:44 · Leetcode
动态规划总结(三)
House Robber问题属于一维的动规问题,这篇文章给大家介绍一下。 1,House Robber 一个小偷去一条街上偷东西,假设这条街上有n个房子,每个房子里都有特定的现金,但是小偷不能偷连续的房子,那样会触发警报,问怎样才能偷到最多的钱。 我们把这条街抽象成一个数组,数组里的值代表了房子里现金的数目,假设小偷拿了第0个房子的钱,那么第1个房子的钱就不能拿,否则就会触发警报。我们创建一个数组result,result 代表了到第i个房子小偷最多能得到的钱数,result = Math.max(result, result + nums) (i > 2),这就是递推式,这样我们一直计算到…
2015-12-22 07:52 · Leetcode
动态规划总结(二)
这篇文章介绍unique path等一系列的题目,它们属于二维动态规划的问题, 之前一篇文章 讲过最长公共子序列(LCS), 最长递增子序列(LIS), 最长非降子序列。有兴趣的可以看一下,这些都是经典的二维动规问题。 1,Unique Paths 给定一个m*n的矩阵,一个机器人在这个矩阵的左上方,它试图走到这个矩阵的右下方,规定机器人只能往右和往下两个方向走,问有多少种不同的路径。 我们把这个矩阵抽象成一个二维数组grid,机器人开始的位置就是grid,它可以往下走,也可以往右走,我们初始化数组让它的第0列和第0行的值都1,因为机器人到这些地方只有一条路。对于其它的地方grid* = g…
2015-12-21 02:32 · Leetcode
动态规划总结(一)
动态规划在算法中属于难的问题了,在leetcode中属于中等偏上难度,但是动规是面试容易问到的,因此掌握基本的动规题目很有必要。下面列举leetcode中用DP处理的题目,其中有些用到贪心算法,就不单列出来了,本质上贪心也是动态规划的一个特例。动态规划重要的是能找出递推式,这需要我们多加练习,需要有一个过程。 有关买卖股票的题目有几道,这里列举前两道题。 1,Best Time to Buy and Sell Stock 给定一个整形数组,第i个元素代表第i天股票的价格。如果我们只能做一次交易,也就是只能买卖一次,如何能得到最大的利益。 我们把它抽象一下,就是从一个数组中找到两个元素,使他们…
2015-12-20 13:37 · Leetcode
Remove Duplicate from Unsorted List
之前介绍过在排好序的链表中删除节点,只需要遍历一遍链表,所以时间复杂度为O(n)。这篇文章讨论对无序链表的去重问题。 给定一个无序链表,删除里面的重复元素,我们用bruce force来进行的话时间复杂度为O(n^2),我们从头节点开始判断,如果有相等的元素,就将当前节点的next指向下一个节点的next。每个元素都要遍历一次它们后面的元素。代码如下: public ListNode deleteDuplicates(ListNode head) { if(head == null) return head; ListNode current = head; while(current !=…
2015-12-20 13:08 · Leetcode
并查集总结
leetcode中有关并查集的题目不多,这里现列举一道简单的题目,理解并查集的思想。 Longest Consecutive Sequence 给定一个未排序的整型数组,找出最长的连续子序列。要求时间复杂度为O(n)。 例如:给定nums = {100, 4, 200, 1, 3, 2} 输出:4 最长连续子序列为(1,2,3,4) 我们用哈希处理元素是否被访问过,然后从第一个元素开始,分别检查它两边的元素,也就是对它进行加1和减1的操作,检查哈希表中是否存在,记录最大的个数。这就好像以节点构造了几棵树,只要找到最大的那棵树就是结果了。代码如下: public class Solution …
2015-12-18 03:48 · Leetcode
Clone Graph
之所以把这道题单独拿出来,是因为通过它我们可以了解到图的结构,以及如何处理,我们分别用递归,广搜和深搜来完成这道题。 Clone Graph 复制一个无向图,图中每个节点都有一个label和一个neighbors集合。 解决图的题,因为图中存在环,我们要判断哪些点已经访问过了,做上标记,以防止进入死循环。这里我们用哈希函数来判断一个顶点是否被访问过,如果没被访问过就加入到哈希表中。 首先我们通过广搜来完成它。广搜用到队列,代码如下: /** * Definition for undirected graph. * class UndirectedGraphNode { * int label…
2015-12-17 09:25 · Leetcode
Binary Tree的题目总结(四)
本文列举leetcode中两个关于构造二叉树的题目。 1,Construct Binary Tree from Inorder and Postorder Traversal 已知中序遍历序列,和后序遍历序列,通过这两个序列构造二叉树。 通过后序遍历序列的最后元素,我们总能找到根节点,然后通过这个值可以将中序序列分为两部分,然后在递归左右两部分。代码如下: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * Tree…
2015-12-16 13:25 · Leetcode
Binary Tree的题目总结(三)
这篇文章主要列举数组或者链表如何转换为二叉树。 1,Convert Sorted Array to Binary Search Tree 将一个有序数组变为二叉平衡树。 因为数组有序,我们通过二分法,依次将数组元素变为数节点,代码如下: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { publi…
2015-12-16 08:15 · Leetcode
Binary Tree的题目总结(二)
这篇文章列出了leetcode中有关二叉树遍历的题目,之前在 二叉树的深搜和广搜 中介绍过,这里再重复一下,因为这都是最基本的操作,需要我们熟练掌握。 1,Binary Tree Level Order Traversal 二叉树的广度优先搜索,输出所有节点的值,说的广搜,我们一律用队列来完成,代码如下: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } *…
2015-12-16 04:59 · Leetcode
Binary Tree的题目总结(一)
与数组和链表相比,树的题目比它们要难一些,我们往往通过递归来处理树的题目,下面是对leetcode有关树操作的几道题目,包括找出树的所有路径,计算完全二叉树节点个数,二叉搜索树的最近公共祖先,普通二叉树的最近公共祖先。 1,Binary Tree Paths 给定一个二叉树,输出所有根节点到叶子节点的路径。 用深度优先遍历(DFS),依次保留搜索过的节点。代码如下: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; *…
2015-12-16 03:40 · Leetcode
Bit Manipulation总结(二)
这篇文章介绍通过位运算求解子集,反转二进制数,判断是否为2的幂等。 1,Number of 1 Bits 给定一个无符号的整数,输出它包含1的个数。 通过右移,依次与1位与,得到1的个数。 代码如下: public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int count = 0; for(int i = 0; i < 32; i++) { if((n >> i & 1) == 1) { count ++; } } return count;…
2015-12-15 17:12 · Leetcode
Bit Manipulation总结(一)
在 位运算这篇文章中 已经介绍了关于位运算的一些知识,这里主要介绍leetcode中出现的有关位运算的题目。 有关找单独元素的有三道题,要求空间复杂度为O(n),空间复杂度为O(1),我们都可以通过位运算来解决。 1,Single Number 给定一个数组,每个元素都出现了两次,只有一个元素出现了一次,找出这个元素. 我们将所有的元素进行异或操作,最终的结果就是单独的元素,相同元素异或为0. 代码如下: public class Solution { public int singleNumber(int[] nums) { int result = 0; for(int i = 0; i…
2015-12-15 16:50 · Leetcode
Parentheses总结
这篇文章总结leetcode中有关括号的问题,最简单的是判断输入的括号是否有效,例如“))”就不属于有效的括号,括号的题目无非是添加,删除,找到最长有效括号等。最长有效括号是一道DP问题,我们在DP总结中结合最长回文子串一起列出。下面列举几个基本的题目。 1,Valid Parentheses 给定一个字符串序列,它包含'(', ')', '{', '}', '',判断字符串是否是有效括号组成的。 例如:"()" 和 "(){}" 是有效字符串;而 "(]" 和 "(" 就不是合法字符串。 我们用堆栈解决这道题,从第一个字符开始遍历,遇到‘(’ , '{' 或‘{’时,我们就把它压入到堆栈中…
2015-12-15 09:21 · Leetcode
Palindrome总结
这篇文章总结leetcode中回文的题目,其中关于palindrome partition有两道题目,第二道属于动态规划的题目,我们动态规划的总结中讨论。简单的讲回文就是将它翻转后和原来一样。 1,Palindrome Number 给定一个数字,判断它是否为回文数。 对于数字来讲,负数不属于回文数,对于正数,我们将它逆转,然后与原始值比较,如果相等就为回文数。代码如下: public class Solution { public boolean isPalindrome(int x) { if(x < 0) return false; int result = 0; int tem = …
2015-12-15 05:44 · Leetcode