KickCode
- 浏览: 184675 次
- 性别:
- 来自: 济南
-
最新评论
文章列表
二叉树广度优先遍历我们采用队列来实现，这里列举三道leetcode中有关二叉树BFS的题目，总的思想是一样的，题目要求的输出不同，我们需要根据不同的要求来编写，考察我们对于二叉树搜索的基本思想掌握以及java基础的掌握。
1，Binary Tree Level Order Traversal
给定一颗二叉树，用广度优先搜索遍历所有节点，并输出结果。
例如：
3
/ \
9 20
/ \
15 7
输出：
[
[3],
[9,20],
[15,7]
]
这是基本的二叉树水平遍历，我们只需要借助几个变量，来辅助记录什么时候应该记录结果，什么时候 ...
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 = [1,3,-1,-3,5,3,6,7], an ...
首先简单介绍一下什么是格雷码。在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。有关格雷码的详细讲解请大家查阅网上其它资料，这里主要讲解格雷码是如何编码的。
我们不妨从简单例子开始进一步看一下什么是格雷码，假设n代表格雷码的位数，当n=1时，我们只有两种选择(0, 1); 当 n =2 时，格雷码为(00, 01, 11, 10); 当n = 3时，格雷码为(000, 001, 011,010, 110, 111, 101, 100)；我们发现了一个规律，就是 ...
Wildcard Matching
给定两个字符串p和q，判断两个字符串是否匹配。规则是：‘*’可以代表任意长度的字符串，也可以代表空串；‘?’代表任意单个的字符串。
例如：
isMatch("aa", "a") → false
isMatch("aa", "aa") → true
isMatch("aaa", "aa") → false
isMatch("aa", "*") → true
isMatch("aa", ...
Kth Largest Element in an Array
给定一个无序的数组，找出第K大的元素，假定k一直有效，1 ≤ k ≤ array's length。
例如给定：nuts[] = [3,2,1,5,6,4], k = 2
返回 5
如果我们用Arrays的sort方法将数组排序，然后输出nums[nums.length - k]就是第k大的元素。代码如下：
public class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
...
Majority Element II
给定一个长度为n的数组，找出所有出现次数大于[n/3]的元素。
这道题是Majority Element的变形，如果次数大于[n/2]时，只可能有一个元素，这里要求出现次数多于[n/3]次，也就是说有可能有两个元素，同样我们可以用哈希表来做，这样时间复杂度为O(n)，空间复杂度为O(n)。代码如下：
public class Solution {
public List<Integer> majorityElement(int[] nums) {
HashMap<Integer, Integer> ...
Majority Element
给定一个长度为n的数组，从中找出出现次数最多的元素，这个元素出现的次数多余[n/2]次。假设数组不为空并且始终存在一个majority元素。
解决这道题有很多种方法，但是时间复杂度和空间复杂度各不相同，在这里 ...
House Robber问题属于一维的动规问题，这篇文章给大家介绍一下。
1，House Robber
一个小偷去一条街上偷东西，假设这条街上有n个房子，每个房子里都有特定的现金，但是小偷不能偷连续的房子，那样会触发警报，问怎样才能偷到最多的钱。
我们把这条街抽象成一个数组，数组里的值代表了房子里现金的数目，假设小偷拿了第0个房子的钱，那么第1个房子的钱就不能拿，否则就会触发警报。我们创建一个数组result[]，result[i]代表了到第i个房子小偷最多能得到的钱数，result[i] = Math.max(result[i - 1], result[i-2] + nums[i - 1] ...
这篇文章介绍unique path等一系列的题目，它们属于二维动态规划的问题，之前一篇文章讲过最长公共子序列(LCS), 最长递增子序列(LIS), 最长非降子序列。有兴趣的可以看一下，这些都是经典的二维动规问题。
1，Unique Paths
给定一个m*n的矩阵，一个机器人在这个矩阵的左上方，它试图走到这个矩阵的右下方，规定机器人只能往右和往下两个方向走，问有多少种不同的路径。
我们把这个矩阵抽象成一个二维数组grid，机器人开始的位置就是grid[0][0]，它可以往下走，也可以往右走，我们初始化数组让它的第0列和第0行的值都1，因为机器人到这些地方只有一条路。对于其它的地方grid[ ...
动态规划在算法中属于难的问题了，在leetcode中属于中等偏上难度，但是动规是面试容易问到的，因此掌握基本的动规题目很有必要。下面列举leetcode中用DP处理的题目，其中有些用到贪心算法，就不单列出来了，本质上贪心也是动态规划的一个特例。动态规划重要的是能找出递推式，这需要我们多加练习，需要有一个过程。
有关买卖股票的题目有几道，这里列举前两道题。
1，Best Time to Buy and Sell Stock
给定一个整形数组，第i个元素代表第i天股票的价格。如果我们只能做一次交易，也就是只能买卖一次，如何能得到最大的利益。
我们把它抽象一下，就是从一个数组中找到两个元素，使他们 ...
之前介绍过在排好序的链表中删除节点，只需要遍历一遍链表，所以时间复杂度为O(n)。这篇文章讨论对无序链表的去重问题。
给定一个无序链表，删除里面的重复元素，我们用bruce force来进行的话时间复杂度为O(n^2),我们从头节点开始判断，如果有相等的元素，就将当前节点的next指向下一个节点的next。每个元素都要遍历一次它们后面的元素。代码如下：
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode current = head;
while(cur ...
leetcode中有关并查集的题目不多，这里现列举一道简单的题目，理解并查集的思想。
Longest Consecutive Sequence
给定一个未排序的整型数组，找出最长的连续子序列。要求时间复杂度为O(n)。
例如：给定nums[] = {100, 4, 200, 1, 3, 2}
输出：4 最长连续子序列为（1，2，3，4）
我们用哈希处理元素是否被访问过，然后从第一个元素开始，分别检查它两边的元素，也就是对它进行加1和减1的操作，检查哈希表中是否存在，记录最大的个数。这就好像以节点构造了几棵树，只要找到最大的那棵树就是结果了。代码如下：
public class So ...
之所以把这道题单独拿出来，是因为通过它我们可以了解到图的结构，以及如何处理，我们分别用递归，广搜和深搜来完成这道题。
Clone Graph
复制一个无向图，图中每个节点都有一个label和一个neighbors集合。
解决图的题，因为图中存在环，我们要判断哪些点已经访问过了，做上标记，以防止进入死循环。这里我们用哈希函数来判断一个顶点是否被访问过，如果没被访问过就加入到哈希表中。
首先我们通过广搜来完成它。广搜用到队列，代码如下：
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* ...
本文列举leetcode中两个关于构造二叉树的题目。
1，Construct Binary Tree from Inorder and Postorder Traversal
已知中序遍历序列，和后序遍历序列，通过这两个序列构造二叉树。
通过后序遍历序列的最后元素，我们总能找到根节点，然后通过这个值可以将中序序列分为两部分，然后在递归左右两部分。代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* ...
这篇文章主要列举数组或者链表如何转换为二叉树。
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; }
* }
...