sisterAn / JavaScript-Algorithms

基础理论+JS框架应用+实践,从0到1构建整个前端算法体系
5.49k stars 633 forks source link

字节算法题:扑克牌问题 #80

Open sisterAn opened 4 years ago

sisterAn commented 4 years ago

魔术师手中有一堆扑克牌,观众不知道它的顺序,接下来魔术师:

如此往复(不断重复以上两步),直到魔术师手上的牌全部都放到了桌子上。

此时,桌子上的牌顺序为: (牌顶) 1,2,3,4,5,6,7,8,9,10,11,12,13 (牌底)。

问:原来魔术师手上牌的顺序,用函数实现。

sisterAn commented 4 years ago

感谢 @Eileenxj 的指出,已调整

解答:反向推导

假设,原来魔术师手上牌的顺序数组为 origin ,最后放在桌子上的顺序数组为 result

正向的操作为: origin 取出第一个插入 result 前面, origin 再取出第一个换到自己的末尾,如此重复;

反向操作为: origin 最后一个放到自己的第一个前面, result 拿出第一个插入 origin 前面,如此重复;

const calc = (arr) => {
    const origin = [];
    for (let i = 0; i < arr.length; i++) {
        if (origin.length) {
            const item = origin.pop();
            origin.unshift(item);
        }
        origin.unshift(result[i])
    }
    return origin;
}

// 测试
const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
// 原有顺序
calc(result)
// [13, 2, 12, 6, 11, 3, 10, 5, 9, 1, 8, 4, 7]
7777sea commented 4 years ago

