两道有意思的面试题

在面试中遇到了这么两道题，当时没有做出来，挺有意思，记录下来。

一、数组中找出项的组合

1	从一个数组中找出几个项和为M的所有可能。

当时乍一看想到把所有情况枚举一边，但是仔细看不知道怎么下手，回来仔细想了下，确定了个思路，可以把每一个组合转化成二进制，比如[1, 2, 3, 4]中数组第一项和第三项的组合就可以用1010表示，这样就可以快速列出所有组合的情况，然后算出对应项的和，等于M的就返回。

这个思路需要解决这么几个问题：

如何把所有的组合罗列出来进行遍历？
如何根据二进制的表示计算出这个组合中项的和？
如果，规定组合只能有几项，而不是要求所有情况该怎么处理？

我们来一个一个看。

首先，如何把所有组合罗列出来进行遍历？

既然决定采用二进制表示，那么最简单的方式实际上就是累加。

例如，[1, 2, 3, 4]组合有16种：

0000、0001、0010、0011、
0100、0101、0110、0111、
1000、1001、1010、1011、
1100、1101、1110、1111

其实换算成10进制就是0到15，共16中情况，也就是 2的数组长度的次方Math.pow(2, arr.length)，只要一个循环累加就可以。

接着，如何根据这个二进制表示计算项的和？

我第一时间想到的，就是把这个字符串一位一位遍历，如果字符串的项是1，则进行累加，并把对应的数组中的项记录下来。

let binStr = i.toString(2);
binStr.split('').forEach((item, index) => {
  if (item === '1') {
    s += arr[index]
    temp.push(arr[index])
  }
})

这里有个问题，在把一个数利用toString()转换成二进制字符串时，是不会出现0110这样的字符串，而是会出现110，需要补零。

let binStr = i.toString(2);
// 对二进制的字符串进行补零，保证字符串长度和数组长度一致
binStr = '0'.repeat(arr.length - binStr.length) + binStr;
binStr.split('').forEach((item, index) => {
  if (item === '1') {
    s += arr[index]
    temp.push(arr[index])
  }
})

最后，如果限定项数，就需要多加一层过滤，增加一个用来计数的counter来计算每个字符串的项数。

1 2	// 获取数字转化成二进制字符串后有多少个1 const counter = num => num.toString(2).replace(/0/g, '').length;

这三个问题解决后，来看下所有代码。

function GetCombBySumFromArray(arr, sum, count) {
  // 获取数字转化成二进制字符串后有多少个1
  const counter = num => num.toString(2).replace(/0/g, '').length;
  let len = arr.length, res = [];
  // 外循环：数组项随机组合的所有可能性组合
  for (let i = 0; i < Math.pow(2, len); i++) {
    if (!count || counter(i) == count) {
      let s = 0, temp = [], binStr = i.toString(2);
      // 对二进制的字符串进行补零，保证字符串长度和数组长度一致
      binStr = '0'.repeat(arr.length - binStr.length) + binStr;
      // 内循环，主要作用是把在这个组合中的对应的数组的项相加，推入临时数组
      binStr.split('').forEach((item, index) => {
        if (item === '1') {
          s += arr[index]
          temp.push(arr[index])
        }
      })
      // 满足要求
      if (s == sum) {
        res.push(temp)
      }
    }
  }
  return res;
}

来测试下，看下执行结果。

1	console.log(GetCombBySumFromArray([-1, 3, 9, 4, 6, -4, 5, 8, 1, 7], 5, 0));

看起来是正常的，接下来，考虑一个问题，既然已经采用二进制，是不是可以考虑用位运算？答案肯定是可以的，我本身对位运算使用不多，所以借助了下网上的资料，发现有两个地方可以优化。

原本在内循环中是通过拆字符串一项一项比较，其实可以通过位运算去判断这一项是不是在这个组合中

for (let j = 0; j < len; j++) {
  // 判断当前数是否在这个组合中
  if (0b0110 & 1 << (len - 1 - j)) {
  	s += arr[j]
    temp.push(arr[j])
  }
}

循环还是大同小异的循环，只不过，判断的方法变成了(0b0110 & 1 << (len - 1 - j))，这里才是重点，根据循环，0b0110需要依次和1000、100、10、1进行&运算，这样结果不为0的就表示这项在这个组合中存在。

counter的升级，也是运用了&运算

const counter = num => {
  let count = 0
  while (num) {
    num = num & (num - 1)
    count++
  }
  return count
}

来看下升级过后的函数：

const GetCombBySumFromArray = (arr, sum, count) => {
  // 获取数字转化成二进制字符串后有多少个1
  const counter = num => {
    let count = 0
    while (num) {
      num = num & (num - 1)
      count++
    }
    return count
  }
  let len = arr.length, res = [];
  // 外循环：数组项随机组合的所有可能性组合
  for (let i = 0; i < Math.pow(2, len); i++) {
    if (!count || counter(i) == count) {
      let s = 0, temp = [];
      // 内循环，主要作用是把在这个组合中的对应的数组的项相加，推入临时数组
      for (let j = 0; j < len; j++) {
        // 判断当前数是否在这个组合中
        if (i & 1 << (len - 1 - j)) {
          s += arr[j]
          temp.push(arr[j])
        }
      }
      // 满足要求
      if (s == sum) {
        res.push(temp)
      }
    }
  }
  return res;
}

位运算还是挺有意思的，可是平时用的还是不多，导致解决问题时不一定能想起来采用位运算，有机会需要更深入了解下位运算的应用。

这个题应该还有其他解法，先放在这，等后面有功夫再想想其他解法。

二、同心圆

1	这样一个同心圆，三种颜色，你用几个div可以做到？

这个题，当时听道，第一反应就是一个，div+border+box-shadow就可以做到：

#circle {
  margin:100px auto;
  width: 300px;
  height: 300px;
  border-radius: 50%;
  background: aqua;
  position: relative;
  border: 50px solid orange;
  box-shadow: 0px 0px 0px 50px yellow;
}

然后后面继续问道，四种颜色呢？

这时候我第一反应是，CSS的渐变。

#circle {
  margin:100px auto;
  width: 300px;
  height: 300px;
  border-radius: 50%;
  background: repeating-radial-gradient(circle, rgb(255, 255, 255) 10%, rgb(0, 0, 0) 20%);
  position: relative;
}

渐变的我话，别说四个，更多的也可以解决。但是要求是不能使用渐变。这个时候就有点懵，面试官这时候提示道CSS的伪元素可以么，想了下，确实可以。

#circle::before {
  content: ' ';
  position: absolute;
  width: 100px;
  height: 100px;
  border-radius: 50%;
  top: 50%;
  left: 50%;
  margin-top: -50px;
  margin-left: -50px;
  background: purple;
  z-index: 20;
}
#circle::after {
  content: ' ';
  position: absolute;
  width: 200px;
  height: 200px;
  border-radius: 50%;
  top: 50%;
  left: 50%;
  margin-top: -100px;
  margin-left: -100px;
  background: chartreuse;
  z-index: 10;
}

问题解决。以往自己用到before和after多的还是icon或者清除浮动等，很久不接触，突然想不起来，其实伪元素的作用真的挺大，自己在CSS方面的基础真的还需要再去细细梳理下。前端还是非常有意思的。