国内实习996,怎么安排时间准备秋招?

一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

瞄准秋招
跟Shawn一起刷算法题

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code: 20%off 打八折

深入浅出AB Test
从入门到精通
coupon code: 20%off 打八折
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 326|回复: 12
收起左侧

[数组] 问一道题的follow up

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
wst1234 发表于 2019-5-16 07:50:44 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
最近面试onsite 被 问道了 一道题,

首先原题是这样的, 一个数组,里面只有只有0和1,把0排到前面去,{1,0,1,1,0, 1} ->{0,0,1,1,1}
这道题第一问很简单,
方法1:统计0 的个数
方法2: 双指针法,

方法2的代码:

void sort(int[] A) {
        int left = 0, right = A.length - 1;
        while( left < right) {
                while(left < right && A[left] == 0) {
                        left++;
                }
                while(left < right && A[right] == 1) {
                        right--;
                }
                if(left < right) {
                        int tmp = A[left];
                        A[left] = A[right];
                        A[right] = tmp;
                        left++;
                        right--;
                }
        }
}
               
我当时写了方法二的代码,follow up 是 如果 数组是类似{1,0,1,0,0, X, X, X, X } 这样,X代表其他的未知数(不为0或1), 如何修改代码?
大家来讨论下
       

评分

参与人数 1大米 +5 收起 理由
14417335 + 5

查看全部评分


上一篇:大家有没有推荐的效果非常好的中文网络课堂,交钱的也可以啊
下一篇:【面试新题】绝妙的二分查找题,一定要练习一下
我的人缘0
bobli1993 发表于 2019-5-16 11:29:59 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (19)
 
 
0% (0)    👎
这个有点像DNF问题啊,参考:https://en.wikipedia.org/wiki/Dutch_national_flag_problem
把所有非0,1的元素当做一种元素,排在末尾就好?
回复

使用道具 举报

我的人缘0
nlx 发表于 2019-5-16 11:35:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (69)
 
 
1% (1)    👎
是要求XXX这些字符排在0和1中间?要不要保证XXX本身的次序?
回复

使用道具 举报

我的人缘0
609064231 发表于 2019-5-16 12:24:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   63% (84)
 
 
36% (49)    👎
这不就是283吗
回复

使用道具 举报

我的人缘0
渣渣程序员 发表于 2019-5-16 13:27:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (128)
 
 
10% (15)    👎
我最近也被问到了。。。当初有点卡壳,太惨了。
最简单的办法就是用两个指针从end开始往前遍历,先把非0的元素都填上。指针1到起点以后,把指针2之前的所有数字都填0。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (34)
 
 
0% (0)    👎
283 从后面开始扫
回复

使用道具 举报

我的人缘0
 楼主| wst1234 发表于 2019-5-17 04:04:36 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
zoey59 发表于 2019-5-16 15:47
283 从后面开始扫

不是283,我可能没说清楚,  最后输出要是 {0,0,0,,x,x, x,x ,1, 1} 这样的
回复

使用道具 举报

我的人缘0
 楼主| wst1234 发表于 2019-5-17 04:04:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎

不是283,我可能没说清楚,  最后输出要是 {0,0,0,,x,x, x,x ,1, 1} 这样的
回复

使用道具 举报

我的人缘0
 楼主| wst1234 发表于 2019-5-17 04:05:44 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
nlx 发表于 2019-5-16 11:35
是要求XXX这些字符排在0和1中间?要不要保证XXX本身的次序?

对的, xxxx在中间,顺序没关系
回复

使用道具 举报

我的人缘0
 楼主| wst1234 发表于 2019-5-17 04:08:50 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
渣渣程序员 发表于 2019-5-16 13:27
我最近也被问到了。。。当初有点卡壳,太惨了。
最简单的办法就是用两个指针从end开始往前遍历,先把非0的 ...

我当时第一反应也是283 move zeros那道题, 但不是那样的, 最后输出要是 {0,0,0,x,x, x,x ,1, 1} 这样的,
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-5-27 16:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表