Winjourn

包含min函数的栈 要求O(1)的时间完成正常的栈操作，以及获取栈中最小元素的操作 思路 首先可能想到用一个辅助变量存最小值。但是当这个最小值被弹出，就不能以O(1)的时间找到次小值。因此次小值也许需要在push的时候存…

归并排序 解析看这一篇就好 http://blog.csdn.net/yuehailin/article/details/68961304 代码 #include <stdio.h> #include <…

快速排序 1、先从数列中取出一个数作为基准数 2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边 3、再对左右区间重复第二步，直到各区间只有一个数 步骤二的时间复杂度为O(n)，而对序列n，假设…

堆排序 首先明确堆的性质 最大堆要求节点的元素都要不小于其孩子 对于数组的一个节点(下标为x)，则的两个儿子节点的下标为 2x + 1 2x + 2； 算法步骤 将待排序序列初始化为大顶堆 从最后一个非叶子节点(有子节点…

题目 反转链表，思路一直接用栈转置一下链表，思路二，记录前驱。因为链表结点的移动需要知道next，而修改当前结点的next节点为前一个结点修改了next，所以再需要一个变量寸当前节点的next，也就是需要，前驱，当前，后…

题目 输入一个链表，输出该链表中倒数第k个结点。 思路一 遍历两遍链表，第一遍求总共有几个节点n，然后算出倒数第k个是正数第几个就行了 ans = n – k +1。 思路二 如果只要求遍历一次链表，则需要用…

题目 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 朴素做法 可以想到用空间换时间，先将奇数…

题目 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 思路 考虑一个链表为空时如何处理。多脑测几组数据。 代码 #include<iostream> #inclu…

数值的整数次方 想到使用快速幂的算法，但是第一次没有考虑到指数为负数的情况，提交之前要慎重思考。 牛客网上朴素的一层循环效率O(n)的算法也能过。 代码 #include<iostream> #include…

题目 二进制中1的个数 思路 很容易想到，直接判断最右边是否为1（二进制与操作），然后不断右移就好。 但是负数的存在会使这个函数出现死循环。 处理的方法是，放弃通过这个数不断右移与1进行与运算(位运算右移，位运算与操作&…