2018腾讯内部调岗面试试题2——打印A-Z这26个字母的所有子集
2018腾讯内部调岗面试试题2——打印A-Z这26个字母的所有子集
恋喵大鲤鱼
发布于 2018-08-03 10:14:02
发布于 2018-08-03 10:14:02
题目：有一个集合由A-Z这26个字母组成，打印这个集合的所有子集，每个子集一行，使用C/C++实现，不要使用递归。
分析：该题可参见著作《编程之法：面试和算法心得》。26个大写字母，乍一看真没啥思路，假设只有三个字母ABC，那么子集有：
{}
A
B
C
AB
AC
BC
ABC把ABC看作三个比特位，分别为：
000
100
010
001
110
101
011
111对上面的比特位表示的数值做个排序：
000
001
010
011
100
101
110
111可以发现数值范围是0到2^3-1，数值中每一个比特位非零，表示该子集中包含对应位置的字母。同理，针对26个字母，我们只需要遍历0-2^26-1，检查每一个比特位是否为1，即可打印所有子集。
实现：
#include <iostream>
using namespace std;
int main()
{
int dCapitalLetterNum=3;
char caCapitalLetter[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for(int i=1;i<1<<dCapitalLetterNum;++i)
{
for(int j=0;j<dCapitalLetterNum;++j)
{
if(i>>j&0x1)
cout<<caCapitalLetter[j];
}
cout<<endl;
}
//输出空集
cout<<"空集"<<endl;
}输出结果：
A
B
AB
C
AC
BC
ABC
空集如果想打印26的大写字母的所有子集，只需要将dCapitalLetterNum改为26即可。
参考文献
[1]编程之法：面试和算法心得
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年05月24日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录