可能的组合和转换成字母算法 - Javascript(由 Facebook 询问)
Possible combinations and convert into alphabet algorithm - Javascript (asked by Facebook)
我正在为下次面试学习算法,我发现了这个问题。
Facebook 问的
问题来了。
给定映射 a = 1,b = 2,... z = 26,以及一条编码消息,计算可以解码的方式数。
例如,消息“111”会给出 3,因为它可以解码为“aaa”、'ka' 和 'ak'。
我想我可以处理映射和转换为字母部分。但是组合对我来说并不容易。
想想我花了好几个小时才想出下面这段代码。
function combinations(str) {
var fn = function(active, rest, a) {
// if nothing, just return
if (!active && !rest)
return;
// there is nothing left in rest add active to A
if (rest.length == 0) {
a.push(active);
} else {
// append first number of rest to the end of the active item
// [1] + 1 => 111
// [1,2] + [3,4] = [1,2,3] + [4]
if (rest.length > 0){
fn(active.concat(rest[0]), rest.slice(1), a);
}else {}
// join
fn((active+rest[0]).split(","), rest.slice(1), a);
}
return a;
}
return fn([], str, []);
}
// run it
combinations(1,2,3);
我只知道这个。
[ [ 1, 2, 3 ],
[ '1', '23' ],
[ '12', 3 ],
[ '123' ],
[ '1', 2, 3 ],
[ '1', '23' ],
[ '12', 3 ],
[ '123' ] ]
查看重复项。我想我现在可以除以 2 并得到我想要的答案。这仍然不是一个好的答案。
你能把它变成更好的代码吗?
谢谢
上面的代码差不多就是来自这个link
在这种情况下,我们不需要实际创建组合来计算它们。我们可以使用 dynamic programming.
令 f(i)
表示解码字符串 S
中消息的有效方式的数量,直至并包括索引 i
处的字符(从零开始)。那么:
f(0) = 1
f(i) =
if S[i] > 6 or S[i-1] > 2:
// Nothing changes, we just
// added a letter
f(i-1)
else:
// All the ways to decode
// up to (i-1) plus all the
// ways to decode up to (i-2)
// (let f(-1) equal 1)
f(i-1) + f(i-2)
示例:
S = "123"
f(0) = 1
f(1) = f(0) + f(-1) = 2
f(2) = f(1) + f(0) = 3
这个过程的复杂度是 O(n)
时间和 O(1)
space。
我将@גלעד ברקן 的回答更改为 javascript,希望它不会破坏任何东西,而且我认为它正在运行。
const Number = 11222;
let sum = 0;
const AlphabetGen = (i) => {
if(i == 0 ){
sum =+ 1;
}else if ((Number[i] > 6) || (Number[i-1] > 3)){
sum =+ AlphabetGen(i-1);
}else if(i > 0){
if(i > 1){
sum =+ AlphabetGen (i-1) + AlphabetGen(i-2);
}else if (i == 1){
sum =+ AlphabetGen (0) + 1
}
}
return sum;
};
console.log(AlphabetGen(4));
我在 JavaScript 中使用简单迭代器对此的看法:
let processString = ( message, possibleWays = 0 ) => {
if ( message.length ) {
// First decode using single digit.
// Shorten string by one and process again.
possibleWays = processString( message.slice( 1 ,message.length), possibleWays );
// Then check if current digit can be combined
// with the next digit for cases like '11' for J, '12' for K, etc.
const numCurr = parseInt( message[0] );
const numNext = "undefined" === typeof message[1] ? null : parseInt(message[1]);
if ( numCurr && numNext
&& numCurr < 3 // first digit can't be more that 2 as 26 letter max.
&& ( numCurr + numNext ) < 27 // sum of two should be < 26 as 26 letter max.
) {
// Shorten string by two and process again.
possibleWays = processString( message.slice( 2 ,message.length), possibleWays );
}
} else {
// Reached end of the string: + 1 possible way to decode it.
possibleWays++;
}
return possibleWays;
}
console.log( 'Total number of decoding possbilities: ' + processString('12325') );
我正在为下次面试学习算法,我发现了这个问题。
Facebook 问的
问题来了。
给定映射 a = 1,b = 2,... z = 26,以及一条编码消息,计算可以解码的方式数。
例如,消息“111”会给出 3,因为它可以解码为“aaa”、'ka' 和 'ak'。
我想我可以处理映射和转换为字母部分。但是组合对我来说并不容易。
想想我花了好几个小时才想出下面这段代码。
function combinations(str) {
var fn = function(active, rest, a) {
// if nothing, just return
if (!active && !rest)
return;
// there is nothing left in rest add active to A
if (rest.length == 0) {
a.push(active);
} else {
// append first number of rest to the end of the active item
// [1] + 1 => 111
// [1,2] + [3,4] = [1,2,3] + [4]
if (rest.length > 0){
fn(active.concat(rest[0]), rest.slice(1), a);
}else {}
// join
fn((active+rest[0]).split(","), rest.slice(1), a);
}
return a;
}
return fn([], str, []);
}
// run it
combinations(1,2,3);
我只知道这个。
[ [ 1, 2, 3 ],
[ '1', '23' ],
[ '12', 3 ],
[ '123' ],
[ '1', 2, 3 ],
[ '1', '23' ],
[ '12', 3 ],
[ '123' ] ]
查看重复项。我想我现在可以除以 2 并得到我想要的答案。这仍然不是一个好的答案。
你能把它变成更好的代码吗?
谢谢
上面的代码差不多就是来自这个link
在这种情况下,我们不需要实际创建组合来计算它们。我们可以使用 dynamic programming.
令 f(i)
表示解码字符串 S
中消息的有效方式的数量,直至并包括索引 i
处的字符(从零开始)。那么:
f(0) = 1
f(i) =
if S[i] > 6 or S[i-1] > 2:
// Nothing changes, we just
// added a letter
f(i-1)
else:
// All the ways to decode
// up to (i-1) plus all the
// ways to decode up to (i-2)
// (let f(-1) equal 1)
f(i-1) + f(i-2)
示例:
S = "123"
f(0) = 1
f(1) = f(0) + f(-1) = 2
f(2) = f(1) + f(0) = 3
这个过程的复杂度是 O(n)
时间和 O(1)
space。
我将@גלעד ברקן 的回答更改为 javascript,希望它不会破坏任何东西,而且我认为它正在运行。
const Number = 11222;
let sum = 0;
const AlphabetGen = (i) => {
if(i == 0 ){
sum =+ 1;
}else if ((Number[i] > 6) || (Number[i-1] > 3)){
sum =+ AlphabetGen(i-1);
}else if(i > 0){
if(i > 1){
sum =+ AlphabetGen (i-1) + AlphabetGen(i-2);
}else if (i == 1){
sum =+ AlphabetGen (0) + 1
}
}
return sum;
};
console.log(AlphabetGen(4));
我在 JavaScript 中使用简单迭代器对此的看法:
let processString = ( message, possibleWays = 0 ) => {
if ( message.length ) {
// First decode using single digit.
// Shorten string by one and process again.
possibleWays = processString( message.slice( 1 ,message.length), possibleWays );
// Then check if current digit can be combined
// with the next digit for cases like '11' for J, '12' for K, etc.
const numCurr = parseInt( message[0] );
const numNext = "undefined" === typeof message[1] ? null : parseInt(message[1]);
if ( numCurr && numNext
&& numCurr < 3 // first digit can't be more that 2 as 26 letter max.
&& ( numCurr + numNext ) < 27 // sum of two should be < 26 as 26 letter max.
) {
// Shorten string by two and process again.
possibleWays = processString( message.slice( 2 ,message.length), possibleWays );
}
} else {
// Reached end of the string: + 1 possible way to decode it.
possibleWays++;
}
return possibleWays;
}
console.log( 'Total number of decoding possbilities: ' + processString('12325') );