头像

我要出去乱说

百度 - 网盘技术部




离线:4小时前


最近来访(1875)
用户头像
吊车尾92
用户头像
不拿周赛牌不改名
用户头像
gjt
用户头像
Booming
用户头像
HAMRUS
用户头像
小灰灰我是
用户头像
差不多AC
用户头像
规则
用户头像
初恋的感觉
用户头像
忘打周赛Duck
用户头像
Fluent
用户头像
jxj777
用户头像
sunchenxi
用户头像
jieHeEternity
用户头像
罗小呆
用户头像
爱吃土豆雷
用户头像
有情人终成兄妹
用户头像
1357649762
用户头像
majoege
用户头像
ryangee


一直都很忙,从除夕夜到初二,断断续续整理了一些可能有用的信息发出来给大家参考看看。目前我的状况是:入职六个月,已转正。

一、半年来的工作感受

  • 我是百度网盘这边的后端,平时迭代开发非常忙,一个迭代差不多一个月,当前迭代的活儿还没干完,下个迭代的活儿就给你分好了,节奏紧,经常需要跨团队合作,工作压力很大;

  • 我们是纯业务开发,写代码主要还是用if语句和for循环,用不上什么算法,项目的主要时间花在设计评审、业务理解以及各方沟通协调上,实际研发写代码的时间占比不高;

  • 在做一个较大的需求前,要先做技术评审。类似答辩那种,先自己拟订一个设计方案,然后拉会议室请组内大佬过来,讲出你的方案,让大佬们提意见。这个环节是真能学到东西的,每人每个季度至少做一次技术评审。

二、工作时间

  1. 稳定在1095,虽然我自己也经常加班超过9点,但9点是真的可以走了,没人会说你啥;

  2. 周末双休,但你的活儿没干完,周末还是得自己在家里加班。前三个月我周末还到处去走走玩玩,后三个月开始上手干活,基本上每个周末我都要带电脑回去加个班;

三、研发流程

我不确定其他厂的研发规范,但百度是非常严格的,比如我需要对一个接口做修改,以下是一个标准的研发流程:

  1. 先建立研发卡片,卡片中写清楚研发内容、研发&测试负责人、研发起止时间、所需工时等信息;

  2. 从代码库master中拉新分支,绑定到卡片;

  3. 在容器或开发机中完成开发后提交代码,提交后流水线会自动跑一组代码检查(代码是否符合百度内部规范、增量行单测覆盖率是否达到70%等等);

  4. 通过机器检查后再请人做Code Review代码评审,一般会请对该模块比较了解的人,或你的导师来评审;

  5. 若评审不通过,打回后修改完继续提交评审,直至通过;

  6. QA(测试)提测,若改动较小,可以选择自测;

  7. 分级发布上线,同时做回归测试。

四、薪资

  • 关于在北京,每月24k究竟能到手多少,工资单想了想还是不放图了。最近三个月到手都是18500左右,也就是打了77折,不同base的同学可以参考个人所得税计算器 ,个税是累计的,越到年终扣得越多。百度补贴只有两种:午餐补贴(20 * 出勤天数)+ 通讯补贴(每月最多可报销50话费);

  • 公积金交得比较多,每月缴存5866元公积金,每月可以提1500,我跟同事都一直提的,好像公积金余额太多了也没用?

五、福利

  • 新人每年12天年假,这次春节我请了前三后二,一共12天假,几个老员工请了前五后二,一共14天假,感觉也够了;

  • 免费早餐九点半截止,免费晚餐晚上八点后开始,免费打车晚上10点后开始(十点难打到车,可能要等半个小时以上)。

