归档 2014

Java OOP与Python OOP的区别
作者是 发布于 在 译林.

For a Java guy Python is an anarchic playgound where anyone can grab a club and start mauling your head.

对于Java的忠实粉丝来说，Python就像是一个无政府主义的游乐场，任何人都可以随手拿起一根棍子敲你的头。

For a Python guy Java is a an Orwellian universe where you are constantly shackled to someone ...

继续阅读

Java容器类LinkedList与ArrayList使用时机对比
作者是 发布于 在 Java, 译林.

  大多数Java初学者在使用动态数组时，会不假思索的选择ArrayList。但实际上，除了ArrayList，还有LinkedList可供选用。

  那么，在使用Java的动态数组时，怎样在ArrayList与LinkedList之间做出选择呢？

  一言以蔽之，在大多数使用场景中，ArrayList与ArrayDeque要优于LinkedList。对于初学者来说，在拿不准用哪个时，不妨使用ArrayList。

  LinkedList与ArrayList是List接口的两种不同的实现。LinkedList使用双向链表实现。ArrayList则使用动态可变长数组实现。

  对于标准的链表和数组运算，不同的方法会有不同的算法运行时间。

  对于LinkedList<E>：

  • get(int index)  O(n)
  • add(E element)  O(1)
  • add(int index, E ...

继续阅读

[Leetcode]Sort List
作者是 发布于 在 LeetCode.

题目描述：

Sort a linked list in O(n log n) time using constant space complexity.

题目大意：

使用常数空间复杂度，对一个链表执行O(n log n）时间复杂度的排序

解题思路：

归并排序，链表的中点可以通过“快慢指针”法求得。

Python代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self ...

继续阅读

Java实现单向链表的归并排序
作者是 发布于 在 Java, 他山之石, 数据结构.

由于链表（LinkedList）不支持随机访问（Random Access），只允许顺序访问，因此对于链表的O(logn)时间复杂度的排序算法不可以采用诸如快速排序等基于随机访问的排序算法，而归并排序可以满足这一需求。

归并排序是分治法（Divide and Conquer）的典型应用，其伪代码如下：

merge_sort(list) {
  split list into two halfs, say first and second ;
  merge_sort(firstHalf);
  merge_sort(secondHalf);
  merge(firstHalf,secondHalf);
}

下面的Java代码实现了对单链表（singly linked list）的归并排序，代码实现优美 ...

继续阅读

每月存档

明年