# 数字

# 数学统计

# 1. 数组元素积的符号

https://leetcode.cn/problems/sign-of-the-product-of-an-array/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_1/topic_1.go

已知函数 signFunc(x) 将会根据 x 的正负返回特定值：
如果 x 是正数，返回 1 。
如果 x 是负数，返回 -1 。
如果 x 是等于 0 ，返回 0 。
给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积。
返回 signFunc(product) 。

	func arraySign(nums []int) int {
	ans := 1
	for _, num := range nums {
	if num == 0 {
	return 0
	} else if num < 0 {
	ans *= -1
	}
	}
	return ans
	}

#

# 溢出问题

# 2. 整数反转

https://leetcode.cn/problems/reverse-integer/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_1/topic_2.go

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。

	func reverse(x int) int {
	flag := 1
	ans := 0
	if x < 0 {
	flag = -1
	x = -x
	}
	for x > 0 {
	if ans >= (math.MaxInt32/10)+1 {
	return 0
	}
	ans = ans*10 + x%10

	x = x / 10
	}

	return ans * flag
	}

# 3. 回文数

https://leetcode.cn/problems/palindrome-number/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_1/topic_3.go

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如， 121 是回文，而 123 不是。

	func isPalindrome(x int) bool {
	if x < 0 \|\| (x%10 == 0 && x != 0) {
	return false
	}

	num := 0
	for x > num {
	num = num*10 + x%10
	x = x / 10
	}

	return x == num \|\| x == num/10

	}

#

# 进制问题

# 4. 十进制转换成七进制

https://leetcode.cn/problems/base-7/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_1/topic_4.go

给定一个整数 num ，将其转化为 7 进制，并以字符串形式输出。

	func convertToBase7(num int) string {
	if num == 0 {
	return "0"
	}

	var ans = []byte{}

	flag := false
	if num < 0 {
	num *= -1
	flag = true
	}

	for num > 0 {
	ans = append(ans, byte('0'+num%7))
	num = num / 7
	}

	if flag {
	ans = append(ans, '-')
	}

	for i := 0; i < len(ans)/2; i++ {
	ans[i], ans[len(ans)-1-i] = ans[len(ans)-1-i], ans[i]
	}

	return string(ans)
	}

# 5. 七进制转换成十进制

	func convertToBase10(num int) int {
	ans := 0
	curr := 0

	for num > 0 {
	// 个位数
	digit := num % 10
	ans += digit * int(math.Pow(7, float64(curr)))
	curr++
	num /= 10
	}

	return ans
	}

# 数组加法

# 6. 数组加一

https://leetcode.cn/problems/plus-one/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_2/topic_1.go

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

	func plusOne(digits []int) []int {
	if digits[len(digits)-1] != 9 {
	digits[len(digits)-1] += 1
	return digits
	}

	for i := len(digits) - 1; i >= 0; i-- {
	if i == 0 && digits[i] == 9 {
	digits = append(digits, 0)
	digits[0] = 1
	break
	}

	if digits[i] == 9 {
	digits[i] = 0
	} else {
	digits[i] += 1
	break
	}
	}

	return digits
	}

# 7. 二进制求和

https://leetcode.cn/problems/add-binary/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_2/topic_2.go

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

	func addBinary(a string, b string) string {
	indexA, indexB := len(a)-1, len(b)-1
	ans := []byte{}

	if indexA == -1 {
	return b
	} else if indexB == -1 {
	return a
	}

	carry := 0
	for indexA >= 0 \|\| indexB >= 0 {
	if indexA >= 0 {
	carry += int(a[indexA] - '0')
	}
	if indexB >= 0 {
	carry += int(b[indexB] - '0')
	}

	ans = append(ans, byte('0'+carry%2))
	carry = carry / 2

	indexA--
	indexB--
	}

	if carry > 0 {
	ans = append(ans, '1')
	}

	for i := 0; i < len(ans)/2; i++ {
	ans[i], ans[len(ans)-i-1] = ans[len(ans)-i-1], ans[i]
	}

	return string(ans)
	}

# 幂运算

# 8. 判断 2 的幂

https://leetcode.cn/problems/power-of-two/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_2/topic_3.go

给你一个整数 n ，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

	// 1000
	// 0111
	func isPowerOfTwo(n int) bool {
	return n > 0 && n&(n-1) == 0
	}

# 9. 判断 3 的幂

https://leetcode.cn/problems/power-of-three/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_2/topic_4.go

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
在 32 位有符号整数的范围内，最大的 3 的幂次方是 $3^{19} = 1162261467

	func isPowerOfThree(n int) bool {
	// n, i := 1, 0
	// for n < math.MaxInt32 {
	// n = int(math.Pow(3, float64(i)))
	// i++
	// fmt.Println(i, n)
	// }
	// return true

	return n > 0 && 1162261467%n == 0
	}

# 10. 判断 4 的幂

https://leetcode.cn/problems/power-of-four/description/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_2/topic_5.go

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

	func isPowerOfFour(n int) bool {
	// 1 1
	// 100 4
	// 10000 16
	//1000000 64
	return n > 0 && n&(n-1) == 0 && n&0xaaaaaaaa == 0
	}

# 最大公约数

# 11. 最大公约数

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_3/topic_1.go

	// 辗转相除法 (欧几里得算法)
	// 求最大公约数 GCD (Greatest Common Divisor)
	// eg1:
	// 12，18 的公因数有：1，2，3，6。
	// gcd（12，18）=gcd(18,12%18)=gcd(18,12)
	// gcd（18，12）=gcd(12,18%12)=gcd(12,6)
	// gcd（12，6）=gcd(6,12%6)=gcd(6,0)
	// return 6
	func gcd(a, b int) int {
	k := a % b
	a, b = b, k
	for k != 0 {
	k = a % b
	a, b = b, k
	}
	return a
	}

# 质数和合数

# 12. 判断质数

	func isPrime(num int) bool {
	max := math.Sqrt(float64(num))
	for i := 2; i <= int(max); i++ {
	if num%i == 0 {
	return false
	}
	}

	return true
	}

# 13. 计算质数数量

https://leetcode.cn/problems/count-primes/

https://github.com/Twelveeee/AlgorithmCamp2023/blob/main/13_Number/level_3/topic_3.go

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

	func countPrimes(n int) int {
	primeList := make([]bool, n)
	ans := 0

	for i := 2; i < n; i++ {
	if !primeList[i] {
	ans += 1

	if i*i < n {
	for j := i * i; j < n; j += i {
	primeList[j] = true
	}
	}
	}
	}

	return ans
	}

数据结构算法