LeetCode中级算法-动态规划

作者:神秘网友 发布时间:2021-01-12 20:21:33

LeetCode中级算法-动态规划

跳跃游戏

[题目]

给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

[输入1]

[2,3,1,1,4]

[返回1]

true

解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

[输入2]

[3,2,1,0,4]

[返回2]

false

解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

[解法]

注意数组中的每个元素是你当前最多可以向前跳跃的步数,实际跳跃的步数可以小于当前元素

[代码实现]

package main

import fmt

func main() {
  input := []int {3,2,1,0,4}
  result := computeResult(input)
  fmt.Println(result:, result)
}

func computeResult(input []int) bool {
  mostPosition := 0
  for i := 0; i  len(input); i++ {
    if i = mostPosition {
      mostPosition = Max(mostPosition, i + input[i])
      if mostPosition = len(input) - 1 {
        return true
      }
    }
  }

  return false
}

func Max(a int, b int) int {
  if a  b {
    return a
  }

  return b
}

不同路径

[题目]

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?

[输入1]

m = 3, n = 7

[返回1]

28

[输入2]

m = 3, n = 2

[返回2]

3

[解法]

使用递归法,枚举出所有可能的路径,路径可达就让计数器加一。

[代码实现]

package main

import fmt

func main() {
  m := 3
  n := 2
  result := computeResult(m, n)
  fmt.Println(result:, result)
}

var count = 0

func computeResult(m int, n int) int {
  _compute(0, 0, m, n)
  return count
}

func _compute(x int, y int, maxX int, maxY int) {
  if x == maxX - 1  y == maxY - 1 {
    count++
    return
  }

  if x  maxX {
    _compute(x + 1, y, maxX, maxY)
  }

  if y  maxY {
    _compute(x, y + 1, maxX, maxY)
  }
}

零钱兑换

[题目]

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

[输入1]

coins = [1, 2, 5], amount = 11

[返回1]

3

[输入2]

coins = [2], amount = 3

[返回2]

-1

[解法]

使用递归法,枚举出所有可能的路径,这个题目的解点是当前已经叠加的金额的基础上,尝试叠加给定硬币数组中的一个,要是叠加结果大于设定结果,本次方案作废,要是小于指定的总面额,则继续叠加,要是等于则计数一次,并对比记录是否为最少硬币的情况。

[代码实现]

package main

import fmt

func main() {
  coins := []int {1,2,5}
  input := 11
  result := computeResult(coins, input)
  fmt.Println(result:, result)
}

var count = 0

func computeResult(coins []int, input int) int {
  _compute(0, coins, input, []int{})
  return count
}

func _compute(res int, coins []int, total int, resultItems []int) {
  if res  total {
    return
  } else if res == total {
    if count == 0 {
      count = len(resultItems)
    } else {
      count = Min(count, len(resultItems))
    }
    return
  }

  for i := 0; i  len(coins); i++ {
    resItems := append(resultItems, coins[i])
    _compute(res + coins[i], coins, total, resItems)
  }
}

func Min(a int, b int) int {
  if a  b {
    return a
  }

  return b
}

最长上升子序列

[题目]

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

[输入]

nums = [10,9,2,5,3,7,101,18]

[返回]

2

[解法]

设立一个指针,从当前第i个元素开始向后遍历,比对指针指向的元素和前一个元素的大小,要是递增则继续移动指针,反之则不是严格递增子序列,记录最长子序列,并从指针指向的位置作为基点,继续向后推移指针检测。

[代码实现]

package main

import fmt

func main() {
  input := []int {10,9,2,5,3,7,101,18}
  result := computeResult(input)
  fmt.Println(result:, result)
}

func computeResult(input []int) int {
  pointer := 1
  maxLen := 0
  for i := 0; i  len(input); i++ {
    if pointer  i {
      pointer = i
    }

    for pointer  len(input) - 1 {
      if input[pointer]  input[pointer + 1] {
        maxLen = Max(maxLen, pointer - i + 1)
        break
      }

      pointer++
    }
  }

  return maxLen
}

