最短路径

最短路径问题:

给定带权的有向图G=(V,E),从某顶点出发,沿图的边到达另一个顶点所经过的路径中,各边上权值之和最小的一条路径称为最短路径。

解决最短路径问题可以采用Dijstra算法和Floyd算法,其中Floyed算法可以求解任意两点间最短路径的长度。

一.Dijstra算法

Dijstra算法是按路径长度的非递减次序逐一产生最短路径的算法:首先求得长度最短的一条最短路径,再求得长度次短的一条最短路径,依次类推,直到从源点到其它所有顶点之间的最短路径都已求得为止。

设集合S存放已经求得最短路径的终点,则V-S为尚未求得最短路径的终点。初始状态下集合S中只有一个源点,设为......

二叉树的遍历(前序遍历,中序遍历和后序遍历)

二叉树是数据结构中一种非常重要的数据结构,对于二叉树的遍历也在面试以及实际应用之中非常广泛,下面总结一下对于二叉树的三种遍历方法的递归和非递归实现。

数据结构

这里是采用Java来实现的,首先给出树节点的数据结构:

public class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

以下实现方法都是返回一个遍历的结果序列。

先序遍历

先序遍历是先遍历根节点,然后先序方式遍历左子树,最后先序遍历右子树。先序遍历的递归实现:

public Arra......

位运算--元素出现次数问题

问题1:

一个数组中,除了其中一个元素只出现一次之外,其它元素都出现了两次,怎么快速找到只出现一次的元素?

问题2:

一个数组中,除了其中一个元素只出现一次之外,其它元素都出现了三次,怎么快速找到只出现一次的元素?

对于问题1比较容易解决,将所有的元素异或:ans^=x得到的就是只出现一次的元素。这是因为,相同元素异或(^)为0,出现偶数次的元素异或之后为0,0与只出现一次的元素异或就是该元素本身,这个很好理解。

对于问题2,虽然不能直接用异或,但是同样需要从位操作的角度来考虑。我的思路是:

1.将数据的元素表示为二进制的形式,并将对应的位相加;

2.如果对应的......