算法常见题型-526互联

1. 跳跃问题（贪心）：

给定一个非负整数数组，初始位于第一个位置，输出调到最后一个位置的最短步数，跳不出来则输出-1。

let nums = [4,3,1,0,2,2,3,2,0,4]
console.log(jumpStep(nums))
function jumpStep(nums) {
    let steps = 0, startIndex = 0, endIndex = nums[0]
    let len = nums.length
    if (len <= 1) return 0
    if (endIndex >= len) return 1
    while (endIndex < len) {
      let maxDis = 0;
      for(let i = startIndex; i < endIndex; i++) {
           // 当前跳跃能到达的最远距离，贪心算法
        maxDis = Math.max(maxDis, i + nums[i])  
      }
// 当前的位置比之前能跳的最大的要小，不然就无法跳不过当前位置。
      if (startIndex <= maxDis) { 
        startIndex = endIndex; 
        endIndex = maxDis + 1; 
        steps++;
      } else {
        return -1
      }
    }
    return steps  }
}

递归

let nums = [4,3,1,0,1,2,2,2,0,4]
  let len = nums.length
  let step = 0
  if (len <= 1) return 0
  console.log(dfs(0, nums[0], nums[0]))
 
  function dfs(start, end, maxDis) {
    step++
    if (end >= len - 1) {
      return step
    }
 
    for (let i = start; i <= end; i++) {
      maxDis = Math.max(i + nums[i], maxDis)
    }
    if (maxDis > end) {
      start = end
      end = maxDis
      return dfs(start, end, maxDis)
    } else {
      return -1
    } 
  }

2. 求组合（回溯）：

给定一个不重复的整数数组，给出所有任取其中三个的组合，按排序输出。

let arr = '2,6,3,4,1'.split(',').map(Number).sort((a, b) => a - b)
let res = []
findGroup(0, [])
   function findGroup(depth, path) {
    if (path.length === 3) {
      res.push([...path])
         return
    }
    for (let i = depth; i < arr.length; i++) {
      path.push(arr[i])
      findGroup(i + 1, path)
      path.pop()
    }
  }
console.log(res)

给定一个任意大小的数组，给出所有可能的排序组合。

let arr = "abc".split('')
  let used = new Array(arr.length).fill(false)
  let res = new Set()
  getAllGroup([])
 
 
  function getAllGroup(path) { // 不需要深度
    if (path.length >= arr.length) {
      res.add(path.join('-'))
      return
    }
 
    for(let i = 0; i < arr.length; i++) {
        if (!used[i]) {
          used[i] = true
          path.push(arr[i])
          getAllGroup(path)
 
          used[i] = false
          path.pop()
        }
    }
  }
 
  res.forEach(item => {
    console.log(item.split('-'))
  })

2. 二维数组格子（深度优先搜索DFS）：

给定一个二维数组表示n*n的格子区域，假设新冠表示，0为没有扩散的安全区域，1为有病毒感染区域，每天1都会上下左右扩散一次，问多少天后所有格子全部被感染。

let grid = [
    [1,0,1],
    [0,0,0],
    [1,0,1]
  ]
  let len = grid.length
  let res = new Set()
  let count = 0
 
  for(let i = 0; i < len; i++) {
    for(let j=0; j < len; j++) {
      if (grid[i][j] === 1) {
        res.add(i + '-' + j)
      }
    }
  }
    
  dfs(res, grid)
  function dfs(res, grid) {
    if (res.size === len * len) {
        console.log(count)
        return
    } 
    let temp = new Set([...res])
    res.forEach(item => {
      // console.log(item)
      let i = item.split('-')[0] - 0
      let j = item.split('-')[1] - 0
      if (i + 1 < len && grid[i+1][j] === 0) {
          grid[i+1][j] = 1
          temp.add(Number(i + 1) + '-' + j)
      }
      if (j + 1 < len && grid[i][j+1] === 0) {
          grid[i][j+1] = 1
          temp.add(i + '-' + Number(j + 1))
      }
      if (i - 1 >= 0 && grid[i-1][j] === 0) {
          grid[i-1][j] = 1
          temp.add(Number(i - 1) + '-' + j)
      }
      if (j - 1 >= 0 && grid[i][j-1] === 0) {
          grid[i][j-1] = 1
          temp.add(i + '-' + Number(j - 1))
      }
    })
    count++
    dfs(temp, grid)
  }

