第5章 第8节 链表

推荐给朋友

● 代码题:股票最大值。

参考回答:

最大利润无外乎就是计算后面的数字减去前面的数字得到的一个最大的差值;

求总体的最大差值,需要的数据:当前的最小值,当前的最大差值;遍历求解即可。

class Solution {
public:
int maxProfit(vector<int> prices)
{
int length = prices.size();
if (length < 2)
return 0;
int minPrice = prices[0];
int maxDiff = prices[1] - minPrice;
for (int i = 2; i < length; ++i)
{
if (prices[i - 1] < minPrice)
minPrice = prices[i - 1];
int currentDiff = prices[i] - minPrice;
if (currentDiff > maxDiff)
maxDiff = currentDiff;
}
return maxDiff;
}
};

● 编辑距离

参考回答:

概念

编辑距离的作用主要是用来比较两个字符串的相似度的

编辑距离,又称Levenshtein距离(莱文斯坦距离也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

在概念中,我们可以看出一些重点那就是,编辑操作只有三种。插入,删除,替换这三种操作,我们有两个字符串,将其中一个字符串经过上面的这三种操作之后,得到两个完全相同的字符串付出的代价是什么就是我们要讨论和计算的。

例如:

我们有两个字符串:kitten 和 sitting:

现在我们要将kitten转换成sitting

我们可以做如下的一些操作;

kitten–>sitten 将K替换成S   sitten–> sittin 将e替换成i

sittin–> sitting 添加g

在这里我们设置每经过一次编辑,也就是变化(插入,删除,替换)我们花费的代价都是1。

例如:

如果str1=”ivan”,str2=”ivan”,那么经过计算后等于 0。没有经过转换。相似度=1-0/Math.Max(str1.length,str2.length)=1

如果str1=”ivan1”,str2=”ivan2”,那么经过计算后等于1。str1的”1”转换”2”,转换了一个字符,所以距离是1,相似度=1-1/Math.Max(str1.length,str2.length)=0.8

算法过程

1.str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;

2.初始化(n+1)*(m+1)的矩阵d,并让第一行和列的值从0开始增长。扫描两字符串(n*m级的),如果:str1[i] == str2[j],用temp记录它,为0。否则temp记为1。然后在矩阵d[i,j]赋于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。

3.扫描完后,返回矩阵的最后一个值d[n][m]即是它们的距离。

计算相似度公式:1-它们的距离/两个字符串长度的最大值。

我们用字符串“ivan1”和“ivan2”举例来看看矩阵中值的状况:

1、第一行和第一列的值从0开始增长

图一

首先我们先创建一个矩阵,或者说是我们的二维数列,假设有两个字符串,我们的字符串的长度分别是m和n,那么,我们矩阵的维度就应该是(m+1)*(n+1).

注意,我们先给数列的第一行第一列赋值,从0开始递增赋值。我们就得到了图一的这个样子

之后我们计算第一列,第二列,依次类推,算完整个矩阵。

我们的计算规则就是:

d[i,j]=min(d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp) 这三个当中的最小值。

其中:str1[i] == str2[j],用temp记录它,为0。否则temp记为1

我们用d[i-1,j]+1表示增加操作

d[i,j-1]+1 表示我们的删除操作

d[i-1,j-1]+temp表示我们的替换操作

2、举证元素的产生 Matrix[i - 1, j] + 1 ; Matrix[i, j - 1] + 1 ; Matrix[i - 1, j - 1] + t 三者当中的最小值

3.依次类推直到矩阵全部生成

这个就得到了我们的整个完整的矩阵。

● 如何判断单链表是否是循环链表

参考回答:

时间复杂度:O(n)

空间复杂度:O(1)

两个指针,一个每次走一步,一个每次走两步,如果有环,两者会相遇。相遇后,让一个指针从头结点再次出发,两个指针每次都走一步,直到相遇点即为环入口。

public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
ListNode left = pHead;
ListNode right = pHead;
while(right!=null && right.next!=null){
left = left.next;
right = right.next.next;
if(left==right) break;
}
if(right==null || right.next == null){
return null;
}
left = pHead;
while(left!=right){
right = right.next;
left = left.next;
}
return left;
}
}

● 手写代码:反转链表

参考回答:

public class ListNode {
public int data;
public ListNode next;
}
public ListNode reverseList(ListNode pHead){

ListNode pReversedHead = null; //反转过后的单链表存储头结点

ListNode pNode = pHead; //定义pNode指向pHead;

ListNode pPrev = null; //定义存储前一个结点

while(pNode != null){

ListNode pNext = pNode.next; //定义pNext指向pNode的下一个结点

if(pNext==null){ //如果pNode的下一个结点为空,则pNode即为结果

pReversedHead = pNode;

}

pNode.next = pPrev; //修改pNode的指针域指向pPrev

pPrev = pNode; //将pNode结点复制给pPrev

pNode = pNext; //将pNode的下一个结点复制给pNode

}
return pReversedHead;
}