Scrawl - 自留地 - 房前屋后，种瓜种豆

[原创]生成Excel列名

def ExcelColumns(num):
    res = ''
    while num > 0:
        res = chr(ord('A') + ((num-1) % 26)) + res
        num = (num-1) / 26
    return res
    
if __name__ == '__main__':
    all_columns = [ExcelColumns(i) for i in range(1000)]
    print all_columns[1:]

[原创]单链表逆序

LinkNode* ReverseLink(LinkNode *pLink)
{
	if (pLink->pNext == NULL || pLink == NULL)
		return pLink;
	LinkNode *pHead = ReverseLink(pLink->pNext);
	pLink->pNext->pNext = pLink;
	pLink->pNext = NULL;
	return pHead;

}

LinkNode* ReverseLink(LinkNode *pLink)
{
	if (pLink->pNext == NULL || pLink == NULL)
		return pLink;
	LinkNode *p, *q, *r;
	p = NULL;
	q = pLink;
	r = q->pNext;
	while (r != NULL)
	{
		q->pNext = p;		
		p = q;
		q = r;
		r = r->pNext;

	}
	q->pNext = p;
	return q;
}

[原创]树相关代码

void PreTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
    stack<TreeNode*> nodeStack;
	nodeStack.push(pRoot);
	cout<<"preTravel:"<<endl;
	while (!nodeStack.empty())
	{
		TreeNode *pNode = nodeStack.top();
		nodeStack.pop();
		cout<<pNode->data<<' ';
		if (pNode->pRight != NULL)
		{
			nodeStack.push(pNode->pRight);
		}
		if (pNode->pLeft != NULL)
		{
			nodeStack.push(pNode->pLeft);
		}
	}
	cout<<endl<<endl;

}

void midTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	stack<TreeNode*> nodeStack;
	TreeNode *pNode = pRoot;
	cout<<"midTravel:"<<endl;
	while (pNode != NULL || !nodeStack.empty())
	{
		if (pNode != NULL)
		{
			nodeStack.push(pNode);
			pNode = pNode->pLeft;
		} 
		else
		{
			pNode = nodeStack.top();
			cout<<pNode->data<<' ';
			nodeStack.pop();
			pNode = pNode->pRight;
		}
	}
	cout<<endl<<endl;
}

void postTravel(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	stack<TreeNode*> nodeStack;
	TreeNode *pNode = pRoot;
	cout<<"postTravel:"<<endl;
	while (pNode != NULL || !nodeStack.empty())
	{
		if (pNode != NULL)
		{
			nodeStack.push(pNode);
			pNode = pNode->pLeft;
		} 
		else
		{
			pNode = nodeStack.top();
			nodeStack.pop();
			if (!pNode->visited)
			{
				pNode->visited = true;
				nodeStack.push(pNode);
				pNode = pNode->pRight;
			} 
			else
			{
				cout<<pNode->data<<' ';
				pNode = NULL;
			}
		}
	}
	cout<<endl<<endl;
}

void layerTravel(TreeNode *pRoot)
{
        if (pRoot == NULL)
		return;
	deque<TreeNode*> nodeDeque;
	nodeDeque.push_back(pRoot);
	cout<<"layerTravel:"<<endl;
	while (!nodeDeque.empty())
	{
		TreeNode *pNode = nodeDeque.front();
		nodeDeque.pop_front();
		cout<<pNode->data<<' ';
		if (pNode->pLeft != NULL)
			nodeDeque.push_back(pNode->pLeft);
		if (pNode->pRight != NULL)
			nodeDeque.push_back(pNode->pRight);
	}
	cout<<endl<<endl;
}

void ConstructTree(int* preSeq, int* midSeq, int treeLen, TreeNode **ppRoot)
{
	if (NULL == preSeq || NULL == midSeq || treeLen <= 0)
		return;
	int nRoot = *preSeq;
	TreeNode *pNode = new TreeNode(nRoot, false, NULL, NULL);
	if(NULL == *ppRoot)
		*ppRoot = pNode;
	int nPos = -1;
	for (int i=0; i<treeLen; ++i)
	{
		if (midSeq[i] == nRoot)
		{
			nPos = i;
			break;
		}
	}
	if (nPos >= treeLen || nPos < 0)
		return;
	ConstructTree(preSeq+1, midSeq, nPos, &pNode->pLeft);
	ConstructTree(preSeq+nPos+1, midSeq+nPos+1, treeLen-nPos-1, &pNode->pRight);

}

void DestroyTree(TreeNode *pRoot)
{
	if (pRoot == NULL)
		return;
	if (pRoot->pLeft != NULL)
	{
		DestroyTree(pRoot->pLeft);
		pRoot->pLeft = NULL;
	}
	if (pRoot->pRight != NULL)
	{
		DestroyTree(pRoot->pRight);
		pRoot->pRight = NULL;
	}
	cout<<"data "<<pRoot->data<<" has been deleted."<<endl;
	delete pRoot;
	pRoot = NULL;
}