func Max(a int, b int) int {
  if a  b {
    return a
  }

  return b
}

LeetCode中级算法-动态规划 相关文章

  1. LeetCode中级算法-数学(1)

    快乐数 [题目] 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐

  2. Angel图神经网络算法在推荐场景下的实践

    分享嘉宾:孙瑞鸿?腾讯大数据 编辑整理:赵文娇 出品平台:DataFunTalk、AI启蒙者 导读: 随着数据多样性的发展,图计算已经成为业界的一个重要的研究方向,其中图神经网络广泛应用于图的表征学习,与传统的图学习相比,既能学习图网络的拓扑结构,也能聚合

  3. 贪心算法:我要监控二叉树!

    一路跟着「代码随想录」刷题的录友们,二叉树是不是都快忘了,哈哈,反正我讲过的内容我就默认大家都会了,来来来,本题是二叉树上的贪心。需要重温二叉树的录友,传送门: leetcode刷题最强指南(版本1.0) 通知: 一些录友表示经常看不到每天的文章,现在

  4. LeetCode中级算法-数学(2)

    Pow(x, n) [题目] 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 [输入1] 2.00000, 10 [返回1] 1024.00000 [输入2] 2.10000, 3 [返回2] 9.26100 [输入3] 2.00000, -2 [返回3] 0.25000 [解法] 无 [代码实现] package mainimport fmtfunc main() { input := floa

  5. Angel推荐算法在游戏推荐中的应用

    文章作者:王培军?腾讯 高级工程师 整理编辑:李沛欣 出品平台:DataFunTalk、AI启蒙者 导读: Angel是腾讯自研的分布式高性能的机器学习平台,支持机器学习、深度学习、图计算以及联邦学习等场景。Angel的深度学习平台已应用在腾讯的很多个场景中。本次分享

  6. 计算机算法的五个特性是什么

    计算机算法的五个特性是:1、有穷性,算法必须能在执行有限个步骤之后终止;2、确切性,算法的每一步骤必须有确切的定义;3、输入项,一个算法有0个或多个输入;4、输出项,一个算法有一个或多个输出;5、可行性,每个计算步骤都可以在有限时间内完成。 算法

  7. 一个算法示例:PHP实现开心消消乐

    本文主要介绍了关于PHP如何实现我们大家都知道的开心消消乐的算法。 推荐:《PHP视频教程》 一、需求描述: 1、在一个8*8的矩阵方格中随机出现5种颜色的色块。 2、当有三个或以上色块在横向或纵向上相连,则消除这些色块。 3、色块消除后,上方色块往下平移,

  8. LRU算法的实现

    缘由:看到redis的缓存淘汰机制,便自己实现了一下 代码实现(双向链表+HashMap) package com.jarjune.jdalao.framework.algorithm;import java.util.*;/** * LRU * @author jarjune * @version 1.0.1 * @date 2020/11/19 */public class LRUCacheK, V { //

  9. 拉斯维加斯算法之n后问题

    1、拉斯维加斯(Las Vegas)算法 舍伍德算法优点在于计算时间复杂度对所有实例相对均匀,但与其相应的确定性算法相比,其平均时间复杂度没有改进。拉斯维加斯算法则不然,它能显著改进算法的有效性,甚至对某些迄今为止找不到有效算法的问题,也能得到满意的算

  10. 拉斯维加斯随机化算法求解整数因子分解

    问题描述 设n1是一个整数。关于整数n的因子分解问题是找出n的如下形式的 唯一分解式 :。其中,p1p2…pk是k个素数,m1,m2,…,mk是k个正整数。如果n是一个合数,则n必有一个非平凡因子x,1xn,使得x可以整除n。 给定一个合数n, 求n的一个非平凡因子的问题称

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词