Javascript笔试刷题小结(三)


生命不息,刷题不止,hhhhhhhhhh … 可爱的我又来了😝

1. Leetcode 1013. 将数组分成和相等的三个部分

**思路一:**最开始看到题目的时候cc是这么想的,既然能分成三个部分,不妨先计算每个部分的和,然后只要能成功地截取两边的部分,中间部分肯定也满足条件了,就可以判定能划分。所以我把题目转化为寻找 [0,i), [i,j), [j,num.length)中的i和j,使得sum(A[0]-A[i-1]) = totalSum/3sum(A[j]-A[length-1] = totalSum/3)

代码就这么出炉了:

var canThreePartsEqualSum = function(A) {
  if(A.length < 3){
    return false
  }
  let totalSum = A.reduce((pre,cur) => pre+cur) // 计算数组之和
  if(totalSum % 3 !== 0){ // 和不能被3整除,不可能存在划分
    return false
  }
  let partSum = totalSum / 3
  let i = 1, j = A.length-1
  let partA = A[0],partC = A[j]
  while(partA !== partSum || partB !== partSum){
    if(partA !== partSum){
      partA += A[i]
      i++
    }
    if(partB !== partSum){
      j--
      partB += A[j]
    }
    if(i >= j){
      return false
    }
  }
  return true 
}

运行结果:
Leetcode运行结果
上面我这种方法是比较直接的两侧遍历法,我就叫做两头分割法了,(emmm 怎么感觉有点血腥)
看了其他人的题解,还有如下方法,都比较简单:
思路二、遍历计数法:也是像我上面一样,计算整个数组的和,进而得到每部分的和,从左到右遍历,记录遍历过的数值之和temp和与部分数目count

  • temp= totalSum/3的时候sum = 0, cnt ++
    遍历过程中,count只要等于3都可以划分,当然大于也可以[0,0,0,0,0],所以count = 3 的时候就可以返回true
var canThreePartsEqualSum = function(A){
  let totalSum = A.reduce((pre,cur) => pre+cur)
  if(totalSum % 3 !== 0)  return false
  let temp = 0
  let cnt = 0
  for(let item in A){
    temp += A[item]
    if(temp === totalSum/3){
      temp = 0
      cnt ++
    }
    if(cnt === 3) return true
  }
  return false
}

效率感人。。。
第二种看似代码简单,但实际的性能并不强,所以cc还是安利自己的血腥**“双头分割法”**(2333333),类似双头指针的原理。

2. Leetcode 300. 最长上升子序列

思路一:动态规划法:遍历一遍数组,记录当前位置的上升子序列长,和当前最长的上升子序列长,遍历结束,输出最长上升子序列长度即可,在i>j的情况下,

  • 如果nums[i] > nums[j], maxLen[i] = max(maxLen[j]+1, maxLen[i])
  • 如果nums[i] <= nums[j],maxLen[i]不变
  • 记录当前全局的max 也就是所有maxLen[i]中的最大值
    图解动态规划思路
var lengthOfLIS = function(nums){
  if(nums.length < 2){
    return nums.length
  }
  let max = 1
  let maxLens = new Array(nums.length).fill(1)
  for(let i = 1; i < nums.length; i++){
    for(let j = 0; j < i; j++){
      if(nums[i] > nums[j]){
        maxLens[i] = Math.max(maxLens[j]+1, maxLens[i])
      }
    }
    max = Math.max(maxLens[i], max)
  }
  return max
}

在上述遍历情况下的,时间复杂度:O(n*n),空间复杂度:O(n), 是否有可能简化遍历呢?可能需要我们重新设计状态定义

思路二: 动态规划+二分查找法:结合二分查找,改变思路一中的双重for循环,可以将时间复杂度降至O(nlogN),具体的思路就类似于插入排序,依旧是i>j的情况下:

  • 当我们当前遍历的元素大于递增序列的尾元素时( num[i] > num[j]),把当前元素直接放到序列后面
  • 否则(num[i] <= num[j]),把之前递增序列中第一个比当前元素大的元素替换为当前元素,插入后依然有序
    (比方,之前递增序列为[1,2,5,9],当前元素是4,那么就把序列替换为[1,2,4,9],插入的过程就是使用二分查找)
  • 这种方法得到的序列未必是方法一中最终的递增序列,但是长度和最长递增序列肯定是相同的
var lengthOfLIS = function(nums){
  let n = nums.length
  if(n < 2){
    return n
  }
  let tail = new Array(n);
  tail[0] = nums[0]
  let end = 0
  for(let i = 1; i < n; i++){
    if(nums[i] > tail[end]){
      tail[++end] = nums[i]      
    }else{
      let left = 0
      let right = end
      while(left < right){
        let mid = left + ((right-left) >>1)
        if(tail[mid] < nums[i]){
          left = mid + 1
        }else{
          right = mid
        }
      }
      tail[left] = nums[i]
    }
  }
  return end + 1 
}

