数据结构与算法 - zhongjiajie/zhongjiajie.github.com GitHub Wiki
栈实现队列功能
- bitmap解决海量数据寻找重复
- 判断个别元素是否在海量数据当中等问题.最后说说BitMap的特点已经在各个场景的使用性
例子: 给一台普通PC，2G内存，要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数，给出一个整数，问如果快速地判断这个整数是否在文件40亿个数据当中
思考情况: 40亿个int占（40亿\*4）/1024/1024/1024大概为14.9G左右，很明显内存只有2G，放不下，因此不可能将这40亿数据放到内存中计算.要快速的解决这个问题最好的方案就是将数据搁内存了，所以现在的问题就在如何在2G内存空间以内存储着40亿整数。一个int整数在java中是占4个字节的即要32bit位，如果能够用一个bit位来标识一个int整数那么存储空间将大大减少，算一下40亿个int需要的内存空间为40亿/8/1024/1024大概为476.83 mb
思路: 1个int占4字节即4*8=32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据，其中N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:
- tmp[0]: 可表示0~31
- tmp[1]: 可表示32~63
- tmp[2]: 可表示64~95
那么接下来就看看十进制数如何转换为对应的bit位,假设这40亿int数据为：6,3,8,32,36,......，那么具体的BitMap表示为下图.如何判断int数字在tmp数组的哪个下标，这个其实可以通过直接除以32取整数部分，例如：整数8除以32取整等于0，那么8就在tmp[0]上。另外，我们如何知道了8在tmp[0]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp[0]中的第8 mod上32等于8，那么整数8就在tmp[0]中的第八个bit位（从右边数起）。
java有一个比较老的bitset工具
# java原生工具
import java.util.BitSet;
public class BitSetTest {
public static void main(String[] args) {
int [] array = new int [] {1,2,3,22,0,3,63};
BitSet bitSet = new BitSet(1);
System.out.println(bitSet.size()); //64 (int) Math.ceil((double) 1 / 32)) + 1 防止32溢出
bitSet = new BitSet(65);
System.out.println(bitSet.size()); //128
bitSet = new BitSet(23);
System.out.println(bitSet.size()); //64
//将数组内容组bitmap
for(int i=0;i<array.length;i++) {
bitSet.set(array[i], true);
}
System.out.println(bitSet.get(22));
System.out.println(bitSet.get(60));
System.out.println("下面开始遍历BitSet：");
for ( int i = 0; i < bitSet.size(); i++ ) {
System.out.println(bitSet.get(i));
}
}
}
# 自己实现的bitmap工具
/**
* 实现BitMap
*注：这个bitMap的index是从1开始的
*/
public class BitMap {
private long length;
private static int[] bitsMap;
//构造函数中传入数据中的最大值
public BitMap(long length) {
this.length = length;
// 根据长度算出，所需数组大小
bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
}
public int getBit(long index) {
int intData = bitsMap[(int) ((index - 1) >> 5)];
int offset = (int) ((index - 1) & 31);
return intData >> offset & 0x01;
}
public void setBit(long index) {
// 求出该index - 1所在bitMap的下标
int belowIndex = (int) ((index - 1) >> 5);
// 求出该值的偏移量(求余)
int offset = (int) ((index - 1) & 31);
int inData = bitsMap[belowIndex];
bitsMap[belowIndex] = inData | (0x01 << offset);
}
public static void main(String[] args) {
BitMap bitMap = new BitMap(32);
bitMap.setBit(32);
System.out.println(bitMap.getBit(1));
System.out.println(bitMap.getBit(32));
}
}二叉树具有以下几个性质：
- 二叉树中，第 i 层最多有
2^(i-1)个结点。 - 如果二叉树的深度为 K，那么此二叉树最多有
2^K-1个结点。（这个是2^1-1 + 2^2-1 + .... + 2^i-1化简到的） - 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则
n0=n2+1。（详见二叉树）
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。其有如下属性：
- 满二叉树中第 i 层的节点数为
2^(n-1)个。 - 深度为 k 的满二叉树必有
2^k-1个节点 ，叶子数为2^(k-1)。 - 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
- 具有 n 个节点的满二叉树的深度为
log2(n+1)。
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。其除了有二叉树的性质外还有：
- n 个结点的完全二叉树的深度为
[log2n]+1（⌊log2n⌋表示取小于 log2n 的最大整数。例如，⌊log24⌋= 2，而 ⌊log25⌋ 结果也是 2。） - 对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：
- 当
i>1时，父亲结点为结点[i/2]。（i=1 时，表示的是根结点，无父亲结点） - 如果
2*i>n（总结点的个数） ，则结点i肯定没有左孩子（为叶子结点）；否则其左孩子是结点2*i。 - 如果
2*i+1>n，则结点 i 肯定没有右孩子；否则右孩子是结点2*i+1。
- 当
二叉树遍历算法包括：先序遍历、中序遍历、后序遍历、层序遍历。其中的先中后是针对根节点来说的，层次遍历是从节点少的层到节点多的层一次遍历
0
/ \
1 2
/ \ / \
3 4 5 6- 先序遍历：
根节点 -> 左子树 -> 右子树，所以其结果是0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 - 中序遍历：
左子树 -> 根节点 -> 右子树，所以其结果是3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6 - 后序遍历：
左子树 -> 右子树 -> 根节点，所以其结果是3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0 - 层序遍历：
从最顶层的节点开始，从左往右依次遍历，所以其结果是0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
排序是非常耗时的工作,所以得到一个有序数列后要保持他的有序性,提高性能
分治法(Divide&Conquer),把一个大的问题,转化为若干个子问题(Divide),每个子问题都解决,大的问题便随之解决(Conquer).减治法只需要解决其中的一个子问题就行了
- 快速排序,时间复杂度
O(n*lg(n))
减治法(Reduce&Conquer)是分治法的特例,把一个大的问题,转化为若干个子问题(Reduce),这些子问题中只解决一个,大的问题便随之解决(Conquer),分治法需要解决所有的子问题
- 二分查找,时间复杂度
O(lg(n))
2的幂次方转换成二进制后,很容易就会发现有一个特点：二进制中只有一个1,并且1后面跟了n个0；因此问题可以转化为判断1后面是否跟了n个0就可以了.如果将这个数减去1后会发现,仅有的那个1会变为0,而原来的那n个0会变为1；因此将原来的数与去减去1后的数字进行与运算后会发现为零.
def is_power_of_2(n):
return n & (n - 1) == 0从arr[1, n]这n个数中,找出最大的k个数(k<n),如在arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中,找出最大的k=5个拜托,面试别再问我TopK
-
先对数组排序然后切片,伪代码
sort(arr, 1, n);return arr[1, k],时间复杂度O(n*lg(n)).缺点:明明只需要TopK,却将全局都排序了,提高了算法的复杂度。那能不能不全局排序,而只局部排序呢？这就引出了第二个优化方法 -
不再全局排序,只对最大的k个排序.冒泡排序,每冒一个泡,找出最大值,冒k个泡,就得到TopK,伪代码
for(i=1 to k) { bubble_find_max(arr,i); } return arr[1, k];
时间复杂度:
O(n*k).这个方法将全局排序优化为了局部排序,非TopK的元素是不需要排序的,节省了计算资源。不少朋友会想到,需求是TopK,是不是这最大的k个元素也不需要排序呢？这就引出了第三个优化方法 -
只找到TopK,不排序TopK.先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素.接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素.扫描完所有n-k个元素,最终堆中的k个元素,就是猥琐求的TopK
heap[k] = make_heap(arr[1, k]); for(i=k+1 to n){ adjust_heap(heep[k],arr[i]); } return heap[k];
时间复杂度
O(n*lg(k)),n个元素扫一遍,假设运气很差,每次都入堆调整,调整时间复杂度为堆的高度,即lg(k),故整体时间复杂度是n*lg(k).堆,将冒泡的TopK排序优化为了TopK不排序,节省了计算资源。堆,是求TopK的经典算法 -
随机选择算法,引入快速排序(分治法)的partition思想,加上减治法的只解决其中一个子问题就解决整个问题的思想,
i = partition(arr, low, high)-
再回过头来看看第一次partition,划分之后：
i = partition(arr, 1, n);- 如果i大于k,则说明arr[i]左边的元素都大于k,于是只递归arr[1, i-1]里第k大的元素即可；
- 如果i小于k,则说明说明第k大的元素在arr[i]的右边,于是只递归arr[i+1, n]里第k-i大的元素即可；
- 随机选择算法randomized_select,其伪代码如下
int RS(arr, low, high, k){ if(low== high) return arr[low]; i= partition(arr, low, high); temp= i-low; //数组前半部分元素个数 if(temp>=k) return RS(arr, low, i-1, k); //求前半部分第k大 else return RS(arr, i+1, high, k-i); //求后半部分第k-i大 }
复杂度是
O(n) -
-
bitmap,用时间换空间(如果机器内存足够情况下),比随机选择算法效率更高.bitmap需要多少储存空间取决于集合中的元素值域.如果值域是整个int类型的话就申请
2^32个bit(4G内存),可以将S={1,3,5,7,9}转换成1010101010000000.bitmap的一个缺点是相同的元素会被去重,多个相同的数只会记录一次bit值,这是只要将bit的值从0 1换成对应数字出现的次数就行,如arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6}的计数bitmap是121112211000000,求topk只需要将最高位出现的次数相加就行
[0, 1, 1, 2, 3, 5, 8, 13, ...]
- 递归法
# n for fib number
def fib_recur(n):
assert n > 0, "fib number have to gt 0"
if n <= 1:
return n
return fib_recur(n-2) + fib_recur(n-1)- 推导法
# n for fib number
def fib_loop(n):
assert n > 0, "fib number have to gt 0"
r = [0]
a, b = 0, 1
for i in range(n):
a, b = b, a + b
r.append(a)
return r- 生成器,相对来说更加节省空间
def fib_generator(n):
assert n > 0, "fib number have to gt 0"
i = 0
a, b = 0, 1
while i <= n:
yield a
a, b = b, a + b
i += 1
for i in fib_generator(10):
print(i)实现一个栈,除了普通栈的pop及push之外,还可以进行getMin操作,返回栈中最小的元素.栈中存储的都是int元素
- 用一个变量保存栈的最小元素,当push进来的值比变量小的时候更新栈,否则不更新.当pop的元素和最小元素相等时,遍历栈更新最小元素, 时间复杂度 pop
O(n),其他操作O(1). 空间复杂度O(1)
class minStack():
"""
>>> s = minStack()
>>> s
[]
>>> s.pop()
Traceback (most recent call last):
...
IndexError: pop empty stack
>>> s.push(3)
>>> s.push(2)
>>> s.push(1)
>>> s
[3, 2, 1]
>>> s.push(4)
>>> s.get_min()
1
>>> s.pop()
4
>>> s
[3, 2, 1]
>>> s.get_min()
1
>>> s.pop()
1
>>> s.get_min()
2
>>> s.pop()
2
>>> s.pop()
3
>>> s
[]
"""
_stack = []
_minEle = None
def __repr__(self):
return str(self._stack)
def pop(self):
if len(self._stack) == 0:
raise IndexError("pop empty stack")
last = self._stack.pop()
if last == self._minEle:
self._minEle = None
return last
def push(self, e):
self._stack.append(e)
if (not self._minEle) or (e < self._minEle):
self._minEle = e
def get_min(self):
if not self._stack:
raise ValueError("empty stack have no min values")
return self._minEle if self._minEle else min(self._stack)
if __name__ == "__main__":
import doctest
doctest.testmod()import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
public class minStack {
private List<Integer> data = new ArrayList<Integer>();
private Integer mins = null;
public void push(int num) {
data.add(num);
if (mins == null) {
// 初始化mins
mins = num;
} else {
if (num < mins) {
mins = num;
}
}
}
public int pop() {
// 栈空，异常，返回-1
if (data.size() == 0) {
throw new EmptyStackException();
}
int last = data.remove(data.size() - 1);
if (last == mins) {
mins = null;
}
return last;
}
public int getMin() {
if (mins == null) {
if (data.size() == 0) {
throw new EmptyStackException();
} else {
mins = data.get(0);
}
for (int i : data) {
if (mins > i) {
mins = i;
}
}
return mins;
} else {
return mins;
}
}
public static void main(String[] args) {
minStack s = new minStack();
s.push(3);
s.push(2);
s.push(1);
System.out.println(s.getMin() == 1);
s.push(4);
System.out.println(s.getMin() == 1);
s.pop();
s.pop();
System.out.println(s.getMin() == 2);
s.pop();
s.push(1);
System.out.println(s.getMin() == 1);
}
}- 通过空间换时间降低程序的时间复杂度.申请一个辅助栈,保留数据栈的最小值,每次push判断如栈元素和最小值的大小,将较小的值设为当前最小值并存入辅助栈,每次pop两个栈一起出栈, 时间复杂度
O(1). 空间复杂度O(n)
class minStack():
"""doctest like below"""
_stack = []
_minEle = []
def __repr__(self):
return str(self._stack)
def pop(self):
if len(self._stack) == 0:
raise IndexError("pop empty stack")
self._minEle.pop()
return self._stack.pop()
def push(self, e):
self._stack.append(e)
if not self._minEle:
self._minEle.append(e)
else:
if e < self.get_min():
self._minEle.append(e)
else:
self._minEle.append(self.get_min())
def get_min(self):
return self._minEle[len(self._minEle) - 1]
if __name__ == "__main__":
import doctest
doctest.testmod()import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
public class minStack {
private List<Integer> data = new ArrayList<Integer>();
private List<Integer> mins = new ArrayList<Integer>();
public void push(int num) {
data.add(num);
if (mins.size() == 0) {
// 初始化mins
mins.add(num);
} else {
// 辅助栈mins每次push当时最小值
int min = getMin();
if (num >= min) {
mins.add(min);
} else {
mins.add(num);
}
}
}
public int pop() {
// 栈空，异常，返回-1
if (data.size() == 0) {
throw new EmptyStackException();
}
// pop时两栈同步pop
mins.remove(mins.size() - 1);
return data.remove(data.size() - 1);
}
public int getMin() {
// 栈空，异常，返回-1
if (mins.size() == 0) {
throw new EmptyStackException();
}
// 返回mins栈顶元素
return mins.get(mins.size() - 1);
}
public static void main(String[] args) {
minStack s = new minStack();
s.push(3);
s.push(2);
s.push(1);
System.out.println(s.getMin() == 1);
s.push(4);
System.out.println(s.getMin() == 1);
s.pop();
s.pop();
System.out.println(s.getMin() == 2);
s.pop();
s.push(1);
System.out.println(s.getMin() == 1);
}
}- 申请一个辅助栈,这个栈保存的是最小元素的索引,而不是最小元素本身,当辅助栈为空时将入栈元素的索引入辅助栈(此时主栈也为空),当辅助栈不为空,入栈元素如果比辅助栈索引对应的值大,不入栈,如果小,则将元素的所以入辅助栈.这样可以节省辅助栈的空间副复杂度,
实现一个具备普通栈的功能,又可以获得栈中最大和最小元素的栈
class Stack(object):
"""
>>> s = Stack()
>>> s.show()
'Stack is empty'
>>> s.push(10)
>>> s
Stack ([10], min=10, max=10)
>>> s.push(50)
>>> s
Stack ([10, 50], min=10, max=50)
>>> s.push(20)
>>> s
Stack ([10, 50, 20], min=10, max=50)
>>> s.push(9)
>>> s
Stack ([10, 50, 20, 9], min=9, max=50)
>>> s.min
9
>>> s.max
50
>>> s.pop()
9
>>> s
Stack ([10, 50, 20], min=10, max=50)
>>> s.pop()
20
>>> s.pop()
50
>>> s
Stack ([10], min=10, max=10)
"""
_min_idx_stack = []
_max_idx_stack = []
_data = []
def __repr__(self):
if not self._data:
return "Stack is empty"
return "Stack ({}, min={}, max={})".format(
self._data,
self.min, self.max)
def _push_idx_stack(self, stack):
stack.append(len(self._data) - 1)
def _pop_idx_stack(self):
data_last_idx = len(self._data) - 1
if self._min_idx_stack[-1] == data_last_idx:
self._min_idx_stack.pop()
if self._max_idx_stack[-1] == data_last_idx:
self._max_idx_stack.pop()
def _idx_stack_data(self, stack):
return self._data[stack[-1]]
def push(self, item):
self._data.append(item)
if (not self._min_idx_stack) or \
(item < self._idx_stack_data(self._min_idx_stack)):
self._push_idx_stack(self._min_idx_stack)
if (not self._max_idx_stack) or \
(item > self._idx_stack_data(self._max_idx_stack)):
self._push_idx_stack(self._max_idx_stack)
def pop(self):
if len(self._data) == 0:
raise ValueError("stack is empty")
self._pop_idx_stack()
return self._data.pop()
@property
def min(self):
if len(self._data) == 0:
raise ValueError("stack is empty")
else:
return self._idx_stack_data(self._min_idx_stack)
@property
def max(self):
if len(self._data) == 0:
raise ValueError("stack is empty")
else:
return self._idx_stack_data(self._max_idx_stack)
def show(self):
return self.__repr__()
if __name__ == '__main__':
import doctest
doctest.testmod()栈的特点是先入后出,队列的特点是先入先出,如果先要用栈模拟队列的操作,需要用到辅助栈作为过度.其中的一个栈负责如栈,另一个栈负责出栈.当需要模拟时将入栈数据转移到出栈数据中进行出栈.
- 入队: 不管什么情况,直接操作栈的入栈操作
- 出队: 如果出队栈为空,要实现两个栈的转换操作,将入队栈的元素逐个出栈,逐个放入出队栈中,最后在出队栈中出队;如果队出栈非空,直接出栈.
private Stack<Integer> stackA = new Stack<Integer>();
private Stack<Integer> stackB = new Stack<Integer>();
/**
* 入队操作
* @param element 入队的元素
*/
public void enQueue(int element) {
stackA.push(element);
}
/**
* 出队操作
*/
public Integer deQueue() {
if(stackB.isEmpty()){
if(stackA.isEmpty()){
return null;
}
transfer();
}
return stackB.pop();
}
/**
* 栈A元素转移到栈B
*/
private void transfer(){
while(!stackA.isEmpty()){
stackB.push(stackA.pop());
}
}
public static void main(String[] args) throws Exception{
StackQueue stackQueue = new StackQueue();
stackQueue.enQueue(1);
stackQueue.enQueue(2);
stackQueue.enQueue(3);
System.out.println(stackQueue.deQueue());
System.out.println(stackQueue.deQueue());
stackQueue.enQueue(4);
System.out.println(stackQueue.deQueue());
System.out.println(stackQueue.deQueue());
}复杂度: 时间复杂度,入队O(1);出队,不涉及两个栈的交换O(1),涉及两个栈的交换O(n);空间复杂度2n既O(n)
包括用栈实现队列,用队列实现栈,能获得最大最小值的栈
class MaxMinStack(object):
"""
_data为存储数据的主栈 申请_min_idx_stack及_max_idx_stack两个辅助栈分别存储在_data中最大值和最小值的索引
每次入栈要通过辅助栈的索引找到_data的最大值和最小值 并更具具体情况更新
每次出栈元素如果在_data中的索引是_min_idx_stack及_max_idx_stack中最后一位的值 _data出栈的同时辅助栈也要出栈
>>> s = MaxMinStack()
>>> s.show()
'Stack is empty'
>>> s.push(10)
>>> s
Stack ([10], min=10, max=10)
>>> s.push(50)
>>> s
Stack ([10, 50], min=10, max=50)
>>> s.push(20)
>>> s
Stack ([10, 50, 20], min=10, max=50)
>>> s.push(9)
>>> s
Stack ([10, 50, 20, 9], min=9, max=50)
>>> s.min
9
>>> s.max
50
>>> s.pop()
9
>>> s
Stack ([10, 50, 20], min=10, max=50)
>>> s.pop()
20
>>> s.pop()
50
>>> s
Stack ([10], min=10, max=10)
"""
_min_idx_stack = []
_max_idx_stack = []
_data = []
def __repr__(self):
if not self._data:
return "Stack is empty"
return "Stack ({}, min={}, max={})".format(
self._data,
self.min, self.max)
def _push_idx_stack(self, stack):
stack.append(len(self._data) - 1)
def _pop_idx_stack(self):
data_last_idx = len(self._data) - 1
if self._min_idx_stack[-1] == data_last_idx:
self._min_idx_stack.pop()
if self._max_idx_stack[-1] == data_last_idx:
self._max_idx_stack.pop()
def _idx_stack_data(self, stack):
return self._data[stack[-1]]
def push(self, item):
self._data.append(item)
if (not self._min_idx_stack) or \
(item < self._idx_stack_data(self._min_idx_stack)):
self._push_idx_stack(self._min_idx_stack)
if (not self._max_idx_stack) or \
(item > self._idx_stack_data(self._max_idx_stack)):
self._push_idx_stack(self._max_idx_stack)
def pop(self):
if len(self._data) == 0:
raise ValueError("stack is empty")
self._pop_idx_stack()
return self._data.pop()
@property
def min(self):
if len(self._data) == 0:
raise ValueError("stack is empty")
else:
return self._idx_stack_data(self._min_idx_stack)
@property
def max(self):
if len(self._data) == 0:
raise ValueError("stack is empty")
else:
return self._idx_stack_data(self._max_idx_stack)
def show(self):
return self.__repr__()
class StackAsQueue(object):
"""
分成入队栈和出队栈 入队统一在入队栈中入队
出队如果出队栈中有数据 直接在出队栈中出栈
如果出队栈中没有数据则进行转换操作 将入队栈中全部的数据逐个出栈并入栈到出队栈中 完成顺序的反转
>>> q = StackAsQueue()
>>> q.enqueue(1)
>>> q.enqueue(2)
>>> len(q)
2
>>> q.dequeue()
1
>>> q.enqueue(3)
>>> len(q)
2
>>> q.dequeue()
2
>>> q.enqueue(4)
>>> q.enqueue(5)
>>> q.dequeue()
3
>>> q.dequeue()
4
>>> q.dequeue()
5
>>> q.dequeue()
Traceback (most recent call last):
...
ValueError: queue is empty
"""
_stack_enqueue = []
_stack_dequeue = []
@staticmethod
def _get_stack_last(stack):
# if not stack:
# raise ValueError("stack is empty")
return stack.pop()
def _transfer(self):
while len(self._stack_enqueue):
self._stack_dequeue.append(self._get_stack_last(self._stack_enqueue))
def enqueue(self, item):
self._stack_enqueue.append(item)
def dequeue(self):
if self._stack_dequeue:
return self._get_stack_last(self._stack_dequeue)
elif self._stack_enqueue:
self._transfer()
return self._get_stack_last(self._stack_dequeue)
else:
raise ValueError("queue is empty")
def __len__(self):
return len(self._stack_enqueue) + len(self._stack_dequeue)
class QueueAsStack(object):
"""
申请两个队列 每次操作都保持一个队列有数据一个队列没数据或者两个队列没数据(空栈)的情况
入栈时找有数据的队列入栈 如果两个都没有数据则随便入栈
出栈时把有数据的队列`n-1`个元素逐个出队 并入队到另一个空队列中 将最后一个元素返回
>>> s = QueueAsStack()
>>> s.push(1)
>>> s.push(2)
>>> s.pop()
2
>>> s.push(3)
>>> s.push(4)
>>> len(s)
3
>>> s.pop()
4
>>> s.pop()
3
>>> s.pop()
1
"""
from collections import deque
_queue_one = deque()
_queue_two = deque()
def _transfer_and_pop(self):
if self._queue_one:
for _ in range(len(self._queue_one) - 1):
self._queue_two.append(self._queue_one.popleft())
return self._queue_one.popleft()
else:
for _ in range(len(self._queue_two) - 1):
self._queue_one.append(self._queue_two.popleft())
return self._queue_two.popleft()
def _push_not_empty(self, item):
if self._queue_one:
self._queue_one.append(item)
else:
self._queue_two.append(item)
def pop(self):
if (not self._queue_one) and (not self._queue_two):
raise ValueError("stack is empty")
return self._transfer_and_pop()
def push(self, item):
self._push_not_empty(item)
def __len__(self):
return len(self._queue_one) + len(self._queue_two)
class QueueAsStack1(object):
"""
申请两个队列 每次操作都保持一个队列有数据一个队列没数据或者两个队列没数据(空栈)的情况
入栈时找有数据的队列入栈 如果两个都没有数据则随便入栈
出栈时把有数据的队列`n-1`个元素逐个出队 并入队到另一个空队列中 将最后一个元素返回
>>> s = QueueAsStack1()
>>> s.push(1)
>>> s.push(2)
>>> s.pop()
2
>>> s.push(3)
>>> s.push(4)
>>> len(s)
3
>>> s.pop()
4
>>> s.pop()
3
>>> s.pop()
1
"""
from collections import deque
_queue = deque()
def pop(self):
if not self._queue:
raise ValueError("stack is empty")
_len = len(self._queue)
for _ in range(_len - 1):
self._queue.append(self._queue.popleft())
return self._queue.popleft()
def push(self, item):
self._queue.append(item)
def __len__(self):
return len(self._queue)
if __name__ == '__main__':
import doctest
doctest.testmod()有一个由很多木棒构成的集合,每个木棒有对应的长度,请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 0 的简单多边形且所有木棒都要用上,简单多边形即不会自交的多边形 初始集合是空的,有两种操作,要么给集合添加一个长度为 L 的木棒,要么删去集合中已经有的某个木棒。每次操作结束后你都需要告知是否能用集合中的这些木棒构成一个简单多边形。
输入描述: 每组测试用例仅包含一组数据,每组数据第一行为一个正整数 n 表示操作的数量(1 ≤ n ≤ 50000) , 接下来有n行,每行第一个整数为操作类型 i (i ∈ {1,2}),第二个整数为一个长度 L(1 ≤ L ≤ 1,000,000,000)。如果 i=1 代表在集合内插入一个长度为 L 的木棒,如果 i=2 代表删去在集合内的一根长度为 L 的木棒。输入数据保证删除时集合中必定存在长度为 L 的木棒,且任意操作后集合都是非空的。
输出描述: 对于每一次操作结束有一次输出,如果集合内的木棒可以构成简单多边形,输出 "Yes" ,否则输出 "No"。
示例1 输入 5 1 1 1 1 1 1 2 1 1 2
输出 No No Yes No No
def can_be_polygon(nested_list):
operation_num = nested_list[0]
operation_detail = nested_list[1:]
check_polygon = []
for operation_flag, length in operation_detail:
# operation
if operation_flag == 1:
check_polygon.append(length)
elif operation_flag == 2:
check_polygon.remove(length)
# check
"""边数要大于三并且最大边<n-1的最小边之和"""
if len(check_polygon) > 2:
max_check_polygon = max(check_polygon)
sum_of_other = reduce(lambda x, y: x + y, check_polygon) - max_check_polygon
if max_check_polygon < sum_of_other:
print 'YES'
else:
print 'NO'
else:
print 'NO'
if __name__ == '__main__':
list = [5, [1, 1], [1, 1], [1, 1], [2, 1], [1, 2]]
can_be_polygon(list)一个数组中,将奇数放在前面,偶数放在后面进行排序。如[8, 4, 1, 6, 7, 4, 9, 6, 4]其中一个接受的输出是[9, 7, 1, 8, 4, 6, 4, 6, 4]
a = [8, 4, 1, 6, 7, 4, 9, 6, 4]
result = []
for i in a:
if i % 2 == 0:
result.append(i)
else:
result.insert(0, i)
print result风口之下,猪都能飞。当今中国股市牛市,真可谓“错过等七年”。给你一个回顾历史的机会,已知一支股票连续n天的价格走势,以长度为n的整数数组表示,数组中第i个元素（prices[i]）代表该股票第i天的股价
假设你一开始没有股票,但有至多两次买入1股而后卖出1股的机会,并且买入前一定要先保证手上没有股票。若两次交易机会都放弃,收益为0。设法计算你能获得的最大收益。 输入数值范围：2<=n<=100,0<=prices[i]<=100
输入例子:
3,8,5,1,7,8
输出例子:
12def max_diff_order(lst):
"""单个交易周期最大的利润 其中per_idx<post_idx"""
max_ = None
for i, v1 in enumerate(lst):
for v2 in lst[i + 1:]:
max_ = max(max_, v2 - v1)
return max_
def max_earn(lst):
"""找出整个周期内最大的盈利 先将整个周期分成两半 分别找出最大盈利然后相加"""
max_earn = None
for i in range(2, len(a) - 2):
part_1 = a[0:i + 1]
part_2 = a[i + 1:]
earn_1 = max_diff_order(part_1)
earn_2 = max_diff_order(part_2)
max_earn = max(earn_1 + earn_2, max_earn)
return max_earn
if __name__ == '__main__':
a = [int(i) for i in '385178']
print max_earn(a)Excel Sheet Column Title
Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
1 -> A
2 -> B
3 -> C
…
26 -> Z
27 -> AA
28 -> AB
* 其中的原理
A 1 AA 26+ 1 BA 2*26+ 1 ... ZA 26*26+ 1 AAA 1*26²+1*26+ 1
B 2 AB 26+ 2 BB 2*26+ 2 ... ZB 26*26+ 2 AAB 1*26²+1*26+ 2
. . .. ..... .. ....... ... .. ........ ... .............
. . .. ..... .. ....... ... .. ........ ... .............
. . .. ..... .. ....... ... .. ........ ... .............
Z 26 AZ 26+26 BZ 2*26+26 ... ZZ 26*26+26 AAZ 1*26²+1*26+26
Now we can see that ABCD＝A*26³＋B*26²＋C*26¹＋D＝1*26³＋2*26²＋3*26¹＋4
ZZZZ＝Z*26³＋Z*26²＋Z*26¹＋Z＝26*26³＋26*26²＋26*26¹＋26
We can use (n-1)%26 instead, then we get a number range from 0 to 25.def convertToTitle(num):
# 生成字符串列表 从A到Z
# ord 返回字符的integer
# chr 返回integer的string
capitals = [chr(x) for x in range(ord('A'), ord('Z') + 1)]
result = []
while num > 0:
# num - 1是因为 index从0开始
result.append(capitals[(num - 1) % 26])
# // 除直接不要余数
num = (num - 1) // 26
result.reverse()
return ''.join(result)
if __name__ == '__main__':
n = 27
n1 = 12345
print convertToTitle(n)
print convertToTitle(n1)有两个数组a,b,大小都为n,数组元素的值任意,无序
要求：
通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小。def min_diff_sum(lst1, lst2):
"""
将两个列表合并倒序 记录两个结果列表的和
for循环合并列表 并将合并列表最大的值放到结果列表和的最小值
"""
result_lst1 = []
result_lst2 = []
lst_sorted = sorted(lst1 + lst2, reverse=True)
for val in lst_sorted:
sum_result_lst1 = sum(result_lst1)
sum_result_lst2 = sum(result_lst2)
if sum_result_lst1 <= sum_result_lst2:
result_lst1.append(val)
else:
result_lst2.append(val)
lst_sum_diff = abs(sum(result_lst1) - sum(result_lst2))
return result_lst1, result_lst2, lst_sum_diff
if __name__ == '__main__':
lst1 = [1, 2, 3, 4, 5]
lst2 = [6, 7, 8, 9, 10]
print min_diff_sum(lst1, lst2)给定一个长度为N的数组,找出一个最长的单调自增子序列（不一定连续,但是顺序不能乱）
例如：给定一个长度为8的数组A{1,3,5,2,4,6,7,8}
则其最长的单调递增子序列为{1,2,4,6,7,8},长度为6。
input:
89 256 78 1 46 78 8
6 4 8 2 17
output:
3
3def find_length_sublst(lst):
result_dct = {}
for start_idx in range(len(lst)):
max_val = None
mid_lst = []
for i in lst[start_idx:]:
if i > max_val:
mid_lst.append(i)
max_val = i
result_dct[len(mid_lst)] = mid_lst
return max(result_dct.keys())
if __name__ == '__main__':
lst1 = [89, 256, 78, 1, 46, 78, 8]
lst2 = [6, 4, 8, 2, 17]
print find_length_sublst(lst1)
print find_length_sublst(lst2)给定一个整数n,从中去掉k个数字,要求剩下的新数字尽可能小,怎么去除.如1593212删除3个数字得到最新整数是1212,给定30200删除1个数字,最小的是200.需要注意的是，给定的整数大小可以超过long类型的范围，所以需要用字符串来表示.一开始可能想到把最大的数字删除,但其实数字的位置比数字的大小更加重要,高位数字即使减掉了1也会比低位减掉9要减得多,如3549,如果根据数字大小删除,应该删除9,但是删除5会使得数字更小.所以核心是把高位的数字降低，方法是我们把原整数的所有数字从左到右进行比较，如果发现某一位的数字大于它右面的数字，那么在删除该数字后，必然会使得该数位的值降低.对已k个数字的问题,使用k个局部最优最终得到全局最优解的 贪心算法解决
// 较容易写出来的版本
// 外层循环基于删除次数（k），内层循环从左到右遍历所有数字。当遍历到需要删除的数字时，利用字符串的自身方法subString() 把对应数字删除，并重新拼接字符串。显然，这段代码的时间复杂度是O（kn）
// 每一次内层循环，都需要从头遍历所有数字
// subString方法本身性能不高 subString方法的底层实现，涉及到了新字符串的创建，以及逐个字符的拷贝。这个方法自身的时间复杂度是O（n）
public static String removeKDigits(String num, int k) {
String numNew = num;
for(int i=0; i<k; i++){
boolean hasCut = false;
//从左向右遍历，找到比自己右侧数字大的数字并删除
for(int j=0; j<numNew.length()-1; j++){
if(numNew.charAt(j) > numNew.charAt(j+1)){
numNew = numNew.substring(0, j) + numNew.substring(j+1,numNew.length());
hasCut = true;
break;
}
}
//如果没有找到要删除的数字，则删除最后一个数字
if(!hasCut){
numNew = numNew.substring(0, numNew.length()-1);
}
//清除整数左侧的数字0
numNew = removeZero(numNew);
}
//如果整数的所有数字都被删除了，直接返回0
if(numNew.length() == 0){
return "0";
}
return numNew;
}
private static String removeZero(String num){
for(int i=0; i<num.length()-1; i++){
if(num.charAt(0) != '0'){
break;
}
num = num.substring(1, num.length()) ;
}
return num;
}
public static void main(String[] args) {
System.out.println(removeKDigits("1593212",3));
System.out.println(removeKDigits("30200",1));
System.out.println(removeKDigits("10",2));
System.out.println(removeKDigits("541270936",3));
}
// 性能较好一点的方式,用字符串长度作为外循环
// 不用substring切割字符串
/**
* 删除整数的k个数字，获得删除后的最小值
* @param num 原整数
* @param k 删除数量
*/
public static String removeKDigits(String num, int k) {
//新整数的最终长度 = 原整数长度 - k
int newLength = num.length() - k;
//创建一个栈，用于接收所有的数字
char[] stack = new char[num.length()];
int top = 0;
for (int i = 0; i < num.length(); ++i) {
//遍历当前数字
char c = num.charAt(i);
// 当栈顶数字大于遍历到的当前数字，栈顶数字出栈（相当于删除数字）
// 如果当前字符比前面的数个要大也是可以完成的
while (top > 0 && stack[top-1] > c && k > 0) {
top -= 1;
k -= 1;
}
//遍历到的当前数字入栈
stack[top++] = c;
}
// 找到栈中第一个非零数字的位置，以此构建新的整数字符串
int offset = 0;
while (offset < newLength && stack[offset] == '0') {
offset++;
}
return offset == newLength? "0": new String(stack, offset, newLength - offset);
}
public static void main(String[] args) {
System.out.println(removeKDigits("1593212", 3));
System.out.println(removeKDigits("30200", 1));
System.out.println(removeKDigits("10", 2));
System.out.println(removeKDigits("541270936", 3));
System.out.println(removeKDigits("123456789", 3));
}
// 使用 Stack 和 StringBuilder 完成
public String removeKdigits(String num, int k) {
int len = num.length();
//corner case
if(k == len) {
return "0";
}
Stack<Character> stack = new Stack<>();
int i = 0;
while(i < num.length()){
//whenever meet a digit which is less than the previous digit, discard the previous one
while(k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(i)){
stack.pop();
k--;
}
stack.push(num.charAt(i));
i++;
}
// corner case like "1111"
while(k > 0){
stack.pop();
k--;
}
//construct the number from the stack
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty())
sb.append(stack.pop());
sb.reverse();
//remove all the 0 at the head
while(sb.length() > 1 && sb.charAt(0) == '0')
sb.deleteCharAt(0);
return sb.toString();
}def removeKdigits(num, k):
if len(num) <= k:
return '0'
stack = []
for digit in num:
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
while k: #corner case 112 remove 1
stack.pop()
k -= 1
return ''.join(stack).lstrip('0') or '0'每次团日活动,都要将团队成员分成多组,求这多个组的分类
import random
# solution 1
def div_tearm(people, group_names):
group_num = len(group_names)
random.shuffle(people)
grouped = {}
for i in range(group_num):
grouped[group_names[i]] = people[i::group_num]
return grouped
if __name__ == '__main__':
p = list(range(8))
g_names = ['A', 'B', 'C', 'D']
print(div_tearm(p, g_names))
# solution 2
def div_tearm(arr, group_num):
total_people_num = len(arr)
if total_people_num < group_num:
raise ValueError("group_num should bigger than total")
shuffle(arr)
each_group_base, remainder = divmod(total_people_num, group_num)
if not remainder:
return [Group(i + 1, e) for i, e in enumerate(arr)]
else:
total_group = []
start_ind = 0
end_ind = 0
split_ind = [each_group_base] * group_num
for i in range(remainder):
split_ind[i] = split_ind[i] + 1
for i in range(group_num):
end_ind += split_ind[i]
total_group.append(Group(i + 1, arr[start_ind: end_ind]))
start_ind += split_ind[i]
return total_group
# solution 3
def devide_group(arr, group_num):
total_people_num = len(arr)
if total_people_num < group_num:
raise ValueError("group_num should bigger than total")
elif total_people_num == group_num:
total_group = []
for i in range(total_people_num):
to_group = choice(arr)
total_group.append(Group(i + 1, to_group))
arr.remove(to_group)
return total_group
each_group_base, remainder = divmod(total_people_num, group_num)
group_index = 0
group_size = 0
group_member = []
total_group = []
while group_index < group_num:
if group_size < each_group_base:
group_member.append(arr.pop(randint(0, total_people_num - 1)))
total_people_num -= 1
group_size += 1
else:
total_group.apeach_group_basepend(group_member)
group_index += 1
group_size = 0
group_member = []
# do to remain element
if not remainder:
remain_to_group = list(range(group_num))
for i in range(remainder):
to_group = choice(remain_to_group)
total_group[to_group].append(arr[i])
remain_to_group.remove(to_group)
return [Group(i + 1, e) for i, e in enumerate(total_group)]
if __name__ == "__main__":
arr = [1, 3, 5, 7]
group_num = 4
print(devide_group_1(arr, group_num))
arr = [1, 3, 5, 7, 9, 11, 13]-
漫画：什么是B-树: MongoDB及文档系统的索引
-
漫画：什么是B+树: MySQL的索引
-
漫画：什么是跳跃表: 查询复杂度为O(logN),Redis中的sorted-set使用的也是跳跃表
-
漫画：什么是布隆算法: url去重 邮件白名单, 多次计算string的hash值(一般是8次)并将值存进bitmap,当全部在bitmap中为1时才认为相等