l*****b
发帖数: 82 | 1 请几天面试一个梦想的公司,结果悲惨地死在了一道数学编程题.
请板上的大牛帮忙看看怎么解,这样我也好知道自己的差距在哪里.
题目是这样的, 给出任意一串数字, 找出旋转180度以后还是原来的值得数字串.
比如, 69旋转180度后还是69.
用什么算法来编出这个程序?
小弟的印象中好像没有任何算法是可以用来旋转数字的，难道要用图形来辅助？ |
L*****e
发帖数: 8347 | 2 翻转180度后，还能是valid的数字的数字有1,6,8,9,0？除了6变成9,9变成6以外，其它
的原样？
如果是这样的话，把原数字reverse一下
int rev = 0;
while (num != 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
然后后原数字比，6和9match，9和6match,其它数字和本身match。如果有1,6,8,9,0以
外的数字，返回false。。。
【在 l*****b 的大作中提到】
: 请几天面试一个梦想的公司,结果悲惨地死在了一道数学编程题.
: 请板上的大牛帮忙看看怎么解,这样我也好知道自己的差距在哪里.
: 题目是这样的, 给出任意一串数字, 找出旋转180度以后还是原来的值得数字串.
: 比如, 69旋转180度后还是69.
: 用什么算法来编出这个程序?
: 小弟的印象中好像没有任何算法是可以用来旋转数字的，难道要用图形来辅助？
|
d***a
发帖数: 13752 | 3 先找出0,1,6,8,9构成的子串，再从子串的两边开始左右匹配，1可以和1匹配，6可以和
9匹配，如此这般，左右index相逢就找到了一个解。算法复杂度是O(n^2),可能有更优
解。 |
b*******s
发帖数: 5216 | 4 就 0 1 6 8 9 需要考虑
【在 l*****b 的大作中提到】
: 请几天面试一个梦想的公司,结果悲惨地死在了一道数学编程题.
: 请板上的大牛帮忙看看怎么解,这样我也好知道自己的差距在哪里.
: 题目是这样的, 给出任意一串数字, 找出旋转180度以后还是原来的值得数字串.
: 比如, 69旋转180度后还是69.
: 用什么算法来编出这个程序?
: 小弟的印象中好像没有任何算法是可以用来旋转数字的，难道要用图形来辅助？
|
L*****e
发帖数: 8347 | 5 为啥要找子串？它是整个数字翻转？还是数字中的子串翻转？
楼主的问题好像是不知道如何把一个数字“翻转”180度。。。
【在 d***a 的大作中提到】
: 先找出0,1,6,8,9构成的子串，再从子串的两边开始左右匹配，1可以和1匹配，6可以和
: 9匹配，如此这般，左右index相逢就找到了一个解。算法复杂度是O(n^2),可能有更优
: 解。
|
b*******s
发帖数: 5216 | 6 先切分一次，以不在这个数字集合里的为边界切成一系列子串
这个复杂度O(n)
然后每个字串找回文子串，这是个经典题
唯一需要修改的是，69的处理，可以先当成一个数字，然后几种模式再检查一次
【在 l*****b 的大作中提到】
: 请几天面试一个梦想的公司,结果悲惨地死在了一道数学编程题.
: 请板上的大牛帮忙看看怎么解,这样我也好知道自己的差距在哪里.
: 题目是这样的, 给出任意一串数字, 找出旋转180度以后还是原来的值得数字串.
: 比如, 69旋转180度后还是69.
: 用什么算法来编出这个程序?
: 小弟的印象中好像没有任何算法是可以用来旋转数字的，难道要用图形来辅助？
|
L*****e
发帖数: 8347 | 7 其实都不用先reverse数字，可以对原数字每次首尾各取一个digit互相比较。至于怎么
从首尾每次各取一个digit，稍微想一下就知道了，小学数学的知识就够。。。
【在 L*****e 的大作中提到】
: 翻转180度后，还能是valid的数字的数字有1,6,8,9,0？除了6变成9,9变成6以外，其它
: 的原样？
: 如果是这样的话，把原数字reverse一下
: int rev = 0;
: while (num != 0) {
: rev = rev * 10 + num % 10;
: num /= 10;
: }
: 然后后原数字比，6和9match，9和6match,其它数字和本身match。如果有1,6,8,9,0以
: 外的数字，返回false。。。
|
b*******s
发帖数: 5216 | 8 in place的算法只是技巧问题
【在 L*****e 的大作中提到】
: 其实都不用先reverse数字，可以对原数字每次首尾各取一个digit互相比较。至于怎么
: 从首尾每次各取一个digit，稍微想一下就知道了，小学数学的知识就够。。。
|
L*****e
发帖数: 8347 | 9 楼主题目说的很模糊，这个“数字”是string啊？还是int？还是其它？然后是整个数
字转？还是部分子串转？
【在 b*******s 的大作中提到】
: 先切分一次，以不在这个数字集合里的为边界切成一系列子串
: 这个复杂度O(n)
: 然后每个字串找回文子串，这是个经典题
: 唯一需要修改的是，69的处理，可以先当成一个数字，然后几种模式再检查一次
|
b*******s
发帖数: 5216 | 10 反正这题比较简单的
【在 L*****e 的大作中提到】
: 楼主题目说的很模糊，这个“数字”是string啊？还是int？还是其它？然后是整个数
: 字转？还是部分子串转？
|
|
|
L*****e
发帖数: 8347 | 11 看他题目要求了，如果input数字是int，你或者要先itoa，这个不但占了时间还另占空
间；如果是先reverse int的话，有可能有overflow的问题，所以能in place地做是最好
的。。。
【在 b*******s 的大作中提到】
: in place的算法只是技巧问题
|
l*****b
发帖数: 82 | 12 小弟英语很一般, 只能听到大概, 给位老大请见谅. 大概就是给一串int的数字串, 如"
3448835642345044354369401203911....", 找出旋转后还是原来值得int子串的数目.
【在 L*****e 的大作中提到】
: 楼主题目说的很模糊，这个“数字”是string啊？还是int？还是其它？然后是整个数
: 字转？还是部分子串转？
|
n*****t
发帖数: 22014 | |
b*******s
发帖数: 5216 | 14 回文要用trie
【在 n*****t 的大作中提到】
: 我看这就是 atoi 的变形虫，有木有
|
p*****2
发帖数: 21240 | 15 (defn rotate [num]
(let [m {\0 \0, \1 \1, \6 \9, \8 \8, \9 \6}
str (str num)
rot (clojure.string/join (reverse (map #(or (m %) \*) str)))]
(= str rot))) |
b*******s
发帖数: 5216 | 16 看起来真是美，不过一些情况你估计没考虑到
比如
619
【在 p*****2 的大作中提到】
: (defn rotate [num]
: (let [m {\0 \0, \1 \1, \6 \9, \8 \8, \9 \6}
: str (str num)
: rot (clojure.string/join (reverse (map #(or (m %) \*) str)))]
: (= str rot)))
|
n*****t
发帖数: 22014 | 17 发明这语法的肯定是天杀的，一点美感都没有
【在 p*****2 的大作中提到】
: (defn rotate [num]
: (let [m {\0 \0, \1 \1, \6 \9, \8 \8, \9 \6}
: str (str num)
: rot (clojure.string/join (reverse (map #(or (m %) \*) str)))]
: (= str rot)))
|
p*****2
发帖数: 21240 | 18
619应该true还是false呢？
【在 b*******s 的大作中提到】
: 看起来真是美，不过一些情况你估计没考虑到
: 比如
: 619
|
r**i
发帖数: 886 | 19 应该是true
【在 p*****2 的大作中提到】
:
: 619应该true还是false呢？
|
p*****2
发帖数: 21240 | 20
我这个就是true呀
【在 r**i 的大作中提到】
: 应该是true
|
|
|
d****i
发帖数: 4809 | 21 clojure就是lisp的马甲，以前在本科上AI的时候学过lisp，就从来没喜欢过它的语法
，觉得就是个银样蜡枪头，不中用，既不像C那样贴近机器，又不像Java那样贴近抽象
对象。
【在 n*****t 的大作中提到】
: 发明这语法的肯定是天杀的，一点美感都没有
|
c****d
发帖数: 116 | 22 1也能算么？转180度就不是1了吧
【在 b*******s 的大作中提到】
: 就 0 1 6 8 9 需要考虑
|
n**s
发帖数: 2230 | 23 这题不就是reverse string 的变种吗？ |
n*w
发帖数: 3393 | 24 很美
再贴个f#
let rotate i =
let m = [ '0', '0'; '1','1';'6','9';'8','8';'9','6']|> Map.ofList
string i |> Seq.fold (fun a e -> m.[e]::a)[] |> String.Concat |> int = i
c#
bool rotate (int i)
{
var m= new Dictionary(){{'0','0'},......
var l= i.ToString(). Select (c => m[c]).ToArray();
Array. Reverse ();
return Convert. ToInt32(String. Concat(l))== i;
}
【在 p*****2 的大作中提到】
: (defn rotate [num]
: (let [m {\0 \0, \1 \1, \6 \9, \8 \8, \9 \6}
: str (str num)
: rot (clojure.string/join (reverse (map #(or (m %) \*) str)))]
: (= str rot)))
|
i**i
发帖数: 1500 | 25 js:
(function(s){return Number((''+s).split("").map(function(v){if(v!=6&&v!=9)
return v; return {6:9,9:6}[v];}).reverse().join(""));})(919) |
i**i
发帖数: 1500 | 26 ver 2:
(function(s){s=''+s; if(!/^[01689]+$/.test(s)) return false; return s===s.
split("").map(function(v){return {0:0,1:1,6:9,8:8,9:6}[v];}).reverse().join(
"");})(60109) |