或者也可以这样写,通过更新新增的索引来求长度

var lengthOfLIS = function(nums){
  let n = nums.length
  if(n < 2){
    return n
  }
  let tail = [nums[0]]
  for(let i = 0; i < n; i++){
    if(nums[i] > tail[tail.length-1]){
      tail.push(nums[i])
    }else{
      let left = 0
      let right = tail.length - 1
      while(left < right){
        let mid = (left + right) >> 1
        if(tail[mid] < nums[i]){
          left = mid + 1
        }else{
          right = mid
        }
      }
      tail[left] = nums[i]
    }
  }
  return tail.length
}

3. Leetcode 695. 岛屿的最大面积

思路一: 万能的递归法+DFS,计算某个位置(i,j)处的岛屿面积,(i,j)处的岛屿面积情况如下:如果此处是岛屿,则他周围的岛屿面积等于1+四周的岛屿面积;否则返回0。遍历整个二维数组,记录每个(i,j)处的岛屿面积,记录最大值,输出

var maxAreaOfIsland = function (grid) {
  let maxArea = 0
  // 查找相邻的岛屿面积
  const getArea = function(i, j){
    if(grid[i] === void 0 || grid[i][j] === void 0 || grid[i][j] === 0){
      return 0
    }
    // 如果该块已经被统计过了,置为0,防止重复统计
    grid[i][j] = 0
    return 1 + getArea(i-1,j) + getArea(i+1,j) + getArea(i,j-1) + getArea(i,j+1)
  }
  // 循环遍历找最大岛屿面积
  for(let i = 0; i < grid.length; i++){
    for(let j = 0; j < grid[i].length; j++){
      maxArea = Math.max(getArea(i,j), maxArea)
    }
  }
  return maxArea
};

时间和空间复杂度都是O(m*n)
思路二: 广度优先遍历(BFS),遍历二维数组,📝借助队列记录非水区域块grid[i][j]=1的坐标[i,j],和相关的区域面积area。每次都弹出队头,如果队头满足在区域内且是非水区域,则岛屿面积加一(area++),同时弹入其四周的位置入队列;否则继续弹出队头,直到队列为空,更新最大面积(maxArea = max(area, maxArea))。继续遍历二维数组,将非水区域的坐标放入空队列,初始化岛屿面积0,弹出队头元素,弹入… … 直到遍历结束,输出最大面积maxArea

var maxAreaOfIsland = function(grid){
  let maxArea = 0
  let row = grid.length, column = grid[0].length
  let dx = [1, -1, 0, 0], dy = [0, 0, 1, -1]
  for(let i = 0; i < row; i ++){
    for(let j = 0; j < column; j++){
      if(grid[i][j] === 0)  continue
      // 初始化小岛块区域的坐标和岛屿面积
      let queue = [[i,j]]
      let area = 0
      while(queue.length > 0){ // 队列不为空的时候
        let [x,y] = queue.shift() // 弹出队头位置的坐标
        if(x < 0 || x >= row ||y < 0 || y >= column || grid[x][y] === 0)  continue
        ++ area // 弹出的是范围内的非水块,面积加一
        grid[x][y] = 0 // 将该块标记为0,防止重复计算
        for(let k = 0; k < 4; k ++){
          queue.push([x+dx[k], y+dy[k]]) // 将四周的位置坐标弹入队列
        }
      }
      maxArea = Math.max(area, maxArea)
    }
  }
  return maxArea
};

或者也可以在弹入队列的时候就判断周围元素坐标范围,只让范围内的区域坐标🌁进队列,避免弹入又弹出的麻烦

var maxAreaOfIsland = function(grid){
  let maxArea = 0
  let row = grid.length, column = grid[0].length
  let dx = [1,-1,0,0], dy = [0,0,1,-1]
  for(let i = 0; i < row; i++){
    for(let j = 0; j < column; j++){
      if(grid[i][j] === 0)  continue
      // 初始化非水块队列及岛屿面积
      let queue = [[i,j]]
      let area = 0
      while(queue.length > 0){
        // 弹出队头坐标,区域面积+1,置0防止重复计算
        let [x,y] = queue.shift()
        if(grid[x][y] === 0) continue
        ++ area
        grid[x][y] = 0
        // 弹入四周位置时,添加判断,满足条件再入队列
        for(let k = 0; k < 4; k ++){      
          // 判断是否在范围内
          if(x+dx[k] >= 0 && x+dx[k] < row && y+dy[k] >=0 && y+dy[k] < column){
            queue.push([x+dx[k],y+dy[k]])
          }
        }
      }
      maxArea = Math.max(area, maxArea)
    }
  }
  return maxArea
}