六、想吐槽的的点

  1. 百度的代码审核非常严格,严格到病态的程度,每次提交代码都会经过流水线检查,少打一个空格,每行超过160字符、注释写得不规范、单测覆盖率不足等等情况,都会直接打回让你重改。而且流水线运行比较慢,每次提交完可能要等上20分钟才知道结果;

  2. 单元测试比较恶心人,经常是改了两三行代码,写一天的单测。因为很多老代码是没有单元测试的,但这些代码库现在都开启了单元测试检查。只要你改动了这些代码,就需要为它写一个新的单测,我曾经为一个单元测试折腾了两天,很痛苦,不想再碰老代码。上个月同事改了老代码一个方法(150行)的最后几行,为了达成覆盖率指标,需要为整个方法构造单元测试,活活折腾了一天。
    在实际研发过程中,这些指标会让你觉得太过形式化,不仅没有提效,反而还降低了研发效率。但如果没有这些指标限制,代码可能会加速腐化变质,或许这本就是一条难走的路,要忍着痛走下去;

  3. 百度内部不使用gin、gorm、docker、mq等开源框架或技术,全是自研的。出去面试可能会啥也不知道。基础架构很完善,但不一定好用;

七、其他零碎的东西

  • 后端地位并不是最高的,感觉fe(前端)na(ios与安卓客户端)pm(产品)都在催你干活;

  • 所有人都带着耳机,一边听歌一边写代码;

  • 周末节假日加班没有多倍工资,最多只有调休,需要申请,离职前需要强制把年假休完;

  • 除了我这种纯业务开发的部门,还有一种叫基础架构的部门,就是做公司内部工具的研发,用来提升研发效率的。这种部门就纯做技术,不用太关心业务,对技术细节钻得比较深;

  • 内部大家都少用百度搜索,内网自带梯子,大家谷歌用得比较多;

  • 组内每次有面试都会记录下来放到团队知识库里边,看了近两个月的面试,算法题感觉不难,问得最多的是反转链表,八股也都是老八股。tcp、http那一套,算法题的面试记录会像下面这样:

2810.png
代码规范有很多,最基础的比如命名要有意义,不要直接abc这样,还有适当的空格与缩进,不要把代码写成一坨。

  • 百度的工位很大,每个人还有个储物柜,但刚来可能会被安排到临时工位待几个月(我是坐了三个月临时工位才搬到正式工位的),工位图如下:
    工位.jpeg

八、一些常被提到的问题

1. 百度是否已经没落,职场PUA,新人背绩效,试用期劝退等,还值得去吗?
  • 能感觉到PUA,可能职场或多或少都会有点吧,我因为工作有一些纰漏,试用期答辩后,主管直接约我谈话,数落我一通,压力真的拉满;

  • 我现在还不知道绩效情况,可能要等三月份发年终的时候才知道了,到时候评论区我再补充吧;

  • 脉脉上经常看到有说试用期劝退的,目前我自己还没听说身边有这种情况,我们组6个校招生试用期全过了,我答辩被喷很惨,但也过了。我知道的说法是:新人首先应该是内部转岗,不会直接劝退裁员;

  • 大的方向我也不好说,进来的话技术肯定是能学到的,高工都很厉害。来之前我也经常刷脉脉,全是说不要来百度,快跑之类的,确实很吓人,现在来了半年,感觉没有外界传的那么差,还是可以呆的。如果没有更好的offer可以来,技术这块应该是要强一点吧。

2. 现在去百度要写PHP吗?会不会太过时了?
  • 不会,现在只有很老很老的代码库才保持用PHP了,能重构的都用Go语言重构了,企业网盘这边全是用Go语言开发的。新入职的几个校招生只有一个同学被安排去改一点点PHP代码,但占比很少,大家主要还是用Go开发。
3. 百度的新人培养机制如何?
  • 内部有各种培训课程(线上或线下),感觉干货较少,我也不指望从中学到太多东西了;

  • 最关键的是mentor(导师),新人试用期6个月,期间会分一个mentor指导你,有的mentor很细心负责,有的就不闻不问,差别比较大。不过只要你够主动,平时多问,mentor也会耐心给你解答。我入职三个月导师就跑路去国企了,中途换了个导师,新导师很忙也没时间管我,总之还是得自己主动问吧,有问题不要一直憋着就行。




