Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
给定一个有序链表，将其转换为一个高度平衡的二叉搜索树。
首先遍历链表获得链表长度。之后通过递归生成二叉搜索树。其生成过程和树的中序遍历类型：先是左子树，然后是根节点，最后是右子树。每添加一个树节点，就把链表节点的值赋给树节点，然后指针指向下一个链表节点。
Continue reading LeetCode #109 Convert Sorted List to Binary Search Tree (有序链表转换为平衡二叉搜索树)
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given[100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is[1, 2, 3, 4]. Return its length:4.
Your algorithm should run in O(n) complexity.
给定一个数组，求该数组中的数字所能构成的最长连续数列的长度。要求时间复杂度为O(n)。
我们使用HashMap。其中key为数组中的数字；value为该数字作为某个连续数列的边界时，该数列的长度。例如，对于数列{1,2,3,4,5}，该数列的边界时1和5，那么在HashMap中1和5对应的value都是该数列的长度5。
当我们新读取一个数字时，该数字可能和其左侧或右侧的某个连续数列连接在一起。通过读取HashMap中 n-1 和 n+1 对应的value即可获得左侧和右侧连续数列的长度。之后将它们连接在一起，构成了一个新的更长的数列。最后将新数列边界元素的value更新为新的长度即可。
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], return6.
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个长条的高度，取较短的那个，就是该位置蓄水的最大高度。最后把每个位置的蓄水量加起来即可。
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 -> 4and you are given the third node with value3, the linked list should become1 -> 2 -> 4after calling your function.
删除链表中的指定节点。
这道题目很有意思。没有给出链表的头结点，因此也就无法知道要删除节点的前一个节点。这怎么能行呢？乍一看是个不可能完成的任务。其实不然。我们在做链表操作的时候往往有一种思维定式，光想着修改next，却想不到还可以修改val。直接把下一个节点的值复制到当前节点，然后再按照一般方法删除下一个节点即可。
另外注意一下，使用C或者C++等语言时，要防止内存泄露。
Java
|
1 2 3 4 5 6 |
public class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } } |
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多数投票算法)
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 (队列实现栈)
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 (栈实现队列)
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,
0 1 2 4 5 6 7might become4 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
|
1 2 3 4 5 6 7 8 |
<?php add_filter( 'avatar_defaults', 'custom_gravatar' ); function custom_gravatar($avatar_defaults) { $my_avatar = get_bloginfo('siteurl') . '[图片路径]'; $avatar_defaults[$my_avatar] = "[头像名称]"; return $avatar_defaults; } ?> |
Given a linked list, return the node where the cycle begins. If there is no cycle, return
null.Follow up:
Can you solve it without using extra space?
检查链表是否有回路。如果有回路，则返回回路的起始节点；如果没有，则返回null。
基本思路还是使用Floyd判圈算法。指针hare每次向后移动2个节点，指针tortoise每次向后移动1个节点。如果hare最终指向尾节点则该链表无回路。否则，该链表有回路。（详见《LeetCode #141 Linked List Cycle》）
现在我们已经知道了链表有没有回路，但是如何在不使用额外空间并且不修改原链表的基础上获得回路的起始节点呢？这需要一些数学推导：
设链表起始节点为H，回路起始节点为S，两指针第一次相遇节点为M。
设回路的长度为c，S到M的距离为c1，M到S的距离为c2。
设H到S的距离为d。
设hare每次移动2，tortoise每次移动1。移动k次后两者相遇。不难发现，H到M的距离为k。
为了便于理解，请参考下图：
