腾讯笔试编程题

 

删除k层结点

一棵n个结点的二叉树，牛牛想要删除概树中的k层结点，

如删除第2层，则输出[{3}，{15，7}]

删除2、3层，则输出[3]

 

思路：

跟层序遍历差不多，用temp[]来保存一层的结点（用例全对了但没AC，没找到答案），具体看代码讲解

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @param a int整型一维数组 
 * @return TreeNode类一维数组
 */
 function deleteLevel( root ,  a ) {
  // write code here
  if (!root)  return [];
  let lisat=[];
  let queue=[];
  queue.push( root );
  let count=1;//当前层数
  let num=new Set();//用set来判断当前层数是否存在于数组a中
     for(let j=0;j<a.length;j++){
      num.add(a[j]);
     }

  let res=[];res.push(root);//先把根结点入栈
  while( queue.length >0){
    let temp=[];

    count++;//当前层数为temp所在的那一层
    for( let i=0; i<queue.length; i++ ){//遍历que的下一层结点压入temp
      if(queue[i].left) {
        temp.push( queue[i].left );
      }
      if(queue[i].right) {
        temp.push( queue[i].right );
      }
    }
    
    if(num.has(count)){//如果当前层数==a
      for( let i=0; i<queue.length; i++ ){//temp的上一层的子节点指向null
        if(queue[i].left) {
          queue[i].left=null;
        }
        if(queue[i].right) {
          queue[i].right=null;
        }
      }

      for( let k=0; k<temp.length; k++ ){//将temp的下一层结点压入res
        if(temp[k].left) {
          res.push( temp[k].left );
        }
        if(temp[k].right) {
          res.push( temp[k].right );
        }
      }

    }
    queue=temp;
  }
  return res;
  
}
module.exports = {
  deleteLevel : deleteLevel
};

出现至少k次的小写字母

给定一个小写字母组成的字符串s，求多少小写字母至少出现了k次

思路：用map即可简单实现

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param S string字符串 
 * @param k int整型 
 * @return int整型
 */
 function howMany( S ,  k ) {
  // write code here
  let map=new Map();//用map来统计每个字符出现的次数
  let arr=S.split("");//转化为数组
  for(let i=0; i<arr.length; i++) {//遍历
    if(!map.has(arr[i])){
      map.set(arr[i],1);
    }
    else{//已经存在的话就count+1
      let count=map.get(arr[i]);
      map.set(arr[i],count+1);
    }
  }
  let total=0;
  for (let num of map.values()){
    if(num >= k) total++;
  }
  return total;

}
howMany('aaa',2)
module.exports = {
  howMany : howMany
};

数组扁平化（指定层数）

给定数组arr和层数n，扁平化到n层

如 [1,2,3,[[2]]] , 1

输出 [1,2,3,[2]]

...可以看作将【】去掉，如[].concat(...[[2]]),即将[2]存入[]中。concat的作用是将数组合并

常规法1：
function flat(arr,n){
  if(n===0) return arr;
  let res=[];
  for(let i=0;i<arr.length;i++){
    if(Array.isArray(arr[i])){//先判断是不是数组
      res.concat(flat(arr[i],n-1));//concat连接数组可将数组扁平化
    }
    else{//不是数组直接压入res
      res.push(arr[i]);
    }
  }
  return res;
}


方法2：
function flatten(arr,n){
  for(let i=0;i<n;i++){
    arr=[].concat(...arr);
  }
}