突然想开贴记录下程序员上班的生活是怎样的,在百度上班是什么感觉。只要我还在😂就不定期更新吧。下图是北京的百度大厦,也是我上班的地方。

百度大厦.jpg

第一个月

入职培训

入职现场.jpg

  • 第一天入职报道,每人会发一台13英寸的macbook pro,M1芯片,16G内存,已经预装了百度监控套件,所以我到现在为止,都没有在这台mac上装微信等社交软件(现在已经全装了/doge);

  • 入职培训时会教你怎么配置mac,还说了很多注意事项及公司福利等等;

  • 给研发人员配的显示器是惠普E24 G4,23.8寸,1080p,均价1498;

  • 每个新人会有一个指定的导师mentor带,帮助你度过六个月的试用期(不同导师风格差别很大,有的会事无巨细地教你,我导师之前就带着我一个一个认git命令。有的就默认你全会了或者看看文档就能理解,这时候你就得多主动问,没有见过特别push或者态度不好的导师)。

新人培养

  • 百度自诩为互联网的黄埔军校,呃。。。个人感觉一般吧,新人培养大致可以分为:公司级培养、事业群级培养和团队内部培养,说实话前两个都没啥用;

  • 公司级培养:各种新人必修课,包括一些线下活动,主要是为了给你灌输企业文化;

  • 我所在的事业群是ACG,也就是百度智能云群组,培养:各种在线视频课程,考试(百度军规、职业道德与行为规范等),我已经不指望从以上两种培训中学到啥东西了;

  • 团队内部培养:mentor、试用期每天写日报(转正后只需要写周报)、新人第一个月模块串讲等等,其实你的成长很大程度上取决于你的mentor

工作氛围

  • 首先是轻松,问了好几个新入职的同事(包括其他部门的),他们原本有更好的offer(字节、华为、拼多多等),待遇都比百度好,最后选了百度是因为不那么累;

  • 1095工作制,我们团队晚上八点半开始陆续走人,10点应该没啥人了,反正我从没待到过晚上10点;

  • 节奏很慢,上了一个月班,我就只在第四周的时候写了一个简单的接口,一百来行代码,大部分还是复制粘贴的哈哈;

  • 每周要开一个半小时的周会,每个人轮流讲自己这周做了什么、遇到哪些困难、如何解决、需要什么帮助等。我们新人没啥工作,就几句话带过了;

  • 同事都挺不错的,我遇到问题时都他们很有耐心地给我讲解,倒是我自己经常做出一些令人窒息的操作😅比如直接把代码push到master分支上(其实是push不上去的,但是操作会被别人看到);

  • 百度的L字型工位挺大的,每个工位上还有一个储物柜,但由于工位紧缺,我们这批新入职的只能坐临时工位了,就是下图这样:

临时工位2.jpg

工作内容

  • 第一个月主要是参加各种新人培训和看文档,了解团队在做什么东西。每个人分了一个模块来学习,梳理模块代码逻辑、画流程图、制作PPT,每个新人第一个月都要串讲自己负责的模块,有点像答辩,讲半小时,团队所有人在一边听着,中间会穿插一些问题。但不会很难,都知道我们是新人,啥也不懂哈哈;

  • 月末的时候我开始做一个简单的需求,就是写一个内部接口,更新一下转存文件的状态,我直接把另一个类似的接口复制过来,改改参数再加一个if判断就行了,很简单。我们全是用go语言来写代码,但不会用gin等开源框架,使用的框架都是公司内部自研的(有的好用、有的很难用),就连IDE都是自研的(在VSCode基础上开发的IDE);

  • 就目前来看,写代码本身不难,要实现的逻辑都很简单,难的是写代码之外的部分:

    1. 编码前要跟相关人员沟通,确定设计方案(比如接口要实现什么功能,达到什么样的效果,提供给谁来用,约定好入参出参等),再编写设计文档(需求背景、设计方案、入参出参、接口流程图等);
    2. 编码时要遵循公司各种规范(命名规范、代码注释规范等);
    3. 编码完成后还要跑沙盒环境、编写测试用例、让导师评审、让测试人员提测,最后一步才是上线。

