题目解释 鸡尾酒排序问题实际上是冒泡排序的一个改进。冒泡排序是一个单向的递增或者递减的交换排序，而鸡尾酒排序则是双向的，也就是说，如果我们以要求一个数组有n个数字从小到大排序，则： 第一趟是正向排序，选出第n个值（最大值）； 第二趟是反向排序，选出第1个值（最小值）； 第三趟是正向排序，选出第n-1个值（次大值）； 第四趟是反向排序，先出第2个值（次小值）。 然后以此类推，最后得出整个序列，所以实际上就相当于将原来的冒泡排序有一段代码写成了两段。然后为了优化运行时间，所以设置一个标志位，当确定没有元素交换的时候，就…

荷兰国旗问题 荷兰国旗问题，或者说黑猫白猫灰猫问题，其实都是一样的，就是说有三类数据乱序排列，然后要求用O(N)的时间复杂度，O(1)的空间复杂度使其有序。因其类似于荷兰国旗，所以被称为荷兰国旗问题（德国、法国在这里表示不服~）。 输入 0,1,2,1,2,0,1,1,0,2,1,0,1,2,2,1,0,0 输出 0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2 代码解析 排序方法：设置start/end/current三个指针，分别指向开头、开头、结尾。在current<=end的背景…

排序 外排中使用置换选择排序的目的,是为了增加初始归并段的长度。√ 插入排序：需要有一个对比查找过程；选择排序直接插入指定位置。 快速排序中，第i趟排序结果至少确定i个元素的位置。 使用堆排序方法排序（45,78,57,25,41,89），初始堆为89,78,57,25,41,45。 将两个各有n个元素的有序表归并成一个有序表,最少的比较次数是n，最多是2n-1。 解析： 方法： 1. 首先将所有元素按照初始顺序填充到一个完全二叉树中 2. 从“最后一个非终端节点”开始，调用siftdown方法，调整堆的结构，直到…

C++/C语言基础 对下列语句正确的描述是? const int *x;   //① int * const x;   //② 答案：语句②的含义是指针变量x不能更改 解析：const修饰 * 左侧的时候，表示指向的数据类型为常量；当const修饰 * 右侧的时候，表示指针本身为常量。 下述静态数据成员的特征中，D是错误的。 解析： 1. 静态数据成员在定义或说明时前面加关键字static。//静态变量的定义 2. 静态成员初始化与一般数据成员初始化不同。静态数据成员初始化的格式如下： <数据类型>&l…

Surrounded Regions 题目描述 Given a 2D board containing'X'and'O', capture all regions surrounded by'X'.A region is captured by flipping all'O's into'X's in that surrounded region . For example, X X X X X O O X X X O X X O X X After running your function, the board…

Edit distance(dynamic programing) 题目描述 Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)You have the following 3 operations permitted on a word:a) Insert a character b) …

Construct binary tree from preorder and inorder traversal 题目描述 Given preorder and inorder traversal of a tree, construct the binary tree. Note:  You may assume that duplicates do not exist in the tree. 思路 关于根据前序和中序如何得到二叉树的结构的计算方式，我就不重复了，之前的程序里面也有，这里就只说说代码里几个参数…