先来一个简单的 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; }
这是新装了VS2013看着PL忍不住玩一下么
我还在用 vs 2005,2013 长啥样
蛮好看的 都忍不住要装win8来试下了
差集的 +128的写法木有看明白,不加不是照样 做出来吗?
嗯,一般情况是没问题的,但是注意到 a b 两个变量,是声明为 char* 类型,而不是 unsigned char* 类型,所以 a[i] b[i] 的值可能为负,如果为负,用负值作为下标去索引 bitsetA bitsetB 就可能越界