食堂

  • 百度在北京有很多个办公区:百度科技园(最大)、百度大厦(通勤最方便)、甲骨文大厦(百度租了一部分)、奎科大厦、鹏寰大厦,不同工区的食堂区别还挺大,我是在百度大厦,个人感觉挺一般,吃一个月已经是吃腻了,饭菜一般是下图的风格(食堂不便宜,下面两餐分别是26和28,最便宜的一碗面要14):

正餐1.jpg

正餐2.jpg

  • 百度每天有20块钱的饭补,一个月差不多就是400块钱。每天的早餐免费(9:30关闭),早餐品类很少,如下图,每天晚上8点后晚餐免费(我从没去吃过,太饿了等不了);

早餐.jpg

  • 每天下午工位旁边会放水果,每人可以拿一个,也可以不拿,通常是:苹果、梨子、香蕉、一小盒李子、一小盒酸奶轮着来。

生活方面

  • 我住的地方离公司2公里,每天骑共享单车通勤需要15分钟,房租3000一月,两户合租。问了一圈同事,大家租的房都是2400~3500不等,想要一居室的整租起码得5000,百度是没有房补的;

  • 北京真是啥都有,我每个周末都会一个人出去走走看看:吃东西探店(叙利亚餐厅、印度餐厅、北京的百年老店等等)、体验barbershop、去北京电影节。后面还想去体验一下徒步、射箭、攀岩等等运动。


后面的等三个月、六个月的时候再写吧,可能会推翻我之前说的一些东西嘿嘿。




上班一个月,发现自己git用得一团乱,打算好好记录一下常用的git操作。

一、创建版本库

1. 配置git环境

  • git 安装好以后,需要配置环境变量,命令行中输入以下命令:
git config --global user.name "Your Name"
git config --global user.email "email@example.com"
  • git config --list:查看当前的git配置;

  • 配置好环境后,使用命令 git init,即可将当前目录变成一个git可以管理的仓库;

  • git顺序:工作区 - - add - -> 暂存区 - - commit - -> 版本库 - - push - -> 远程版本库。

二、时光机穿梭

1. 版本回退

  • git status:查看仓库的当前状态;

  • git diff:查看上次修改的内容;

  • git log:显示所有提交日志,可以增加--pretty=oneline参数减少输出,可以使用--graph --pretty=oneline --abbrev-commit参数使输出更加直观;

  • git reset --hard HEAD^:回退到上一版本,在git中,HEAD表示当前版本,HEAD^表示上一版本,HEAD^^表示上上版本,HEAD~10表示往前第10个版本;

  • git reset --hard <commit_id>:回退到指定的commit id版本,commit id可以不用输完整,输前几位就能找到;

  • git reflog:查看历史命令,可以用来找回commit id

2. 撤销修改

  • git restore <file_name>:撤销对文件的修改(工作区);

  • git restore --staged <file_name>:撤销已经 git add 放到暂存区的文件;

  • git reset --hard HEAD^:撤销已经git commit到版本库的修改,即回退到上一版本。--hard表示之前的修改直接丢掉,--mixed(default)表示之前的修改保留在工作区,--soft表示之前的修改保留在暂存区。

3. 删除文件

  • git rm <file_name>:删除版本库中的文件,需要再使用git commit提交删除到版本库;

  • 若删除了工作区的文件,想从版本库中恢复到工作区,可以使用git restore <file_name>

三、分支管理

1. 创建与合并分支

  • git checkout -b dev-b参数表示创建并切换到dev分支,该命令同git switch -c dev

  • git merge dev:合并dev分支到当前分支;

  • git merge --no-ff dev:合并但禁用快速合并(推荐),因为dev分支上可能会有很多零碎的提交,这种方式能够避免搅乱master的提交历史;

  • git branch -d dev:删除dev分支,参数-D表示强制删除,用来删除还未合并的分支。

