vim  python_file.py
---
print ("hello world")
---
time python python_file.py
>>> 
    real    0m0.146s
    user    0m0.047s
    sys     0m0.063s

import sys
sys.getsizeof()
>>> 123 #betye

# python
class ListNode(object):
    def __init__(self,value=None):
        self.data=value
        self.next=None
    # 获得数据
    def getData(self):
        return self.data
    # 获得下一个节点的引用
    def getNext(self):
        return self.next
    # 修改数据
    def setData(self, newdata):
        self.data = newdata
    # 修改下一节点的引用
    def setNext(self, newnext):
        self.next = newnext

struct ListNode
{
    double value;
    ListNode *next;
};

import numpy as np

np.array(···，dtype=None,shape=[])

list_1=["abc","defffff","ghiiiiiiiiiii"]
list_2=["abc","defffff"]
list_3=["abc"]
array_1=np.array(list_1)
array_2=np.array(list_2)
array_3=np.array(list_3)

print (sys.getsizeof(list_1)-sys.getsizeof(list_2)) #8 
print (sys.getsizeof(list_2)-sys.getsizeof(list_3)) #8
print (sys.getsizeof(list_3)) #72

print (sys.getsizeof(array_1)-sys.getsizeof(array_2)) #100
print (sys.getsizeof(array_2)-sys.getsizeof(array_3)) # 44
print (sys.getsizeof(array_3)) # 108

print(sys.getsizeof("abc")) #60
print (sys.getsizeof("defffff")) #72
print (sys.getsizeof("ghiiiiiiiiiii")) #90 

// 1维数组

int array[100]; 　　//定义了数组array，并未对数组进行初始化
int array[100] = {1，2}；　　//定义并初始化了数组array

int* array = new int[100];  
delete []array;　　//分配了长度为100的数组array 

int* array = new int[100](1，2); 　
delete []array;　//为长度为100的数组array初始化前两个元素

//2 维数组

int array[10][10];　　//定义了数组，并未初始化
int array[10][10] = { {1,1} , {2,2} };　　//数组初始化了array[0][0,1]及array[1][0,1]

int (*array)[n] = new int[m][n];
delete []array;

int** array = new int*[m];　
for(i) array[i] = new int[n];  
for(i) delete []array[i]; 
delete []array;    //多次析构
int* array = new int[m][n];  
delete []array;      //数组按行存储

//多维数组
int* array = new int[m][3][4];    //只有第一维可以是变量，其他维数必须是常量，否则会报错
delete []array;       //必须进行内存释放，否则内存将泄漏

class Stack(object):
    def __init__(self):
        self.stack=[]
    def isEmpty(self):
        return self.stack==[]
    def push(self,item):
        self.stack.append(item)
    def pop(self):
        if self.isEmpty():
            raise IndexError,'pop from empty stack'
        return self.stack.pop()
    def peek(self):
        return self.stack[-1]
    def size(self):
        return len(self.stack)

# 内置
from queue import LifoQueue #LIFO队列,Last in First Out,后进先出
lifoQueue = LifoQueue()
lifoQueue.put(1)
lifoQueue.put(2)
lifoQueue.put(3)
print('LIFO队列',lifoQueue.queue)
lifoQueue.get() #返回并删除队列尾部元素
lifoQueue.get()
print(lifoQueue.queue)

class Queue(object):
    def __init__(self):
        self.queue=[]
    def isEmpty(self):
        return self.queue==[]
    def enqueue(self,x):
        self.queue.append(x)
    def dequeue(self):
        if self.queue:
            a=self.queue[0]
            self.queue.remove(a)
            return a
        else:
            raise IndexError,'queue is empty'
    def size(self):
        return len(self.queue)

# 内置
from queue import Queue #LILO队列 Last in Last Out,后进后出
q = Queue() #创建队列对象
q.put(0)    #在队列尾部插入元素
q.put(1)
q.put(2)
print('LILO队列',q.queue)  #查看队列中的所有元素
print(q.get())  #返回并删除队列头部元素
print(q.queue)

from queue import PriorityQueue #优先队列
priorityQueue = PriorityQueue() #创建优先队列对象
priorityQueue.put(3)    #插入元素
priorityQueue.put(78)   #插入元素
priorityQueue.put(100)  #插入元素
print(priorityQueue.queue)  #查看优先级队列中的所有元素
priorityQueue.put(1)    #插入元素
priorityQueue.put(2)    #插入元素
print('优先级队列:',priorityQueue.queue)  #查看优先级队列中的所有元素
priorityQueue.get() #返回并删除优先级最低的元素
print('删除后剩余元素',priorityQueue.queue)
priorityQueue.get() #返回并删除优先级最低的元素
print('删除后剩余元素',priorityQueue.queue)  #删除后剩余元素
priorityQueue.get() #返回并删除优先级最低的元素
print('删除后剩余元素',priorityQueue.queue)  #删除后剩余元素
priorityQueue.get() #返回并删除优先级最低的元素
print('删除后剩余元素',priorityQueue.queue)  #删除后剩余元素
priorityQueue.get() #返回并删除优先级最低的元素
print('全部被删除后:',priorityQueue.queue)  #查看优先级队列中的所有元素

