1.数组中只有一个数字只出现一次,其他都成对出现
如:int a[] = {2,3,5,6,4,3,2,5,6}; 打印出4。
首先呢,先分析此题。
可将数组的第一个元素与后边其他元素进行异或,(异或的性质:任何一个数字异或自己都为0)若为0,则将这个元素删除。
如:数组第一个元素为2,当碰到后边那个2时,将后边元素删除。a[] = {2,3,5,6,4,3,5,6}。
然后比较数组第二个,以此类推。
当我们在数组前面找到这个这个只出现一次的元素,即可return。因为题目给出的是只有一个数字只出现一次呢。
int FindOneNum(int* a,int size)
{
int i = 0;
for(int j=i+1;j<size-i;j++)
{
if(i<size)
{
if(((a[i])^(a[j])) == 0)
{
for(int k=j;k<size-i;k++)
{
a[k] = a[k+1];
}
i++;
j = i;
continue;
}
if(((a[i])^(a[j])) != 0 && j == size-i-1)
{
return a[i];
}
}
}
return a[i];
}
//测试函数
void Test()
{
int a[] = {4,2,3,5,6,3,2,5,6};
//int a[] = {2,3,5,6,4,3,2,5,6};
//int a[] = {2,3,5,6,3,2,5,6,4};
int size = sizeof(a)/sizeof(a[0]);
int ret = FindOneNum(a,size);
cout<<ret<<endl;
return 0;
}
//测试结果
2.数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。
分析:
数组若为无序,则先将数组排序。
数组中有一个元素的次数超过数组长度的一半,也就是说它的出现次数比其他数字之和还要多。
因此我们在遍历数组时,应该保存两个值:一个是数字,一个是次数。当我们遍历到下一个数字时,若与我们之前保存的数字相同,则次数加1,不同次数减1。若次数为0,则需要保存下一个数字,并将次数置为1。那么我们要找的可能就是最后一次将次数置为1的数字。
bool CheckArray(int* a,int size)//检查数组是否合法
{
if(a == NULL || size <= 0)
return false;
return true;
}
void Sort(int* a,int size)//数组排序
{
if(CheckArray(a,size))
{
int i = 0;
int j = 0;
for(i=0;i<size-1;i++)
{
for(j=0;j<size-i-1;j++)
{
if(a[j] > a[j+1])
{
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
return;
}
bool MornThanHalf(int* a,int size,int num)//是否超过一半
{
int count = 0;
for(int i=0;i<size;i++)
{
if(a[i] == num)
{
count++;
}
}
if(count*2 >= size)
{
return true;
}
return false;
}
int MoreThan(int* a,int size)//次数较多的数
{
if(!CheckArray(a,size))
return 0;
int num = a[0];
int count = 1;
for(int i=1;i<size;i++)
{
if(num == a[i])//数字相同
{
count++;
}
else
{
count--;
}
if(count == 0)
{
num = a[i];
count = 1;
}
}
if(MornThanHalf(a,size,num))
{
return num;
}
return 0;
}
//测试函数
void Test()
{
int a[] = {3,2,3,3,2,3,4,3,4,2,3,3};
int size = sizeof(a)/sizeof(a[0]);
Sort(a,size);
int ret = MoreThan(a,size);
cout<<ret<<endl;
}
//测试结果
3.实现一个函数,可以右旋字符串中的k个字符。(可以左旋字符串中的k个字符)
ABCDE右旋一个字符得到BCDEA
ABCDE右旋两个字符得到CDEAB
ABCDE左旋一个字符得到EABCD
ABCDE左旋两个字符得到DEABC
void move(char* left,char* right)
{
while(left < right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
int main()
{
char p[] = {"ABCDE"};
int size = strlen(p);
int n = 0;
cin>>n; //n=3
//右旋n为
//move(p,p+n-1); //CBADE
//move(p+n,p+size-1); //CBAED
//move(p,p+size-1); //DEABC
//cout<<p<<endl;
//左旋n位
move(p+n,p+size-1); //ABEDC
move(p,p+n-1); //BAEDC
move(p,p+size-1); //CDEAB
cout<<p<<endl;
}
第3题扩展:判断一个字符串是否为另外一个字符串旋转之后的字符串。
bool CheckEquel(char* p,char* q,int size)
{
char* tmp = new char[size+1];
for(int n=0;n<size;n++) //最多可旋转size个字符
{
strcpy(tmp,p); //每次进出都必须将p的内容复制给tmp
move(tmp,tmp+n-1); //调用move函数,旋转n个字符
move(tmp+n,tmp+size-1);
move(tmp,tmp+size-1);
if(strcmp(tmp,q) == 0) //旋转后的字符串与q相等
{
return true;
}
}
return false;
}
int main()
{
char p[] = {"ABCDE"};
char q[] = {"CDEAB"};
int size = strlen(p);
bool ret = CheckEquel(p,q,size);
if(ret == true)
{
cout<<"字符串是由旋转得来的"<<endl;
}
else
{
cout<<"字符串不是由旋转得来的"<<endl;
}
return 0;
}
测试结果:
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。