2. 解决冲突

  • 若合并时存在冲突,使用git status查看冲突文件;

  • 然后手动编辑文件解决冲突。

3. Bug分支

  • 修复Bug时,通常我们会创建新的Bug分支进行修复,然后合并,最后删除;

  • 当手头工作没有完成,需要先把工作现场git stash储藏起来,改完Bug后再用git stash pop还原工作现场,可以使用git stash list查看储藏列表;

  • master分支上修复的Bug,可以通过git cherry-pick <commit_id>复制到当前分支。

4. 多人协作

  • git remote -v:查看远程分支详细信息;

  • git push origin <branch_name>:推送到远程指定的分支上;

  • git checkout -b dev origin/dev:创建远程的dev分支到本地;

  • git pull:从远程获取最新版本并merge到本地,会自动合并或修改当前的工作;

  • git fetch:从远程拉取到本地仓库,不会自动合并或修改当前的工作。

  • git branch --set-upstream-to=origin/dev dev:设置dev分支与远程origin/dev分支的链接,链接完成后,在dev分支中git pull就会直接从origin/dev上拉取了。

  • dev分支上执行git rebase master:若此时master上有新的提交,则用master上的新提交来作为dev的新基底,若master上没有新提交,则类似于进行了merge操作。一般公司里会禁用rebase,统一使用merge,因为rebase会整合分支提交记录,不清楚主线上谁合了代码以及他们合代码的先后顺序。注意:总的原则是,只对尚未推送或分享给别人的本地修改执行变基操作清理历史, 从不对已推送至别处的提交执行变基操作。

参考文献

廖雪峰的官方网站
Git Book




1、思路

  • 在动态规划中,我们用nums[i]来代表i个节点的搜索二叉树有多少种可能;

  • 假设一棵二叉搜索树有i个节点,若以j (1 <= j <= i)作为头节点,那么i的左子树有i - 1个节点,右子树有i - j个节点。故以i为头节点的可能结构有nums[i - 1] * nums[i - j]种。

2、代码

#include <iostream>
#include <vector>

using namespace std;

int numTrees(int n)
{
    if (n < 2)
    {
        return 1;
    }

    vector<long long> nums(n + 1, 0);
    nums[0] = 1;                        //初始化 0 个节点有 1 中可能结构

    for (int i = 1; i <= n; ++ i)       //二叉搜索树有 i 个节点
    {
        for (int j = 1; j <= i; ++ j)   //以 j 为头节点
        {
            nums[i] = ((nums[j - 1] * nums[i - j] % 1000000007) + nums[i]) % 1000000007;
        }
    }

    return nums[n];
}

int main()
{
    int n;
    cin >> n;

    cout << numTrees(n) << endl;

    return 0;
}



1、思路

  • 思路与上一题【程序员面试金典 8.7:无重复字符串的排列组合(DFS)】基本一致 ,只不过在DFS处理全排列的过程中(for循环内)需要用一个Set集合来存放已经交换过的重复元素,即不让当前的S[i]与一个等值的已经交换过的字母再进行交换;

  • 例如:对qqe操作,只会将第一个qe进行交换,不会将第二个qe交换。

2、代码

class Solution {
public:
    void dfs(vector<string>& res, string& S, int i)
    {
        if (i == S.length())
        {
            res.push_back(S);
            return;
        }

        set<char> hash;                         //注意哈希表要在循环前创建

        for (int j = i; j < S.length(); ++ j)
        {
            if (hash.find(S[j]) == hash.end())  //对集合内不存在的字母才进行递归
            {
                hash.insert(S[j]);              //当前元素插入集合中

                swap(S[i], S[j]);       
                dfs(res, S, i + 1);
                swap(S[i], S[j]);
            }
        }
    }

    vector<string> permutation(string S) {
        vector<string> res;

        dfs(res, S, 0);

        return res;
    }
};