方法二的时间复杂度和空间复杂度依旧是O(m*n),但实际在leetcode上运行的结果显示,DFS的运行效果要更优

4. 剑指offer 01.06. 字符串压缩

思路: 统计字符串中连续出现的字符的数目,压缩后的新字符串cstr = {char in str + count}*,比较cstr 和 str 选择较短者

var compressString = function(S){
  if(S.length < 2)  return S
  let res = ''
  let c = S[0]
  let cnt = 1
  for(let i = 1; i < S.length; i++){
    if(c === S[i]){
     cnt ++
    }else{
      res += c + cnt.toString()
      c = S[i]
      cnt = 1
    }
  }
  res += c + cnt.toString()
  return res.length < S.length ? res : S  
}

5. Leetcode 1160. 拼写单词

思路: 计算每个单词中字符的个数,遍历单词集中的每个单词中字符出现的次数,和字母集中的字符次数做对比,如果字母集中的字符的个数小于单词中的字符个数,则不能拼写,若单词中每个字符的个数都小于等于字母集中的字符个数,则可以拼写,计入长度

var countCharacters = function(words, chars){
  let ans = 0
  let countChars = function(word, char){
    // 计算字符串word中出现字符char的次数
    let res = 0
    for(let item of word){
      res += item===char? 1: 0
    }
    return res
  }

  for(let word of words){
    let isSuccess = 1 // 标记是否可以拼词成功
    for(let letter of word){
      if(countChars(word, letter) > countChars(chars, letter)){
        isSuccess = 0
        break
      }
    }
    if(isSuccess === 1){
      ans += word.length
    }
  }
  return ans
};

思路二:哈希计数法,遍历字母集chars用map记录每个字母出现的次数_set get has;遍历单词集words,检查每个字符并计数,复制一份map,check函数:检查字符w是否出现在map中,(map.has(i) && map.get(i) > 0),出现则map中的次数减一

var countCharacters = function(words, chars){
  let map = new Map()
  let count = 0
  for(let c of chars){
    map.set(c, map.has(c)? map.get(c)+1: 1)
  }
  for(let w of words){
    if(check(w, new Map(map))){
      count += w.length
    }
  }
  return count
};
function check(w, map){
  for(let i of w){
    if(map.has(i) && map.get(i) > 0){
      map.set(i, map.get(i)-1)
    }else{
      return false
    }
  }
  return true
}

6. Leetcode 836. 矩形重叠

**思路:**初次根据两个矩形的左下角坐标判断两矩形的相对位置,接下来我的说法也是将矩形当做点来看待,一共有四种情况,在每种情况下,判断圈中的点与矩形1中点的位置关系,比如当矩形2在第二象限时,判断矩形2的右下角点A与矩形1的左上角点B的位置关系,如果A在B的右下方,两矩形重叠输出true,否则返回false,请看cc的抽象派手绘图

矩形位置关系分析
思路确定之后,就是各种暴力的判断了:

var isRetangleOverlap = function(rec1, rec2){
  //判断相对位置,比较每个位置上对应的两点 
  if(rec1[0] < rec2[0] && rec1[1] < rec2[1]){
    // 第一象限        
    return rec1[2] > rec2[0] && rec1[3] > rec2[1] 
  }
  else if(rec1[0] > rec2[0] && rec1[1] < rec2[1]){
    // 第二象限        
    return rec1[0] < rec2[2] && rec1[3] > rec2[1] 
  }
  else if(rec1[0] > rec2[0] && rec1[1] > rec2[1]){
    // 第三象限        
    return rec1[0] < rec2[2] && rec1[1] < rec2[3] 
  }
  else{
    // 第四象限
    return rec1[2] > rec2[0] && rec1[1] < rec2[3]
  }
  return false
}

这个思路不算复杂,但代码看起来非常的难缠,有没有更简便的方法呢,围观了大佬的做法

思路二:在一维的情况下,如果判断两个线段是否相互重叠,例如[l1,r1][l2,r2],如果两线段重叠的话,必有max(l1,l2) < min(r1,r2)同样,扩展到二维的情况下,我们不直接比较两个矩形,而是分别比较两个矩形在x轴和y轴上的投影线段,如果两轴上的投影线段都重合,那说明两个矩形必定垂直。两矩形在x轴上的投影线段分别为[rec1[0], rec1[2]][rec2[0], rec2[2]],在y轴上的投影线段分别为[rec1[1], rec1[3]][rec2[1], rec2[3]]

var isRectangleOverlap = function(rec1, rec2){
  return (Math.max(rec1[0],rec2[0]) < Math.min(rec1[2],rec2[2]))&& (Math.max(rec1[1],rec2[1]) < Math.min(rec1[3],rec2[3]))
}

