前端面试算法题

找到坏鸡蛋

const egg=[1,1,1,1,1,1,1,1,-1,1,1,1];
const sum=(arr)=>arr.reduce((i,j)=>i+j)
const bad=(badEgg,i,flag)=>{
  // 坏鸡蛋出现在第i组
  // flag表示坏鸡蛋大于还是小于好鸡蛋，大于为true
  // 坏鸡蛋大于好鸡蛋时m为0,n为1
  // 坏鸡蛋小于好鸡蛋时j为1,n为0
  let m=flag?0:1
  let n=flag?1:0
  if (badEgg[m]>badEgg[n]) {
    return 0+3*(i-1)
  }else if(badEgg[m]<badEgg[n]){
    return 1+3*(i-1)
  }else{
    return 2+3*(i-1)
  }
};
/**
 * @description: 3次对比机会，得到12颗鸡蛋中坏的那一颗在哪？
 * @param {array} egg 所有鸡蛋
 * @return {number} 坏鸡蛋下标
 */
const badEgg=(egg)=>{
  const egg1=egg.slice(0,3)
  const egg2=egg.slice(3,6)
  const egg3=egg.slice(6,9)
  const egg4=egg.slice(9,12)
  // 判断坏鸡蛋在哪组里
  // 坏鸡蛋在1,2组
  if (sum(egg1)>sum(egg2)) {
    // 如果坏鸡蛋在第1组，只可能坏鸡蛋的重量大于好鸡蛋
    if (sum(egg1)>sum(egg3)) {
      return bad(egg1,1,true)
    }
    // 坏鸡蛋在第2组
    if (sum(egg2)<sum(egg3)) {
      return bad(egg2,2,false)
    }
  }
  if(sum(egg1)<sum(egg2)){
    // 坏鸡蛋在第1组
    if (sum(egg1)<sum(egg3)) {
     return bad(egg1,1,false)
    }
    // 坏鸡蛋在第2组
    if (sum(egg2)>sum(egg3)) {
      return bad(egg2,2,true)
    }
  }
  // 坏鸡蛋在3,4组
  if (sum(egg3)>sum(egg4)) {
    // 如果坏鸡蛋在第3组，只可能坏鸡蛋的重量大于好鸡蛋
    if (sum(egg3)>sum(egg1)) {
      return bad(egg3,3,true)
    }
    // 坏鸡蛋在第4组
    if (sum(egg4)<sum(egg1)) {
      return bad(egg4,4,false)
    }
  }
  if(sum(egg3)<sum(egg4)){
    // 坏鸡蛋在第3组
    if (sum(egg3)<sum(egg1)) {
     return bad(egg3,3,false)
    }
    // 坏鸡蛋在第4组
    if (sum(egg4)>sum(egg1)) {
      return bad(egg4,4,true)
    }
  }
}
console.log(badEgg(egg));

有效的括号

var isValid = function (s) {
    let stack = [],
        map = {
            '(': ')',
            '{': '}',
            '[': ']',
        };
    for (let i = 0; i < s.length; i++) {
        if (map[s[i]]) {
            stack.push(s[i]);
        } else if (s[i] !== map[stack.pop()]) {
            return false;
        }
    }
    return stack.length === 0;
};

合并两个排序的链表

var mergeTwoLists = function(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    var head = null;
    if (l1.val < l2.val) {
        head = l1;
        head.next = mergeTwoLists(l1.next, l2)
    } else {
        head = l2;
        head.next = mergeTwoLists(l2.next, l1)
    }
    return head
};

反转链表

var reverseList = function(head) {
    let cur=head
    let pre=null
    while(cur){
        const next=cur.next
        cur.next=pre
        pre=cur
        cur=next
    }
    return pre
};

输出 1-100内的素数

const isN=()=>{ 
  let res=[]
  let flag=true
  A:for(let j=2;j<=100;j++){
    flag=true
    B:for(let i=2;i<=Math.sqrt(j);i++){
      if(j%i===0){
        flag=false
        break B;
      }
    }
    if (flag) {
      res.push(j)
    }
  }
  return res
}

JS 实现两个大数相加？

let a = "9007199254740991";
let b = "1234567899999999999";
function add(a, b) {
  let maxLength=Math.max(a.length,b.length)
  a=a.padStart(maxLength,'0')
  b=b.padStart(maxLength,'0')
  let res=[]
  let i=maxLength,j=0
  while(i--){
    const sum=parseInt(a[i])+parseInt(b[i]);
    if (sum+j>=10) {
      res[i]=(sum+j)%10
      j=Math.floor((sum+j)/10)
    }else{
      res[i]=sum+j
      j=0
    }
  }
    if (j > 0) {
        res.unshift(j);
    }
  return res.join('')
}

console.log(add(a,b));//1243575099254740990

移动零

function moveZero(arr){
  let i=0
  let j=0
  while(j<arr.length){
    if(arr[i]!==0){
      i++
    }else if(arr[j]!==0){
      [arr[i],arr[j]]=[arr[j],arr[i]]
      i++
    }
    j++
  }
  return arr
}
console.log(moveZero([0,1,0,3,12])); // [ 1, 3, 12, 0, 0 ] 

扁平化对象

var entry = {
  a: {
    b: {
      c: {
        dd: 'abcdd'
      }
    },
    d: {
      xx: 'adxx'
    },
    e: 'ae'
  }
}

// 要求转换成如下对象
var output = {
  'a.b.c.dd': 'abcdd',
  'a.d.xx': 'adxx',
  'a.e': 'ae'
}

function isObject (obj) {
    return Object.prototype.toString.call(obj) === '[object Object]'
}
function flatObj (obj, prefix = '', res = {}) {
    for (let i in obj) {
        let key = prefix ? prefix + '.' + i : i
        isObject(obj[i]) ? flatObj(obj[i], key, res) : (res[key] = obj[i])
    }
    return res
}

a1, b1, c1, 20
a1, b1, c2, 5
a2, b1, c2, 10

[0, 1]

3

a1, b1, 25
a2, b1, 10