2018腾讯内部调岗面试试题2——打印A-Z这26个字母的所有子集

题目:有一个集合由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]编程之法:面试和算法心得

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏成猿之路

Java面试题基础篇

13160
来自专栏Vamei实验室

Java基础10 接口的继承与抽象类

在实施接口中,我们利用interface语法,将interface从类定义中独立出来,构成一个主体。interface为类提供了接口规范。 在继承中,我们为了提...

209100
来自专栏MyBlog

Effective.Java 读书笔记(11)关于clone方法

说到clone方法,我们来提一提Cloneable这个接口,这个接口是用来作为一种标记某对象允许被clone的一种混合接口,可是不幸运的是,这个接口并没能起到该...

11720
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:面向对象语法一(入门版)

16750
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:面向对象语法二(入门版)

15660
来自专栏进击的君君的前端之路

Math对象、数组、日期函数

16850
来自专栏java技术学习之道

深入理解 Java 中的 Lambda

14720
来自专栏Jimoer

java8在Collection中新增加的方法removeIf

记得我在以前找工作的经历中,遇到过一个面试官问过我一个很基础的问题。问题是:有一个List中有10个元素,我现在想从中删除3个元素,请问怎么做?我当时也没想,就...

37080
来自专栏华章科技

从Zero到Hero,一文掌握Python关键代码

首先,什么是 Python?根据 Python 创建者 Guido van Rossum 所言,Python 是一种高级编程语言,其设计的核心理念是代码的易读性...

9030
来自专栏Java面试通关手册

最最最常见的Java面试题总结-第一周

这里会分享一些出现频率极其极其高的面试题,初定周更一篇,什么时候更完什么时候停止。

10110

扫码关注云+社区

领取腾讯云代金券