from collections import deque   #双端队列
dequeQueue = deque(['Eric','John','Smith'])
print(dequeQueue)
dequeQueue.append('Tom')    #在右侧插入新元素
dequeQueue.appendleft('Terry')  #在左侧插入新元素
print(dequeQueue)
dequeQueue.rotate(2)    #循环右移2次
print('循环右移2次后的队列',dequeQueue)
dequeQueue.popleft()    #返回并删除队列最左端元素
print('删除最左端元素后的队列：',dequeQueue)
dequeQueue.pop()    #返回并删除队列最右端元素
print('删除最右端元素后的队列：',dequeQueue)

    address_in_table=hash(key)mod(n)
    if address_in_table 相同:
        依据冲突处理规则处理
    return address_in_table

import hashlib

md5 = hashlib.md5()
md5.update('how to use md5 in python hashlib?'.encode('utf-8'))
print(md5.hexdigest())

>>> d26a53750bc40b38b65a520292f69306

# python dict 
dict={key:value}

#include <iostream> 
#include <vector> 
#include <unordered_map>
using namespace std; 

class Myclass { 
    public: int first; 
    vector<int> second; // 重载等号，判断两个Myclass类型的变量是否相等 
    bool operator== (const Myclass &other) const { 
        return first == other.first && second == other.second; } }; // 实现Myclass类的hash函数 

    namespace std { 
        template <> struct hash<Myclass> { 
            size_t operator()(const Myclass &k) const 
            {   int h = k.first;
                for (auto x : k.second) { 
                    h ^= x;
                    } 
                return h;
                } 
        }; 
    } 

int main()
{ 
    unordered_map<Myclass, double> S; 
    Myclass a = { 2, {3, 4} }; 
    Myclass b = { 3, {1, 2, 3, 4} };
    S[a] = 2.5; 
    S[b] = 3.123; 
    cout << S[a] << ' ' << S[b] << endl; 
    return 0;
 }

class LinearMap(object):
    def __init__(self):
         self.items = []
    # 往表中添加元素    
    def add(self, k, v):  
        self.items.append((k,v))

    # 线性方式查找元素
    def get(self, k): 
        for key, value in self.items:      
            if key == k:      # 键存在，返回值，否则抛出异常
                return value
        raise KeyError

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t
    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self,obj):
        self.key = obj

    def getRootVal(self):
        return self.key

class BinarySearchTree(object):
    def __init__(self,key):
        self.key=key
        self.leftChild=None
        self.rightChild=None

    def search(self, node, parent, data):
        if node is None:
            return False, node, parent
        if node.data == data:
            return True, node, parent
        if node.data > data:
            return self.search(node.leftChild, node, data)
        else:
            return self.search(node.rightChild, node, data)
        # 插入
    def insert(self, data):
        flag, n, p = self.search(self.root, self.root, data)
        if not flag:
            new_node = BinarySearchTree(data)
        if data > p.data:
            p.leftChild = new_node
        else:
            p.rightChild = new_node

import heapq 
heap = []            # creates an empty heap
heappush(heap, item) # pushes a new item on the heap
item = heappop(heap) # pops the smallest item from the heap
item = heap[0]       # smallest item on the heap without popping it
heapify(list_x)           # transforms list into a heap, in-place, in linear time
item = heapreplace(heap, item) # 返回最小值，同时将新item加入堆中，堆的大小不变

D={}
while (没有找到正确答案)：
    正确答案=Di?
    i+=1

function (n){
    return function (n-1) ;
}

int* product =new product[3]
product[1]=~~

function (n){

    return function (n-1) ;
}

Dfs(node) {
    //可行性减支
    if(node 访问过)
        return ;  
    将node标记为访问过;
    node相邻的点加入到candidate_node_stack 总
    从candidate_node_stack里面确定下一个点node_i:  
    Dfs(node_i);
    }

int main() {
    while(在图中能找到未访问过的点k) {
         Dfs(k);
    } 
         }

