Javascript笔试刷题小结（四）

最近在准备美团的笔试，本来就想着继续刷心爱的leetcode，但是看了下是在赛码网OJ，，发现并不是直接写函数体那样，输入输出要有所改变，#%￥……@%#&@#*&^%$
输入(按行)： read_line()
输出：print() 和 console.log()
多行输入：

// A + B 示例：
while(line = read_line()){
  var row = line.split('') // 划分为数组，内容是字符，如果需要数字手动转化
  console.log(parseInt(row[0]) + parseInt(row[1]))
}

// 输入两行，一行数目，一行数组，但读入的都是字符串
var line1 = read_line()
var line2 = read_line()
var n = parseInt(line1)  // 数目
var arr = line2.split(' ')  // 数组

https://www.cnblogs.com/carolina/p/5875479.html

1、赛码网OJ.翻转数组

题目： 给定一个长度为n的整数数组a，元素均不相同，问数组是否存在这样一个片段，只将该片段翻转就可以使整个数组升序排列。其中数组片段[l,r]表示序列a[l], a[l+1], …, a[r]

var line1 = read_line()
var line2 = read_line()
var n = parseInt(line1)  // 数目
var arr = line2.split('').map(Number)  // 数组
var isReverseArray = function(n, arr){
  let index = 1
  while(index < n && arr[index] > arr[index-1]){// 升序
    index ++
  }
  let left = index-1 // 记录升序的最后一个位置
  while(index < n && arr[index] < arr[index-1]){// 降序
    index ++
  }
  let right = index
  if(arr[left] > arr[right]){ // 倒序之后，衔接不上，不再升序
    console.log("no")
  }
  while(index < n && arr[index] > arr[index-1]){
    index ++
  }
  if(index == n){
    console.log("yes")
  }else{
    console.log("no")
  }
}   
isReverseArray(n, arr)

2、赛码网OJ.约德尔测试

思路： 先使用正则式匹配将第一个字符串中的数据翻译成二进制串，之后和第二个字符串比较匹配个数，计算匹配率, over ~

var str1 = read_line()
var str2 = read_line()
var reg = /[0-9a-zA-Z]/
var temp = ''
for(let i = 0 ; i < str1.length; i++){
  if(reg.test(str1[i])){
    temp += '1'
  }else{
    temp += '0'
  }
} 
var cnt = 0
for(let i = 0; i < str1.length; i++){
  if(res[i] === str2[i]){
    cnt ++
  }
}
console.log((count/str1.length*100).toFixed(2) + '%')

3、赛码网OJ.分苹果

思路： 关于一群傻熊熊分苹果，我掉进了一个误区，就是逆向去利用最后一个熊熊只能分到一个苹果去计算最初的苹果，也就是迭代（（N + 1） * N + 1 ） * N + 1， 实际上，这样的苹果虽然正序也可以分成这样的结果，但是不能够就认为最后一只熊至少有一只苹果~ 而是要考虑再划分N等份的过程中，是否能够满足 1）每次对N取余都是1 ，2）并且剩下的N-1份给了下一只后还能够继续划分下去的问题，因此解决的方法是穷举i去计算i在2）中是否依旧N次平分时都满足条件1）和2）

var n = read_line()
n = parseInt(n)
var cnt // 当前的苹果数目
for(let i = n+1; ; i++){
  cnt = i
  for(let j = 1; j <= n; j ++){
    // 模拟划分N次的迭代过程
    cnt = ( cnt - 1 ) / n * (n-1)
  }
  if(Math.floor(cnt) === cnt && cnt !== 0){
    // 判定划分之后的数目是整数，并且最后一只熊还能分到非0个
    console.log(i)
    // 满足题意，此时的i就是我们要找的最少苹果数目
    break;
  }
}

但非常不幸的是，这个题在OJ上面因为超时只AC了（75%），所以仔细看了下，发现在迭代过程中确实时间复杂度偏高了,都没有判断当前苹果数是否满足对N取余是1就直接下一次了，傻乎乎
改进版如下：

var n = read_line()
n = parseInt(n)
for(let i = n+1; ; i++){
  let cnt = i // 初始苹果数目
  let successsBear = 0
  while(successBear < n){
    if(cnt % n == 1){
      // 满足本次划分的条件，去掉扔的一个和当前熊熊留下的那份，进入下一次
      cnt -= (cnt - 1) / n + 1 
      successBear ++  // 成功分好苹果的熊数
    }else{
      // 不满足，终止当前迭代，继续穷举i      
      break;
    }
  }
  if(successBear === n){
    console.log(i) // 输出满足N次划分的最小苹果数目
    break
  }
}

