练手代码白板

先来一个简单的 list

#include <stdio.h>

class ListNode {
public:
	ListNode(int n) {
		this->n = n;
		this->pNext = NULL;
	}
	int n;
	ListNode* pNext;
};

class List {
public:
	ListNode* pHead;
	List(ListNode* pHead) {
		this->pHead = pHead;
	}
	List* add(ListNode* node) {
		ListNode* pCurr = pHead;
		while (pCurr->pNext) {
			pCurr = pCurr->pNext;
		}	
		pCurr->pNext = node;
		return this;
	}
	List* reverse() {
		ListNode* pCurr = pHead;
		ListNode* pNext = pCurr->pNext;
		pHead->pNext = NULL;
		while (pNext) {
			ListNode* pTmp = pNext->pNext;
			pNext->pNext = pCurr;
			pCurr = pNext;
			pNext = pTmp;
		}
		pHead = pCurr;
		return this;
	}
	List* sort() {
		ListNode* pOldHead = pHead->pNext;		
		ListNode* pNewHead = pHead;
		pNewHead->pNext = NULL;
		while (pOldHead) {
			ListNode *pNewPre = NULL, 
				*pNewCurr = pNewHead, 
				*pTmp = pOldHead->pNext;
			for (; pNewCurr && pNewCurr->n <= pOldHead->n; 
				pNewPre = pNewCurr, pNewCurr = pNewCurr->pNext);
			if (pNewCurr == pNewHead) {
				pOldHead->pNext = pNewHead;
			} else {
				pNewPre->pNext = pOldHead;
				pOldHead->pNext = pNewCurr;
			}
			pOldHead = pTmp;
		}
		pHead = pNewHead;
		return this;
	}
	List* print() {
		ListNode* pCurr = pHead;
		while (pCurr) {
			printf("%d -> ", pCurr->n);
			pCurr = pCurr->pNext;
		}
		printf("NULL\n");
		return this;
	}
	~List() {
		ListNode* pCurr = pHead;
		while (pCurr) {
			ListNode* pNext = pCurr->pNext;
			printf("deleting %d\n", pCurr->n);
			delete pCurr;
			pCurr = pNext;
		}
	}
};

int main() {
	List* l = new List(new ListNode(0));
	l->add(new ListNode(2))
		->add(new ListNode(3))
		->add(new ListNode(1))
		->add(new ListNode(4))
		->add(new ListNode(0))
		->add(new ListNode(5));
	l->print();
	l->sort();
	l->print();
	delete l;
	return 0;
}

几个排序

#include <stdio.h>

void print(int* pArr, int n) {
	while (n--) {
		printf("%d\t", *pArr);
		pArr++;
	}
	printf("\n");
}

inline swap(int* pA, int* pB) {
	int tmp = *pA;
	*pA = *pB;
	*pB = tmp;
}

void bubbleSort(int* pArr, int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < n - i; j++) {
			if (pArr[j-1] > pArr[j]) {
				swap(&pArr[j-1], &pArr[j]);
			}
		}
	}
}

void selectSort(int* pArr, int n) {
	for (int i = 0; i < n; i++) {
		int min = i;
		for (int j = i; j < n; j++) {
			if (pArr[j] < pArr[min]) {
				swap(&pArr[j], &pArr[min]);
			}
		}
	}
}

void quickSort(int* pArr, int i, int j) {
	int a = i, b = j, p = (i + j) / 2;
	while (a <= b) {
		while (pArr[a] < pArr[p]) {
			a++;
		}
		while (pArr[b] > pArr[p]) {
			b--;
		}
		if (a <= b) {
			swap(&pArr[a], &pArr[b]);
			a++;
			b--;
		}
	}
	if (i < b) {
		quickSort(pArr, i, b);
	}
	if (a < j) {
		quickSort(pArr, a, j);
	}
}

int main() {
	int a[] = {5, 2, 1, 4, 3, 0, 0};
	int len = sizeof(a)/sizeof(int);
	print(a, len);
	//bubbleSort(a, len);
	//selectSort(a, len);
	quickSort(a, 0, len);
	print(a, len);
	return 0;
}

再来,字符集差集

#include <bitset>
#include <vector>

