一亩三分地论坛

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

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

狗家新鲜面经

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

2016(10-12月) 码农类 博士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
热乎乎的面经 赞人品 求onsite!给一个整数,求大于这个数的最小回文数。

一开始没想到最优解,先让我写了一个暴力解,然后我直接问了是不是还有更优解才告诉我有。剩下的时间写了最优解跑了一个例子就结束了。。。



本帖被以下淘专辑推荐:

rcholic 发表于 2016-10-28 07:21:55 | 显示全部楼层
感觉就是一个reverse() 函数,然后比较结果和输入是否一样,从给的整数不断的加1算吧?
回复 支持 反对

使用道具 举报

工图新一 发表于 2016-10-28 07:22:13 | 显示全部楼层
这个是不是将这个数的前半部分翻转一下替换后半部分,另外注意一下digit数目的奇偶
回复 支持 反对

使用道具 举报

工图新一 发表于 2016-10-28 07:28:38 | 显示全部楼层
工图新一 发表于 2016-10-28 07:22
这个是不是将这个数的前半部分翻转一下替换后半部分,另外注意一下digit数目的奇偶
.1point3acres缃
好像不对,还需要考虑翻转后的部分要大于原来的后半部分,在前半部分 + 1
回复 支持 反对

使用道具 举报

rcholic 发表于 2016-10-28 07:33:02 | 显示全部楼层
这个解法对不对? 好像太慢了?

  1. public int minPalindrome(int num) {
  2.         int n = num;

  3.         while (true) {
  4.             if (n == reverse(n)) {
  5.                 return n;
  6.             }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.             n++;
  8.         }. visit 1point3acres.com for more.
  9.     }

  10.     private int reverse(int num) {

  11.         int reverse = 0;
  12.         while (num > 0) {
  13.             reverse = reverse * 10 + num % 10;
  14.             num /= 10;
  15.         }. From 1point 3acres bbs

  16.         return reverse;
  17.     }
复制代码
回复 支持 反对

使用道具 举报

rcholic 发表于 2016-10-28 07:35:26 | 显示全部楼层
工图新一 发表于 2016-10-28 07:28.1point3acres缃
好像不对,还需要考虑翻转后的部分要大于原来的后半部分,在前半部分 + 1

这个不对吧? 比如12,你翻转成121?但是最小回文数是22啊
回复 支持 反对

使用道具 举报

yydcool 发表于 2016-10-28 07:39:38 | 显示全部楼层
从中间往两边找到第一个不相等的数
回复 支持 反对

使用道具 举报

huai10 发表于 2016-10-28 07:41:12 | 显示全部楼层
http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/
真是看都不想看
回复 支持 反对

使用道具 举报

工图新一 发表于 2016-10-28 07:43:28 | 显示全部楼层
rcholic 发表于 2016-10-28 07:35
这个不对吧? 比如12,你翻转成121?但是最小回文数是22啊

12 前半部分是1,1翻转成1, 小于2,所以前半部分++,变成2,然后前半部分(2) + 翻转后的前半部分(2) 结果是22.
回复 支持 反对

使用道具 举报

 楼主| peteraristo 发表于 2016-10-28 07:43:49 | 显示全部楼层
那个链接给的解法是对的
回复 支持 反对

使用道具 举报

 楼主| peteraristo 发表于 2016-10-28 07:47:27 | 显示全部楼层
大家太活跃了,大概就是@工图新一 说的解法 才用了6分钟。。。
回复 支持 反对

使用道具 举报

 楼主| peteraristo 发表于 2016-10-28 07:50:37 | 显示全部楼层
悲剧了,发现写错了,没有考虑到999这种会进位的情况。
回复 支持 反对

使用道具 举报

工图新一 发表于 2016-10-28 07:51:03 | 显示全部楼层
  1. public int minPalindrom(int number) {
  2.         String numStr = String.valueOf(number);.1point3acres缃
  3.         int len = numStr.length();
  4.         String prefix = numStr.substring(0, len / 2);
  5.         String reversedPrefix = new StringBuilder(prefix).reverse().toString();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.         if (len % 2 == 0) {. visit 1point3acres.com for more.
  7.             if (reversedPrefix.equals(numStr.substring(len / 2))) return number;
  8.             if (Integer.valueOf(reversedPrefix) > Integer.valueOf(numStr.substring(len / 2))) {
  9.                 return Integer.valueOf(prefix + reversedPrefix);
  10.             } else {
  11.                 String updatedPrefix = generateNextString(prefix);
  12.                 String updatedReversePrefix = new StringBuilder(updatedPrefix).reverse().toString();. 1point3acres.com/bbs
  13.                 return Integer.valueOf(updatedPrefix + updatedReversePrefix);
  14.             }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  15.         } else {
  16.             if (reversedPrefix.equals(numStr.substring(len / 2 + 1))) return number;
  17.             char midChar = numStr.charAt(len / 2);
  18.             if (Integer.valueOf(reversedPrefix) > Integer.valueOf(numStr.substring(len / 2 + 1))) {. from: 1point3acres.com/bbs
  19.                 return Integer.valueOf(prefix + midChar + reversedPrefix);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.             } else {
  21.                 String updatedPrefix = generateNextString(prefix + midChar);
  22.                 String updatedReversePrefix = new StringBuilder(updatedPrefix.substring(0, updatedPrefix.length() - 1)).reverse().toString();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.                 return Integer.valueOf(updatedPrefix + updatedReversePrefix);. 1point3acres.com/bbs
  24.             }
  25.         }
  26.     }
  27.     private String generateNextString(String s) {. 鍥磋鎴戜滑@1point 3 acres
  28.         Integer num = Integer.valueOf(s) + 1;
  29.         return String.valueOf(num);
  30.     }
复制代码
回复 支持 反对

使用道具 举报

工图新一 发表于 2016-10-28 07:57:33 | 显示全部楼层

写错了一种case,1221输出的不是1221,而是下一个palindrom
回复 支持 反对

使用道具 举报

 楼主| peteraristo 发表于 2016-10-28 08:17:52 | 显示全部楼层
工图新一 发表于 2016-10-28 07:57
写错了一种case,1221输出的不是1221,而是下一个palindrom
. more info on 1point3acres.com
1221应该输出1331
回复 支持 反对

使用道具 举报

工图新一 发表于 2016-10-28 09:04:28 | 显示全部楼层
.鏈枃鍘熷垱鑷1point3acres璁哄潧
嗯,直接将第7行和16行删掉就OK了
回复 支持 反对

使用道具 举报

oldwhite 发表于 2016-10-28 09:36:53 | 显示全部楼层
二分法做吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 01:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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