更惊艳的是，大佬的数列递推公式：

所以这个题分分钟变成了数列问题，太了：

console.log(n**n - n + 1)

一句话,over~

4、Leetcode 365. 水壶问题

还是我脑子有问题吧，看到这个题最开始画了半天图解，怎么也操作不出示例的结果… 然后看了题解，才明白出题的意图，原来在使用水壶度量水的过程中根本不在乎已经衡量好的水放在哪里，不一定在壶里，只是最后要用x和y壶来装，并且壶也是可以随便清空的，所以换成数学思维解答就比较简单了。

思路： 无论是怎样操作，我们的操作对于水量的影响无非是+x、x、+y、-y。所以可以将本题进行一个转化，目标：找到一对整数，使得ax + by = z，只要满足z >= x + y 且存在这样的 a,b, 就可以返回True了, 如何判断是否存在a,b呢，我们就需要寻找x,y的最大公约数，假设k = Math.gcd(x,y),那么原式就变为，寻找满足amk + bnk = z的a和b是否存在，我们可以变相的寻找am+nb是否存在(通过判断z能否整除k，也即z%k === 0 ？)，JS中没有内置的计算最大公约数的函数，所以要自己写下

var canMeasureWater = function(x, y, z){
  if(x + y < z){ 
    // 两个都装满都小于z，必然不可以
    return false
  }
  if(x === 0 || y === 0){
    // 其中一个为空壶，判断是否z为0或者另一个壶恰好等于z
    return z === 0 || x + y === z
  }
  // 是否有a,b存在
  return z % gcd(x,y) === 0
}
var gcd = function(a, b){
  return b === 0 ? a : gcd(a, a%b)
}

插播题外话：做到这里突然就想感慨一下，不愧是“学好数理化，走遍…” ，巧用数学节省了好多行代码，看来我要研读一下被我加入书单多年的《数学之美》了，当然这也需要有一颗clever的小脑袋，cc没有三重否定！

5、Leetcode 945. 使数组唯一的最小增量

思路： 使用先对数组进行排序，遍历数组，如果当前遍历元素等于前面一个元素（a[i] == a[i-1]说明重复了），将当前元素加一，避免重复;还有一种情况就是当前元素小于上一个元素，因为有2次以上重复的时候，第二个元素已经为了避免重复增大过，这种情况下，还是将当前元素增大，增大到比前面的元素还要大一的数值。其实两种情况下，虽然增值不同，但是都是以前一个元素作为增加依据，当前元素的增值始终是A[i-1] - A[i] + 1，所以代码就很简单了。

var minIncrementForUnique = function(A){
  A = A.sort((a,b) => a-b)
  let count = 0
  for(let i = 0; i < A.length; i++){
    if(A[i] <= A[i-1]){
      count += A[i-1] - A[i] + 1
      A[i] = A[i-1] + 1
    }
  }
  return count
}

5、剑指Offer 17.16. 按摩师

思路： 就是记录每次能使得工作时长最高的一种选择，并且将这个选择作为last继续遍历并记录

var massage = function(nums){
  let last = 0, next = 0
  nums.forEach((item) =>{
    let temp = Math.max(next, last+item)
    last = next
    next = temp
  })
  return next
}

6、Leetcode 999. 车的可用捕获量

思路： （本来作为象棋小白很慌张，但发现题目其实不需要任何象棋基础。）主要的思路其实就是：确定车的位置 -> 上下左右移动车 -> 碰到边缘则停止变色 -> 若是碰到卒,记录count++

var numRookCaptures = function(board){
  let cnt = 0
  let xIndex= 0, yIndex = 0
  // 遍历寻找白车
  for(let i = 0; i < 8; i ++){
    for(let j = 0; j < 8; j++){
      if(board[i][j] == 'R'){
        xIndex = i
        yIndex = j
        break
      }
    }
  }
  // 定义移动的方向
  dx = [0, 1, 0, -1]
  dy = [1, 0, -1, 0]
  // 分别尝试上下左右四个方向的移动
  for(let i = 0; i < 4; i++){
    for(let step = 0; ;step ++){
      const xNewIndex = xIndex + step*dx[i]
      const yNewIndex = yIndex + step*dy[i]
      if(xNewIndex < 0 || xNewIndex > 8 || yNewIndex < 0 || yNewIndex > 8 || board[tx][ty] === 'B'){
        // 超出范围或者有白色象阻拦
        break
      }
      if(board[xNewIndex][yNewIndex] == 'p'){
        cnt ++
        break
        // 这个方向已经不能继续搜查了
      }
    }
  }
  return cnt
}