1、思路

  • 多叉树问题,每名员工有若干个直接下级员工,除老板外,每名员工都有唯一的直接上级;

  • 某一级节点来不来参加派对,要看这级节点来还是不来两种情况下,哪一种获得的收益最多,分两种情况:

    1、当前节点来参加派对收的益 = 当前节点的快乐值 + 其所有子节点不来参加派对的收益之和(注意:子节点不来参加派对的收益不一定为0,因为它的孙子节点可能来参加,这种情况要递归计算);

    2、当前节点不来参加派对的收益 = max(子节点来参加派对的收益, 子节点不来参加派对的收益)。

2、代码

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode
{
    int happy;
    vector<TreeNode*> employees;

    TreeNode(int _happy) : happy(_happy) {}
};

struct ReturnData
{
    int yes;        //该员工来参加派对的收益
    int no;         //该员工不来参加派对的收益

    ReturnData(int _yes, int _no) : yes(_yes), no(_no) {}
};

ReturnData* getMax(TreeNode *node)
{
    int yesNode = node->happy;      //该员工来参加派对的收益就是他本身的快乐值
    int noNode = 0;                 //不来参加,收益先初始化为 0

    if (node->employees.empty())
    {
        return new ReturnData(yesNode, noNode);
    }
    else                            //若子树不为空,继续递归计算子员工来与不来的收益
    {
        for (auto employee : node->employees)
        {
            ReturnData *subTreeInfo = getMax(employee);
            yesNode += subTreeInfo->no;
            noNode += max(subTreeInfo->yes, subTreeInfo->no);
        }
    }

    return new ReturnData(yesNode, noNode);
}

int main()
{
    int n, root;
    cin >> n >> root;

    int happyVal, boss, employee;
    vector<TreeNode*> happy(n + 1);

    for (int i = 1; i <= n; ++ i)   //一共有 n 个员工,下标从 1 开始
    {
        cin >> happyVal;
        happy[i] = new TreeNode(happyVal);
    }

    for (int i = 2; i <= n; ++ i)   //除老板外一共有 n - 1 个员工,下标从 2 开始
    {
        cin >> boss >> employee;
        happy[boss]->employees.push_back(happy[employee]);
    }

    ReturnData *allTreeInfo = getMax(happy[root]);          //从根节点的老板开始
    cout << max(allTreeInfo->yes, allTreeInfo->no) << endl;

    return 0;
}



1、思路

  • 这道题通常做法是开一个bool类型的状态数组,标记每个字母是否使用过;

  • 仔细观察可以发现,求不同全排列的问题其实是可以利用交换字符串元素来完成的;

  • 若字符串长度为n,将第一个字母分别与后面每一个字母进行交换,生成n种不同的全排列;再用第二个元素与后面每一个元素进行交换,生成n - 1种不同的全排列……

2、代码

class Solution {
public:
    void dfs(vector<string>& res, string& S, int i)
    {
        if (i == S.length())
        {
            res.push_back(S);
        }
        else
        {
            //注意 j 的下标从 i 开始,因为原排列也是一种排列
            for (int j = i; j < S.length(); ++ j)
            {
                swap(S[i], S[j]);       //交换字母
                dfs(res, S, i + 1);
                swap(S[i], S[j]);       //还原
            }
        }
    }

    vector<string> permutation(string S) {
        vector<string> res;

        dfs(res, S, 0);

        return res;
    }
};



1、思路

  • A柱中的前n - 1个盘子与最后第n个盘子看成两部分,进行如下操作:

    1、将A柱中的前n - 1个盘子移动到柱B

    2、A柱中最后一个盘子移动到柱C

    3、B柱中所有的n - 1个盘子移动到柱C

  • 上述的第1步与第3步可以继续递归地分解,直到n == 1时再移动数组内元素;

  • 注意在实际的递归过程中,就是在调用moveDisks方法时,数组内元素是没有移动的,我们只是把递归的次数想象成移动的次数,当递归到最后一层,即柱中盘子只剩一个时,才真正移动数组中的元素。

2、代码

