剑指offer-笔记

1.任意进制间的转换

   思想：转换到10进制以后在转换为想要的进制

  要点：注意大于10进制的用‘A~Z’来表示

  

string Cvt(string str1,int m,int n)
{
  string str2;
  long int tem=0;
  int p;
  for(int i=0;i<str1.size();i++)
  {
     if(str1[i]>='0'&& str1[i]<='9')
         p=str1[i]-'0';
     else
         p=str1[i]-'A'+10;
     tem=tem*m+p;
  }
  while(tem)
  {
    p=tem%n;
    tem=tem/n;
    if(p>=0 && p<=9)
      str2=char('0'+p)+str2;
    else
      str2=(char)(p-10+'A')+str2; 
  }
 return str2;

}
int main()
{
  string str1="350A";
  int m=16;
  int n=10;
  string str2=Cvt(str1, m, n);
  cout << str2 << endl;

}

2.非循环和乘除的1+2+3+.....n

 思想：利用构造函数+静态变量

 要点： 类外初始化静态变量

using namespace std;

class A
{
private:
    static unsigned int N;
    static unsigned int Sum;
public:
    A(){++N;Sum+=N;}
    static void init(){N=0;Sum=0;}
    static unsigned int getSum(){return Sum;};
};

unsigned int A::N=0;
unsigned int A::Sum=0;

void main()
{
    int n=10;
    A *a=new A[n];
    delete []a;
    a=NULL;
    unsigned int Sum=A::getSum();
    
    cout<<Sum<<endl;


}

 3.快速排序求第K 大或者中位数

   思想：第k大就是排后所在的顺序

  要点；快排的时候对end的更新

  

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include<ctime>
using namespace std;

template<typename T>
 T RandomInRange(T start ,T end)
{
    srand(time(0));
    return rand()%(end-start)+start;

}


int parttion(int data[],int len,int start,int end)
{
    if(data==NULL || len<0 || start<0 || end>len)
        throw new std::exception("Invalid Parameters!");
    int index=RandomInRange(start ,end);
    swap(data[end],data[index]);
    
    int small=start-1;
    for(int i=start;i<end;i++)
    {  
       if(data[i]<data[end])
       {
         small++;
         if(small!=i)
            swap(data[small],data[i]);
       }
    }
    small++;
    swap(data[small],data[end]);
    return small;

}
void QuickSort(int data[],int len,int start ,int end)
{
    if(start==end)
        return;
    int index=parttion(data,len,start, end);
    if (index>start)
            QuickSort(data,len,start ,index-1);
    if (index<end)
            QuickSort(data,len,index+1,end);


}

void main()
{
    
    int a[7]={1,4,4,8,8,8,8};

    int len=7;
    int index=0;
    int mid_len=len>>1;
    int start=0;
    int end=6;
    while(index!=mid_len)
    {
       index=parttion(a,len,start, end);
       if(index>mid_len)
           end=index-1;
       else
           start=index+1;
    }
   cout<<a[index]<<endl;
    

}

4.利用c++自带的sort函数求解：

   

bool compare(int a,int b)
{
      return a<b;   //升序排列，如果改为return a>b，则为降序

}

int _tmain(int argc, _TCHAR* argv[])
{
     int a[20]={2,4,1,23,5,76,0,43,24,65},i;
     for(i=0;i<20;i++)
       cout<<a[i]<<endl;
     sort(a,a+20,compare);
     for(i=0;i<20;i++)
       cout<<a[i]<<endl;
     return 0;
}