7、Leetcode 892. 三维形体的表面积

这道题还蛮有意思的，我挺喜欢，想起了《我的世界》，做这道题就需要空间的逻辑思维能力了，最好还是动手画下。主要有两种思路——做法和做法，思想等同于我们初中计算一个形状不确定的立方体表面积，我们需要寻找的是露在外面的面数。

思路一：减去柱间重叠的面积 每个立方体有6个面，n个立方体便是6n个面。但是每有一对立方体接触，那么就会减少两个面，假设e对立方体相互接触，那么表面积就是6n-2e。
而接触的情况无非是两种，柱内上下叠加 和 柱间相邻：

• v个立方体的柱子内部，有v-1个接触面
• 高度分别为v、k的两个立方体之间的接触面是min(v,k)

var surfaceArea = function(grid){
  let N = grid.length // 网格的规格
  let n = 0, e = 0 // 记录立方体的个数和接触面数目
  // 遍历记录n和e
  for(let i = 0; i < N; i++){
    for(let j = 0; j < N; j++){
      // 记录立方体的块数
      n += grid[i][j]
      // 记录接触面的数目
      if(grid[i][j] <= 0){        
        continue // 进入下一次循环
      }
      // 柱内上下叠加
      e += grid[i][j] - 1
      // 柱间相邻的情况，按照遍历的顺序，只考虑上柱子和左柱子，min(v,k)
      if(i > 0){
        e += Math.min(grid[i-1][j],grid[i][j])
      }
      if(j > 0){
        e += Math.min(grid[i][j-1],grid[i][j])
      }
    }
  }
  return 6*n-2*e 
}

思路二：加上柱子露出的面积 一次计算每个柱子的表面积，（i,j）位置上的柱子高度为v,对v进行判断：
首先，判断：v > 0 ？柱子存在，顶部和底部的面积确定为2。其实主要考虑侧面积，前后左右四个侧面，举例左侧面积，也就三种情况：

• 如果柱子位于整个网格的左侧or左侧无柱子left.v=0，那么左侧的表面积为v;
• 柱子比左侧矮，左侧会被遮挡，左侧表面积为0；
• 柱子比左侧高，左侧露出的表面积为v - left.v
  以上情况用一个伪表达式表示就是：
  areaLeft = indexY - 1 >= 0 ? max(v - left.v, 0 ) : v

var surfaceArea = function(grid){
  let N = grid.length
  let res = 0
  for(let i = 0; i < N; i++){
    for(let j = 0; j < N; j++){
      // 判断有无柱子
      if(grid[i][j] === 0){
        continue // 无柱子，遍历下一个
      }
      // 有柱子，加上顶部和底部的表面积
      res += 2
      // 前侧(平面表格上方向)表面积
      res += i-1 >= 0? Math.max(grid[i][j] - grid[i-1][j], 0): grid[i][j]
      // 后侧(平面表格下方向)表面积
      res += i + 1 < N? Math.max(grid[i][j] - grid[i+1][j], 0): grid[i][j]
       // 左侧表面积
      res += j-1 >= 0? Math.max(grid[i][j] - grid[i][j-1], 0): grid[i][j]
      // 左侧表面积
      res += j+1 < N? Math.max(grid[i][j] - grid[i][j+1], 0): grid[i][j]
    }
  }
  return res
};

相比之下，我觉得思路一实现起来会更加简单些，毕竟情况比较少, 加面积的这种要考虑四个方向侧面积的三种情况总的来说要相对复杂些

8、Leetcode 914. 卡牌分组

题意就是希望卡牌能够分为，一组X个，并且组内X个牌的数字都一样，存在这样的X 且 X ≥ 2就可以返回true
思路： 依照上面的题意，我们就是需要找能恰好分组的情况，那这个判断依据就是每种牌的数目count[i]和X的整除关系了，只要各类的牌数都能整除X且X >=2 就可以了。统计每种牌的数目我选择的是Hash, 但是我们的整除关系判定不建议从X出发去遍历count，最好的办法就是计算所有count的最大公约数gcd，看是否满足大于等于2，全部满足的话，可以成功实现分组