最近刚好在面试里遇到了这道题,说下当时的思路:这是一个已知结果倒推的过程,可以把过程想象为动作的倒放,即:纸牌从桌上返回到手里的过程 原始的扑克牌顺序存放:牌顶 => 牌底 ,用一个数组存放,base=[] 既成现实的桌面纸牌顺序:牌顶 => 牌底,res = [13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 正常操作顺序为: base 拿出第一个插入 res 前面, base 再拿出第一个换到自己的末尾, 如此重复 反向的顺序则为:base 最后一个放到自己的第一个前面, res 拿出第一个插入 base 前面, 如此重复

上代码

const res = [13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] ;
const runBackward = () => {
    const base = [];
    for (let i = 0; i < res.length; i++) {
        if (base.length) {
            const item = base.splice(base.length - 1, 1)[0];
            base.unshift(item);
        }
        base.unshift(res[i])
    }
    return base;
}
xyyVee commented 4 years ago

最近刚好在面试里遇到了这道题,说下当时的思路:这是一个已知结果倒推的过程,可以把过程想象为动作的倒放,即:纸牌从桌上返回到手里的过程 原始的扑克牌顺序存放:牌顶 => 牌底 ,用一个数组存放,base=[] 既成现实的桌面纸牌顺序:牌顶 => 牌底,res = [13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 正常操作顺序为: base 拿出第一个插入 res 前面, base 再拿出第一个换到自己的末尾, 如此重复 反向的顺序则为:base 最后一个放到自己的第一个前面, res 拿出第一个插入 base 前面, 如此重复

上代码

const res = [13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] ;
const runBackward = () => {
    const base = [];
    for (let i = 0; i < res.length; i++) {
        if (base.length) {
            const item = base.splice(base.length - 1, 1)[0];
            base.unshift(item);
        }
        base.unshift(res[i])
    }
    return base;
}

“将牌堆第一张放到桌子上,再将接下来的牌堆的第一张放到牌底”,照字面理解的话,我感觉两个数组的第一个数字应该是一样的?因为是先放第一张过去到桌子上,再去换牌堆的顺序?

7777sea commented 4 years ago

最近刚好在面试里遇到了这道题,说下当时的思路:这是一个已知结果倒推的过程,可以把过程想象为动作的倒放,即:纸牌从桌上返回到手里的过程 原始的扑克牌顺序存放:牌顶 => 牌底 ,用一个数组存放,base=[] 既成现实的桌面纸牌顺序:牌顶 => 牌底,res = [13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 正常操作顺序为: base 拿出第一个插入 res 前面, base 再拿出第一个换到自己的末尾, 如此重复 反向的顺序则为:base 最后一个放到自己的第一个前面, res 拿出第一个插入 base 前面, 如此重复 上代码

const res = [13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] ;
const runBackward = () => {
    const base = [];
    for (let i = 0; i < res.length; i++) {
        if (base.length) {
            const item = base.splice(base.length - 1, 1)[0];
            base.unshift(item);
        }
        base.unshift(res[i])
    }
    return base;
}

“将牌堆第一张放到桌子上,再将接下来的牌堆的第一张放到牌底”,照字面理解的话,我感觉两个数组的第一个数字应该是一样的?因为是先放第一张过去到桌子上,再去换牌堆的顺序?

你可以这么理解,有两个数组,一个是空数组A(桌子),另一个是B数组(牌堆),然后每次从B取出一张牌放到A数组,然后把B数组中的第一位取出来,放到B数组的最后一位

CreatorMr commented 4 years ago

解答:反向推导

假设,原来魔术师手上牌的顺序数组为 origin ,最后放在桌子上的顺序数组为 result

正向的操作为: origin 取出第一个插入 result 前面, origin 再取出第一个换到自己的末尾,如此重复;

反向操作为: origin 最后一个放到自己的第一个前面, result 拿出第一个插入 origin 前面,如此重复;

const calc = (arr) => {
    const origin = [];
    for (let i = 0; i < arr.length; i++) {
        if (origin.length) {
            const item = origin.pop();
            origin.unshift(item);
        }
        origin.unshift(result[i])
    }
    return origin;
}

// 测试
const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
// 原有顺序
calc(result)
// [13, 2, 12, 6, 11, 3, 10, 5, 9, 1, 8, 4, 7]

你这个不对吧,导不出来呢

CreatorMr commented 4 years ago
 const result = [1,2,3,4,5,6,7,8,9,10,11,12,13]
 const getOrigin = (arr)=>{
    let origin = []
    for(let i = arr.length-1; i>=0; i--) {
      if(origin.length) {
        let item = origin.shift()
        origin.push(item)
      }
      origin.push(arr[i])
    }
    return origin;
 }
 let res = getOrigin(result);
 console.log(res)
 // [ 1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7 ]
shens3 commented 4 years ago
function undo(nums) {
  const result = [...nums];
  const origin = [];
  while (result.length) {
    origin.push(result.pop());
    if (result.length > 0)
      origin.push(origin.shift());
  }

  return origin;
}

function wash(nums) {
  const origin = [...nums];
  const result = [];

  while (origin.length) {
    result.push(origin.pop());
    if (origin.length > 0)
      origin.unshift(origin.pop())
  }
  return result;
}

const origin = undo([1,2,3,4,5,6,7,8,9,10,11,12,13])
console.log(origin); // 底 [7, 10, 6, 13, 5,  9, 4, 11, 3,  8, 2, 12, 1] 顶
console.log(wash(origin)) // 底 [1, 2, 3 ,4, 5, 6, 7, 8, 9, 10, 11, 12, 13] 顶
Eileenxj commented 4 years ago

解答:反向推导

假设,原来魔术师手上牌的顺序数组为 origin ,最后放在桌子上的顺序数组为 result

正向的操作为: origin 取出第一个插入 result 前面, origin 再取出第一个换到自己的末尾,如此重复;

反向操作为: origin 最后一个放到自己的第一个前面, result 拿出第一个插入 origin 前面,如此重复;

const calc = (arr) => {
    const origin = [];
    for (let i = 0; i < arr.length; i++) {
        if (origin.length) {
            const item = origin.pop();
            origin.unshift(item);
        }
        origin.unshift(result[i])
    }
    return origin;
}

// 测试
const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
// 原有顺序
calc(result)
// [13, 2, 12, 6, 11, 3, 10, 5, 9, 1, 8, 4, 7]

你这个答案是针对 牌顶-》排底的result顺序吧,但是你题目又是说的 排底-》牌顶为 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

VivenZZ commented 4 years ago
function getOrigin(result) {
// 设置原数组
    let origin = []
    while(result.length > 1) {
//取出结果中的最后一项,放入原数组中的最后一项,然后取出原数组第一项放入最后一项。
      let item = result.pop()
      origin.push(item)
      origin.push(origin.shift())
    }
// 最后一次放入的时候,不用调换位置
    origin.push(result.pop())
    return origin
  }
  console.log(getOrigin([1,2,3,4,5,6,7,8,9,10,11,12,13])) //[  7, 10, 6, 13, 5,  9,  4, 11, 3,  8, 2, 12, 1]
lbdhr commented 3 years ago

我这边写了个输入为牌底 -> 牌顶的~

const arrRes = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];

const mySolution = (arrFinal) => {
    const arrOri = [];
    for(let i=1; i<=arrFinal.length; i++) {
      if(i===1 || i===arrFinal.length) {
        arrOri.unshift(arrFinal.slice(-i)[0]);
      } else {
        arrOri.unshift(arrFinal.slice(-i)[0]);
        const tmp = arrOri.splice(-1, 1)[0];
        arrOri.unshift(tmp);
      }
    }
    return arrOri;
}

console.log(mySolution(arrRes));
lewisYe commented 3 years ago

function cal(arr){ let old = [] for(let i=arr.length-1;i>=0;i--){ if(old.length){ let num = old.pop() old.unshift(num) } old.unshift(arr[i]) } return old } const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] console.log(cal(result)) // [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7]

tomorrowIsNewDay commented 3 years ago

`/**

zhw2590582 commented 3 years ago
function getOrigin(arr = []) {
  let result = [];
  while (arr.length) {
    if (result.length > 1) result.unshift(result.pop());
    result.unshift(arr.shift());
  }
  return result;
}