class Graph(object):
  def __init__(self,*args,**kwargs):
    self.node_neighbors = {}
    self.visited = {}
  def add_nodes(self,nodelist):
    for node in nodelist:
      self.add_node(node)
  def add_node(self,node):
    if not node in self.nodes():
      self.node_neighbors[node] = []
  def add_edge(self,edge):
    u,v = edge
    if(v not in self.node_neighbors[u]) and ( u not in self.node_neighbors[v]):
      self.node_neighbors[u].append(v)
      if(u!=v):
        self.node_neighbors[v].append(u)
  def nodes(self):
    return self.node_neighbors.keys()
  def depth_first_search(self,root=None):
    order = []
    def dfs(node):
      self.visited[node] = True
      order.append(node)
      for n in self.node_neighbors[node]:
        if not n in self.visited:
          dfs(n)
    if root:
      dfs(root)
    for node in self.nodes():
      if not node in self.visited:
        dfs(node)
    print order
    return order
  def breadth_first_search(self,root=None):
    queue = []
    order = []
    def bfs():
      while len(queue)> 0:
        node = queue.pop(0)
        self.visited[node] = True
        for n in self.node_neighbors[node]:
          if (not n in self.visited) and (not n in queue):
            queue.append(n)
            order.append(n)
    if root:
      queue.append(root)
      order.append(root)
      bfs()
    for node in self.nodes():
      if not node in self.visited:
        queue.append(node)
        order.append(node)
        bfs()
    print order
    return order

dfs(int x)
{
    if(x>n)return;
    if(!check1(x))return;
    ....
    return;
}

long long ans=987474477434487ll;
dfs(int x,...)
{
    if(x... && ...)
    {
        ans=....;
        return ...;
    }
    //最优性剪枝 
    if(check2(x)>=ans)
    {
        return ...;
    }
    for(int i=1;...;++i)
        {
            vis[...]=1; 
            dfs(...);
            vis[...]=0;
        }
}

long long ans=987474477434487ll;
dfs(int x,...)
{
    if(x... && ...)
    {
        ans=....;
        return ...;
    }
    if(vis[x]!=0)
        return f[x];
        vis[x]=1;
    for(int i=1;...;++i)
        {
            vis[...]=1;
            dfs(...);
            vis[...]=0;
            f[x]=...;
        }
}

BFS(){
        初始化队列
        while（队列不为空且未找到目标节点） 
        {
            取队首节点扩展，并将扩展出的非重复节点放入队尾 ；
            必要时记住每个节点的父节点；
        }
}

1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一子问题求解，得到子问题的局部最优解；
4. 把子问题的解局部最优解合成原来解问题的一个解。

##  插入排序
### 打牌 拿牌的时候排序
def insert_sort(raw_list):
    # raw_list:[2,5,3,5 ]
    # sorted_list:[2,5]
    for flag_index in range(1,len(raw_list)):
        insert_value = raw_list[flag_index]
        insert_index=flag_index
        # insert_value:3
        if insert_value < raw_list[flag_index-1]:
            # if 3 < 5
            for j in range(insert_index-1,-1,-1):  # 对于  sorted_list
                if raw_list[j] > insert_value :
                    # if 5>3
                    raw_list[j+1] = raw_list[j]
                    # 
                    insert_index = j   #记录待插入下标
                else :
                    break
            raw_list[insert_index] = insert_value
        print ("flag_index {} 的 {}:{}".format(flag_index,raw_list[flag_index],raw_list))
    return raw_list

myList = [49,38,65,97,76,13,27,49]
insert_sort(myList)
print(myList)


flag_index 1 的 49:[38, 49, 65, 97, 76, 13, 27, 49]
flag_index 2 的 65:[38, 49, 65, 97, 76, 13, 27, 49]
flag_index 3 的 97:[38, 49, 65, 97, 76, 13, 27, 49]
flag_index 4 的 97:[38, 49, 65, 76, 97, 13, 27, 49]
flag_index 5 的 97:[13, 38, 49, 65, 76, 97, 27, 49]
flag_index 6 的 97:[13, 27, 38, 49, 65, 76, 97, 49]
flag_index 7 的 97:[13, 27, 38, 49, 49, 65, 76, 97]

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#插入排序，缩小增量
def shell_sort(raw_list):
    gap = len_of_list = len(raw_list)
    result_list=[]
    while(gap > 1):
        gap = gap/2
        for i in range(0, len_of_list):
            for j in range(i, len_of_list - gap, gap):
                if result_list[j] > result_list[j+gap]:
                    result_list[j], result_list[j+gap] = result_list[j+gap], result_list[j]
    return result_list

## 1.1 选择排序
### 先选第一个，确定第一个最小，再确定第二个 
def select_sort(raw_list):
    sorted_list=raw_list
    len_of_list=len(raw_list)
    for i in range(0, len_of_list- 1):
        selected_index = i
        for j in range(i + 1, len_of_list):
            if sorted_list[selected_index] > sorted_list[j]:
                selected_index = j
            sorted_list[i], sorted_list[selected_index] = sorted_list[selected_index], sorted_list[i]
        print ("选择 {}:{}".format(raw_list[i],sorted_list))
    return sorted_list
