1编程维持第一天：冒泡排序
//注意，数组的长度需要手动传入
#include<iostream>
using namespace std;
void bubble_sort(int* a,int size)
{
//1空的输入
if(a == nullptr)
return;
//2注意边界条件
for(int i=size-1;i>=0;i--)
{
for(int j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
int tmp = a[j];
a[j]= a[j+1];
a[j+1] =tmp;
}
}
}
}
int main()
{
int a[]={100,20,30,50,60,40,90,80,70,10};
int len_a = sizeof(a)/sizeof(a[0]);
cout<<len_a<<endl;
cout<<"before sorting";
for(int i=0;i<len_a;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
//冒泡排序
bubble_sort(a,len_a);
cout<<"after sorting";
for(int i=0;i<len_a;i++)
{
cout<<a[i]<<" ";
}
}
2编程维持第2天：快速排序
//终止条件：注意是>=,==的话就报错
//快速排序
//终止条件：注意是>=,==的话就报错
#include<iostream>
using namespace std;
void quick_sort(int *a ,int begin,int end)
{
if(begin >=end)//注意是>=,==的话就报错
return;
//定义1个基准值
int base= a[begin];
int i=begin;
int j=end;
while(i!=j)
{
//从右往左找第一个小于基准值的数
while(a[j]>=base && i<j)
{
j--;
}
//从左往右找第一个大于基准值的数
while(a[i]<=base && i<j)
{
i++;
}
//两个数进行交换
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
a[begin] =a[i];
a[i] =base;
//在基准值左边和右边进行快速排序
quick_sort(a,begin,i-1);
quick_sort(a,i+1,end);
}
int main()
{
int a[10]={9,1,8,2,7,3,6,4,5,0};
cout<<" before quick_sort"<<endl;
for(int i=0;i<(sizeof(a)/sizeof(a[0]));i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
quick_sort(a,0,9);
cout<<" after quick_sort"<<endl;
for(int i=0;i<(sizeof(a)/sizeof(a[0]));i++)
{
cout<<a[i]<<" ";
}
}
3编程维持第3天：二进制中1的个数
//注意：a<<1；//对a是没有效果的。
//n&flag 不是一直为1的
//必须强化手写代码的能力，怎么考就怎么测试
//普通解法
#include<iostream>
using namespace std;
int NumOf1(int n)
{
int flag=1;
int count =0;
for(int i=0;i<32;i++)//因为int8个字节，32位
{
if(n&flag)//按位与
{
count++;
}
flag=flag<<1;
}
return count;
}
int main()
{
int num=NumOf1(7);
cout<<num<<endl;
}
//好一点的解法
#include<iostream>
using namespace std;
int NumOf1(int n)
{
if(n==0)
return 0;
int count=0;
while(n)
{
count++;
n=n&(n-1);
}
return count;
}
int main()
{
int num=NumOf1(8);
cout<<num<<endl;
}
4编程维持第4天：归并排序
#include<iostream>
using namespace std;
void merge(int* a,int begin,int mid,int end)
{
//步骤1：
//定义1个临时区域
int* tmp= new int[end-begin+1];
//定义第1个有序区索引
int i=begin;
//定义第二个有序区索引
int j=mid+1;
//定义临时区域索引
int k=0;
//步骤2：将数往临时区域存放
while(i<=mid && j<=end)
{
if(a[i]<a[j])
tmp[k++]=a[i++];
else
tmp[k++]=a[j++];
}
while(i<=mid)
{
tmp[k++]=a[i++];
}
while(j<=end)
{
tmp[k++]=a[j++];
}
//步骤3：把临时区域中的数往a中存放
for(i=0;i<k;i++)
{
a[begin+i]=tmp[i];
}
delete[] tmp;
}
void mergesort(int*a ,int begin,int end)
{
//终止条件
if(begin>=end)
return;
int mid = (begin+end)/2;
//步骤1：左边变为有序序列
mergesort(a,begin,mid);
//步骤2：右边变为有序序列
mergesort(a,mid+1,end);
//步骤3：合并两个有序序列
merge(a,begin,mid,end);
}
int main()
{
int a[10]={9,0,8,1,7,2,6,3,5,4};
cout<<"before merging sorting:";
for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
mergesort(a,0,9);
cout<<"after merging sorting :";
for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
5编程维持第5天：二分查找
二分查找非递归排序
//二分查找
#include<iostream>
//注意：数列必须是有序的才行啊
using namespace std;
int BinarySearch(int* a,int begin,int end,int n)
{
while(begin!=end)
{
int mid = (begin+end)/2;
if(n<a[mid])//小于的话，往前移
end= mid-1;
else if(n>a[mid])//大于的话，往后移动
begin= mid+1;
else
return mid;
}
if(a[begin]==n)
return begin;
else
return 0;
}
int main()
{
//数列必须是有序的才行啊
int a[]={3,4,5,6,7,8,9,10,11,12};
//0:开始，9：结束，5，要搜索的数
int result =BinarySearch(a,0,9,100);
cout<<result<<endl;
}
二分查找递归排序
//二分查找
#include<iostream>
//注意：数列必须是有序的才行啊
//递归排序
using namespace std;
int BinarySearch(int* a,int begin,int end,int n)
{
//终止条件
if(begin>=end)
{
if(a[begin]==n)
return begin;
else
return 0;
}
int mid=(begin+end)/2;
if(n<a[mid])
{
BinarySearch(a,begin,mid-1,n);
}
else if(n>a[mid])
{
BinarySearch(a,mid+1,end,n);
}
else
return mid;
}
int main()
{
//数列必须是有序的才行啊
int a[]={3,4,5,6,7,8,9,10,11,12};
//0:开始，9：结束，5，要搜索的数
int result =BinarySearch(a,0,9,10);
cout<<result<<endl;
}
6编程维持第6天：反转数字
臻迪科技面试题：
给定一个32位的整数，将整数中的数字进行反转并打印(4个字节 int类型 )
例如：
输入：123，输出321
输入：-123，输出-321
输入：120，输出21
思路：可以用栈
#include<iostream>
#include<math.h>
using namespace std;
int reverse(int n)
{
//对输入的值的范围进行判断
if(n>1200||n<-1200)
return 0;
//步骤1：先判断该数是否小于0，如果小于0，进行取反
//正数和负数的标志
int flag=0;
if(n<0)
{
n=-n;
flag=1;//负数为1
}
cout<<"num:"<<n<<endl;
//步骤2：判断该数一共有几位
int count=0;
for(int i=9;i>=0;i--)
{
int tmp = pow(10,i);
if(n/tmp!=0)
{
count=i+1;
break;
}
}
cout<<"num's count:"<<count<<endl;
//步骤3:得到新的数
//比如123
//123/100%10=1
//123/10%10=2
//123/1%10=3
int reverse_num=0;
int k=0;
for(int j=count-1;j>=0;j--)
{
int tmp = pow(10,j);
reverse_num+=((n/tmp%10)*pow(10,k));
k++;
}
//步骤4:对正负进行判断
if(flag==1)
reverse_num=(-reverse_num);
return reverse_num;
}
int main()
{
int num=1300;
cout<<reverse(num)<<endl;
}
