LeetCode中级算法-数学（2）

码农帮派

发布于 2021-01-12 06:57:25

28000

代码可运行

文章被收录于专栏：码农帮派码农帮派

运行总次数：0

代码可运行

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]

[返回1]

[输入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

[返回]

[解法]

使用二分查找，举例说明，被除数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:]
}