数学问题

这里主要是考一些数学概念之类的，这里我简单分分类

# 公倍数与公因数

利用辗转相除法，我们可以很方便地求得两个数的最大公因数（greatest common divisor，gcd）；将两个数相乘再除以最大公因数即可得到最小公倍数（least common multiple, lcm）。

// 求解最大公因数
func gcd(a int, b int) int {
   // 这里我们使用辗转相除法来求解
   if b == 0 {
      return a
   } else {
      return gcd(b,a%b)
   }
}
// 求解最小公倍数(只需要把两个数相乘然后再除以最大公因数就可以得到最小公倍数了)
func lcm(a int, b int) int {
   return a*b/gcd(a,b)
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 质数

质数又称素数，指的是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。值得注意的是，每一个数都可以分解成质数的乘积。

# 计数质数

204. 计数质数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

唉，这题，暴力算法无解。。。。我太难了

方法一，使用挨氏筛选法从 1 到 n 遍历，假设当前遍历到 m，则把所有小于 n 的、且是 m 的倍数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数

// 方法一 埃拉托斯特尼筛法
func countPrimes(n int) int {
   if n <= 2 {
      return 0
   }
   prime:=make([]bool,n+1)
   count:=n-2 //去掉本身还有1
   // 我们2开始进行遍历
   for i := 2; i <= n; i++ {
      // 如果这个数没有标记，那么我们就进行计算
      if !prime[i] {
         // 这里我们直接计算以i为倍数时，把所有小于n且是i的倍速的全部标记一下
         for j := 2 * i; j < n; j += i {
            // 如果当前数据没有标记，那么我们就标记一下，并让count-1
            if !prime[j] {
               prime[j] = true
               count--
            }
         }
      }
   }
   // 最后剩下的count其实就是质数了
   return count
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

当然，我们还可以优化一下

func countPrimes(n int) int {
   if n <= 2 {
      return 0
   }
   prime:=make([]bool,n+1)
   count:=n/2 // 偶数一定不是质数
   i:=3
   sqrt:=int(math.Sqrt(float64(n)))
   // 最小质因子一定小于等于开方数
   for i<=sqrt {
      // 如果这个数没有标记，那么我们就进行计算
      if !prime[i] {
         // 这里我们直接计算以i为倍数时，把所有小于n且是i的倍速的全部标记一下
         for j := i * i; j < n; j += 2*i {
            // 如果当前数据没有标记，那么我们就标记一下，并让count-1
            if !prime[j] {
               prime[j] = true
               count--
            }
         }
         for  {
            // 这里我们不断遍历，把偶数去掉
            i+=2
            if !(i <= sqrt && prime[i]) {
               break
            }
         }
      }
   }
   // 最后剩下的count其实就是质数了
   return count
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 数字的处理

# 七进制数

504. 七进制数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

题目比较简单，其实就是不断除于7，然后我们求余数就可以了

func convertToBase7(num int) string {
   if num==0 {
      return "0"
   }
   // 先判断是否为负数
   isNegative:=num<0
   // 如果是负数，直接取反
   if isNegative {
      num = -num
   }
   ans:=""
   // 下面这里就是计算7进制数了
   for num >0 {
      a:=num/7
      b:=num%7
      ans = strconv.Itoa(b)+ans
      num=a
   }
   // 如果是负数那么就需要前面加一个负号
   if isNegative {
      ans = "-"+ans
   }
   return ans
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 随机取样

# 打乱数组

384. 打乱数组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

使用洗牌算法，这个算法很简单，其实就是随机交换位置来实现位置的打乱

type Solution struct {
   arr []int
}

func Constructor(nums []int) Solution {
   // 创建并返回solution结构体
   return Solution{nums}
}

/** Resets the array to its original configuration and return it. */
func (this *Solution) Reset() []int {
   return this.arr
}

/** Returns a random shuffling of the array. */
func (this *Solution) Shuffle() []int {
   n := len(this.arr)
   res := make([]int, n)
   // 拷贝数据
   copy(res, this.arr)
   // 打乱数组
   for i := n-1; i >= 0; i-- {
      // 返回返回[0, i]范围的整数
      j := rand.Intn(i+1)
      // 交换元素的位置
      res[i], res[j] = res[j], res[i]
   }
   return res
}