1.第k个数（丑数）
剑指offer里有此题，但是其认为1为第一个丑数。
牛客网上此题认为1不为丑数，但是如果要正确计算的话，那么必须设置第一个丑数为1，那么求第k个数就转化为求第k+1个数
class KthNumber {View Code
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 {View Code
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 {View Code
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 SetupDictionaryView Code
{
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 {View Code
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 {View Code
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 {View Code
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;
}
};
代码不好理解，最好配合调试输出进行理解。