class Solution {
public:
    void moveDisks(int n, vector<int>& A, vector<int>& B, vector<int>& C)
    {
        if (n == 1)                 // n == 1 时才真正移动数组元素
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        moveDisks(n - 1, A, C, B);  //将 n - 1 个盘子从 A 通过 C 移动到 B
        C.push_back(A.back());      //此时 A 中只剩一个盘子,将其移动到 C
        A.pop_back();
        moveDisks(n - 1, B, A, C);  //将 n - 1 个盘子从 B 通过 A 移动到 C
    }

    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();           // n 个盘子
        moveDisks(n, A, B, C);      //将 n 个盘子从 A 通过 B 移动到 C
    }
};

3、错误的解法

class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        while (A.size() > 1)            //将 A 中的 n - 1 个盘子移动到缓冲区 B 中
        {
            B.push_back(A.back());
            A.pop_back();
        }

        C.push_back(A.back());          //最后一个盘子放到 C 中
        A.pop_back();

        while (!B.empty())              //缓冲区中所有盘子移动到 C 中
        {
            C.push_back(B.back());
            B.pop_back();
        }
    }
};

用以上代码也能通过该题,但违反了题意,因为我们不能直接取到最底部的盘子。




1、思路

  • 先找出两个数中较大的数big和较小的数 smallhelper()方法的作用是计算bigsmall的乘积,我们用一个变量halfProd来保存bigsmall乘积的一半;

  • small为偶数,则直接将halfProd加倍返回即可,若small为奇数,则在halfProd加倍的基础上再返回一个big

  • 每次递归相当于将small除以2,同时将big乘以2

  • 时间复杂度为 $O(s)$ , $s$ 表示两个数中较小的那个。

2、代码

class Solution {
public:
    int helper(int small, int big)
    {
        if (small == 0) return 0;           //递归返回的两种情况
        else if (small == 1) return big;

        int s = small >> 1;
        int halfProd = helper(s, big);

        if (small % 2 == 0)
        {
            return halfProd + halfProd;
        }
        else
        {
            return halfProd + halfProd + big;
        }
    }

    int multiply(int A, int B) {
        int big = A > B ? A : B;            //先找出较大和较小的数
        int small = A > B ? B : A;

        return helper(small, big);
    }
};



解法一:递归

1、思路

  • 遍历数组,对于每个元素有选和不选两种情况,将每种情况都放到结果数组中即可;

  • 时间复杂度为 $O(N) ,空间复杂度为 $O(N) 。

2、代码

class Solution {
public:
    void dfs(vector<int>& nums, vector<vector<int>>& res, vector<int>& tmp, int i)
    {
        if (i == nums.size()) return;

        tmp.push_back(nums[i]);
        res.push_back(tmp);

        dfs(nums, res, tmp, i + 1);     //选择当前元素
        tmp.pop_back();
        dfs(nums, res, tmp, i + 1);     //不选当前元素
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;

        res.push_back(tmp);             //先放入一个空集
        dfs(nums, res, tmp, 0);

        return res;
    }
};

解法二:迭代

1、思路

  • 因为每个元素有选和不选两种情况,所以长度为 $n$ 的数组,其子集个数有 $2^n$ 个;

  • 构造所有子集就等同于构造所有的二进制数,迭代访问从 $1$ 到 $2^n$ 的所有数字,再将这些数字的二进制表示转换成集合即可;

  • 时间复杂度为 $O(N) ,空间复杂度为 $O(N) 。

2、代码

class Solution {
public:
    vector<int> convertIntToVector(vector<int>& nums, int i)
    {
        vector<int> subset;
        int idx = 0;

        // 遍历数字 i 的二进制位,若为 1 表示选择当前元素
        for (int j = i; j > 0; j >>= 1)
        {
            if ((j & 1) == 1)
            {
                subset.push_back(nums[idx]);
            }

            ++ idx;
        }

        return subset;
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        int max = 1 << nums.size();         //一共有 2^n 个子集

        for (int i = 0; i < max; ++ i)
        {
            res.push_back(convertIntToVector(nums, i));
        }

        return res;
    }
};