给定一个二维数组表示n*n的格子区域，给定一个字母，输出能连续走出该字母的坐标，不能走出字母，则输出false

let grid = [
        ['A', 'C', 'C', 'F'],
        ['C', 'D', 'E', 'D'],
        ['B', 'E', 'S', 'S'],
        ['F', 'E', 'C', 'A'],
    ]
    let num = grid.length
    let target = 'ACCESS'
 
    for(let i = 0; i < num; i++) {
        for(let j = 0; j < num; j++) {
            if (grid[i][j] === target[0]) {
                find(i, j, [], '')
            }
        }
    }
    
    function find(i, j, road, str) {
        if (road.length > target.length) {
            return
        }
    
 if ( i<0 || j<0 || i >= num || j >= num || grid[i][j] === 1) {
            return
        }
        let temp = grid[i][j]
        road.push([i, j])
        str += temp
        grid[i][j] = 1  // 表示已经走过
 
        if (str === target) {
            road.forEach(item => {
                console.log(`(${item.join(',')})`)
            })
        }
            
        find(i, j + 1, [...road], str)
        find(i + 1, j, [...road], str)
        find(i, j - 1, [...road], str)
        find(i - 1, j, [...road], str)
        
        grid[i][j] = temp // 恢复
    }

给定一个二维数组表示n*n的格子区域，相连的1表示一个岛屿，输出有几个岛屿

let grid = [
    [1,1,1,0],
    [0,0,0,1],
    [1,0,0,0],
    [1,0,1,1]
  ]
  let n = grid.length
  let step = 0
  
  for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        step++
        dfs(i,j)
      }
    }
  }
  console.log(step)
  
function dfs(i, j) {
 if (i < 0 || j < 0 || i >= n || j >= n || grid[i][j] === 0) {
      return
    }
    grid[i][j] = 0
 
    dfs(i, j+1)
    dfs(i+1, j)
    dfs(i, j-1)
    dfs(i-1, j)
  }

3. 栈：

给出一组火车编号，火车站只有一个方向进出，要求输出所有火车出站的方案，以字典序排序输出。

let train = [1, 2, 3]
let len = train.length
    let res = []
    let station = []
    let out = []
    function backtrace(train, station, out) {
        // console.log(out.length, len)
        if (out.length === len) {
            res.push([...out])
            // console.log([...out])
            return
        }
 
        if (station.length === 0 && train.length !== 0) {
            station.push(train.shift())
            backtrace(train, station, out)
   } else if (station.length !== 0 && train.length === 0) {
            out.push(station.pop())
            backtrace(train, station, out)
   } else if (station.length !== 0 && train.length !== 0) {
            let temp1 = [...out]
            let temp2 = [...station]
            let temp3 = [...train]
 
            // 出站
            out.push(station.pop())
            backtrace(train, station, out)
 
            out = temp1
            station = temp2
            train = temp3
            
            // 进站
            station.push(train.shift())
            backtrace(train, station, out)
        }
 
    }
    backtrace(train, station, out)
    res.sort((a, b) => a.join('') - b.join(''))
    res.forEach(item => {
        console.log(item.join(' '))
    })

4. 滑窗：

给定一个字符串，求最长回文。

Let line = ‘cdabbacc’ 
let lines = '#' + line.split('').join('#') + '#'
    for (let index in lines) {
        let newLen = getMaxLenByCenter(lines, index)
        if (newLen > maxLen) {
            maxLen = newLen
        }
    }
    console.log(maxLen)
 