class CCharSubSet {
public:
    char* a;
    char* b;
    std::vector<char> c;
    
    CCharSubSet() {
        a = "abcd";
        b = "bd";
    }
    
    int Sub() {
        std::bitset<256> bitsetA, bitsetB;
        bitsetA.reset();
        bitsetB.reset();
        for (size_t i = 0; i < strlen(a); i++) {
            bitsetA[a[i] + 128] = true;
        }
        for (size_t i = 0; i < strlen(b); i++) {
            bitsetB[b[i] + 128] = true;
        }
        bitsetA ^= bitsetB;
        for (int i = 0; i < 256; i++) {
            if (bitsetA[i]) {
                c.push_back(i - 128);
            }
        }
        for (size_t i = 0; i < c.size(); i++) {
            printf("%c\n", c[i]);
        }
        return 0;
    }
};


int main() {
    CCharSubSet oCharSubSet;
    oCharSubSet.Sub();
    return 0;
}

条件找数

#include <bitset>
#include <set>
#include <vector>
#include <map>

class CNumber {
    static const int MAX = 100000;
    std::vector<int> vecPrimeTable;

    int InitPrimeTable() {
        std::bitset<MAX> isPrime;
        isPrime.set();
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i*i < MAX; i++) {
            if (isPrime[i]) {
                for (int j = i*i; j < MAX; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        for (int i = 2; i < MAX; i++) {
            if (isPrime[i]) {
                vecPrimeTable.push_back(i);
            }
        }
        return 0;
    }

    std::map<int, int> mapDigitalSum;

    int DigitalSumOf(int n) {
        if (mapDigitalSum[n] == 0) {
            int iTmp = n;
            int iSum = 0;
            while (iTmp) {
                iSum += iTmp % 10;
                iTmp /= 10;
            }
            mapDigitalSum[n] = iSum;
        }
        return mapDigitalSum[n];
    }

    std::set<int> setResult;
    
    int Dfs(int iCurr, int iMulti, int iSum) {
        //printf("%d, %d, %d\n", iCurr, iMulti, iSum);
        if (iMulti > MAX || iMulti < 0) {
            return -1;
        }
        if (DigitalSumOf(iMulti) == iSum) {
            setResult.insert(iMulti);
        }
        for (size_t i = 0; i < vecPrimeTable.size(); i++) {
            if (vecPrimeTable[i] < iCurr) {
                continue;
            }
            if (Dfs(vecPrimeTable[i], iMulti * vecPrimeTable[i],
                iSum + DigitalSumOf(vecPrimeTable[i])) == -1) {
                break;
            } 
        }
        return 0;
    }

    int Print() {
        for (std::set<int>::iterator it = setResult.begin();
                it != setResult.end(); it++) {
            printf("%d\n", *it);
        }
        return 0;
    }
    
public:
    int Run() {
        InitPrimeTable();
        Dfs(vecPrimeTable[0], 1, 0);
        Print();
        return 0;
    }
};

int main() {
    CNumber oNumber;
    oNumber.Run();
    return 0;
}

————————————-

2014-3-7 09:16:05 update 字符集差集还可以这么来写

#include <set>
#include <vector>
#include <algorithm>
#include <string>

class CCharSetDiff {
public:
    std::string Diff(std::string strA, std::string strB) {
        std::set<char> setA(strA.begin(), strA.end());
        std::set<char> setB(strB.begin(), strB.end());
        std::vector<char> vecDiff(256);
        std::set_difference(setA.begin(), setA.end(),
            setB.begin(), setB.end(), vecDiff.begin());
        return std::string(vecDiff.begin(), vecDiff.end());         
    }
};

int main() {
    CCharSetDiff oCharSetDiff;
    printf("%s\n", oCharSetDiff.Diff("abcd", "bd").c_str());
    return 0;
}

5 thoughts on “练手代码白板

    • 嗯,一般情况是没问题的,但是注意到 a b 两个变量,是声明为 char* 类型,而不是 unsigned char* 类型,所以 a[i] b[i] 的值可能为负,如果为负,用负值作为下标去索引 bitsetA bitsetB 就可能越界

Leave a Reply

Your email address will not be published. Required fields are marked *