The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

阅读全文 »

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

阅读全文 »

​ 本科在学习数据结构时学起来就一直很吃力，特别是对于树和图的掌握不是特别牢固。在刷LeetCode关于二叉树的额题目基本束手无力。所以就趁机把二叉树的知识进行回顾，并且总结。找的是斯坦福大学的一位教授写得笔记，通俗易懂，也将几个题目事先按照自己的思路先写一写，再与参考答案进行对照。具体见最后附录。

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

今天刷LeetCode 547.Friend Circles 时发现，其就是一道典型的并查集。但是还是不能靠本科学的数据结构知识写出完整的代码，所以就趁机将并查集小结一下，主要参考资料是普林斯顿大学的《Algorithm 4th》。

浪潮之巅

吴军

2014-11-26 20:53:14

国际商用机器公司

2014-11-26 20:54:15

IBM 仅仅是一个大型计算机制造商，

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

题意：判断一个链表是否带环。

今天在刷到LeetCode 039. Combination Sum这道题时，一看就是完全背包的问题，所以就趁机参考《挑战程序设计竞赛》把背包问题进行一个小结。