Algorithm-Linked List

链表:线性表的链式存储结构。

链表的创建:链表创建的时候要有一个节点永远指向链表的头节点或者首元节点,防止链表丢失。
头节点:一个不存储或者存储链表长度的节点。
首元节点:链表第一个存储数据的节点。

链表节点的添加:链表添加新节点需要
(1)创建新节点,把新节点的next指向插入位置的下一个节点
(2)把插入位置的上一个节点的next指向新节点。
注意:如果不保存插入位置后的节点,那么那些节点将会丢失。因为链表不是顺序存储,你将会把那些节点丢失在内存中。

链表节点的删除:链表删除节点需要
(1)创建一个临时节点用于保存需要删除的节点
(2)把删除节点的上一节点的next指向删除节点的下一个节点。
注意:如果不使用临时节点来保存删除节点,那么删除节点将会丢失。删除的节点需要通过free释放,否则将造成内存泄漏。

C代码:

Algorithm-BinaryHeap

二叉堆:二叉堆是一个完全二叉树或者近似二叉树的一种堆结构,一般分为大顶堆和小顶堆。所谓的大顶堆就是父节点的值大于左右子节点且堆顶是值最大的元素,而小顶堆相反,堆顶为最小元素。

二叉堆的删除:删除堆顶元素,并且把最末尾元素放到堆顶,再依据大/小顶堆的规则调整整个堆结构。
思路:遍历节点并进行判断。
<1>如果该节点的左子节点存在,右子节点不存在,那么删除左子节点,并将左子节点值赋予根节点;
<2>如果该节点的右子节点存在,而该节点的下一个(相邻)节点的左子节点不存在,那么删除该节点的右子节点,并将右子节点的值赋予根节点;
最后进行二叉堆重建,恢复到小/大顶堆的状态。

二叉堆的添加:把元素添加到最末尾,再根据大/小顶堆的结构调整整个堆。

二叉堆的重建:通过递归遍历节点,并比较父节点与子节点的值根据大/小顶堆的规则进行交换,直至遍历完所有节点并且符合该堆的规则。

Python3代码实现:

Algorithm-Bellman_Ford

算法核心:对包含任意边的集合U,其中w(p, n)表示从点p到点n的权重,d(p)表示从起始点到点p的权重。则,有松弛操作,当:

d(n) > w(p, n) + d(p)

时,则更新:

d(n) = w(p, n) + d(p)

所以,松弛操作的作用就是为了更新从起始点到点n的权值,使其趋向最小。

这里举个例子,目前有有向图,设为集合E,表示如下(下方中infinite表示为无穷大的数):
A->B:-3;
B->C:2;
C->D:3;
D->E:2;
A->E:5;
接下来进行,|V|-1轮的松弛操作,因为图的最短路径最长不会经过超过 |V|-1条边,这里的|V|代表的节点的数量。
设起始点为A,则初始化点A到点A,B,C,D,E的距离,设为集合U,表示为:
A->A:0;
A->B:infinite;
A->C:infinite;
A->D:infinite;
A->E:infinite;
第一次遍历执行松弛操作,更新集合U:
A->A:0;
A->B:-3;{d(B) > w(A, B) + d(A) => infinite > 0 + (-3),执行更新}
A->C:infinite;
A->D:infinite;
A->E:5;{d(E) > w(A, E) + d(E) => infinite > 0 + 5,执行更新}
第二次遍历执行松弛操作,更新集合U:
A->A:0;
A->B:-3;
A->C:-1;{d(C) > w(B, C) + d(B) => infinite > (-3) + 2,执行更新}
A->D:infinite;
A->E:5;
第三次遍历执行松弛操作,更新集合U:
A->A:0;
A->B:-3;
A->C:-1;
A->D:2;{d(D) > w(C, D) + d(C) => infinite > -1 + 3, 执行更新}
A->E:5;
第四次遍历执行松弛操作,更新集合U:
A->A:0;
A->B:-3;
A->C:-1;
A->D:2;
A->E:4;{d(E) > w(D, E) + d(D) => 5 > 2 + 2,执行更新}
完成所有4轮松弛操作,得到A到各个节点的最优解。

这里会发现一个问题,如果有负权环怎么办。负权环的存在会导致在该权环中的值可以无限的小。所以这里直接可以进行一个简单的判断,判断进行n-1轮(n表示节点数量)后该图是否还存在可以进行松弛操作的点,如果存在,即表示该图中存在负权环,没有解。

Python3代码实现:

Algorithm-LeetCode_Plus_One

Plus One

English:

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Example 2:

中文:

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

示例 2:

Answer(Use Time:52ms; Language: Python3):

Best Answer(Use Time:36ms; Language: Python3):

Algorithm-LeetCode_Length_Of_Last_Word

Length Of Last Word

English:

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

中文:

给定一个仅包含大小写字母和空格 ' ' 的字符串,返回其最后一个单词的长度。

如果不存在最后一个单词,请返回 0 。

说明:一个单词是指由字母组成,但不包含任何空格的字符串。

示例:

Answer(Use Time:44ms; Language: Python3):

Best Answer(Use Time:36ms; Language: Python3):