function getMaxLenByCenter(str, index) {
    let len = 0
    let left = index
    let right = index
 
while( str[left] === str[right] && left >= 0 && right <= str.length) {
        len = right - left + 1
        left--
        right++
    }
    return (len - 1) / 2
}

给一个字符串，输出其中最长的不重复子串

let str = 'werasdgdfasswer'
    let arr = str.split('')
    let used = new Set()
 
    let maxStr = ''
    let len = arr.length
    for(let i = 0; i < len; i++) {
        used.clear()
        used.add(arr[i])
        for(let j = i + 1; j <= len && !used.has(arr[j]); j++) {
        // console.log(i, j, [...arr].slice(i, j + 1))
            used.add(arr[j])
            let temp = arr.slice(i, j + 1)
            if (temp.length >= maxStr.length) {
                maxStr = temp.join('')
            }
        }
    }
 
    console.log(maxStr)

5．堆积木

积木宽高相等，长度不等，每层只能放一个或拼接多个积木，每层长度相等，最少2层。现给定一组积木长度，如果可以搭建，返回最大层数，如果不可以返回-1。

let nums = [9, 9, 9, 5, 3, 3, 2, 2, 3].sort((a,b) => b-a)
console.log(solution(nums))
 
function solution(nums) {
 　　let sums = nums.reduce((a,b) => a+b) 
 　　for (let i = nums.length; i > 1; i--) {
　　　　if (sums % i === 0 && nums[0] <= sums / i) {
　　　　　　let sum = sums / i
　　　　　　let arr = new Array(i).fill(sum)
　　　　　　let res = new Array(i).fill(0).map(() => [])
    　　　 if ( dfs(nums, arr, res) ) {
     　　　　return i
    　　　 }
   　　 }
　　 }
 　　　　return false
　　}
 
　　function dfs(nums, arr, res) { // nums，需要填满的数组,存放分组
 　　　　if (!nums.length) {
  　　　　　　console.log(res)
   　　　　　　return true
　　　　　}
 
　　　　　for (let i = 0; i < arr.length; i++) {
　　　　　　if (arr[i] === nums[0] || arr[i] - nums[0] >= nums[nums.length - 1]) {
　　　　　　　　let temp = nums.shift()
　　　　　　　　arr[i] -= temp
　　　　　　　　res[i].push(temp)
                    
　　　　　　　　if (dfs([...nums], [...arr], res)) {
 　　　　　　　　return true
　　　　　　　　}
　　　　　　　　return false
　　　　　　}
　　　}
}

6. 最短路径：

数组表示开始->结束位置的距离，输出给出任意[x, y]，输出x到y的最短距离

 const lines = [
        'b c 13',
        'a b 11',
        'a c 50'
    ]
    const target = ['a', 'c']
 
    const MAX_INT = Number.MAX_SAFE_INTEGER
    let nums = []
    let temp = new Set()
    for (let i = 0; i < lines.length; i++) {
        let item = lines[i].split(' ')
        temp.add(item[0])
        temp.add(item[1])
    }
 
    nums = [...temp]
    const len = nums.length
    let dist = new Array(len).fill().map(() => new Array(len).fill(MAX_INT))
    for (let i = 0; i < lines.length; i++) {
        let item = lines[i].split(' ')
        dist[nums.indexOf(item[0])][nums.indexOf(item[1])] = item[2] - 0
        dist[nums.indexOf(item[0])][nums.indexOf(item[1])] = item[2] - 0
    }
 
    for (let i = 0; i < len; i++) {
        dist[i][i] = 0
    }
 
    for (let k = 0; k < len; k++) {
        for (let i = 0; i < len; i++) {
            for (let j = 0; j < len; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
 
    // console.log(dist) 
    console.log(dist[nums.indexOf(target[0])][nums.indexOf(target[1])])

optimization算法proximal常见问题