var hasGroupSizeX = function(deck){
  let map = new Map()
  for(let count of dack){
    map.set(n, map.has(n)?map.get(n)+1:1)
  }
  let arr = [...map.values()]
  let res = arr[0]
  return arr.every(item => (res = gcd(res, item)) > 1)
}
let gcd = (a, b) => (b == 0? a: gcd(b, a%b))

9、字符串前缀的判断

题目描述： 输入有序的字符串数组，以及前缀数组，判断每个前缀在数组中匹配的第一个字符串的索引,找不到返回-1
看例子最直观：

array = [“apple”, “April”, “Bob”, “Nana”, “Zoey”]
prefix = “a” return 0
prefix = “c” return -1
prefix = “Na” return 3

思路：开始想的就是逐个遍历，后来突然看了一眼题目sorted Array，所以就使用二分查找，将时间复杂度降低到了O(logn)。

function findIndex1(array, pre) {  
// 检查以pre为前缀的第一个字符串的索引   
let index = -1   
let len = pre.length   
for(let i = 0; i < array.length; i++){     
  if(array[i].slice(0,len) === pre){
         return i     
  }   
}   
  return index
}
function findIndex2(array, pre) {
  // 检查以pre为前缀的第一个字符串的索引
  let index = -1
  let len = pre.length   
  let left = 0   
  let right = array.length-1   
if(len === 0) return index   
while(left < right){
  // 使用二分查找
  let mid = left + Math.floor((right-left)/2)     
  if(mid === left || mid === right){
    break     
  }
  // 比较mid位置上字符串的前缀和pre的大小关系
  if(array[mid].slice(0,len) > pre){ // right左移
    right = mid - 1
  }else if(array[mid].slice(0,len) < pre){ // left右移
    left = mid + 1     
  }else{
    // mid处的string前缀恰好为pre不代表它一定是第一个匹配的string，还要向前检查
    while(array[mid-1].indexOf(pre) === 0){         
      mid --       
    }       
    index = mid
    break
  }     
  if(left === right){ return array[left].indexOf(pre) === 0 ? left : -1}   
  }   
  return index
}

10、Leetcode 820. 单词的压缩编码

思路一：插入预检法，类似题目出现的情况，当我们插入某个word时，需要确定他没有出现在前面的编码中index = -1，或者出现在编码中但不能正确读取str[index+len]!='#'，类似"timer#“里面虽然出现了"me”,但却无法正常读取。但是这种方法必须保证单词组的顺序是按照单词长度由大到小排列的，因为（若是“me”在“time”之前编码，我们插入预检的时候检测不到“time”编码，所以还会插入time#,导致结果"me#time#"不是最佳的编码方式）。概括来说，按照单词由长到短的顺序进行编码，时间复杂度O(n*n)

var miniumLengthEncoding = function(words){
  if(words.length === 0){
    return 0
  }
  // 按照长度对单词组排序
  words = words.sort((a,b) => { return a.length < b.length })
  // 初始化编码
  let resStr = words[0] + '#'
  for(let i = 1; i < words.length; i++){
    let index = resStr.indexOf(words[i])
    // 插入预检，不能正确读的时候才插入
    if(index === -1 || resStr[index+words[i].length] != '#'){
      resStr += words[i] + '#'
    }
  }
  return resStr.length
}

由于对数组进行了排序，所以方式一的时间复杂度偏高，此外不断更新编码串，其实没有必要，题目要求的不过是长度

思路二：删除重复的词尾：和预检一样，删除重复词尾，就是为了降低编码的长度，所以如果str2是str1的某个词尾（后缀），那么我们只需要对str1进行编码即可，只需要计算 len(strA)+1, 所以在words数组中删除掉词尾重复的单词，剩下的单词总长度 ＋ 总个数 就是 最佳编码长度，即 minLen = len(words) + lenSum(words[0],words[1]...word[len-1])。具体实现：通过哈希表降低查询的复杂度（牺牲空间换时间），对words中的每个元素的词尾做切片对比，如果词尾出现在hashSet单词集中，就删除该元素。

var minimumLengthEncoding = function(words){
  let hashSet = new Set(words)
  for(let item of hashSet){
    for(let i = 1; i < item.length; i++){
      // 切片，看看是否词尾出现在hashSet,是则删除
      let target = item.slice(i)
      hashSet.has(target) && hashSet.delete(target);
    }
  }
  let res = 0
  // 计算剩余字符串的总长度
  hashSet.forEach(item =>{ res += item.length + 1})
  return res
}

如下图，第一行是使用Hash的执行结果，第二行为先排序再预检的结果。相比之下，使用Hash大大降低了算法的时间复杂度。