眯眯眼猫头鹰的小树杈

Owned By Deer&Owl

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

当遇到数组中的值时，即将该值所在的行和列全部改为0。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

可以先参考关于SubsetI的这篇博客再看接下来的内容。
这里的区别在于假设输入的数组存在重复值，则找到所有不重复的子集。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

对于类似体型Jump Game I，请参考这篇博客。
这题相对于I，差别在于已知一定可以到达终点，找到一条最短路径所需要的步数。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

在数组中找到第一个漏掉的正整数。如果可以的话，使用O(N)的时间复杂度和O(1)的空间复杂度。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ? m ? n ? length of list.

将链表中从第m个节点开始翻转至第n个节点结束。要求在第一次遍历中即完成该过程。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

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
[
   [5,4,11,2],
   [5,8,4,5]
]

从树中找到所有符合条件的从根节点到叶节点路径，条件即为树上所有节点值的和等于目标值。
Path Sum I可以参考这篇博客

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
1
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
1
2
3
4
5
The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given heights = [2,1,5,6,2,3],
return 10.

即找到图中可以组合而成的面积最大的矩形。

这里我首先想到的是leetcode 42 Trapping Rain Water，可以参考我的这篇博客。
因为在42题中，如果我找到了当前矩形左右的最近最高矩形即可。而在本题中，同样是需要找到该矩形左右的最高矩形，但不同的是，一旦我在左右搜寻的过程中遇到了一个比当前矩形矮的矩形，遍历即结束。所以两道题目的要求还是存在区别的。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

返回字符串能够组成的所有IP地址。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],
   1
    \
     2
    /
   3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

中序遍历树，并将遍历结果添加到数组中。分别用递归和循环的方式结局。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
    2
   / \
  1   3
Binary tree [2,1,3], return true.
Example 2:
    1
   / \
  2   3
Binary tree [1,2,3], return false.

判断一个树是否是二叉查找树。二叉查找树即满足当前节点左子树的值均小于当前节点的值，右子树的值均大于当前节点的值。

阅读全文 »
0%