1.第k个数（丑数）
剑指offer里有此题，但是其认为1为第一个丑数。
牛客网上此题认为1不为丑数，但是如果要正确计算的话，那么必须设置第一个丑数为1，那么求第k个数就转化为求第k+1个数
class KthNumber { public: int findKth(int k) { // write code here if(k<=0) return 0; else if(1==k) return 3; else if(2==k) return 5; else if(3==k) return 7; else if(k>100) return 0; int index=1,min,res; int *num=new int[k+1]; num[0]=1; int *multi3=num,*multi5=num,*multi7=num; while(index<k+1){ min=minval(*multi3*3,*multi5*5,*multi7*7); num[index]=min; while(*multi3*3<=min) ++multi3; while(*multi5*5<=min) ++multi5; while(*multi7*7<=min) ++multi7; ++index; } res=num[index-1]; delete[] num; num=NULL; return res; } private: int minval(const int& num1,const int& num2,const int& num3){ int min=num1<num2?num1:num2; return min<num3?min:num3; } };
2.字符的全排列（很重要,结果做一次错一次，还是使用递归）
class Permutation { public: static bool compare(const string& s1,const string& s2){ return s1 < s2 ? false : true; } //此题为不重复的全排列 vector<string> getPermutation(string A) { vector<string> res; int len=A.length(); if(len<=1) { res.push_back(A); return res; } PermutationStr(A,0,len-1,res); sort(res.begin(),res.end(),compare); return res; } private: void PermutationStr(string& str,int k,int m,vector<string>& res){ if(k==m){ res.push_back(str);return; } for(int i=k;i<=m;++i){ if(isswap(str,k,i)){ swap(str[k],str[i]); PermutationStr(str,k+1,m,res); swap(str[k],str[i]); } } } bool isswap(string& str,const int& left,const int& right){ if(left>right) return false; for(int i=left;i<right;++i) if(str[i]==str[right]) return false; return true; } void swap(char& a,char& b){ char t=a;a=b;b=t; } };
3.旋转字符串里搜寻数据
这个比剑指offer里寻找第一个数字要有难度，首先寻找规律，然后通过递归去寻找，简直了
class Finder { public: //此题保证了数据是不重复的，如果允许重复就要考虑顺序查找 int findElement(vector<int> A, int n, int x) { int len=A.size(); if(len!=n||len<=0) return 0; else if(1==len){ if(A[0]==x) return 0; else return -1; } return search(A,0,len-1,x); } private: int search(vector<int>& a,const int left,const int right,const int x){ int mid=(left+right)>>1; if(x==a[mid]) return mid; if(right<left) return -1; //左半边或右半边必有一边是正常排序的 if(a[left]<a[mid]){ //左半边为正常排序 if(x>=a[left]&&x<=a[mid]) return search(a,left,mid-1,x); else return search(a,mid+1,right,x); }else if(a[mid]<a[left]){ //右半边为正常排序 if(x>=a[mid]&&x<=a[right]) return search(a,mid+1,right,x); else return search(a,left,mid-1,x); }else if(a[left]==a[mid]){ //左半边都为重复元素 if(a[mid]!=a[right]) return search(a,mid+1,right,x); else { //搜索两边 int res=search(a,left,mid-1,x); if(-1==res){ return search(a,mid+1,right,x); }else return res; } } return -1; } };
我照着写，都能把程序写错，也是简直了
4.求素数小程序
bool judgeprime(int n) { if (n < 2) return false; else if (2 == n) return true; int i, n = (int)sqrt(n); for (i = 3;i < n;i += 2) { if (n%i == 0) return false; } return true; }
写着玩的
5.词频统计（牛客网上提交的是另外一份简易代码，自己用hash_map实现了下，支持重复查找）
class SetupDictionary { public: SetupDictionary() {} ~SetupDictionary() {} public: void setDictionary(vector<string>& book) { table.clear(); int len = book.size(); if (len <= 0) return; hash_map<string, int>::iterator itr; for each ( auto tmp in book) { itr = table.find(tmp); if (table.end() == itr) { table.insert(pair<string, int>(tmp, 1)); } else { ++(itr->second); } } } int getFrequency(string& word) { if (0 == table.size() || word.length() <= 0) return -1; hash_map<string, int>::iterator itr; itr = table.find(word); if (itr == table.end()) return -1; else return itr->second; } private: hash_map<string, int> table; };
尚未做什么鲁棒性检查和优化，不过觉得蛮好玩的，算是自己写代码以来最喜欢的代码吧
6.整数对个数统计
class FindPair { public: //此处应该是默认数据不重复,否则此种解法不适用 int countPairs(vector<int> A, int n, int sum) { int i,left, right, num = 0, len = A.size(), currsum; if (len<2) return num; sort(A.begin(), A.end()); if (A[0] + A[1]>sum) return 0; if (A[len - 1] + A[len - 2]<sum) return 0; left = 0;right = len - 1; while (left<right) { currsum = A[left] + A[right]; if (currsum == sum) { ++num; //从左至右统计 for (i = left + 1;i < right;++i) { if (A[i] + A[right] == sum) ++num; else break; } for (i = right - 1; i > left; --i) { if (A[i] + A[left] == sum) ++num; else break; } ++left;--right; } else if (currsum<sum) { ++left; } else { --right; } } return num; } };
与程序员面试金典一书的解法不同，做了对重复数据的补充计算。
7.加法运算替代
虽然不知道这个有什么作用，不过还是做出来了。。。
class AddSubstitution { public: int calc(int a, int b, int type) { // write code here int i,num=0; if(1==type){ if(0==a||0==b) return 0; else{ if(b<0){ for(i=0;i<absval(b);++i){ num+=a; } if(a<0) return num; else return negate(num); }else{ for(i=0;i<b;++i){ num+=a; } return num; } } }else if(0==type){ if(0==a||0==b) return 0; bool signa=a<0?true:false; bool signb=b<0?true:false; int absa=absval(a),absb=absval(b),res=0; if(absa<absb) return 0; else{ for(res=0;num<=absa;res++){ num+=absb; } } if(signa==signb){ return res+(-1); }else return negate(res)+1; }else if(-1==type){ if(0==a) return b; else if(0==b) return a; return a+negate(b); }else{ return 0; } } private: int negate(int x){ int num=0,d=x<0?1:-1; while(x){ x+=d; num+=d; } return num; } int absval(int x){ if(x<0){ return negate(x); }else return x; } };
8.找出字符串
class Finder { public: int findString(vector<string> str, int n, string x) { int len=str.size(); if(n!=len||n<=0) return -1; int left=0,right=len-1,mid; while(left<=right){ mid=(right-left)/2+left; if(str[mid].length()!=0){ //非空字符串比较 if(str[mid]==x){ return mid; }else{ if(str[mid]>x) right=mid-1; else left=mid+1; } }else{ //空字符串处理 int temp=mid; while(temp>=left&&str[temp].length()==0){ --temp; } if(temp<left) left=mid+1; //此处是最容易忽略的地方 else if(str[temp]==x) return temp; else if(str[temp]<x) left=mid+1; else right=temp-1; } } return -1; } };
9.变位词排序
题目：请编写一个方法，对一个字符串数组进行排序，将所有变位词合并，保留其字典序最小的一个串。
这里的变位词指变换其字母顺序所构成的新的词或短语。例如"triangle"和"integral"就是变位词。
第一次使用map，感觉真的很好使用，不过使用过程中发现键值可能存在冲突，后续查看相关资料。
class SortString { public: vector<string> sortStrings(vector<string> str, int n) { vector<string> res; int i, len = str.size(), pos = 0; if (len != n || n <= 0) return res; string temp; map<string, string> stemp; //排完序的单词对应的变位词 for (i = 0;i<len;++i) { temp = str[i]; sort(temp.begin(), temp.end()); if (stemp.find(temp) == stemp.end() || stemp[temp] > str[i]) { //此处的temp即为key,而stemp[temp]则是根据key寻找到的value值 stemp[temp] = str[i]; } } for each (auto var in stemp) { res.push_back(var.second); } sort(res.begin(), res.end()); return res; } };
10.像素设定（此题考查位操作，需很谨慎）
参考他人代码完成，后续需要自己再联系
class Render { public: vector<int> renderPixel(vector<int> screen, int x, int y) { int len = screen.size(); if (x > y || x<0 || (y / 8)>len || len <= 0) return screen; int i, numx = x / 8, numy = y / 8, endx = x % 8, endy = y % 8; int mask = 1; if (numx == numy) { mask = mask << endx; for (i = endx; i <= endy; i++) { screen[numx] = screen[numx] | mask; mask = mask << 1; } } else { mask = mask << endx; for (i = endx;i < 8;++i) { screen[numx] |= mask; mask = mask << 1; } for (i = 0, mask = 1;i <= endy;++i) { screen[numy] |= mask; mask = mask << 1; } for (i = numx + 1;i <= numy - 1;++i) //绘制中间区域 screen[i] = 255; } return screen; } };
11.洪水
此题甚是巧妙，不用递归也能巧妙解决，赞
class Flood { public: int floodFill(vector<vector<int>> map, int n, int m) { int row = map.size(), col = map[0].size(); if ((1 == n - 1 && 0 == m) || (1 == m - 1 && 0 == n)) return 1; if (1 == n - 1 && 1 == m - 1) return 2; int i, j, res = 0; for (i = 0;i < row;++i) { for (j = 0;j < col;++j) { if (map[i][j] == 1) map[i][j] = INT_MAX; else map[i][j] = -1; } } map[0][0] = 0; while (map[row - 1][col - 1] == -1) { res++; for (i = 0;i < res&&i < row;++i) { for (j = 0;j < res - i&&j < col;++j) { if (map[i][j] == res - 1) { if (i + 1 < row && (map[i + 1][j] == -1 || (map[i + 1][j] != INT_MAX&&map[i + 1][j] > res))) map[i + 1][j] = res; if (j + 1 < col && (map[i][j + 1] == -1 || (map[i][j + 1] != INT_MAX&&map[i][j + 1] > res))) map[i][j + 1] = res; } } } } return res; } };
代码不好理解，最好配合调试输出进行理解。