r**d
发帖数: 316 | 1 很简单，上来先介绍了下自己，做的项目，用什么技术等等
然后在网上做题，
1：判断一个输入的字符串是否是合法数字。
2：给定二叉树，按层次打印，写完后解释下逻辑。
对他们有什么问题
整个过程45分钟，两题大概只用了20多分钟 |
q***y
发帖数: 236 | |
P*F
发帖数: 59 | 3 感谢分享。
【在 r**d 的大作中提到】
: 很简单，上来先介绍了下自己，做的项目，用什么技术等等
: 然后在网上做题，
: 1：判断一个输入的字符串是否是合法数字。
: 2：给定二叉树，按层次打印，写完后解释下逻辑。
: 对他们有什么问题
: 整个过程45分钟，两题大概只用了20多分钟
|
p*****2
发帖数: 21240 | |
i***0
发帖数: 8469 | |
r**d
发帖数: 316 | 6 第二面
仅一题
有一排房子，每幢可以油漆成3种颜色之一，每个房子漆成各种颜色的价钱各不相同，
存放在一个[n][3]的二维数组中，另外要求相邻的两幢房子颜色不同，求最少需要多少
钱。
给定了函数的定义，输入参数为数组，返回一个值。
感觉考官还是挺仁慈的，但自己表现一般，先给了一个直观上的指数级别的算法，并编
程。解释之。后来总算想出快速的办法，结果时间差不多了，刚来得及给出伪代码，好
歹让考官理解了思路。
听天由命了。
【在 r**d 的大作中提到】
: 很简单，上来先介绍了下自己，做的项目，用什么技术等等
: 然后在网上做题，
: 1：判断一个输入的字符串是否是合法数字。
: 2：给定二叉树，按层次打印，写完后解释下逻辑。
: 对他们有什么问题
: 整个过程45分钟，两题大概只用了20多分钟
|
w****x
发帖数: 2483 | |
l*****a
发帖数: 14598 | 8 bull
最佩服那些会dp的了
【在 w****x 的大作中提到】
: 第三题很明显的DP,几个int就够用了
|
d******a
发帖数: 238 | 9 你贴个程序看看, DP该怎么写。
【在 w****x 的大作中提到】
: 第三题很明显的DP,几个int就够用了
|
j********e
发帖数: 1192 | 10 DP吧，用个size为3的数组A，记录从1到第K个房子，并且第K个房子用
第i种颜色(i=0,1,2)的最小价格。
K=1时，A[i] = B[0][i] (B是价格矩阵).
K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
【在 r**d 的大作中提到】
: 第二面
: 仅一题
: 有一排房子，每幢可以油漆成3种颜色之一，每个房子漆成各种颜色的价钱各不相同，
: 存放在一个[n][3]的二维数组中，另外要求相邻的两幢房子颜色不同，求最少需要多少
: 钱。
: 给定了函数的定义，输入参数为数组，返回一个值。
: 感觉考官还是挺仁慈的，但自己表现一般，先给了一个直观上的指数级别的算法，并编
: 程。解释之。后来总算想出快速的办法，结果时间差不多了，刚来得及给出伪代码，好
: 歹让考官理解了思路。
: 听天由命了。
|
|
|
i***e
发帖数: 452 | 11 1判断一个输入的字符串是否是合法数字. 请问lz能不能帖个代码？ 感觉这个题不容易
写。谢谢 |
r**d
发帖数: 316 | 12 正解
【在 j********e 的大作中提到】
: DP吧，用个size为3的数组A，记录从1到第K个房子，并且第K个房子用
: 第i种颜色(i=0,1,2)的最小价格。
: K=1时，A[i] = B[0][i] (B是价格矩阵).
: K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
|
r**d
发帖数: 316 | 13 此题很多地方有答案，不过这次考官并未要求一次写出完美代码，而是从无符号整数开
始，并且也没追究到太深的地步。
【在 i***e 的大作中提到】
: 1判断一个输入的字符串是否是合法数字. 请问lz能不能帖个代码？ 感觉这个题不容易
: 写。谢谢
|
y***n
发帖数: 1594 | 14 可以用Regular Expression 来回答第一个题目吗? |
n*******w
发帖数: 687 | 15 试试这个？
价格矩阵
color
1 2 3
K
1 3 4 5
2 2 3 4
3 11 15 3
第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
choice有dependency，不能这么DP。
【在 j********e 的大作中提到】
: DP吧，用个size为3的数组A，记录从1到第K个房子，并且第K个房子用
: 第i种颜色(i=0,1,2)的最小价格。
: K=1时，A[i] = B[0][i] (B是价格矩阵).
: K>1时，更新 A[i] = min(B[K][i] + A[j]), j!=i and j in (0,1,2)
|
s******k
发帖数: 3716 | 16 要是没影响就是greedy
【在 n*******w 的大作中提到】
: 试试这个？
: 价格矩阵
: color
: 1 2 3
: K
: 1 3 4 5
: 2 2 3 4
: 3 11 15 3
: 第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
: choice有dependency，不能这么DP。
|
j********e
发帖数: 1192 | 17 K = 1, A = { 3, 4, 5}
K = 2, A = { 6, 6, 7}
K = 3, A = { 17, 21, 9}
所以答案是9啦。
【在 n*******w 的大作中提到】
: 试试这个？
: 价格矩阵
: color
: 1 2 3
: K
: 1 3 4 5
: 2 2 3 4
: 3 11 15 3
: 第一反应是，第K个房子颜色选定之后，对K+1颜色有影响。所以子问题对于前一个
: choice有dependency，不能这么DP。
|
n*******w
发帖数: 687 | 18 对的。这个方法没问题。
问题在，这种解法并不是DP。我也被DP这个词误导了。
【在 j********e 的大作中提到】
: K = 1, A = { 3, 4, 5}
: K = 2, A = { 6, 6, 7}
: K = 3, A = { 17, 21, 9}
: 所以答案是9啦。
|
n*******w
发帖数: 687 | 19 greedy跟dp都要求没dependency。我搞过算法证明。
区别在于greedy的choice有greedy原则，dp的choice要try各种possibilities。
【在 s******k 的大作中提到】
: 要是没影响就是greedy
|
t********e
发帖数: 143 | 20 Use 2 D table for DP, first dimension is index, second dimension is color.
color is c0, c1, c2. Formula is
A[i][c2] = (min {A[i-1][c0], A[i-1][c1]}) + n[i][c2];
A[i][c1] = ...
A[i][c0] = ... |
j*******e
发帖数: 1058 | |
j*******e
发帖数: 1058 | |
