一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1356|回复: 13
收起左侧

狗家店面结束了

[复制链接] |试试Instant~ |关注本帖
freshbaby_77 发表于 2016-11-2 07:10:58 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
地里第一帖贡献给了狗家, 下午刚刚面完,烙印面试官判断等差数列。。数组壹:{[size=13.3333px]7 4 2 2}. From 1point 3acres bbs
数组贰:
[size=13.3333px]2 3
1 4
[size=13.3333px]3 4
输出:
[size=13.3333px]Y
[size=13.3333px]N
Y题目很简单但是我道行太浅没反应过来直接暴力O(mn)解决。。
老银说O(m+n)可以解决。。捂脸继续刷题吧。。


补充内容 (2016-11-2 12:14):
数组壹:{7,4,2,2}. more info on 1point3acres.com
数组贰:{{2,3},{1,4}, {3,4}}代表数组壹的index
输出就是判断结果: Y, N, Y

评分

1

查看全部评分

本帖被以下淘专辑推荐:

cezheng2 发表于 2016-11-2 18:47:06 | 显示全部楼层
用dp做存下到每个index结束的最长等差数列的起点。O(m+n)
  1. vector<bool> IsCommonDiffSubarrays(const vector<int>& nums, const vector<pair<int,int>>& ranges) {
  2.         // start_index[i] is the starting 0-based index of common difference subarray that ends at i
  3.         vector<int> start_index(nums.size(), 0);
  4.         int start = 0, prev_diff = 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  5.         int (int i = 1; i < nums.size(); ++i) {
  6.                 int diff = nums[i] - nums[i - 1];
  7.                 start_index[i] = (diff == prev_diff) ? start_index[i - 1] : (i - 1); . From 1point 3acres bbs
  8.         }
  9.         vector<bool> result;
  10.         for (auto& range : ranges) {
  11.                 result.push_back(start_index[ranges.second - 1] < ranges.first);. 1point 3acres 璁哄潧
  12.         }
  13.         return result;
  14. }
复制代码

补充内容 (2016-11-3 12:44):
for循环结束前漏了一行 prev_diff = diff;

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

Lolipop 发表于 2016-11-15 06:17:22 | 显示全部楼层
楼主这表达能力。。。面试官听得懂么? 还是不懂题目是什么。
回复 支持 1 反对 0

使用道具 举报

wansongsong 发表于 2016-11-2 10:30:52 | 显示全部楼层
没太看懂楼主的题目啊,7 4 2 2 为啥是等差数列?
题目就是给一个数组,判断是否为等差数列么?
回复 支持 反对

使用道具 举报

guoyuezhong 发表于 2016-11-2 19:13:48 | 显示全部楼层
没有明白,为何下表1,4不是等差数列,按说如果元素个数<=2,  都会是等差数列啊
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-11-2 21:35:58 | 显示全部楼层
能在解释一下题目吗
回复 支持 反对

使用道具 举报

jacky841102 发表于 2016-11-2 22:23:56 | 显示全部楼层
多谢分享,楼主能再解释第一题多一点吗?不是很懂
回复 支持 反对

使用道具 举报

 楼主| freshbaby_77 发表于 2016-11-2 23:05:46 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

 楼主| freshbaby_77 发表于 2016-11-2 23:13:30 | 显示全部楼层
index代表序列的起始位置。。大概写了一下。。希望大神们补充。。
public static String[] isArithmetic(int[] arr, int[][] ques){
                String[] res = new String[ques.length];
                Arrays.fill(res, "N");
                if(arr.length<=1) return res;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                Map<Integer, Integer> map = new HashMap<>();
                map.put(0, Integer.MIN_VALUE);
                map.put(1, 0);
                int diff = arr[1]-arr[0];. From 1point 3acres bbs
                int index = 0;
                for(int i = 1; i < arr.length-1; i++){. 鍥磋鎴戜滑@1point 3 acres
                        if(arr[i+1]-arr[i]!=diff){. visit 1point3acres.com for more.
                                map.put(i+1, i);
                                index = i;
                                diff = arr[i+1]-arr[i];
                        }else{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                map.put(i+1, index);
                        }
                }
                for(int i = 0 ;i < ques.length; i++){
                        if(map.get(ques[i][1]-1)<=ques[i][0]-1){
                                res[i]="Y";
                        }
                        System.out.println(res[i]);
                }-google 1point3acres
               
                return res;
               
        }. 1point 3acres 璁哄潧

回复 支持 反对

使用道具 举报

ZotNerd 发表于 2016-11-12 07:13:00 | 显示全部楼层
完全没看懂题目。。。。
回复 支持 反对

使用道具 举报

 楼主| freshbaby_77 发表于 2016-11-15 06:26:51 来自手机 | 显示全部楼层
判断给定区间是不是等差数列。。第二个数组对应的是第一个数组区间的起始终止坐标。。
回复 支持 反对

使用道具 举报

 楼主| freshbaby_77 发表于 2016-11-15 06:27:39 来自手机 | 显示全部楼层
等差数列可以只有两个元素。。
回复 支持 反对

使用道具 举报

 楼主| freshbaby_77 发表于 2016-11-15 06:31:13 来自手机 | 显示全部楼层
如果是等差数列返回Y,注意坐标是1index,主贴有乱码。。可以参考补充内容。。如果还不懂就看回复的代码。。如果还不懂。。。。。。。
回复 支持 反对

使用道具 举报

primbo 发表于 4 天前 | 显示全部楼层
cezheng2 发表于 2016-11-2 18:47
用dp做存下到每个index结束的最长等差数列的起点。O(m+n)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
写的很好。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 15:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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