“三次握手” 的目原因： “为了防止已失效的连接 请求报文段突然又传送到了服务端，因而产生错误”， 握手失败怎么办：超时重传，重传指定次数之后仍旧 没有收到客户端的确认报文，服务器关闭这个连接。 建立连接要握手三次，关闭连接时需要挥手四次呢？ 在 TCP 第二次握手的时候，服务端发送的 连接确 认报文段 将一个 ACK 和一个 SYN 合并到一起发送 给服务端，所以减少了一次包的发送，三次便完成 握手。对于四次挥手，因为 TCP 是全双工通信，在 主动方发送连接释放报文段后，被动方可能还要发 送数据，不能立即关闭被动方到主动方的数据通 道，所以被动方不能将确认报文段 与 ...

题目描述 在一个nm×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 如输入这样的一个二维数组， [ [1,3,1], [1,5,1], [4,2,1] ] 那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12 题解1：动态规划 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 ...

题目描述 输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。 1.输出结果可能非常大，所以你需要返回一个字符串而不是整数 2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0 题解：辅助数组，排序 代码 class Solution { public: struct compare{ bool operator()(string a,string b){ return a+b &l...

题目描述 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。 数据范围: 1<=n<=2^10 题解：动态规划 代码 class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { // 根据题意，数据范围n>1，所以不用考虑输入无效的情况 // 动态规划：使用临时变量 int curSum = 0; int resul...

题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 题解1：使用排序 题解2：使用大小根堆 代码： /* 描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值， 那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值， 那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据...

题目描述 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。 例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。 题解1:排序 代码 vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { sort(input.begin(), input.end()); vector<int> v; for (int i = 0; i < k; i++) { v.push_back(inpu...

题目描述: 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。 题解1:使用无序map 代码 int MoreThanHalfNum_Solution(vector<int> numbers) { unordered_map<int, int> m; for (int i = 0; i < numbers.size(); i++) { m[num...

题目描述 输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。 题解 图示引自:NumPy 代码 void permutation(int pos, string str, set<string>& s) { //递归出口 if (pos + 1 == str.length()) {//当 s.insert(str); return; } ...

题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示 题解1:使用辅助数组 图示引自:牛客313925129号 代码 void inOrder(TreeNode* root, vector<TreeNode*> v) { if(!root) return; inOrder(root->left, v); v.push_back(root); inOrder(root->right, v); } TreeNode* Convert(TreeNode* pRootOfTree) { if (!pR...

题目描述 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。 题解1: 采用先深拷贝各个节点，然后random重新指向，最后拆分链表 1、将深拷贝的节点插入在被拷贝节点的后面 2、改变深拷贝的节点的random指针指向 3、将原链表共和新链表拆开 图示引自牛客50...

题目描述 输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n 如二叉树root为{10,5,12,4,7},expectNumber为22 则合法路径有[[10,5,7],[10,12]] 题解:基于深度优先的先序遍历 该题目的二叉树是从根节点、左子树、右子树开始进行遍历的，所以可以采用先序遍历的方法 代码 void dfs(Tr...

题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。 提示： 1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。 2.该题我们约定空树不是二叉搜索树 3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历. 题解: 图示引自:NumPy 代码: class Solution { public: bool check(vector<int> sequence,int left,int right){ ...

题目描述 不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。 题解:层次遍历 代码 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { publ...

题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。 假设压入栈的所有数字均不相等。 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。 题解:使用辅助栈 图是引自:牛客500979850号,该图清晰说明了代码的流程 代码 bool IsPopOrder(vector<int> pushV, vector<int> popV) { stack<int> s;//定义一个栈,存放push...