LeetCode #42 Trapping Rain Water

Posted on 2015/07/25 by NeoShell — No Comments ↓

题目：

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

分析：

给定一个数组，每个数代表该位置上的长条的高度，由此得到一个类似地形图的东西。凹进去的地方可以蓄水，问一共能存多少水。

每一个坑（凹进去的地方）都是由左右2个长条围成的。能存多少水取决于这2个长条中最短的那个。因此，我们对数组进行2次遍历。第1次从左向右，获得该位置左侧最高长条的高度；第2次从右向左，获得该位置右侧最高长条的高度。现在每个位置都知道了它所在的坑被围成的左右2个长条的高度，取较短的那个，就是该位置蓄水的最大高度。最后把每个位置的蓄水量加起来即可。

Continue reading LeetCode #42 Trapping Rain Water→

LeetCode #237 Delete Node in a Linked List

Posted on 2015/07/21 by NeoShell — No Comments ↓

题目：

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

分析：

删除链表中的指定节点。

这道题目很有意思。没有给出链表的头结点，因此也就无法知道要删除节点的前一个节点。这怎么能行呢？乍一看是个不可能完成的任务。其实不然。我们在做链表操作的时候往往有一种思维定式，光想着修改next，却想不到还可以修改val。直接把下一个节点的值复制到当前节点，然后再按照一般方法删除下一个节点即可。

另外注意一下，使用C或者C++等语言时，要防止内存泄露。

代码：

Java

public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

public class Solution {

public void deleteNode(ListNode node) {

node.val = node.next.val;

node.next = node.next.next;

}

LeetCode #229 Majority Element II (BM多数投票算法)

Posted on 2015/07/10 by NeoShell — No Comments ↓

题目：

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

分析：

找出数组中所有出现次数超过总数1/3的元素。

这类问题有一个很经典的算法叫做BM多数投票算法（Boyer-Moore Majority Vote algorithm），时间复杂度O(n)，空间复杂度O(1)。大体思路就是使用一个变量来计数当前出现次数最多的元素X。如果你发现了一个不等于X的数Y，那么计数变量减一。例如，如果数组中有5个X和4个Y，那么可以说X比Y多（5-4）个，或者说有4个X被Y抵消了。想进一步了解该算法的话，请参考http://goo.gl/64Nams。

对于这道题，我们要找到是出现次数大于总数1/3的数，符合要求的数可以能有0个、1个、2个。我们可以在BM多数投票算法的基础上稍作改动，使用2个计数变量即可。其他原理是一样的。需要注意的是，在一轮“抵消”的过程结束后，我们只能保证此时得到的这2个元素是数量最多的，但不见得就超过了总数的1/3。因此，我们还要再分别对这两个数进行一次计数，看它们出现的次数是不是超过了1/3。

Continue reading LeetCode #229 Majority Element II (BM多数投票算法)→

LeetCode #225 Implement Stack using Queues (队列实现栈)

Posted on 2015/07/08 by NeoShell — No Comments ↓

题目：

Implement the following operations of a stack using queues.

push(x) — Push element x onto stack.

pop() — Removes the element on top of the stack.

top() — Get the top element.

empty() — Return whether the stack is empty.

分析：

使用队列实现栈的数据结构。

1个队列。入栈时，先将要入栈的元素添加到队尾，然后将除了这个元素之外的所有元素依次出队，再入队。这样可以保证新入栈的元素总是在队列的最前面。

出栈时，直接出队即可。

Continue reading LeetCode #225 Implement Stack using Queues (队列实现栈)→

LeetCode #232 Implement Queue using Stacks (栈实现队列)

Posted on 2015/07/08 by NeoShell — No Comments ↓

题目：

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.

分析：

使用栈来实现队列的数据结构。

2个栈，stack1用来入队，stack2用来出队。

出队时，如果stack2不为空，则stack2直接弹出一个元素；如果为空，则stack1弹出所有元素，stack1每弹出一个元素就压入stack2，最后stack2再弹出一个元素。

Continue reading LeetCode #232 Implement Queue using Stacks (栈实现队列)→

LeetCode #154 Find Minimum in Rotated Sorted Array II

Posted on 2015/07/03 by NeoShell — No Comments ↓

题目：

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

分析：

一个升序数组(可能有重复元素)，所有元素旋转n个位置，例如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]。但是你不知道n是多少。请找出旋转后的数组中的最小元素。

下面给出一个二分查找的解法。在数列中，最小的数有一个特征：该数左侧的所有数都大于等于右侧的数，并且左侧和右侧的数都分别是递增的。开始，使用2个指针l,r指向数组的两端。根据刚才提到的特征，为了使l和r不断逼近最小的数，l应当尽可能指向更大的数，r应当尽可能指向更小的数。比较r和中间的数m。如果m较小，则r指向m；如果r较小，则l指向m+1。由于数组中可能出现相同的元素，如果m和r相等怎么办？只要把r左移一位再继续查找即可。

另外说明一下，取中间数的时候为什么用 m = l + (r – l) / 2 而不是 m = (l + r) / 2。如果数组的长度太大，以至于大于等于int的上界，l + r可能会引起溢出而变成负数。所以我们分成2步，先做减法，再做加法，防止溢出。

Continue reading LeetCode #154 Find Minimum in Rotated Sorted Array II→