题目描述 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.Return a deep copy of the list. 题目解析 其实这个题目跟剑指offer里面题目35复制复杂链表是一样的。我们以下图为例 所以这个题也是分为三步： - 第一步：逐一复制A和B和C和D，复制后为A'、B'、C'和D'（加…

single-number-ii Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? ​ int singleNumber(int A[], in…

面试的部门是：云与智慧产业事业群（CSIG，即Cloud and Smart Industries Group）。我也不知道凉没凉， 总的来说， 确实有一些部分回答的不是很好，特别是自己存在以下问题： 1.对于没用到但了解的方面，没有深入去说，即便知道一个方法，也应该把它的原理说出来。 2.对于不了解具体方法的，起码要把基本原理说出来。我太实在了，应该说一句我了解基本原理，可以说一下。 3.面试太紧张，说话太没有自信，说话不流畅。 我感觉得找时间专门总结一下自己在面试时候存在的非技术性问题，必须加以改正。 具体问了…

题目1 序列化二叉树 题目描述 请实现两个函数，分别用来序列化和反序列化二叉树 题目解析 序列化二叉树可以使用前序遍历来进行，这样的话响应的反序列化在根节点的数值读出来的时候就可以开始了。如果二叉树读的时候遇到NULL，就输出一个“\$ ”。我们以字符串“1,,2,4,$,\$,\$,3,5,\$,\$,6,\$,\$”为例来分析如何反序列化。第一个读出来的数字是1，所以这肯定是根节点的值，接下来读出来的肯定是根节点左子结点上的值，然后接下来再读到的肯定是其左子结点上的值。接着我们读出了两个“$”，这表明4的左右子…

最大收益问题 问题分析 经过分析，又根据最大流最小割定理，最大流的流值等于最小割容量。即：实验方案净收益=所有实验项目收益-最大流值。所以只需要求出最大流值即可、 算法设计 构建网络。根据输入的数据，添加源点和汇点，从源点s到每个实验项目Ei有一条有向边，容量是项目产生的收益pi。从每个实验仪器Ij到汇点t有一条有向边，容量是仪器费用cj，每个实验项目到该实验项目用到的仪器有一条有向边容量是 ∞，创建混合网络。 基于ISAP算法求网络最大流。 输出最大收益及实验方案。最大收益实验方案就是最小割中的S集合去掉源点。在…

配对方案问题 问题分析 先了解几个概念。 二分图：又称二部图。设G=(V,E)是一个无向图，如果结点集V客分割为两个互不相交的子集（V1,V2），并且图中的每条边（i,j）所关联的两个结点i和j分别属于这两个不同的结点集（i∈V1，j∈V2），则称图G是一个二分图。 匹配：在图论中，一个匹配是一个边的集合，其中任意两条边都没有公共结点。 最大匹配：一个图所有匹配中，边数最多的匹配，成为这个图的最大匹配。 最佳推销员配对方案要求两个推销员男女搭配，相当于男女推销员形成了两个不相交的集合，可以配合工作的男女推销员有连线…

优化扩展——重贴标签算法ISAP 首先对所有的结点标记到汇点的最短距离，称之为高度。标高从汇点开始，用BFS方式，汇点的邻接点高度为1，继续访问的结点高度是2，一直到源点结束。 贴好标签之后，就可以从源点开始，沿着高度h(u)=h(v)+1且具有可行邻接边（cap>flow)的方向前进。我们找到了1-2-4-6。 我们再次从源点开始搜索，沿着高度h(u)=h(v)+1且具有可行邻接边（cap>flow)的方向前进，h(1)=3,h(2)=2，走到这里无法走到4号结点，因为没有邻接边，3号结点不近没有邻接边，而且高度…