1. 判断字符串是否是IP地址
#include#include int main(void){ char str[31], temp[31]; int a, b, c, d; while(gets(str) != NULL) { if (sscanf(str, "%d.%d.%d.%d", &a, &b, &c, &d )== 4 && a >= 0 && a <= 255 && b >= 0 && b <= 255 && c >= 0 && c <= 255 && c >= 0 && c <= 255) { sprintf(temp, "%d.%d.%d.%d", a, b, c, d); if (strcmp(temp, str) == 0) printf("YES\n"); else printf("NO\n"); } else printf("NO\n"); } return 0;}
2. 生成窗口最大值数组
有数组[2，3，4，3，2，5，6]，窗口尺寸为3，设窗口滑动方向为从左向右。得到下列路径图
[2 3 4] 3 2 5 6
2 [3 4 3] 2 5 6 2 3 [4 3 2] 5 6 2 3 4 [3 2 5] 6 2 3 4 3 [2 5 6] 沿路径取窗口最大值得数组[4，4，4，5，6]，要求在长度为N的数组和S指定的窗口尺寸在求得窗口最大值数组。使用上面的例子：
在第一个窗口中有意义数字的下标是{2}，那么最大值就是索引为2的数字4；
在第二个窗口中有意义的数字下标是{2，3}，于是最大值就是链表中第一位为索引的数字4； 在第三个窗口中有意义的数字下标是{2，3，4}，最大值就是链表中第一位为索引的数字4； 在第四个窗口中有意义的数字下标是{5}，最大值就是链表中第一位为索引的数字5； 在第五个窗口中有意义的数字下标是{6}，最大值就是链表中第一位为索引的数字6。
#includeusing namespace std;#include #include vector maxInWindows(const vector & num, unsigned int size){ vector ret; ret.resize(num.size() - size + 1); deque q; int index = 0; for (size_t i = 0; i < num.size(); ++i) { while (!q.empty() && num[q.back()] <= num[i]) { q.pop_back(); } q.push_back(i); if (q.front() == i - size) //队头过期，弹出队头元素，如数组为5,4,3,2，窗口大小为3， { //当将2放入队列中后，此时队头元素下标刚好等于队尾的下标-窗口的大小,此时弹出第一个元素。 q.pop_front(); } if (i >= size - 1)//滑动窗口的个数。 { size_t value = q.front(); ret[index++] = num[value]; } } return ret;}int main(){ vector v; v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(2); v.push_back(6); v.push_back(2); v.push_back(5); v.push_back(1); vector v1 = maxInWindows(v, 3); for (int i = 0; i < v1.size(); ++i) { cout << v1[i] <<" "; } cout<
3. 打印0-1000内的所有素数
#includeusing namespace std;bool isLeagle(int n){ //注意i<=sqrt(n),i要从2开始 for (int i = 2; i <=sqrt(n); i++) { if (0==(n%i)) return false; } return true;}int main(){ for (int i = 1; i < 100; i++) { if (isLeagle(i)) cout << i <<" "; } system("pause"); return 0;}
4. 仅用栈操作和递归逆序一个栈
#include#include using namespace std;int getAndRemoveLastElement(stack &st){ int res = st.top(); st.pop(); if (st.empty()) return res; else { //到最后一个元素时，将最后一个元素也就是栈底元素接收 int last = getAndRemoveLastElement(st); //压栈压的是本层递归的res,也就是栈底元素的上一个元素。 st.push(res); //最后会一直返回栈底元素 return last; }}void reserve(stack &st){ if (st.empty()) return; int i = getAndRemoveLastElement(st); //一直递归到最后一个元素（也就是原来的栈顶元素）然后再依次压栈， //就等于先压原来的栈顶元素，。。等于将栈逆转 reserve(st); st.push(i);}int main(){ stack st; st.push(1); st.push(2); st.push(3); while (!st.empty()) { cout << st.top() << " "; st.pop(); } system("pause");}
5. 用一个栈排序另一个栈
#include#include using namespace std;void SortStackByStack(stack &st){ stack helpStack; while (!st.empty()) { int cur = st.top(); st.pop(); //如果辅助栈不为空，并且辅助栈顶的元素小于当前栈顶的元素cur //则一直将辅助栈的元素弹出，并放入当前栈，直到辅助栈为空，或栈顶元素大于 //cur为止，然后将cur压入辅助栈中，使得辅助栈呈现栈顶到栈底元素依次增大的情况。 while (!helpStack.empty() && helpStack.top() < cur) { st.push(helpStack.top()); helpStack.pop(); } helpStack.push(cur); } while (!helpStack.empty()) { st.push(helpStack.top()); helpStack.pop(); }}int main(){ stack st; st.push(5); st.push(6); st.push(1); st.push(9); st.push(0); SortStackByStack(st); while (!st.empty()) { cout << st.top() << " "; st.pop(); } system("pause"); return 0;}
6. MyString
/* 1.注意在构造函数中要统一用new char[],用delete[] 2. 利用给参数默认值的方法，简化代码 3. 拷贝构造时不能用创建临时对象（调用拷贝构造）然后swap的方法，会死循环 4. 测试用例 1.功能测试 2. 连续赋值测试 3. 自赋值测试*/#include#include using namespace std;class String{public: String(char *str = "") { int len = strlen(str); _str = new char[len + 1]; strcpy(_str, str); } String(const String &str) { int len = strlen(str._str); _str = new char[len + 1]; strcpy(_str, str._str); } String &operator=(String &str) { if (&str != this) { String temp(str); swap(temp._str, _str); } return *this; } ~String() { if (_str) delete[]_str; } void Print() { cout << _str << endl; }private: char *_str;};//普通测试void Test1(){ char* text = "Hello world"; String str1(text); String str2; str2 = str1; printf("The expected result is: %s.\n", text); printf("The actual result is: "); str2.Print(); printf(".\n");}//自己给自己赋值void Test2(){ printf("Test2 begins:\n"); char* text = "Hello world"; String str1(text); str1 = str1; printf("The expected result is: %s.\n", text); printf("The actual result is: "); str1.Print(); printf(".\n");}//连续赋值void Test3(){ printf("Test3 begins:\n"); char* text = "Hello world"; String str1(text); String str2, str3; str3 = str2 = str1; printf("The expected result is: %s.\n", text); printf("The actual result is: "); str2.Print(); printf(".\n"); printf("The expected result is: %s.\n", text); printf("The actual result is: "); str3.Print(); printf(".\n");}int main(){ //Test1(); //Test2(); Test3(); system("pause"); return 0;}
7. 二分查找的应用-寻找数组中出现的重复字符2
/**/#include#include using namespace std;int getCount(const int *arr, int len, int start, int end){ assert(arr); int count = 0; for (int i = 0; i < len; i++) { if (arr[i] >= start&&arr[i] <= end) ++count; } return count;}int getNum(const int *arr, int len){ int start = 1; int end = len - 1; while (start <= end) { int mid = start + ((end - start) >> 1); int count = getCount(arr, len, start, mid); if (end == start) { if (count > 1) return start; else break; } if (count > (mid - start + 1)) end = mid; else start = mid + 1; } return -1;}int main(){ int arr[] = { 2, 3, 1, 0, 2, 5, 3 }; int len = sizeof(arr) / sizeof(arr[0]); int res = getNum(arr, len); cout << res << endl; system("pause"); return 0;}
8. 二分查找法
#include#include using namespace std;int BinarySearch(const int *arr, int len, int goal){ int start = 0; int end = len; while (start < end) { int mid = start + ((end - start) >> 1); if (arr[mid] < goal) start = mid + 1; else if (arr[mid]>goal) end = mid; else return arr[mid]; } return -1;}int main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int len = sizeof(arr) / sizeof(arr[0]); int goal; while (cin>>goal) cout<< BinarySearch(arr,len,goal)<
剑指offer数组中的重复数字
/* 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的， 但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。*//* 因为范围是0--n-1，且都为正整数，所以就可以用交换坐标的排序方式（类似题型）。 从第一个数字开始，如果数组的下标不等于数组的值，则与该数组值作为下标的数字交换 直到，数组下标等于数组值为止，在这个过程中，如果要交换的值等于本值则返回本值。*/#include #include using namespace std;int getNum(int *arr, int len){ assert(arr); for (int i = 0; i < len; i++) { while (i != arr[i]) { if (arr[i] == arr[arr[i]]) return arr[i]; swap(arr[i], arr[arr[i]]); } }}int main(){ int arr[] = { 2, 3, 1, 0, 2, 5, 3 }; int len = sizeof(arr) / sizeof(arr[0]); int res = getNum(arr, len); cout << res << endl; system("pause"); return 0;} 逆序打印链表
#include#include using namespace std;typedef struct Node{ int _data; struct Node *_pNext;}Node,*PNode;//创建新节点时不要忘了将后续指针置空PNode createNewNode(int data){ PNode newNode = (PNode)malloc(sizeof(Node)); if (NULL==newNode) { cout << "内存分配失败" << endl; exit(0); } newNode->_data = data; newNode->_pNext = NULL; return newNode;}void PushFront(PNode* pHead, int data){ assert(pHead); if (NULL == (*pHead)) (*pHead) = createNewNode(data); else { PNode pCur = (*pHead); PNode newNode = createNewNode(data); newNode->_pNext = pCur; (*pHead) = newNode; }}void PrintReverse(PNode pNode){ if (pNode) { PrintReverse(pNode->_pNext); cout << pNode->_data << "->"; }}int main(){ PNode pHead = NULL; PushFront(&pHead,1); PushFront(&pHead, 2); PushFront(&pHead, 3); PushFront(&pHead, 4); PushFront(&pHead, 5); PrintReverse(pHead); system("pause");}
将字符串的空格替换成%20
#include#include using namespace std;int getSpaceNum(const char *arr,int len){ int num = 0; for (int i = 0; i < len; i++) { if (' ' == arr[i]) ++num; } return num;}void addTo20(char *arr, int len){ assert(arr); int num = getSpaceNum(arr, len); int begin = 0; int end = begin + len + 2 * num-1; int tail = len-1; //不要忘了tail要>=0 while (tail>=0&&tail < end) { if (arr[tail] == ' ') { arr[end--] = '0'; arr[end--] = '2'; arr[end--] = '%'; } else { arr[end--] = arr[tail]; } --tail; }}int main(){ //char arr[]=""会带上\0 char arr[100] =" are you ok "; int len = strlen(arr);//10 int len1 = sizeof(arr) / sizeof(arr[0]);//11 addTo20(arr, len); cout << arr << endl; system("pause");}