题目:
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
分析:
任意长度非负整数乘法。
基本思路就是模拟用竖式手算乘法的过程。
注意处理进位和乘0的情况。
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
任意长度非负整数乘法。
基本思路就是模拟用竖式手算乘法的过程。
注意处理进位和乘0的情况。
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 -> 4
and you are given the third node with value3
, the linked list should become1 -> 2 -> 4
after 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 7
might 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; } ?> |