s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
select_sort(s)

选择 0:[0, 4, 3, 6, 2, 9, 7, 1, 8, 5]
选择 1:[0, 1, 3, 6, 4, 9, 7, 2, 8, 5]
选择 2:[0, 1, 2, 6, 4, 9, 7, 3, 8, 5]
选择 3:[0, 1, 2, 3, 6, 9, 7, 4, 8, 5]
选择 4:[0, 1, 2, 3, 4, 9, 7, 6, 8, 5]
选择 5:[0, 1, 2, 3, 4, 5, 9, 6, 8, 7]
选择 6:[0, 1, 2, 3, 4, 5, 6, 9, 8, 7]
选择 7:[0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
选择 8:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

def heap_adjust(L, start, end):
    temp = L[start]

    i = start
    j = 2 * i

    while j <= end:
        if (j < end) and (L[j] < L[j + 1]):
            j += 1
        if temp < L[j]:
            L[i] = L[j]
            i = j
            j = 2 * i
        else:
            break
    L[i] = temp

def heap_sort(raw_list):
    len_of_list = len(raw_list)

    first_sort_count = (len_of_list-1) / 2
    for i in range(first_sort_count):
        heap_adjust(L, first_sort_count - i, len_of_list)

    for i in range(len_of_list - 1):
        L = swap_param(L, 1, len_of_list - i)
        heap_adjust(L, 1, len_of_list - i - 1)

    return [L[i] for i in range(1, len(L))]

## 1.3 交换排序
def bubble_sort(raw_list):
    """冒泡排序 相邻交换, 进行第几轮 最后面的第几个数值确定"""
    print (raw_list)
    for i in range(len(raw_list)-1):    # 这个循环负责设置冒泡排序进行的次数
        print ("交换前{}个数字 ".format(len(raw_list)-i-1))
        for j in range(len(raw_list)-i-1):  # ｊ为列表下标
            if raw_list[j] > raw_list[j+1]:
                raw_list[j], raw_list[j+1] = raw_list[j+1], raw_list[j]
                print ("{}   {}<->{} :{}".format(j,raw_list[j], raw_list[j+1],raw_list))
            else:
                print ("{}   {} --{}: FALSE".format(j,raw_list[j] ,raw_list[j+1]))
    return raw_list

nums = [5,2,4,6,8,2,1]
bubble_sort(nums)

[5, 2, 4, 6, 8, 2, 1]
交换前6个数字 
0   2<->5 :[2, 5, 4, 6, 8, 2, 1]
1   4<->5 :[2, 4, 5, 6, 8, 2, 1]
2   5 --6: FALSE
3   6 --8: FALSE
4   2<->8 :[2, 4, 5, 6, 2, 8, 1]
5   1<->8 :[2, 4, 5, 6, 2, 1, 8]
交换前5个数字 
0   2 --4: FALSE
1   4 --5: FALSE
2   5 --6: FALSE
3   2<->6 :[2, 4, 5, 2, 6, 1, 8]
4   1<->6 :[2, 4, 5, 2, 1, 6, 8]
交换前4个数字 
0   2 --4: FALSE
1   4 --5: FALSE
2   2<->5 :[2, 4, 2, 5, 1, 6, 8]
3   1<->5 :[2, 4, 2, 1, 5, 6, 8]
交换前3个数字 
0   2 --4: FALSE
1   2<->4 :[2, 2, 4, 1, 5, 6, 8]
2   1<->4 :[2, 2, 1, 4, 5, 6, 8]
交换前2个数字 
0   2 --2: FALSE
1   1<->2 :[2, 1, 2, 4, 5, 6, 8]
交换前1个数字 
0   1<->2 :[1, 2, 2, 4, 5, 6, 8]

# 快速排序
## 1.取基准值
## 2. 确保基准值 左<右
def quick_sort(raw_list):
    """快速排序""" 
    if len(raw_list) >= 2:  # 递归入口及出口
        pivot = raw_list[len(raw_list)//2]  # 选取基准值，也可以选取第一个或最后一个元素      
        left, right = [], []  # 定义基准值左右两侧的列表
        raw_list.remove(pivot)  # 从原始数组中移除基准值
        for num in raw_list:
            if num >= pivot:
                right.append(num)
            else:
                left.append(num)
        sorted_list=quick_sort(left) + [pivot] + quick_sort(right)    
    else:
        sorted_list=raw_list
    return sorted_list
# 示例：
array = [2,3,5,7,1,4,6,15,5,2,7,9,12]
print(quick_sort(array))

[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 12, 15]