大佬就是大佬!👍 某人判断半天的语句,大佬一行代码return!流下了没技术的泪水

7.Leetcode 409.最长回文串

思路: 利用Hash表统计字符串中每个字符出现的次数cnt,使用数组存放提高效率,若出现的次数为偶数,res +=cnt; 若出现的次数为奇数, len += cnt-1, 最后如果回文串长度小于总字符串长度res < s.length,说明可以加上一个字母放在回文串正中央,return res + 1

var longestPalindrome = function(s){
  if(s.length === 0) return 0
  s = s.split('') // 将字符串划分为Array
  let counts = new Array(58).fill(0) // A是65,a是97
  let res = 0
  s.filter(item => {
    counts[(item.charCodeAt()-65)] ++
  })
  for(let i = 0 ; i < counts.length && counts[i] > 0; i++){
    res += counts[i]%2 ? counts[i]-1 : counts[i]
  }
  return res < s.length ? res+1: res
}

8.Leetcode 118.杨辉三角

思路: 两层循环即可,每一行数据的首尾部放1,其余位置元素为arr[i][j] = arr[i-1][j-1]+arr[i-1][j]

var generate = function(numRows) {
  let resArr = []
  if(numRows <= 0) return resArr
  for(let i = 0; i < numRows; i++){
     let row = []
     for(let j = 0; j < i; j ++){
       if(j === 0 || j === i-1){
         row.push(1)
         continue
       }
       row.push(resArr[i-1][j-1] + resArr[i-1][j])
     }
     resArr.push(row)
  }
  return resArr
}

9.Leetcode 119.杨辉三角 II

思路: 和上面的差距就在于直接输出第k行的结果,可以直接用上面的办法,令numRows = k,输出第k行的row即可

var getRow = function(rowIndex){
  let res = []
  for(let i = 0; i < rowIndex; i++){
    res.push(1)
    for(let j = i; j > 0; j--){
      res[j] += res[j-1] 
    }
  }
  res.push(1)
  return res
}

💭 但是相比动态更新上面每一层的方法O(n*n),有没有办法可以优化算法的复杂度到O(k)❓ 有的有的❗️
利用递推公式,学过组合数学的同学一定非常清楚了,杨辉三角中的每层中的每一项都可以看做是一个组合数列,如图:
把杨辉三角看作组合数列
因此就可以使用递推公式,逐项通过递推关系求解第k行的数值,递推公式为C(n,k) = C(n, n-k) * (n-k+1) / k! C(n,k) / C(n,k-1) = (n - k +1) / k

var getRow = function(rowIndex){
  let res = [1]
  if(rowIndex === 0) return res
  let value = 1
  for(let i = 1; i <= rowIndex; i++){
    res[i] = value * (rowIndex - i + 1) / i
    value = res[i]
  }
  return res
}

10. 牛客美团面试题——数组的前置和与后置和相等的子数组的个数

题目: 一个数组x[],数组每一个元素都大于0,称x[0] + …+ x[i]为前置和,而x[j] + … + x[n-1]为后置和,写一个程序,求x有多少相同的前置和后置和。

示例 :[1, 2, 5,1, 8, 9, 7, 1] 前置[1,2,5] = 后置[1,7] ,即找到类似这样的子数组的个数。

思路: 在牛客面经里看到的,应该是双指针吧,然后计算前置和后置数组的值,由于数组都是正数,left < right, 左边指针右滑,left > right 时,右边指针左滑,left = right时,个数+1

var findEqualArray = function(nums){
  if(nums.length <= 1) return 0
  let cnt = 0
  let i = 0, j = nums.length-1
  let left = num[i], right = nums[j]
  while(i < j){
     if(left === right){
       cnt ++
     }else if(left < right){
       i++
       left += nums[i]
     }else{
       j--
       right += nums[j]
     }
  }
  return cnt
}

最近要开始各种笔试面试了,加油啊!冲冲冲 🌙


Author: Casey Lu
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Casey Lu !
评论
 Previous
前端图片的预览和上传、加载及下载 前端图片的预览和上传、加载及下载
对于前端开发而言,和图片打交道自然是家常便饭。曾经的项目开发之中,对图片的使用也经历过不少问题,cc最近准备延伸一下,全方位的探讨在前端的多种应用场景下的图片操作,从预览上传、加载到下载到本地,同时也会分析图片的处理方式并share一些和图
2020-03-20
Next 
跨域的原理及解决方案 跨域的原理及解决方案
一、何为跨域 广义的跨域是指一个域下的文档和脚本试图请求另一个域下的资源。 举 资源跳转: A链接、重定向、表单提交 资源嵌入:<link>、<script>、<img>、<frame>等D
2020-03-16
  TOC