LeetCode中级算法-数学(2)

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

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 main

import fmt

func main() {
  input := float64(2.1)
  result := computeResult(input, 3)
  fmt.Println(result:, result)
}

func computeResult(target float64, num int) float64 {
  if num  0 {
    num = num * (-1)
    target = 1 / target
  }

  result := float64(1)
  for i := 0; i  num; i ++ {
    result = result * target
  }

  return result
}

x 的平方根

[题目]

实现 int sqrt(int x) 函数。

[输入1]

4

[返回1]

2

[输入2]

8

[返回2]

2

说明:8的平方根是2.82842...,由于返回类型是整数,小数部分将被舍去。

[解法]

使用二分查找,需要注意的是因为只保留整数部分,我们找到平方根的平方结果只可能小于target,基于以上的分析,在二分查找的时候,在缩小范围的时候,要是结果小于target都进行缓存,这样保证有结果

[代码实现]

package main

import fmt

func main() {
  input := 8
  result := computeResult(input)
  fmt.Println(result:, result)
}

func computeResult(input int) int {
  left, right := 0, input
  result := 1
  for left = right {
    mid := (left + right) / 2
    if mid * mid  input {
      right = mid - 1
    } else {
      result = mid
      left = mid + 1
    }
  }

  return result
}

两数相除

[题目]

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

[输入]

dividend = 10, divisor = 3

[返回]

3

[解法]

使用二分查找,举例说明,被除数10和除数3,那么从1开始尝试有几个3可以组成最靠近10的数字。

[代码实现]

package main

import fmt

func main() {
  input := 10
  num := 3
  result := computeResult(input, num)
  fmt.Println(result:, result)
}

// 使用二分查找计算
func computeResult(input int, num int) int {
  left := 0
  right := input
  result := 0
  for left = right {
    mid := (left + right) / 2
    resItem := _compute(mid, num)
    if input  resItem {
      right = mid - 1
    } else {
      result = mid
      left = mid + 1
    }
  }

  return result
}

func _compute(item int, num int) int {
  result := 0
  for i := 0; i  num; i++ {
    result += item
  }
  return result
}

分数到小数

[题目]

给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 。

如果小数部分为循环小数,则将循环的部分括在括号内。

[输入1]

numerator = 1, denominator = 2

[返回1]

0.5

[输入2]

numerator = 2, denominator = 1

[返回2]

2

[输入3]

numerator = 2, denominator = 3

[返回3]

0.(6)

[解法]

[代码实现]

package main

import (
  fmt
  strconv
)

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

func computeResult(input int, num int) string {
  temp := input % num
  result := strconv.Itoa(input / num)
  if temp == 0 {
    return result
  }

  result += .
  filter := map[int]int{}
  for temp != 0 {
    if pos, exists := filter[temp]; exists {
      result = insert(result, pos, ()
      result += )
      return result
    }
    filter[temp] = len(result)
    temp = temp * 10
    result += strconv.Itoa(temp / num)
    temp = temp % num
  }

  return result
}

func insert(input string, pos int, letter string) string {
  return input[:pos] + letter + input[pos:]
}

LeetCode中级算法-数学(2) 相关文章

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

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

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

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

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

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

  4. 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 { //

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

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

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

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

  7. java面试之归并排序的应用

    文章背景: 在复习算法及数据结构时,找到了面试笔试题目,下面我们来看看题目: (学习视频分享:java教学视频) 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1

  8. 【快速因数分解】Pollards Rho 算法

    Pollard-Rho 是一个很神奇的算法,用于在 $O(n^{\frac{1}4}) $的期望时间复杂度内计算合数 n 的某个非平凡因子(除了1和它本身以外能整除它的数)。事书上给出的复杂度是 \(O(\sqrt{p})\) , p 是 n 的某个最小因子,满足 p 与 n/p 互质。虽然是随机的,但 P

  9. 常用的无损压缩算法有哪些

    常用的无损压缩算法有:1、LZ77算法,该算法是很多其他无损压缩算法的基础;2、LZR算法,是旨在提升LZ77的一个算法;3、LZSS算法,该算法目标是成为LZ77的一个线性时间替换算法;4、DEFLATE算法;5、LZMA算法等等。 数据压缩是保留相同或绝大部分数据前提下

  10. Leetcode(easy stack)

    Leetcode easy stack leetcode简单题目中的栈的全部题目 20 有效的括号 给定一个只包括 ‘(‘,‘)‘,‘{‘,‘}‘,‘[‘,‘]‘ 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注

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

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