#algorithm-project

小象算法学习的每节课的案例的JAVA实现

##第一节

###链表

1. 给定两个链表,分别表示两个非负整数。他们的数字逆序存放在数组中,计算两个数字的和。 如:输入2->4->3,5->6->4 输出 7->0->8

2. 链表的部分翻转,给定一个链表,翻转该链表从m到n的位置,直接翻转,不申请新的空间 如:输入1->2->3->4->5,m=1, n = 3, 输出 1->4->3->2->5

3. 链表去重,给定排序的链表,删除重复元素 如:输入2->3->3->5->7->8->8->8->9->9->10,输出2->3->5->7->8->9->10

4. 给定一个链表和一个值x,将链表划分成两 部分,使得划分后小于x的结点在前,大于 等于x的结点在后。在这两部分中要保持原 链表中的出现顺序。 如:给定链表1->4->3->2->5->2和x = 3,返回 1->2->2->4->3->5

5. 判断一个单向链表是否有环

6. 给定两个单向链表,计算两个链表的第一个公共结点,若没有公共节点,返回空。

###队列

1. 队列的实现

2. 利用队列,对一个有向无环图进行拓扑排序 对一个有向无环图(Directed Acyclic Graph, DAG) G 进行拓扑排序,是将G中所有顶点排成线性序列, 使得图中任意一对顶点u和v, 若边(u,v)∈E(G), 则u在线性序列中出现在v之前。

3. 给定如下图所示的无向连通图,假定图中所有边的权值都为1,显然,从源点A到终点T的最短路径有多条,求不同的最短路径的数目。

最短路径条数

###栈

1. 用链表实现的栈

2. 用栈实现的最长括号匹配

3. 计算逆波兰表达式

##第二节

###字符串的循环移位

给定一个字符串S[0...N-1],要求把S的前k个字符移动到S的尾部,如把字符串"abcdef" 前面的2个字符‘a’、‘b’移动到字符串的尾 部,得到新字符串"cdefab":即字符串循环左移k。

时间复杂度为 O(n),空间复杂度为 O(1)。

###LCS

最长公共子序列,即Longest Common Subsequence

一个序列S任意删除若干个字符得到新序列T,则T叫做S的子序列; 两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序列。 字符串13455与245576的最长公共子序列为455 字符串acdfg与adfc的最长公共子序列为adf

该问题属于动态规划问题,表达式如下

动态规划解决LCS

###LIS

最长递增子序列LIS,找出给定数组最长且单调递增的子序列。

• 解法1:使用LCS解决,将该数组进行排序,形成一个新的数组A,求该数组A和原数组的LCS。
• 解法2:动态规划直接解决

##排序算法

###冒泡排序

两两比较,大的向上冒。时间复杂度O(n),空间复杂度O(1)

###插入排序

假设前i个数已经排好序,将第i+1个数放在其相应的位置上。时间复杂度O(n),空间复杂度O(1)

###选择排序

里层循环每次找最小的,找到的最小的放在外层循环中的第i位。时间复杂度O(n),空间复杂度O(1)

###快速排序

找一个基准元素,小于基准元素的放在列表的左边,大于基准元素的放在列表的右边,递归排序左列表和右列表。 时间复杂度O(n * log n),最坏时间复杂度O(n^2)

###归并排序

时间复杂度O(n * log n)