题目：
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的情况。
Author Archives: NeoShell
LeetCode #109 Convert Sorted List to Binary Search Tree (有序链表转换为平衡二叉搜索树)
题目：
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 (有序链表转换为平衡二叉搜索树)
LeetCode #128 Longest Consecutive Sequence
题目：
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更新为新的长度即可。
LeetCode #42 Trapping Rain Water
题目：
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个长条的高度，取较短的那个，就是该位置蓄水的最大高度。最后把每个位置的蓄水量加起来即可。
LeetCode #237 Delete Node in a Linked List
题目：
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; } } |
LeetCode #229 Majority Element II (BM多数投票算法)
题目：
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 (队列实现栈)
题目：
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 (栈实现队列)
题目：
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
题目：
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
修改WordPress评论默认头像
- 把自己想要设置的默认头像图片上传到服务器。建议上传到 wp-content 目录下的某个位置，例如："/wp-content/gallery/avatar/akarin.jpg"。
-
通过FTP下载主题目录下的 functions.php 文件。编辑该文件，在文件最后添加如下代码，将 [图片路径] 和 [头像名称] 改为你自己的路径和名称。注意，get_bloginfo('siteurl') 会返回网站的url，所以 [图片路径] 应填写相对于根目录的相对地址。如果要填写相对于主题目录的相对路径，则应把 get_bloginfo('siteurl') 替换为 get_bloginfo('template_directory')。
12345678<?phpadd_filter( 'avatar_defaults', 'custom_gravatar' );function custom_gravatar($avatar_defaults) {$my_avatar = get_bloginfo('siteurl') . '[图片路径]';$avatar_defaults[$my_avatar] = "[头像名称]";return $avatar_defaults;}?> - 保存该文件，上传至服务器。
- 修改成功后，我们可以在 后台 – 设置 – 讨论 中看到新上传的头像。选择新头像，保存更改即可。