首页 > 编程语言 >算法常见题型

算法常见题型

时间：2023-10-31 23:12:45浏览次数：36  
标签：题型 nums res 常见 length len 算法 let grid

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])])

 

标签：题型,nums,res,常见,length,len,算法,let,grid
From： https://www.cnblogs.com/h2303/p/17801916.html

相关文章

  • PMP敏捷管理常见考点
    目录PMP敏捷管理常见考点Scrum框架的33553个角色3个工件5个事件5个价值观《敏捷宣言》四个价值观，十二大原则4大价值观12大原则敏捷相关的名词仆人式领导WIP在制品限制看板XP极限编程计划扑克用户故事优先级排序技术MoScow解聚燃尽图燃起图累积流量图PMP敏捷管理常见考点Scrum框......
  • WOA-CNN基于鲸鱼算法优化卷积神经网络的多变量回归预测 可直接运行 注释清晰适合新手
     ✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，代码获取、论文复现及科研仿真合作可私信。......
  • GJO-LSTM-Adaboost基于金豺算法优化长短期记忆神经网络LSTM的Adaboost分类预测
    ✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，代码获取、论文复现及科研仿真合作可私信。......
  • GJO-BILSTM-Adaboost基于金豺算法优化双向长短期记忆神经网络BILSTM的Adaboost分类预
     ✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，代码获取、论文复现及科研仿真合作可私信。......
  • 智慧矿山：智能化解决皮带跑偏问题的视频分析算法
    一、引言随着科技的发展，人工智能技术已经在各个领域得到广泛应用。而在智慧矿山领域，皮带跑偏视频分析是其中一个重要的应用方向。本文将详细介绍皮带跑偏视频分析AI算法的原理，以期为智慧矿山的发展提供有益的参考。二、算法原理1.视频采集：首先，我们需要对皮带跑偏现场进行视频采集，......
  • 1020. 【软件认证】任务调度算法
    题目描述某分布式任务调度系统有taskNum个任务（编号从1到taskNum）需要调度，调度策略：任务之间可能存在依赖关系，且无循环依赖，如任务1依赖任务2，那么要等待任务2执行完才能执行任务1；如果任务之间没有依赖关系，则可以并发执行（假设并发所需资源是充足的）。现给出任务间的依赖关系，并......
  • 二分查找算法题1
    /***https://leetcode.cn/problems/sqrtx/description/*二分查找*将数据分成两部分*第一部分为平方小于等于target*另外的为大于target*left=mid。right=mid-1；使用+1求中**/publicstaticvoidhanShu19(intx){......
  • 国际物流常见风险如何规避_箱讯科技
    外贸物流是国际贸易的重要环节，其管理和效率的高低直接影响着贸易的成本和效益。因此，外贸企业应该重视物流的组织和管理，提高物流运作的效率。国际物流基础知识01什么是“双清包税”和“双清不包税”双清包税上门又叫双清包税到门，意思就是DeliveredDutyPaid(…namedplaceofdes......
  • 常见网络攻击技术
    （1）SQL注入：Web应用未对用户提交的数据做过滤或者转义，导致后端数据库服务器执行了黑客提交的sql语句。黑客利用sql注入攻击可进行拖库、植入webshell，进而入侵服务器。（2）XSS跨站：Web应用未对用户提交的数据做过滤或者转义，导致黑客提交的javascript代码被浏览器执行。黑客利用......
  • 【算法题】2826. 将三个组排序
    题目：给你一个下标从0开始长度为n的整数数组nums。从0到n-1的数字被分为编号从1到3的三个组，数字i属于组nums[i]。注意，有的组可能是空的。你可以执行以下操作任意次：选择数字x并改变它的组。更正式的，你可以将nums[x]改为数字1到3中的任意一个。你将按......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99