Go基础-013 练习题集合

0 leetcode

https://leetcode-cn.com/problemset/all/

1.老鼠试毒

10 只老鼠(小白鼠)，1000 瓶水，其中一瓶有毒药，老鼠喝毒药水 1 个小时死掉。
要求利用 10 只老鼠，在 1 个小时内找出那瓶水有毒。
经典思路:
将 1000 瓶水从 1 至 1000 编号。 将10只老鼠从 1 至 10 编号。

将水瓶的编号转为 2 进制数据，至多有 1000 瓶水，至多需要 10 个位即可。 例如:

之后控制老鼠喝水，将老鼠的编号与水瓶编号二进制位对应。如果某瓶水的编号第一位为 1，则让 1 号老鼠喝水，第二位为 1 则让 2 号老鼠喝水，以此类推。
等 1 个小时后，看死掉的老鼠，将对应的老鼠编号位设置为 1，其他为 0，转成 10 进制， 就是对应水瓶编号。
例如 1，456910 号老鼠死了，那就意味着编号:1100111001，转成 10 进制即可.

2.编程控制工厂内 10 盏灯的开关

要求，使用位运算完成。
可以完成，配置，检测，开，关操作。

3.完成翻转数组

编程实现将数组元素翻转
[1, 2, 3, 4, 5]
得到
[5, 4, 3, 2, 1]

函数原型:
func(a []int) []int

func ListReverse(a []int) []int {
    l := len(a)
    r := make([]int, l)
    for i, j := l-1, 0; i>=0; i, j= i-1, j+1 {
      r[j] = a[i] 
    }
    return r 
}
a := []int{1, 2, 3, 4, 5} 
fmt.Println(ListReverse(a)) //  [5 4 3 2 1]

4.统计字符出现的数量

字符串
hello moto hello golang hello hank
得到:
h: 4
e:3
l:8

函数原型:
func(string) map[string]int

func CharCount(a string) map[string]int { 
    r := map[string]int{}
    // 遍历 string
    for i, l := 0, len(a); i<l-1; i++ {
      // 以当前字符为 key，值累加 
      r[string(a[i])] ++
    }
    return r 
}
a := "hello world, hello golang, hello hank" 
fmt.Println(CharCount(a)) // map[ :5 ,:2 a:2 d:1 e:3 g:2 h:4 l:8 n:2 o:5 r:1 w:1]

5.筛选 4 的幂数

编写程序，判断，某个数是否为 4 的幂数。 4^0 == 1, 1 就算 4 的幂数
4^2 == 16, 16 就算4 的幂数
4^4== 256, 256 就算 4 的幂数

函数原型:
func(int) bool

func IsPowerOf4(n int) bool { 
  // 4 的幂数，转成二进制后，为:
  // 100， 10000， 1000000， 100000000 
  //4, 16, 64, 256

  // 判断是否为 2 的幂
  // 只有一位是 1 的二进制数，减 1 后，与原数做位与运算，结果一定是 0. 100 - 1 = 011 & 100 = 0 
  //return n & (n-1) == 0

  // 判断是否为 4 的幂
  // 100， 10000， 1000000， 100000000
  // 特征是 奇数位为 1. 1， 3， 5， 7 .. 为 1 其他位为 0
  // 构建一个 10101010101010101,奇数位全为 1 的二进制数
  // 与 n 做位与运算，结果若还是 n 则为 4 的幂数。

  // 综合 2 的幂的判断
  tn := 0b01010101010101010101010101010101 
  //tn := 0x55555555
  return n & (n-1) == 0 && tn & n == n
} 
fmt.Println(IsPowerOf4(1))  // true
fmt.Println(IsPowerOf4(8))  // false
fmt.Println(IsPowerOf4(9)) //  false
fmt.Println(IsPowerOf4(16)) // true
fmt.Println(IsPowerOf4(32)) // false
fmt.Println(IsPowerOf4(64))// true

6.判断一个数是否为质数

质数，只能被 1 和本身整除的数。

函数原型:
func(int) bool

func IsPrime(n int) bool { 
  //计算平方根
  m := int(math.Sqrt(float64(n))) 
  for d:=2;d <=m ;d ++ {
    if n % d == 0 {
      return false
    } 
  }
  return true
} 

fmt.Println(IsPrime(3)) 
fmt.Println(IsPrime(5)) 
fmt.Println(IsPrime(7)) 
fmt.Println(IsPrime(9)) 
fmt.Println(IsPrime(11))

7.得到 N 之内的全部质数

N 不能太小，例如 1000， 10w 等。
函数原型:
func(int) []int

思路：利用筛选法

8.搞清楚 1+1=2 是什么意思

哥德巴赫猜想。

9.计算最大公约数和最小公倍数

10.循环实现阶乘

11.循环实现斐波那契数列第 N 项的值

12.计算最大公约数和最小公倍数

13.排序算法(知识点)

1） 冒泡，选择，插入，希尔排序

2） 快速排序

3） 归并排序

4） 桶排序

5） 堆排序

14.二分查找法

折半查找。从一个排序序列中，快速找到目标元素位置。

15.上台阶问题

有一个 50 级的台阶。人一步可跨1级或2级。
问:上去有几种走法?不一样的 1，2 级组合就算一种。

1111111111
222222
112221
1121212121

16.切披萨问题

一块披萨，5 刀最多切几块?(延伸为 N 刀)
披萨是圆的平面