LeetCode #43 Multiply Strings (非负整数高精度乘法)

题目:

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的情况。

Continue reading LeetCode #43 Multiply Strings (非负整数高精度乘法)

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更新为新的长度即可。

Continue reading LeetCode #128 Longest Consecutive Sequence

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], 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

题目:

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

 

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 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

修改WordPress评论默认头像

  1. 把自己想要设置的默认头像图片上传到服务器。建议上传到 wp-content 目录下的某个位置,例如:"/wp-content/gallery/avatar/akarin.jpg"。
  2. 通过FTP下载主题目录下的 functions.php 文件。编辑该文件,在文件最后添加如下代码,将 [图片路径] 和 [头像名称] 改为你自己的路径和名称。注意,get_bloginfo('siteurl') 会返回网站的url,所以 [图片路径] 应填写相对于根目录的相对地址。如果要填写相对于主题目录的相对路径,则应把 get_bloginfo('siteurl') 替换为 get_bloginfo('template_directory')。
  3. 保存该文件,上传至服务器。
  4. 修改成功后,我们可以在 后台 – 设置 – 讨论 中看到新上传的头像。选择新头像,保存更改即可。