[原创]一道面试题

题目： 2n个数，一半奇数，一半偶数，设计一个程序让奇数位上的数是奇数，偶数位上的是偶数

要求：时空复杂度尽量低

看到群里发的这个题目，随手写了个一个答案：

def swap(a, i, j): 
    a[i] = a[i] + a[j]
    a[j] = a[i] - a[j]
    a[i] = a[i] - a[j]
        
def Fun():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list
    i,j = 0,1
    nSwap = 0
    while nSwap < 50 and max(i,j) < 100:
        if the_list[i] % 2 != 0 and the_list[j] % 2 == 0 :
            swap(the_list,i,j)
            i += 2
            j += 2
            nSwap += 1
        elif the_list[i] % 2 == 0 :
            i += 2
        elif the_list[j] % 2 != 0 :
            j += 2
    print "sorted:", the_list

经penny等群友的提醒，优化一下，第二版：

def Fun2():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list 
    for i,j in zip([pos for pos in range(0,100,2) if (the_list[pos] + pos) % 2 != 0],
                              [pos for pos in range(1,100,2) if (the_list[pos] + pos) % 2 != 0]):
        the_list[i], the_list[j] = the_list[j], the_list[i]
    print "sorted:", the_list

附：penny发了一个点积的优化

A[]={<0,4>,<3,5>,<8,3>}
B[]={<3,5>,<9,3>}

C=A*B = {<3,25>}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;	
	if(A[i].index == B[j].index)
	{
		C[k].index = A[i].index;
		C[k].value = A[i].value * B[j].value
		k++
	}
	else if(A[i].index < B[j].index)
	{
		i++;
	}
	else if(A[i].index > B[j].index )
	{
		j++;
	}
}

A_I[]={0,3,8}
B_I[]={3,9}
A_V[]={4,5,9}
B_V[]={5,3}
for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	if(A_I[i] == B_I[j])
	{
		C[k].index = A_I[i];
		C[k].value = A_V[i]*B_V[j];
	}
	else if(A_I[i] < B_I[j])
	{
		i++;
	}
	else
	{
		j++;
	}
}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	i=0;
	j=0;
	bool equal  =  A_I[i] == B_I[j];
	bool smaller=  A_I[i] < B_I[j]; 
	bool bigger =  A_I[i] > B_I[j];
	C[k].index  =  equal*A_I[i];
	C[k].value  =  equal*A_V[i]*B_V[j];
	k+=equal;
	i+=equal;
	j+=equal;
        i+=smaller;
	j+=biger;	
}

[原创]生成自描述的序列

给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】

最省脑细胞的做法自然是盲搜：

def selfDescribableSeqence(arr):
    for guess in range(9*10**len(arr)):
        guess_list = (['0']*(10-len(str(guess))))
        guess_list.extend(list(str(guess)))
        if isOK(arr, guess_list):
            return guess_list   
    
def isOK(top, bottom):
    def freq(val):
        return len(list(filter(lambda x: x == val, bottom)))
    return len(list(filter(lambda x: str(freq(x)) == bottom[int(x)], top))) == len(top)
 

if __name__ == '__main__':
    print(selfDescribableSeqence(list(map(str, list(range(0,10))))))

显然，脑细胞是省下了，CPU就太浪费了，要判断解空间之外的很多分支。改成宽度优先：

def selfDescribableSeqence():
    res = list(range(10))
    while True:
        for pos in range(10):
            adjust(res, pos)
            if isOK(res):
                return res

def freq(arr,val):
    return len(list(filter(lambda x: x == val, arr)))
    
def adjust(arr, pos):
    the_freq = freq(arr, pos)
    if arr[pos] != the_freq:
        arr[pos] = the_freq
        pos = the_freq

def isOK(arr):
    id_and_value = [(id, val) for (id,val) in enumerate(arr)]
    return len(list(filter(lambda x : freq(arr, x[0])==x[1], id_and_value))) == len(id_and_value)

if __name__ == '__main__':
    print(selfDescribableSeqence())

[原创]24点

下了python3.1，写了一个24点的程序练手。

#! /usr/bin/env python
#coding=utf-8
import operator
import itertools
import functools

def compute(a, b, c, d, total):
    for guess_num in itertools.permutations([a,b,c,d], 4):
        for guess_op in itertools.product(['+','-','*','/'],repeat=3):
            tmp_list = [(num, op) for (num, op) in itertools.zip_longest(guess_num, guess_op, fillvalue='')]
            expression = functools.reduce(operator.add, map(lambda x : x[0] + x[1],tmp_list))
            res = eval(expression)
            if abs(float(res) - float(total)) < 0.001:
                print(expression + ' = ' + total)
                return
    print("None.")
       
if __name__ == '__main__':
    compute('2','11','9','8','24')

自留地