腾讯广研部(wxg)五面凉凉之一面（笔试篇）

一、54张牌，洗牌，保持所有的牌都不在原来的位置

// 大概思路就是对牌进行一次遍历，随机获取一张当前牌后边的一张牌，交换位置。
const getRandomCard = (start,end = 53) => {
	return Math.round(start + Math.random()*(end - start))
}
const shuffle = cards => {
	for(let i = 0; i < cards.length - 1; i++){
		let random = getRandomCard(i + 1)
		let temp = cards[i]
		cards[i] = cards[random]
		cards[random] = temp
	}
	return cards
}

二、 121，323，判断对称，不能转字符串

// 判断回文，但前提是不能转字符串，所以不能用常规String(num).split('').reverse().join('')处理。
// 用求余数方式判断
const isPalindrome = function(x) {
    if(x < 0) return false
    let cur = x
    let rest = 0
    while(cur !== 0){
        rest = rest * 10 + cur % 10
        cur = parseInt(cur / 10)
    }
    return x === rest
};

三、 一个人在n个微信群，一个微信群人数是2-n个人，找出这个人所在的微信群

    没看明白这道题要考什么，用了常规的穷举法，复杂度O(n^2)

四、 寻找数组中一个重复的数字，时间复杂度为O(n),空间复杂度为O(1)

// 将数组中的数字放至对应的索引位置，如果有出现位置不同值相同的，即为重复数字
const findRepeatNum = nums => {
    for(let [i, num] of nums.entries()){
        if(nums[i] === nums[num] && i !== num){
            return nums[i]
        } else {
            let temp = nums[i]
            nums[i] = nums[num]
            nums[num] = temp
        }
    }
}

五、 找出字符串中相同的字符，时间复杂度O(n),空间复杂度O(n）

// 用哈希map保存出现次数
const findRepeatChar = str => {
    let map = {}
    let rst = []
    for(let i of str){
        if(!map[i]){
            map[i] = 1
        } else {
            map[i]++
            rst.push(i)
        }
    }
    return rst
}

六、 判断十进制数字n中有多少个0，不能转字符串

// 我当时使用的还是求余的方式
const hasZero = num => {
    let rest = null
    let count = 0
    while(num !== 0){
        rest = num % 10
        num = Math.floor(num / 10)
        if(rest === 0){
            count++
        }
    }
    return count
}

七、 判断二叉树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和

// 使用常规的深度遍历
const hasPathSum = function(root, sum) {
  if(root === null) return false
  sum = sum - root.val
  if(root.left === null && root.right === null){
    return sum === 0
  }
  return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)
};

小结： 共七道题，限时四十分钟，纸上手撕代码。有些题会加上一些限制条件，让你脑壳疼会儿，整体中规中矩不算太偏。