归档 2015年7月31日

题目描述：

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目大意：

给定一个整数数组，除一个元素只出现一次外，其余各元素均出现两次。找出那个只出现一次的元素。

注意：

你的算法应该满足线性时间复杂度。可以不使用额外的空间完成此题吗？

解题思路：

对数组元素执行异或运算，最终结果即为所求。 ...

题目描述：

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

题目大意：

给定一个链表，其中的节点包含一个额外的随机指针，可能指向链表中的任意一个节点或者为空。

返回链表的深拷贝。

解题思路：

解法I：时间复杂度O(n)，空间复杂度O(n)

使用哈希表保存原链表到新链表节点的映射，即可实现对随机指针域的拷贝

Python代码： ...