2016 年文章归档
共 209 篇文章
Clone Graph 克隆图
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. OJ's undirected graph serialization: Nodes are labeled uniquely. We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the seri…
2016-02-12 05:17 · Leetcode
Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. For example, given s = "aab", Return 1 since the palindrome partitioning could be produced using 1 cut. 给定一个字符串s,用最少的次数将它拆分成多个回文子串。我们用动态规划来解决。…
2016-02-12 04:36 · Leetcode
Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = "aab", Return , ] 给定一个字符串,让我们把字符串分割成回文子串,并把所有可能的情况输出。我们采用回溯法,在for循环中递归搜索,如果当然搜索的子串是回文字符串,就把它加入到list中。代码如下: public class Solution { publi…
2016-02-12 03:35 · Leetcode
Surrounded Regions
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X 给定一个二维数组,数组由两…
2016-02-12 02:56 · Leetcode
Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given , The longest consecutive elements sequence is . Return its length: 4. Your algorithm should run in O(n) complexity. 题目要求我们用O(n)的时间复杂度来解决,我们可以采用并查集的思想,当扫描到一个元素,我们从当前元素的两边开始处理,如果连续的都…
2016-02-11 03:44 · Leetcode
Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. For example, 1 / 2 3 The root-to-leaf path 1->2 represents the number 12…
2016-02-11 03:24 · Leetcode
Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time Each intermediate word must exist in the word list For example, Given: beginWord = "hit" endWord …
2016-02-11 02:46 · Leetcode
Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask durin…
2016-02-11 01:57 · Leetcode
Best Time to Buy and Sell Stock II
Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transaction…
2016-02-11 01:42 · Leetcode
Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. 动态规划问题,实际上就是让我们在一个数组中找到两个元素的差最大,较小的元素在较大元素的左边。用一个变量pr…
2016-02-10 05:34 · Leetcode
Pascal's Triangle II
Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return . Note: Could you optimize your algorithm to use only O(k) extra space? 简单的方法就是从0开始一层一层的生成,直到生成到第k行,这样空间复杂度为O(n^2), 代码如下: public class Solution { public List<Integer> getRow(int rowIndex) { List<Integer>…
2016-02-10 04:34 · Leetcode
Pascal's Triangle
Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return , , , , ] 生成杨辉三角。不清楚什么是杨辉三角的构成请参考 维基百科-杨辉三角 。代码如下: public class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> result = new ArrayList<List<Integer>>(); List<Inte…
2016-02-10 03:33 · Leetcode
Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle , , , ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). 我们用动态规划来解决,从下往上开始相加,例如题目中的例子,最后一行是,我们每次从中选取相邻两个元素中…
2016-02-10 02:53 · Leetcode
Populating Next Right Pointers in Each Node
Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may on…
2016-02-10 01:51 · Leetcode
Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE"…
2016-02-09 09:42 · Leetcode
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 2 3 4 5 6 给定一个二叉树,要求我们将它装换成一个链表的形式。我们从左边开始,假设当前节点为root,我们首先保存root的左孩子leftNode和右孩子rightNode,然后将root的左孩子作为它的右孩 子,然后让root的左孩子为空(root.right = leftNode,root.left = n…
2016-02-09 05:20 · Leetcode
Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / 4 8 / / 11 13 4 / \ / 7 2 5 1 return , ] 与Path Sum相比,这道题要求我们输出所有可能的结果,我们同样采用DFS,因为要输出所有可能的结果,我们用回溯法来记录,当找到符合条件的路径就记录下来,然后回溯,继续查找其它的路径。代码如…
2016-02-09 04:56 · Leetcode
Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example: Given the below binary tree and sum = 22, 5 / 4 8 / / 11 13 4 / \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which…
2016-02-09 04:34 · Leetcode
Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. 求一棵树的最短路径,同样用递归来解决。注意的是如果遇到一个节点只有一个孩子,这时我们要继续往下搜,要不然不符合题目的规定,同样的还有处理最大路径的问题,都是采用递归解决。代码如下: 最短路径: /** * Definition for a binary tree node. *…
2016-02-09 04:16 · Leetcode
Balanced Binary Tree
Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. 判断一颗树是否是平衡树。我们先判断根节点左右子树的深度,比较它们的高度差,如果大于1就返回false,如果小于1,递归判断左右子树是否为平衡树。代码如下: /** * …
2016-02-08 05:41 · Leetcode