包含min函数的栈 要求O(1)的时间完成正常的栈操作,以及获取栈中最小元素的操作 思路 首先可能想到用一个辅助变量存最小值。但是当这个最小值被弹出,就不能以O(1)的时间找到次小值。因此次小值也许需要在push的时候存…
剑指Offer17-反转链表
题目 反转链表,思路一直接用栈转置一下链表,思路二,记录前驱。因为链表结点的移动需要知道next,而修改当前结点的next节点为前一个结点修改了next,所以再需要一个变量寸当前节点的next,也就是需要,前驱,当前,后…
剑指Offer15-链表中倒数第K个节点
题目 输入一个链表,输出该链表中倒数第k个结点。 思路一 遍历两遍链表,第一遍求总共有几个节点n,然后算出倒数第k个是正数第几个就行了 ans = n – k +1。 思路二 如果只要求遍历一次链表,则需要用…
剑指Offer14-调整数组顺序使奇数位于偶数前面
题目 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。 朴素做法 可以想到用空间换时间,先将奇数…
剑指Offer13-合并两个有序链表
题目 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 思路 考虑一个链表为空时如何处理。多脑测几组数据。 代码 #include<iostream> #inclu…
剑指Offer12-数值的整数次方
数值的整数次方 想到使用快速幂的算法,但是第一次没有考虑到指数为负数的情况,提交之前要慎重思考。 牛客网上朴素的一层循环效率O(n)的算法也能过。 代码 #include<iostream> #include…
剑指Offer11-二进制中1的个数
题目 二进制中1的个数 思路 很容易想到,直接判断最右边是否为1(二进制与操作),然后不断右移就好。 但是负数的存在会使这个函数出现死循环。 处理的方法是,放弃通过这个数不断右移与1进行与运算(位运算右移,位运算与操作&…