House Robber I

1
2
3
4
5
6
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, 
the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police
if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house,
determine the maximum amount of money you can rob tonight without alerting the police.

假设你现在是一个小偷,想要一整条街上的人家。你不能连着偷两家因为这样会触发警报系统。现在有一个nums数组存放着每一家中的可偷金额,问可以偷的最大金额为多少?

阅读全文 »

题目要求

1
2
3
4
5
6
7
8
9
10
Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

使用队列来模拟实现一个栈。
栈是指先进后出的数据结构,而队列则是先进先出的数据结构。
假设我们分别往栈和队列中顺序输入[1,2,3],那么栈的输出是[3,2,1],而队列的输出的[1,2,3]。

队列的API包括在队列尾插入数据,输出队列头的数据,查看队列的长度,队列是否为空。

那么我们现在看一下如何通过队列来实现栈的操作。

阅读全文 »

题目要求

1
2
3
4
5
6
7
8
9
10
11
Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
Note: Do not use the eval built-in library function.

实现一个简单的计算器,这个计算器可以计算以String为输入的中序表达式。这个中序表达式包含(),+,-和数字。题目中也给出了例子。
还有一个比较特殊的情况为(3)-(4)-(5) = -6

阅读全文 »

题目要求

1
2
3
4
5
6
7
8
9
10
Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

通过队列实现一个栈的功能。栈的api为push(压入栈顶),pop(出栈),peek(栈顶元素),empty(栈是否为空)。这道题和之前的使用栈实现队列功能是类似的,可以参考我的这篇博客

阅读全文 »

题目要求

1
Sort a linked list in O(n log n) time using constant space complexity.

用O(n log n)的时间复杂度和O(1)的空间复杂度检索一个链表。

阅读全文 »

题目要求

实现一个算法来判断一个数字是否开心。一个开心数字是指将数字的各个位上的数求平方和,如果这个数字最终能够计算至1,那么这个数字就是一个开心数字。如果这个数字一直在某个圈中循环,那么这就不是一个开心数字。题目中也给了19这个例子。

阅读全文 »

235题 题目要求

1
2
3
4
5
6
7
8
9
10
11
12
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

现在有一棵搜索二叉树,这个二叉树的特点是左子树的节点一定小于根节点,而右子树的节点一定大于根节点。现在提供这棵树的根节点,并且输入两个节点,问这两个节点的最低共同父节点是谁?
最低共同父节点是指两个节点在沿父节点向上爬升时遇到的第一个共同父节点,同时它也允许父节点就是其本身,比如在上图中2和4的最低共同父节点就是2

阅读全文 »

题目要求

1
2
3
4
Given a range [m, n] where 0 <= m <= n <= 2147483647,
return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

给一个闭区间[m,n],对该闭区间的所有数字进行与(and)运算。
与预算是指 1 and 1 = 0, 1 and 0 = 0, 0 and 1 = 0, 0 and 0 = 0
这里都是以二进制为基础进行与运算。在计算机底层所有的十进制数都是以二进制数进行存储的。写这道题目之前需要先去了解十进制转二进制以及未操作符>>,>>>和<<

阅读全文 »

题目要求

1
2
3
4
5
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

计算所有小于等于n的正整数中数字1的个数。
比如比13小的正整数中包含1的有1,10,11,12,13,一共有6个1。

阅读全文 »
0%